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

Разгадывать кроссворды — не такая простая задача для компьютера, потому что задачи формулируются расплывчато. С другой стороны, тезаурус упрощает задачу. Пример 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).

Источник: geektimes.ru/post/243643/