WebCrow

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

WebCrow работает очень быстро и часто превосходит человеческих соперников на соревнованиях, особенно при решении многоязычных кроссвордов. Отличительной особенностью программного обеспечения WebCrow является комбинирование методов обработки естественного языка, поисковой системы Google и алгоритмов удовлетворения ограничений из области искусственного интеллекта для извлечения знаний и заполнения сетки кроссворда. Важнейший компонент WebCrow — модуль веб-поиска (англ. Web Search Module, WSM), реализующий специализированный веб-алгоритм автоматического ответа на вопросы.

Подход WebCrow к решению кроссвордов существенно отличается от человеческого^[2]: человек обычно в первую очередь отвечает на те вопросы, в которых уверен, и далее использует уже найденные слова для заполнения оставшихся клеток. В отличие от этого, WebCrow использует два чётко разделённых этапа. На первом этапе система обрабатывает все подсказки и пытается найти ответы на каждую: для каждой подсказки формируется множество кандидатов, которые ранжируются по сложным моделям, преимущественно на вероятностных критериях. На втором этапе применяется алгоритм удовлетворения ограничений для заполнения сетки наиболее вероятной комбинацией ответов.

Для взаимодействия с Google WebCrow составляет поисковые запросы на основе полученных подсказок. Для этого используется расширение запроса, задача которого — преобразовать подсказку в более простую и подходящую для Google поисковую строку. Полученные документы анализируются для извлечения списка кандидатов-слов, соответствующих ограничениям по длине. Использование лишь энциклопедических знаний недостаточно, так как многие подсказки в кроссвордах являются игрой слов или заведомо неоднозначны. Для работы с этой частью WebCrow применяет массивную базу уже решённых кроссвордов, а также автоматическое логическое рассуждение на специально организованной базе знаний с набором правил. Завершающий шаг — удовлетворение ограничений — позволяет надёжно подобрать окончательный вариант ответа, хотя, в отличие от человека, система не может быть полностью уверена в точности ответа.

Скорость и эффективность WebCrow^[3] многократно проверялась в состязаниях человек против машины, проходивших на кроссвордах на итальянском, английском и многоязычных схемах. По результатам тестов, WebCrow успешно конкурирует со средними игроками-человеками на кроссвордах на одном языке и показывает экспертный уровень на многоязычных кроссвордах. Однако на кроссвордах только на одном языке экспертного уровня достигнуть пока не удалось.

30 августа 2006 года на Европейской конференции по искусственному интеллекту (ECAI2006), состоялся официальный конкурс: 25 участников конференции и 53 любителя кроссвордов в интернете соревновались с WebCrow. Конкурс включал 5 различных кроссвордов (2 на итальянском, 2 на английском и один многоязычный — на итальянском и английском языках), на решение каждого из которых отводилось по 15 минут. В итальянском конкурсе WebCrow занял 21 место из 74 участников, а в многоязычной и английской номинациях одержал победу.

В декабре 2006 года в Флоренции (Италия), в рамках фестиваля Creativity Festival, состоялось несколько соревнований, а в январе 2007 года ещё одно официальное состязание прошло в Хайдерабаде (Индия), в рамках Международной конференции по искусственному интеллекту, где WebCrow занял второе место из 25 участников.