Решение Wordle с использованием поиска по дереву Монте-Карло, усиление

Обучение и собственный алгоритм искусственного интеллекта

Энни Пейтс (Элизабет), Девин Куинн

Аннотация

Wordle - это игра на угадывание слов, в которой агенты пытаются угадать заранее определенное слово из пяти букв за шесть догадок, используя обратную связь от игры о буквах, использованных в предыдущей догадке, и их размещении. Многие алгоритмы могут быть полезны для оптимизации предположений и угадывания целевого слова. Мы используем поиск по дереву Монте-Карло, обучение с подкреплением и специальный алгоритм Wordle для изучения возможных стратегий решения головоломок Wordle. Обучение с подкреплением, особенно Q-обучение, показало лучшие результаты в нашей игре Wordle, успешно решая головоломку в 84% случаев в среднем за 4,9 попытки.

Введение

Wordle — это простая игра на угадывание слов, в которой у агента есть шесть попыток угадать слово из пяти букв. Среда состоит из шести рядов по пять пустых плиток. По мере того, как агент отправляет предположения, предоставляется обратная связь в виде цветных плиток. Зеленая плитка указывает на правильную букву в правильном положении. Желтая плитка указывает на правильную букву, но в неправильном положении. Черная плитка указывает на то, что буква не является частью правильного слова, как показано на рисунке 1. Угадываемые слова должны быть английскими словами и не могут быть последовательностью случайных букв.

Wordle, запущенный осенью 2021 года, теперь работает через популярную игровую платформу New York Times. Незадолго до своего пика популярности в феврале 2022 года в игру играли более 2 миллионов раз в день (The Guardian). Согласно анализу, проведенному сайтом по подбору слов word.tips, среднее количество догадок по всему миру для решения Wordle составляет 3,919. Поскольку эти данные были основаны на оценках, опубликованных в Твиттере, они, вероятно, будут взвешены в сторону меньшего количества предположений, поскольку люди с большей вероятностью публикуют более высокие оценки.

Словарь wordle представляет собой конечный список из 2316 общих 5-буквенных слов. Это делает слово полностью наблюдаемым, детерминированным, последовательным, статическим, дискретным и единственным агентом, отличным кандидатом для стратегий решения, генерируемых искусственным интеллектом. Чтобы определить эффективный алгоритм решения, нам сначала нужно было разработать игру Wordle на Python. Затем мы разработали несколько алгоритмов: наивный подход, поиск по дереву Монте-Карло и обучение с подкреплением. Из наших подходов Q-обучение показало наилучшие результаты с вероятностью успеха 84% и в среднем с 4,9 догадками для решения головоломки.

Бумага разделена на следующие разделы. В разделе 2 представлена ​​информация о соответствующих алгоритмах, а в разделе 3 описаны другие методы, которые использовались для решения задач Wordle. Раздел 4 подробно описывает наш подход к решению проблемы. В разделе 5 сравнивается эффективность различных алгоритмов и используемых параметров, а в разделе 6 подводятся итоги наших выводов.

Фон

Возможны несколько подходов к поиску оптимальной стратегии решения Wordle. Мы начали с поиска по дереву Монте-Карло, в котором каждое состояние узла хранит статистику выигрышей/проигрышей из повторяющихся развертываний. На первом этапе Выбор пути выбирается от корня к конечному узлу с неисследованными дочерними узлами. Узел выбирается на основе политики выбора, которая уравновешивает исследование (поиск новых путей, если есть лучший, который еще предстоит изучить) и эксплуатацию (глубокое углубление в текущий лучший обнаруженный путь). На следующем этапе расширения выбирается случайный дочерний узел. На этапе моделирования выполняется развертывание (или несколько развертываний) в соответствии с политикой развертывания, и статистика выигрышей/проигрышей сохраняется в узле. Затем, на заключительном этапе, эта статистика выигрышей/проигрышей передается обратно для обновления родительских узлов.

В q-обучении агент должен найти оптимальную политику, не имея модели вероятностей перехода и вознаграждений для среды. Алгоритм работает, играя в игру большое количество раз, а затем «учась улучшать стратегию. На каждом шаге каждого эпизода алгоритм обновляет оптимальную функцию, начиная с состояния S и заканчивая действием A. См. рис. 3 для расчета обновления, выполняемого на каждом шаге. ε-жадное Q-обучение позволяет исследовать лучшие пути, которые алгоритм еще не обнаружил, с вероятностью ε.

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

Похожая работа

Многие исследователи работали над поиском решений для Wordle. Берцимас и Пасков утверждают, что у них есть первый подход, который каждый раз оптимально решает Wordle. Их подход использует марковские процессы принятия решений и точное динамическое программирование для получения оптимального начального слова «SALET» (MIT Sloan). В среднем их алгоритм находит спрятанное слово за 3421 попытку. Андерсон и Мейер используют обучение с подкреплением, чтобы найти оптимальное начальное слово «SOARE». Мы не следовали их методам, потому что они пытались создать подход, которому могли бы следовать люди, в то время как мы воспользовались способностью компьютера вспоминать все возможные слова. Подход Андерсона и Мейера имел общий коэффициент выигрыша 64,8%, и большую часть времени агент делал 6 предположений. Тайлер Глэйел запрограммировал попытку угадать оптимальное первое слово и обнаружил, что «ПОВЕРНУТЬ» лучше всего подходит для быстрого поиска решения, но, поскольку это невозможное решение, он предлагает «ПОВЫШИТЬ» для возможности получения ответа при первом предположении. Эти разрозненные рекомендации «лучшего» начального слова показывают, что еще предстоит проделать работу по оптимизации алгоритма, решающего Wordle.

