Использование спектральной кластеризации и обучения с подкреплением для победы в Wordle
Wordle — это простая словесная игра, разработанная Джошем Уордлом. Прочитав об этом в Нью-Йорк Таймс, я попробовал и сразу же зацепился. Мы с женой немного соперничаем, каждый день сравнивая количество догадок, и я подумал, что было бы забавно создать бота, чтобы добавить в соревнование. В этом посте я рассмотрю правила Wordle и расскажу о дизайне и производительности моего бота в более чем 1000 смоделированных играх. Основные используемые методы ML/AI включают Спектральную кластеризацию и Q Learning.
TLDR;
- Я использовал машинное обучение, чтобы создать бота для игры в Wordle в сложном режиме.
- В более чем 1000 смоделированных играх бот использовал в среднем 3767 догадок, чтобы найти правильное слово.
- Бот проиграл 8 из 1000 смоделированных игр с общим коэффициентом выигрыша 99,2%.
Wordle Primer / Обзор правил
Для непосвященных Wordle — это игра-угадайка, похожая на «Виселицу». Каждый день у вас есть до 6 попыток угадать спрятанное слово. Для каждой буквы каждого предположения вы получаете обратную связь (зеленый, если буква находится в скрытом слове и в правильном месте, желтый, если буква есть в слове, но в неправильном месте, и серый, если буква не находится в скрытом слове). слово).
Если вы играете в игру в сложном режиме, вы обязаны использовать отзывы о каждом предположении для информирования ваших последующих предположений (чтобы вы не могли отправлять предположения исключительно для получения информации и сокращения пул возможных слов). Мой бот играет в сложном режиме.
Связанных с работой
Беглый просмотр блогосферы показал, что я был не единственным, кто был заинтригован использованием науки о данных для решения задачи Wordle.
- Мэтт Рикард описал жадный подход к определению лучшего начального предположения для Wordle, основанного на исключении как можно большего количества вариантов ответа (он остановился на SOARE, о котором я даже не знал, что это слово).
- Марк Шершель II предложил использовать попарные расстояния для измерения центральности слова, выбрав TARES как лучший выбор начального слова из-за его относительной близости к другим словам.
Я хотел внедрить и расширить эти идеи в дизайне своего бота, чтобы создать автономного агента, сосредоточившись не столько на лучшем первом слове, сколько на политике, регулирующей наилучшие следующая догадка для перехода от одного состояния игры к другому. В идеале этот агент должен учиться на своем опыте и повышать свою производительность по мере того, как будет играть все больше и больше игр.
Источник данных
Хотя в английском языке более 12 000 слов из 5 букв, многие из них являются архаичными или эзотерическими. Создатель Wordle ограничил банк ответов примерно 2300 общеупотребительными словами в повседневном языке. Я вручную скопировал банк из 2300 слов из исходного кода Wordle, чтобы обучить своего бота.
График сходства слов
Набор допустимых слов организован в неориентированную графовую структуру данных. Каждый узел или вершина — это слово, и каждое ребро или связь между словами взвешивается простой оценкой сходства. Оценка состоит из 1 балла за каждую общую букву между двумя словами и дополнительного балла, если общая буква также находится в том же месте в слове.
Оценки парного сходства вычисляются для всех слов в меньшем банке ответов и сохраняются в симметричной матрице смежности.
Спектральная кластеризация
Спектральная кластеризация используется для разделения графа на k сообществ (групп похожих узлов). Я использовал значение k, равное 5. Я не буду слишком углубляться в сорняки для этого поста, но если вы не сталкивались с этим алгоритмом, вы можете думать о нем как о K-средних для графов подобия. Для тех, кто хочет читать дальше, ознакомьтесь с этим постом в Википедии (хорошая отправная точка).
Q Обучение
Q-обучение — это форма обучения с подкреплением, которая направлена на изучение политики π на основе опыта (в форме переходов между состояниями, действиями и полученными вознаграждениями). Одной из задач Q Learning является определение дискретного пространства состояний, чтобы агент мог получить достаточный опыт путем экспериментов, чтобы изучить «лучшее» действие в данной ситуации, чтобы максимизировать ожидаемое вознаграждение. Еще одна проблема заключается в создании системы вознаграждения, которая эффективно уравновешивает краткосрочные и долгосрочные вознаграждения (например, легче научить бота есть шоколадный батончик, чем копить на колледж).
В этом упражнении я определяю состояние, дискретизируя распределение узлов среди k сообществ. При k=5 это привело к 126 возможным состояниям.
Действия определялись как из какого сообщества бот должен выбрать следующее угадываемое слово.
Вознаграждения определялись как сумма следующих трех компонентов: коэффициент сокращения, коэффициент правильности и бонус за победу.
Коэффициент сокращения определяется как отношение количества допустимых слов доугадывания к количеству допустимых слов послеугадывания. Чем больше слов исключается при догадке, тем больше коэффициент сжатия.
Фактор правильности определяется как 2 балла за каждую зеленую букву (правильная буква в правильном месте), 1 балл за каждую желтую букву (правильная буква, неправильная позиция) и 0 баллов за каждую серую букву (буква не в правильном слове). .
Бот зарабатывает большой бонус в размере 1000 баллов за каждое выигрышное предположение.
Общая стратегия
Для каждой игры класс Grader случайным образом выбирает слово из банка 2315 обычных 5-буквенных слов. Затем бот использует итеративный подход, чтобы делать предположения. На каждой итерации бот выполняет следующие операции:
- разбивает граф, используя спектральную кластеризацию на множестве оставшихся допустимых слов
- дискретизирует распределение слов по кластерам
- использует Q Learner для выбора кластера, из которого будет сделана следующая догадка
- выбирает предположение как «центроид» выбранного кластера (слово, имеющее наивысший общий показатель сходства в кластере)
- передает предположение классу Grader, который оценивает предположение и возвращает обратную связь в виде вектора оценок для каждой буквы (2 для зеленого, 1 для желтого, 0 для серого)
- фильтрует график, чтобы исключить недопустимые слова на основе отзывов оценщика
- вычисляет награду для передачи Q Learner на следующей итерации
Бот завершает свои итерации, когда угадывает правильное слово.
С помощью этой стратегии я заставляю бота сыграть 1000 игр и записываю количество догадок для каждой.
Производительность
За 1000 игр бот в среднем угадал 3,767. Он «проигрывает» 8 раз (для определения правильного слова требуется более 6 догадок) с общим коэффициентом выигрыша 99,2%. Вот диаграмма, показывающая производительность бота за период в 1000 игр:
Выводы
Я был приятно удивлен производительностью моего бота в целом. Мой собственный Wordle средний балл колеблется между 3 и 4, так что бот определенно может противостоять человеку!
Тем не менее, есть много возможностей для улучшения. Вычисление и сохранение оценок схожести — наименее эффективная с вычислительной точки зрения часть текущего дизайна моего бота, поскольку для вычисления 2315 слов требуется 5 359 225 парных оценок схожести. Поскольку граф симметричен, технически ~ 5 миллионов вычислений сходства можно сократить вдвое до ~ 2,5 миллиона. Поскольку баллы никогда не меняются, их действительно нужно вычислять только один раз (в то время как мой текущий дизайн излишне пересчитывает баллы из целесообразности). Вся симуляция занимает около 45 минут в среде Google Colab, и я уверен, что это время выполнения можно существенно сократить с помощью некоторого рефакторинга.
Кроме того, есть много параметров, которые можно настроить. Например, я произвольно установил количество сообществ равным 5 для этого упражнения и добился достаточно хороших для меня результатов, но может быть какое-то другое оптимальное количество сообществ.
Наконец, я подозреваю, что часть Q Learning бота может быть излишней. Я не заметил уменьшения количества догадок за игру, которое я ожидал увидеть по мере того, как бот набирался опыта, предполагая, что «конвергенции» не произошло. Тем не менее, для забавного короткометражного проекта я очень доволен тем, как все получилось.
Расширенную версию этого поста, включая код, можно найти в Jupyter Notebook на моей странице GitHub. Как бы вы подошли к такому боту? Дай мне знать в комментариях!