Игра в слова вызвала большой интерес вскоре после своего выхода. Задача угадать спрятанное слово из пяти букв невероятно увлекательна. Гениально простые правила игры очаровывают игроков-людей, а также компьютерщиков/математиков, которые хотят найти наилучшее решение. Видео, сделанное преподавателем математики 3Blue1Brown об использовании теории информации для решения Wordle, является одним из самых известных решений, доступных в Интернете. Популярность Wordle также привела к появлению неофициальных реализаций. Некоторые из этих неофициальных версий поддерживают разную длину слов и списки слов для нескольких языков.
Лично у меня проблемы со словарным запасом. Я не смог решить задачу Wordle за шесть попыток без посторонней помощи. Итак, я представил себе решатель мира, который не только поможет другим, кто также страдает от проблем со словарным запасом, получить удовольствие от игры, но и даст ответ на шумиху вокруг Wordle.
Решатель Wordle — это инструмент, который получает от игрока отзывы Wordle, а затем выводит слова-кандидаты, чтобы помочь игроку угадать скрытое слово за шесть попыток или как можно скорее.
К сожалению, у меня не было времени, чтобы вложить много усилий в создание блестящего решателя. Следовательно, любой подход, требующий большого количества симуляций или обучения модели, не будет для меня подходящим путем создания решателя.
Большинство подходов к решению Wordle, опубликованных в Интернете, требуют:
а) Доступ к списку слов конкретной реализации Wordle; и
b.) Моделирование, которое перебирает все или случайно выбранное подмножество возможных пар скрытого слова и угаданного слова со сложностью O (n²) в наихудшем случае.
строить.
Кроме того, я также хотел, чтобы мой решатель мог быть «защищенным от будущего» и «не требующим особого обслуживания» таким образом, чтобы он мог адаптироваться к неофициальным версиям Wordle с минимальными изменениями или даже без них.
Я стратегически утверждаю, что мой решатель Wordle должен:
● Быть ориентированным на будущее и минимальным обслуживанием;
● Займите короткое время, чтобы построить; и
● Быть дешевым в развертывании.
Поэтому практически я не должен:
● Фиксация на списке слов конкретной версии Wordle и пятибуквенных словах; и
● Экспериментируйте с подходами, требующими контролируемого обучения и большого количества симуляций.
1. Списки слов
Во-первых, мне нужен был список английских слов. Поиск был довольно простым. Я нашел два списка, которые мог бы использовать: 10 000 часто используемых английских слов MIT и 466 000 английских слов dwyl.
Можно извлечь два списка слов из кода JavaScript официальной версии Wordle. Один — разрешенные предположения и другой — ответы. Однако эти два списка не очень помогли в моем случае, поскольку я не ориентировался на конкретную реализацию Wordle.
2. Множественное число
Использование всеобъемлющего/общего списка слов представляет собой «проблему множественного числа». Общие списки слов обычно содержат как формы единственного, так и множественного числа слова. Например, в списке можно найти и «бледный», и «бледный».
Включение множественного числа резко расширит пространство поиска как для людей, так и для компьютеров. Например, в задаче угадать спрятанное слово из пяти букв включение множественного числа означает, что задача состоит в угадывании пятибуквенных слов в единственном числе плюс четырехбуквенных слов в единственном числе.
Поэтому мой решатель по умолчанию удаляет множественные числа, но предоставляет возможность сохранить множественные числа. Если известно, что конкретная версия Wordle использует множественное число, у игроков есть возможность включить множественное число в пространство поиска.
3. Сортировка слов-кандидатов
Предлагать хорошие слова игрокам, чтобы они быстрее закончили игру, — ключевая функциональность решателя Wordle. Наиболее эффективные подходы требуют запуска большого количества симуляций угадывания слов, чтобы найти лучшие слова, которые заставляют Wordle давать наиболее информативную обратную связь. Как я упоминал ранее, я намеренно избегал симуляций и контролируемого обучения, за исключением оценивания.
Я начал с интуитивного и наивного подхода с использованием условной вероятности. Каждый раз, когда решатель получает обратную связь от Wordle, решатель преобразует обратную связь в критерии поиска. Слова, не соответствующие критериям поиска, отфильтровываются. Затем решатель ранжирует оставшиеся слова по условным вероятностям символов в каждой позиции и предлагает игрокам несколько лучших слов.
К сожалению, наивный подход сам по себе не работал очень хорошо, потому что решатель в большинстве случаев не мог точно определить скрытые слова за шесть попыток.
Например, для слова «один» оценка будет следующей:
оценка = P('a' в позиции 1) * P('l' в позиции 2) * P('o' в позиции 3) * P('n' в позиции 4) * P('e' в позиции 5 )
4. Двойной список
Для своего эксперимента я загрузил два списка слов: 10 000 наиболее часто используемых английских слов Массачусетского технологического института и исчерпывающий список английских слов dwyl. Я называю их «короткий список» и «длинный список» соответственно. Я задавался вопросом, какой список будет работать лучше. Я обнаружил, что краткий список был «слишком коротким». Некоторые возможные скрытые слова в официальном Wordle не могут быть найдены в шорт-листе. С другой стороны, длинный список был «слишком длинным». Пространство поиска было слишком большим, и очень часто требовалось более шести попыток, чтобы правильно угадать спрятанное слово.
После некоторых экспериментов я обнаружил, что спрятанное слово можно найти за шесть попыток, если выбор списка чередуется на полпути. Это работало, когда решатель использовал короткий список в первых двух попытках, а затем переключался на длинный список с третьей попытки.
Когда я объединил подход с двойным списком с сортировкой по условной вероятности символов, решатель в большинстве случаев смог решить как официальную, так и неофициальную версии Wordle за шесть попыток.
5. Начальный список
Следующее, что нужно сделать, это найти способ выбрать слова, чтобы сформировать мой собственный короткий список для решения Wordle. Я хотел бы назвать этот новый короткий список «начальным списком». Из теории мы знаем, что слова в коротком списке, основанном на 10-тысячном списке Массачусетского технологического института, предоставляют больше информации для сокращения пространства поиска. Предположительно, слова из списка 10 000 были выбраны на основе их повседневного использования.
Видео 3Blue1Brown рассказало нам, как использовать теорию информации для поиска наиболее информативных слов. Однако его подход требует выполнения большого количества симуляций для получения данных для расчета энтропии слов. Такой подход был для меня непрактичным, так как у меня не было роскоши времени.
Итак, я экспериментировал с неконтролируемым обучением. Я попытался найти в длинном списке подслова, представляющие весь набор с точки зрения правописания. Чтобы быть точным, я использовал кластеризацию k-средних, чтобы найти кластеры слов на основе сходства их написания.
Я преобразовал слова в векторы, присвоив каждому символу номер. Я подключил векторы к методу кластеризации k-средних Scikit-learn. За считанные секунды я получил кластеры слов. В каждом кластере есть несколько слов. В каждом кластере я запускал симуляции (внутри кластера), чтобы увидеть, какое слово даст больше комбинаций обратной связи. Лучшее слово из каждого кластера выбирается для формирования нового «начального списка».
Кластеризация требует, чтобы векторы имели одинаковую форму. Таким образом, одновременно могут обрабатываться только слова одинаковой длины. Слова в полном списке сегментированы по длине слова перед векторизацией и кластеризацией. Репрезентативные слова из кластеров разной длины вычисляются отдельно, а затем объединяются в один открывающий список.
6. Производительность
Хотя производительность не является главным приоритетом моего решателя, все же имеет смысл сравнивать производительность моего подхода с производительностью других. Botfights.ai — сайт, посвященный ботам, разгадывающим Wordle. На сайте открылись турниры по разным спискам слов. У меня не было времени участвовать во всех турнирах.
В турнире из 2000 слов в списке скрытых слов официального Wordle мой решатель занял 4/5 место (в среднем 3,6 попытки; на 0,55 попытки больше, чем у чемпиона). В турнире с переменной длиной слова мой решатель занял 7-е место (в среднем 3,5 попытки; на 0,45 попытки больше, чем у чемпиона). (Примечание: чем меньше число догадок, тем выше производительность.)
Для меня производительность приемлемая.
7. Сделать его общедоступным
Приятный пользовательский интерфейс — еще один ключевой компонент моего решателя. Версия Python-CLI недостаточно удобна для большинства людей. Я потратил некоторое время на создание одностраничного веб-приложения с использованием vue.js.
Я представил решатель как функцию WSGI и упаковал его как облачную функцию.
Статический пользовательский интерфейс размещается в корзине Google Cloud, а функция решения — в функции Google. Google взимает всего 0,02 доллара США каждый месяц за размещение статического внешнего интерфейса vue.js и функции.
Мой Wordle Solver (https://solvewordle.games/) не пользовался особой популярностью, но за последние несколько месяцев у меня были пользователи почти каждый час. Возможно, нужно сделать больше для продвижения моего решателя.
Обсуждение
Wordle Solver, который я создал, не является первоклассным, но вполне пригоден для использования. Мне удалось найти баланс между временем сборки и производительностью.
Интуитивный и наивный подход с использованием условной вероятности расположения символов не мог работать сам по себе, но оказался хорошим в сочетании с более открытым списком репрезентативных слов, сгенерированным с помощью кластеризации.
Я надеюсь, что этот Wordle Solver, основанный на списках слов, сможет справиться с большим количеством вариантов Wordle до того, как потребуются какие-либо изменения.