Подход

Создание среды

Чтобы проверить наши подходы к решению Wordle, нам сначала нужно было создать среду, в которой ручные или запрограммированные агенты могли бы играть в игру несколько раз в зависимости от их стратегий. Для этой среды мы использовали список из 2316 общих 5-буквенных слов, который используется разработчиками игр Wordle. Это позволило нам сохранить управляемый размер пространства состояний, а также сделать игру более честной и увлекательной для игроков-людей. Игра была разработана, чтобы играть точно так же, как Wordle. Когда пользователь вводит предположение, наша среда возвращает последовательность из пяти символов: g (зеленая плитка), y (желтая плитка) или b (черная плитка). Агенты могут использовать эту обратную связь, чтобы сообщить о своем следующем предположении, что приведет либо к выигрышу, либо к проигрышу в конце шести догадок. Мы также разработали возможность повторять игру, вычисляя процент побед и среднее количество предположений, сделанных агентом в конце сеанса.

Наивный подход

Чтобы установить эталон производительности, мы разработали наивный подход, основанный на прошлых исследованиях и способности нашего агента знать все возможные слова для цели. Для начала агент выбирает одно из шести слов, определенных прошлым исследованием как оптимальные начальные слова: «сланец», «кран», «наклон», «след», «ящик» и «карта». После каждого предположения агент отслеживает, какие новые желтые и черные буквы были обнаружены, а также местонахождение любых зеленых букв. Проходя список потенциальных слов, он удаляет все слова, содержащие черные буквы. Затем он выбирает слово из оставшегося списка, которое имеет «зеленые» буквы в соответствующих местах, как определено прошлыми результатами. Таким образом, не всегда оптимально пытаться как можно быстрее исправить как можно больше букв. Обнаружение того, что целевое слово не включает в себя общую букву, может уменьшить пространство состояний на столько же или даже больше, чем обнаружение того, что оно содержит общую букву.

Поиск по дереву Монте-Карло

Для нашего подхода MCTS к игре Wordle наш процесс выбора начинается с обратной связи с первоначальным предположением. Эта обратная связь позволяет расширить зеленые и желтые деревья вариантов слов с помощью индикаторов буквенных значений, предоставленных в обратной связи. Слова с зелеными буквами помещаются в зеленое дерево, а слова с желтыми буквами помещаются в желтое дерево, а слова, содержащие черные буквы, удаляются из списка оставшихся возможных вариантов слов. На этапе моделирования словам в желтых и зеленых деревьях присваиваются веса в зависимости от того, сколько зеленых и желтых букв они содержат соответственно. Вес 1 дается за зеленую или желтую букву. Максимально возможный вес равен 5. Присваивается случайное число, и на основе этого значения либо зеленое дерево, либо желтое дерево расширяется дальше, при этом зеленому дереву присваивается больший вес, это начальное значение. Затем выбранное дерево расширяется только до глубины текущего максимального веса. Новое слово на этом уровне выбирается случайным образом, а затем передается обратно, чтобы быть новым предположением, где процесс повторяется до тех пор, пока не будет найдено правильное слово или не будет исчерпано количество попыток.

Обучение с подкреплением

Чтобы применить Q-Learning к среде Wordle, нам нужно было определить состояния эпизодов и действия, а также создать эффективную функцию вознаграждения. Мы определили состояние как кортеж текущего предположения и результата этого предположения (например, «gbbyb» для зеленых, черных, черных, зеленых и желтых букв). Начальное состояние было задано как предположение «Нет», а результат «bbbb». Действие определялось как следующая догадка, выбранная из списка возможных слов. Хотя сначала начальное предположение в каждом раунде будет случайным выбором из списка, по мере того, как агент исследует окружающую среду, он будет выбирать на основе прошлых вычисленных значений Q.

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

В начале обучения Q-значения для всех пар состояний и действий устанавливаются равными нулю. Предположения выбираются с использованием ε-жадного подхода, при котором с вероятностью = ε выбирается случайное слово. В противном случае лучшее слово выбирается на основе наивысшего значения Q (выбирается случайным образом среди слов с наибольшим значением). Это позволяет агенту балансировать между использованием догадок, которые, как он знает, дают хорошие результаты, и изучением неизвестных догадок в случае, если есть та, которая работает лучше. Значение ε можно настроить, чтобы отрегулировать баланс между разведкой и эксплуатацией. Агент воспроизводит выбранное предположение и использует результат для обновления Q-таблицы на основе функции вознаграждения и уравнения обновления, показанного выше. После каждого предположения пул возможных оставшихся слов фильтруется во время расчета вознаграждения.

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

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

