Введение: кроссворды
В этой статье мы рассмотрим построение кроссворда. Кроме того, мы показываем, как методы искусственного интеллекта можно использовать для решения проблемы построения кроссвордов.
Наша история
Я люблю слова, язык и головоломки. Но, если честно, я не очень хорошо разгадываю кроссворды. Поскольку мне трудно разгадывать кроссворды, я чувствовал, что составление кроссворда было для меня недостижимой целью. Но затем я встретил талантливого студента по имени Отис Петерсон, который с детства разгадывал кроссворды. Он даже работал над составлением собственного кроссворда.
Чем больше мы говорили о кроссвордах, тем больше убеждались, что можем создать собственное приложение для составления кроссвордов. Таким образом, при поддержке Суортморского колледжа мы смогли продолжить исследовательский проект по созданию веб-приложения для составления кроссвордов на https://www.crosswordconstruction.com.
Прежде чем мы обсудим наше веб-приложение, нам нужно рассказать вам немного больше о кроссвордах и понятии вычислительной сложности.
Читайте также: Может ли ИИ написать словарь? Знает ли ИИ, что означают слова?
Кроссворды
Кроссворды — это забавные и познавательные словесные головоломки, которые часто встречаются в газетах, средствах массовой информации, на веб-сайтах и в мобильных приложениях. Кроссворд представляет собой сетку, содержащую пустые и заштрихованные квадраты, а также список подсказок. Пустые квадраты предназначены для заполнения буквами алфавита для формирования горизонтальных и вертикальных ответов, соответствующих заданным подсказкам.
К кроссвордам применяется множество общих ограничений. Например, некоторые издатели требуют, чтобы кроссворды имели 180-градусную симметрию и чтобы все ответы имели длину не менее 3 символов. Такие ограничения могут сделать кроссворды более насыщенными ответами и усложнить их составление.
Теперь мы можем определить Задача на составление кроссворда. Эта задача требует заполнения заданной сетки кроссвордов так, чтобы каждый горизонтальный и вертикальный ответ был допустимым словом в данном словаре.
Для этой задачи мы не генерируем подсказки. Генерация улик — это отдельная и важная проблема, которую мы еще не решали.
Вычислительная твердость
В целом построение кроссворда считается сложной вычислительной задачей. В частности, проблема составления кроссворда. NP-полный.
NP-полнота — важное математическое свойство в информатике. С практической точки зрения NP-полные задачи считаются сложными в вычислительном отношении. Другими словами, мы пока не знаем, существуют ли эффективные алгоритмы, решающие эти проблемы во всех случаях.
За дополнительной информацией о проблеме построения кроссворда и NP-полноте мы отсылаем читателя к ГП14 в Компьютеры и трудноразрешимые проблемы: руководство по теории NP-полноты Майкл Гэри и Дэвид Джонсон.
Наше решение
Хотя задача построения кроссворда является NP-полной, мы считаем, что эвристики можно использовать для эффективного решения проблемы для небольших размеров сетки и больших словарей. Наивный подход к решению задачи построения кроссворда — попробовать все комбинации заполнения сетки потенциальными ответами из словаря. Однако этот подход можно значительно улучшить, если уменьшить количество комбинаций, которые нам приходится пробовать из словаря на каждом шаге. Фактически, в статье были представлены некоторые интересные концепции и методы для этого. Найдите уроки, извлеченные из кроссвордов который был опубликован в АААИ 1990 г. М. Гинзберг, М. Франк, М. Хэлпин и М. Торранс.
Для нашего решения мы применили соответствующие методы, чтобы максимально эффективно постоянно сокращать количество комбинаций. В конце концов наш алгоритм оказался успешным и стабильно генерировал кроссворды стандартного размера (15 на 15) на больших списках слов, содержащих 100 000 слов. Прототип нашего веб-приложения с ранней реализацией нашего алгоритма можно найти по адресу https://www.crosswordconstruction.com/generator.
Мы считаем, что наш алгоритм связан с ИИ, поскольку наш алгоритм по существу сокращает дерево поиска на каждом этапе, что является методом, используемым в алгоритмах, связанных с ИИ, для поиска, принятия решений и игр.
Предварительная работа над кроссвордами
Иногда в классах начальной школы появляются менее строгие кроссворды. Эти головоломки имеют меньше ограничений и содержат меньше горизонтальных и вертикальных ответов. Мы называем такие головоломки классными кроссвордами.
Ранее я работал с Итаем Ливни и несколькими коллегами над составлением кроссвордов в классе. Наша работа под названием Преобразование неструктурированных веб-данных в последовательные образовательные игры STEM был представлен на PyCon 2018.
В то время я разработал и внедрил генератор макетов кроссвордов в классе. Эта программа будет брать список слов и генерировать кроссворд в классе, используя эти слова в качестве горизонтальных и вертикальных ответов. В частности, программа попытается создать макет, пытаясь максимизировать количество связей между ответами, сохраняя при этом баланс высоты и ширины головоломки. Этот конкретный компонент нашей более широкой работы был выпущен с открытым исходным кодом, и его можно найти по адресу https://github.com/MichaelWehar/Crossword-Layout-Generator.
Большое спасибо за чтение! Мы будем рады любым идеям, отзывам и комментариям.
Я прекрасно провел время, работая с Отисом, и он проделал потрясающую работу! Я надеюсь, что мы сможем продолжать совершенствовать наши алгоритмы построения кроссвордов, чтобы создавать головоломки более высокого качества, которые интересно и сложно решать.
Читайте также: Переосмысление искусства с помощью генеративного искусственного интеллекта
Рекомендации
МайклВехар. «GitHub — MichaelWehar/Crossword-Layout-Generator: Генератор макетов кроссвордов — с открытым исходным кодом». GitHub, https://github.com/MichaelWehar/Crossword-Layout-Generator. По состоянию на 7 февраля 2023 г.
«Презентация: Преобразование неструктурированных веб-данных в последовательные образовательные игры STEM». PyCon 2018 в Кливленде, штат Огайо, https://pycon-archive.python.org/2018/schedule/presentation/179/. По состоянию на 7 февраля 2023 г.
Генератор кроссвордов. https://www.crosswordconstruction.com/generator. По состоянию на 7 февраля 2023 г.