[Перевод] Решаем Wordle с 3,64 попыток в 99,4% случаев
Недавно я играл в головоломку Wordle, параллельно думая, как бы её могла решать программа.
[Прим. пер.: Wordle — игра в отгадывание слов, напоминающая «быки и коровы». Правила достаточно ясны по скриншоту выше.]
Первым делом я извлёк списки слов с сайта Wordle. Любопытно, что существует «целевой» список из 2315 слов, которые могут быть ответами, но и дополнительный список из 10657 возможных догадок — вариантов, которые могут вводить пользователи, но которые никогда не будут ответом. Если вам нужны эти списки, то в репозитории ниже есть пара set в формате Python.
Первым делом я подумал, что для управления моей стратегией угадываний стоит использовать частотность букв английского языка. Однако потом я осознал, что есть способ получше: использовать частотность букв в целевом списке! Ведь это самое важное? Никаких мне etaoin shrdlu!
Также у меня возникла мысль, что я могу замерить частотность букв в конкретных позициях. Допустим, для первой позиции пятибуквенного слова частотность согласных будет больше, чем гласных? Или, возможно, я ошибаюсь.
Затем я подумал: почему бы не измерять эту частотность для возможных целевых слов на основании предыдущих догадок, отсекая ненужные варианты после каждой новой догадки?
Всё это я превратил в программу, выполняющую следующие шаги:
- Вычисляем частотность букв в позициях 1–5 для целевого списка слов.
- Выбираем слово, которое с наибольшей вероятностью даст новые зелёные буквы на основании частотности слов в каждой позиции.
- Используем результаты новой догадки, чтобы оставить в целевом списке только те слова, которые возможны с учётом всех предыдущих догадок.
- Повторяем.
По ходу дела у меня также возникла мысль, что в качестве списка потенциальных догадок можно использовать расширенный список, в котором есть все целевые слова и возможные догадки. Это увеличит возможность получения зелёной буквы. Однако, как вы можете увидеть в коде, я провёл этот эксперимент, но ответ при таком решении на самом деле оказался хуже! Потом я подумал, что есть смысл использовать расширенный список для первых одной-двух догадок, а затем пользоваться только целевыми словами. Это решение тоже было хуже, чем просто использование целевых слов.
Кроме того, сначала я не реализовал логику, гласящую, что когда жёлтая буква находится на той же позиции в слове, то это слово не является ответом. Добавление одной только этой логики позволило снизить среднее количество догадок с 4,5 до 3,6.
Программа может и проигрывать, в 14 случаях из 2315! Эти слова и догадки любопытны:
wound: [slate: 00000, crony: 00120, hound: 02222, bound: 02222, pound: 02222, mound: 02222] shave: [slate: 20202, share: 22202, shame: 22202, shape: 22202, shake: 22202, shade: 22202] vaunt: [slate: 00110, taunt: 02222, jaunt: 02222, haunt: 02222, daunt: 02222, gaunt: 02222] found: [slate: 00000, crony: 00120, hound: 02222, bound: 02222, pound: 02222, mound: 02222] boxer: [slate: 00001, fever: 00022, rider: 00022, cower: 02022, poker: 02022, homer: 02022] ratty: [slate: 00120, fatty: 02222, catty: 02222, batty: 02222, patty: 02222, tatty: 02222] catch: [slate: 00110, taunt: 12000, patch: 02222, match: 02222, hatch: 02222, batch: 02222] stamp: [slate: 20210, start: 22200, staid: 22200, stank: 22200, staff: 22200, stash: 22200] baste: [slate: 10122, paste: 02222, caste: 02222, haste: 02222, taste: 02222, waste: 02222] watch: [slate: 00110, taunt: 12000, patch: 02222, match: 02222, hatch: 02222, batch: 02222] goner: [slate: 00001, fever: 00022, rider: 00022, cower: 02022, poker: 02022, homer: 02022] fight: [slate: 00010, tight: 02222, might: 02222, wight: 02222, right: 02222, night: 02222] willy: [slate: 01000, golly: 00222, billy: 02222, hilly: 02222, dilly: 02222, filly: 02222]
Иногда программа выполняется в другом порядке, вероятно, это как-то связано с работой множеств в Python? Простите меня за код, я программист-самоучка с дипломом философа.
Код
https://github.com/tomlockwood/wordle-solve
(Множества слов находятся в ./lib/words.py)
Что дальше
Часть кода в репозитории поддерживает различные типы игр, и я продолжил работу, написав несколько альтернативных стратегий игры. Самая многообещающая выполнялась всю ночь на моём слабом ноутбуке, а потом у неё закончилась память. Чтобы решить эту проблему, я начал кэшировать на диск часть результатов, и эта база данных (sqlite) разрослась до размера 50 ГБ.
Я решил исследовать возможность реализации программы на Rust, и пока то, что занимало на Python 1 ГБ ОЗУ на Rust в буквальном смысле занимает 1 МБ! Я пытаюсь уместить программу в 8 бит, но не занимался ничем подобным раньше. Возможно, появится ещё один пост! Думаю, вполне возможно выигрывать каждую игру в среднем меньше чем за 3,5 догадки!
Мой текущий солвер предназначен для сложного режима игры и я считаю, что солвер для лёгкого режима проявит себя лучше. Похоже, наблюдение за решениями программы немного улучшили мои навыки игры в Wordle!
Habrahabr.ru прочитано 20282 раза