Эксперименты и результаты

Наивный подход

Наивный подход позволил создать алгоритм, который угадывал загаданное слово в 49% случаев из 1000 запущенных игр. Наивный агент делал в среднем 5,45 предположений. Хотя это значительно ниже результатов исследований человека и других исследований, оно служит хорошей отправной точкой.

МТС

Агент поиска по дереву Монте-Карло смог улучшить нашего наивного агента. На пике своего развития MCTS давал 52,2% успешных попыток и в среднем 5,04 предположения. Опытным путем мы смогли определить, что агент работал лучше, когда «начальный порог» был ниже. По сути, агент более успешен, когда он склонен к зеленым буквам, а не к желтым. Хотя увеличение процента выигрышей незначительно по сравнению с нашим наивным агентом, разница в требуемых предположениях достаточно значительна, чтобы сделать MCTS значительным улучшением. MCTS может занять несколько итераций, чтобы изучить пространство, поэтому возможно, что агент не имеет достаточного опыта в среде, прежде чем его шесть догадок закончатся. Предел предположения ограничивает, насколько успешным может быть агент MCTS.

Обучение с подкреплением

Агент Q-обучения очень успешно угадал спрятанное слово. С 10 000 тренировок и 1000 тестов он выиграл 84% игр и в среднем угадал 4,88. Это улучшение винрейта согласуется с целым рядом переменных.

Изменение веса, назначенного зеленым и желтым буквам в функции вознаграждения, мало влияет на результат, указывая на то, что большая часть эффективности зависит от того, насколько пространство состояний ограничено цветом букв в результате. Показатели успеха и средние предположения существенно не отличались, независимо от того, были ли веса 200 и 100 или 2 и 1.

Результаты также не были существенно изменены при изменении значений эпсилон или проведении большего количества раундов обучения. Это также указывает на то, что большая часть эффективности алгоритма связана с ограничением пространства состояний для последующих предположений, поскольку компромисс между исследованием и эксплуатацией, по-видимому, незначителен. Возможно, это связано с тем, что потенциал пар состояние-действие огромен, даже с ограниченным словарем в 2316 слов. Состояние — это кортеж любого слова в словаре в качестве предположения и его обратной связи по сравнению с любым другим словом в качестве цели. В сочетании с действием, которое является еще одним словарным словом, существует более 12 миллиардов пар состояния-действия, если только не уменьшить пространство состояний. Из-за этого очень трудно осмысленно исследовать пространство, независимо от фактора исследования или количества завершенных раундов обучения.

Заключение

Мы обнаружили, что лучший подход к решению Wordle — использовать Q-Learning с функцией вознаграждения, основанной на состоянии победы, возвращенных зеленых и желтых буквах и способности каждого предположения сокращать оставшиеся потенциальные слова. Независимо от весов в функции вознаграждения и факторов исследования, этот подход постоянно достигал успеха около 83% менее чем за 5 попыток. Этот результат превосходит попытки Андерсона и Мейера разработать агента с человеческими ограничениями. Q-агент, по-видимому, требует больше догадок, чем в среднем человек, однако эти данные, вероятно, искажены, чтобы завышать высокие баллы.

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

Код

Пожалуйста, посетите наш репозиторий GitHub, чтобы увидеть наш код: https://github.com/devin-p-quinn/wordle_solver/blob/main/wordle.py

Ссылки

Андерсон, Б.Дж., Мейер, Дж.Г. 2022. Поиск оптимальной человеческой стратегии для wordle с использованием максимальных вероятностей правильных букв и обучения с подкреплением. http://dx.doi.org/10.48550/ ARXIV.2202.00557.

Берцимас Д., Пасков А. 2022, 20 сентября. Точное и интерпретируемое решение Wordle. Массачусетский технологический институт Слоан. https://auction-upload-files.s3.amazonaws.com/Wordle_Paper_Final.pdf.

Glaiel, T. 2021. Математически оптимальное первое предположение в wordle. https://medium.com/@tglaiel/the-mathematically-optimal-first-guess-in-wordle-cbcb03c19b0a.

Холл, Р. 2022 г., 11 января. Wordle Creator поражен глобальным успехом Hit Puzzle. The Guardian. https://www.theguardian.com/games/2022/jan/11/wordle-creator-overwhelmed-by-global-success-of-hit-puzzle

Хо, А. 2022, 6 марта. Решение Wordle с помощью обучения с подкреплением. Веса и уклоны. https://wandb.ai/andrewkho/wordle-solver/reports/Solving-Wordle-with-Reinforcement-Learning--VmlldzoxNTUzOTc4.

Янку, Мирела. 2022, январь. Где в мире лучше всего решать Wordle? Подсказки. https://word.tips/wordle-wizards.

Тренчени, М., 2022 г., 19 января. Оптимальное покрытие Wordle методами Монте-Карло. Bytepawn. https://bytepawn.com/optimal-coverage-for-wordle-with-monte-carlo-methods.html#optimal-coverage-for-wordle-with-monte-carlo-methods.