Использование спектральной кластеризации и обучения с подкреплением для победы в Wordle

Wordle — это простая словесная игра, разработанная Джошем Уордлом. Прочитав об этом в Нью-Йорк Таймс, я попробовал и сразу же зацепился. Мы с женой немного соперничаем, каждый день сравнивая количество догадок, и я подумал, что было бы забавно создать бота, чтобы добавить в соревнование. В этом посте я рассмотрю правила Wordle и расскажу о дизайне и производительности моего бота в более чем 1000 смоделированных играх. Основные используемые методы ML/AI включают Спектральную кластеризацию и Q Learning.

TLDR;

  • Я использовал машинное обучение, чтобы создать бота для игры в Wordle в сложном режиме.
  • В более чем 1000 смоделированных играх бот использовал в среднем 3767 догадок, чтобы найти правильное слово.
  • Бот проиграл 8 из 1000 смоделированных игр с общим коэффициентом выигрыша 99,2%.

Wordle Primer / Обзор правил

Для непосвященных Wordle — это игра-угадайка, похожая на «Виселицу». Каждый день у вас есть до 6 попыток угадать спрятанное слово. Для каждой буквы каждого предположения вы получаете обратную связь (зеленый, если буква находится в скрытом слове и в правильном месте, желтый, если буква есть в слове, но в неправильном месте, и серый, если буква не находится в скрытом слове). слово).

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

Связанных с работой

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

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

Источник данных

Хотя в английском языке более 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. Как бы вы подошли к такому боту? Дай мне знать в комментариях!