Самый сложный кроссворд, составленный компьютером



    Разгадывать кроссворды — не такая простая задача для компьютера, потому что задачи формулируются расплывчато. С другой стороны, тезаурус упрощает задачу. Пример Deep Blue показывает, что программы ИИ могут участвовать в викторинах и обыгрывать людей. Почему не сделать то же самое с кроссвордами?

    Американский разработчик Мэтью Гинсберг (Matthew Ginsberg) создал программу под названием Dr Fill, которая справляется с кроссвордами гораздо лучше, чем абсолютное большинство людей, пишет New Scientist.

    Программа выдвигает несколько вариантов ответа, указывая вероятность для каждой из них. Если софт работает в паре с человеком, то разгадка кроссворда становится банальным делом. Гораздо сложнее обеспечить автономную работу ПО.

    Математик Мэтью Гинсберг занимается этой проблемой около 40 лет. В 1976 году он написал, вероятно, первую в мире программу для составления кроссвордов. Потом он забросил это дело на 10 лет или больше, пока его друг не сказал, что пару составленных им кроссвордов приняли в газету The New York Times.

    Прошло много лет, пока Гинсберг не закончил создание своей чемпионской программы Dr Fill, которая дебютировала на Чемпионате США по кроссвордам. Она сразу хорошо проявила себя, и с тех пор только улучшала показатели.

    Секретное оружие Dr Fill — база из 6 млн вопросов и ответов для кроссвордов. На каждый вопрос она ищет соответствия в базе, а затем пытается совместить слова на сетке. Если не получается, программа пробует другую комбинацию. Подробнее об алгоритмах см. в научной работе.

    Автор сравнивает Dr Fill с работой движка рекомендаций на сайтах вроде Netflix: это одно из применений анализа данных (big data).

    Если разгадывание кроссворда можно сравнить с брутфорсом паролей, то составление нового кроссворда и генерация описаний для каждого слова — задача более сложная. Как и остальные программы, Dr Fill в этом пока не слишком хорош. Однако, по просьбе New Scientist автор согласился сгенерировать один кроссворд по сетке в стиле The New York Times. Этот кроссворд перед вами. Попробуйте свои силы в сражении против «искусственного интеллекта».

    Кроссворд, составленный программой


    При генерации кроссворда пришлось немного помочь программе, чтобы избавиться от слишком похожих слов. Тем не менее, по словам Гинсберга, на сегодняшний день это самый сложный кроссворд, сгенерированный практически полностью компьютерной программой (ответы опубликуют 17 января в журнале New Scientist).
    • +10
    • 15,6k
    • 7
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 7
    • –1
      26 по вертикали — Tiki.
      Чем-то напомнило мне статью про ИИ и игру Го. Теперь есть над чем подумать на досуге.
      • +1
        Слишком много чисто американских атрибутов, тяжеловато будет разгадывать.
        • +3
          Странно. Я думал, что кроссворды уже давно программно все генерируются, они же каждый день появляются.
          • +2
            Вот же, не знал, что составление кроссворда является сложной проблемой. Когда работал в газете — написал программу для составления готовых кроссвордов.

            Самой большой проблемой было составление базы слов и вопросов. После пробного пользования — составили огромную базу слов, а по фактически заполненной сетке уже писали вопросы всех редакцией :)

            Кому интересно — объясняю принцип построения.

            1) Каждая клетка кроссворда анализировалась на предмет, является ли она первой, второй,… последней.
            2) Определялись самые длинные слова в кроссворде и заполнялись первыми словами с учетом той информации, которая получена на шаге № 1 (например, нельзя ставить слово, у которого мягкий знак попадает на клетку, помеченную признаком «Первая» — то есть какое-то другое слово начинается с этой клетки).
            3) Методом перебора к первым самым длинным словам прикреплялись подходящие все более короткие слова, но не менее 4 знаков. При этом каждая цепочка запоминалась и если для более короткого слова варианты заканчивались, предыдущее слово в цепочке менялось попытка подобрать более короткое слово повторялось.

            К этому моменту кроссворд уже на 80% заполнен, в нем нет только слов на 3 и 4 буквы.

            4) Подбирались короткие слова для пустых мест. Таких слов в базе было больше всего и обычно это не составляло труда (опять следует иметь ввиду, что все слова, поставленные ранее, ставились не на обум, а по правилам, т.е. не было такой экзотики, как двойные или тройные одинаковые буквы по соседству… ).

            Некоторые замечания:

            Надо сказать, что мои сетки были попроще, чем вариант выше.
            Успешными были более 90% попыток, при этом этот процент рос по мере добавления правил, какую букву куда нельзя, а какое сочетание букв можно.
            Время формирования — от минуты до часов. Обычно если время переваливало за час, делался стоп и все запускалось по новой.
            • 0
              Обожаю скндинавские кроссворды. Особенно «правильно составленные» — это искусство!
              • НЛО прилетело и опубликовало эту надпись здесь
                • +2
                  Cтатью вообще-то здесь. А ваша почему-то ведет на неё через некий «прокси» Sci-Hub, который тут же просит денег. Я не очень понимаю, почему нельзя было дать прямую ссылку на arXiv (ну т.е. понимаю, но всё же). Сорри за некропостинг.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.