Кроссворды, созданные ИИ — Искусственный интеллект +

Нейронные сети

Кроссворды, созданные ИИ — Искусственный интеллект + | DeepTech

DEEPTECH

September 26, 2023

Введение: кроссворды

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

Наша история

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

Чем больше мы говорили о кроссвордах, тем больше убеждались, что можем создать собственное приложение для составления кроссвордов. Таким образом, при поддержке Суортморского колледжа мы смогли продолжить исследовательский проект по созданию веб-приложения для составления кроссвордов в https://www.crosswordconstruction.com.

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

Читайте также: Может ли ИИ написать словарь? Знает ли ИИ, что означают слова?

Кроссворды

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

К кроссвордам применяется множество общих ограничений. Например, некоторые издатели требуют, чтобы кроссворды имели 180-градусную симметрию и чтобы все ответы имели длину не менее 3 символов. Такие ограничения могут сделать кроссворды более насыщенными ответами и усложнить их составление.

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

Для этой задачи мы не генерируем подсказки. Генерация улик — это отдельная и важная проблема, которую мы еще не решали.

Вычислительная твердость

В целом построение кроссворда считается сложной вычислительной задачей. В частности, проблема составления кроссворда. NP-полный.

NP-полнота — важное математическое свойство в информатике. С практической точки зрения NP-полные задачи считаются сложными в вычислительном отношении. Другими словами, мы пока не знаем, существуют ли эффективные алгоритмы, решающие эти проблемы во всех случаях.

За дополнительной информацией о проблеме построения кроссворда и NP-полноте мы отсылаем читателя к ГП14 в Компьютеры и трудноразрешимые проблемы: руководство по теории NP-полноты Майкл Гэри и Дэвид Джонсон.

Наше решение

Изображение плаката, представленного на NCUR 2021 (источник https://www.crosswordconstruction.com)

Хотя задача построения кроссворда является NP-полной, мы считаем, что эвристики можно использовать для эффективного решения проблемы для небольших размеров сетки и больших словарей. Наивный подход к решению задачи построения кроссворда — попробовать все комбинации заполнения сетки потенциальными ответами из словаря. Однако этот подход можно значительно улучшить, если уменьшить количество комбинаций, которые нам приходится пробовать из словаря на каждом шаге. Фактически, в статье были представлены некоторые интересные концепции и методы для этого. Найдите уроки, извлеченные из кроссвордов который был опубликован в АААИ 1990 г. М. Гинзберг, М. Франк, М. Хэлпин и М. Торранс.

Для нашего решения мы применили соответствующие методы, чтобы максимально эффективно постоянно сокращать количество комбинаций. В конце концов наш алгоритм оказался успешным и стабильно генерировал кроссворды стандартного размера (15 на 15) на больших списках слов, содержащих 100 000 слов. Прототип нашего веб-приложения с ранней реализацией нашего алгоритма можно найти по адресу https://www.crosswordconstruction.com/generator.

Мы считаем, что наш алгоритм связан с ИИ, поскольку наш алгоритм по существу сокращает дерево поиска на каждом этапе, что является методом, используемым в алгоритмах, связанных с ИИ, для поиска, принятия решений и игр.

Предварительная работа над кроссвордами

Иногда в классах начальной школы появляются менее строгие кроссворды. Эти головоломки имеют меньше ограничений и содержат меньше горизонтальных и вертикальных ответов. Мы называем такие головоломки классными кроссвордами.

Пример кроссворда в классе (источник https://github.com/MichaelWehar/Crossword-Layout-Generator) — Пример классного кроссворда (источник https://github.com/MichaelWehar/Crossword-Layout-Generator)

Ранее я работал с Итаем Ливни и несколькими коллегами над составлением кроссвордов в классе. Наша работа под названием Преобразование неструктурированных веб-данных в последовательные образовательные игры STEM был представлен на ПиКон 2018.

В то время я разработал и внедрил генератор макетов кроссвордов в классе. Эта программа будет брать список слов и генерировать кроссворд в классе, используя эти слова в качестве горизонтальных и вертикальных ответов. В частности, программа попытается создать макет, пытаясь максимизировать количество связей между ответами, сохраняя при этом баланс высоты и ширины головоломки. Этот конкретный компонент нашей более широкой работы был выпущен с открытым исходным кодом, и его можно найти по адресу https://github.com/MichaelWehar/Crossword-Layout-Generator.

Большое спасибо за чтение! Мы будем рады любым идеям, отзывам и комментариям.

Я прекрасно провел время, работая с Отисом, и он проделал потрясающую работу! Я надеюсь, что мы сможем продолжать совершенствовать наши алгоритмы построения кроссвордов, чтобы создавать головоломки более высокого качества, которые интересно и сложно решать.

Читайте также: Переосмысление искусства с помощью генеративного искусственного интеллекта