Как и многие люди в моей хронике твиттера, последние несколько дней я играл в Wordle. Это забавная простая маленькая игра, в которой вы угадываете слова из 5 букв, и она сообщает вам, сколько букв вы ввели правильно и находятся ли они на правильных позициях или нет. Частью игры является то, что есть только один в день, и это одно и то же слово для всех, кто играет.

Поэтому я решил сделать бота, чтобы играть в игру оптимально для меня. Теперь вы можете подумать об этом обмане, но, учитывая, как легко обмануть, «просто найдя ответ на сегодняшнюю головоломку», я не думаю, что создание такого бота неэтично или что-то в этом роде. Но знание «наилучшего первого слова» может испортить вам игру, поэтому вам следует прекратить чтение сейчас, если вы не хотите знать.

В любом случае, давайте начнем.

Во-первых, я взял списки слов, которые использует игра. Есть отдельный список для решений и возможных догадок (так что вы можете вводить странные слова, такие как AAHED, но они никогда не будут отображаться как фактическое решение головоломки, потому что это не часто используемое слово), и оба списка доступны просмотрев исходный код игры. Есть 2315 возможных решений и 12972 слова, которые он принимает в качестве предположений.

Быстрая оценка того, сколько времени это займет, я сначала умножил 12972 на 2315, чтобы получить ~ 30 миллионов предположений, и оценка каждого предположения снова умножит это на 2315, что составит порядка 60 миллиардов вычислений. 60 миллиардов вычислений кажутся большим количеством, но это тот же порядок величины, что и количество операций, которые ЦП может выполнять в секунду (4 ГГц x 8 ядер = 32 миллиарда), поэтому должно быть возможно сделать это с помощью грубой силы. . Я выбрал C++, чтобы иметь как можно меньше накладных расходов, а также потому, что он мне очень удобен.

Я выложил код бота здесь на гитхаб, для справки.

После небольшого кодирования у меня был «простой» тест. Для каждого возможного предположения он сверяет его со всеми возможными решениями. «Зеленые» квадраты (буква стоит на правильном месте) оцениваются в 2 очка, «Желтые» квадраты (буква есть в слове, но не в том месте) оцениваются в 1 балл, а серые квадраты (буква отсутствует). существуют в слове) оцениваются в ноль баллов. Предположение с наивысшим средним баллом (слово с наибольшей вероятностью наличия большого количества зеленых и желтых слов) возвращается как предположение.

Эта система работает достаточно хорошо. В среднем он находит решение с 3,69017 догадками. Первое слово, которое он выбирает, — SOARE («молодой ястреб»). Однако этот бот не каждый раз выигрывает игру. В худшем случае требуется 8 догадок, чтобы найти решение.

Теперь, хотя этот метод чрезвычайно быстр, мы можем добиться большего. Более конкретной метрикой того, насколько хороша догадка, будет «сколько в среднем возможных решений остается после этой догадки». Еще через пару часов у меня была версия бота, использующая этот метод, многопоточная, чтобы он мог вычислить результат за разумное время. Эта версия бота находит решение в среднем за 3,49417 догадок, а в худшем случае — за 5 догадок (это означает, что он *всегда* находит решение). Идеальным первым предположением, использующим этот метод, является ROATE.

Честно говоря, эффективность, с которой этот бот находит решения, впечатляет. Посмотрите, как быстро он находит правильное решение для сегодняшней (29.12) головоломки:

Итак, у вас есть идеальное первое предположение для Wordle — ROATE. Это означает: «Совокупная чистая прибыль после уплаты налогов, доступная акционерам обыкновенных акций, с поправкой на амортизацию нематериальных активов, затронутая налогом, за календарные кварталы в каждом календарном году в указанный период времени, деленная на средний материальный обыкновенный капитал акционера».

Но подождите, ROATE может быть идеальной первой догадкой, основанной на средней длине догадки, но, поскольку она находится только в списке догадок, а не в списке решений, она никогда не попадет в «дыру в одном». И если вы действительно хотите произвести впечатление на своих друзей, вы хотите иметь возможность получить шанс 1 из 2315 получить его с первого раза. Для этого идеальной первой догадкой будет RAISE. С ПОВЫШЕНИЕМ в качестве первого предположения у вас будет в среднем 3,49546 предположений для решения, что лишь немного хуже, чем ВРАЩЕНИЕ, но у вас будет приятный, приятный шанс попасть в эту дырку. (Поднятие — это также слово с лучшей производительностью в «наихудшем случае», поэтому я сам сейчас предпочитаю это)

Итак, у вас есть это. ROATE — это математически оптимальное первое предположение в Wordle. RAISE немного менее хорош, но дает вам шанс попасть в цель. Wordle решен!

…

or is it?

Итак, ROATE — это оптимальное первое предположение, если метрика, которую вы измеряете, — это «размер списка возможных решений после предположения». Но если вы действительно хотите «найти решение с наименьшим количеством ходов в среднем», это не совсем эквивалентно тому, что я измерял здесь.

Мне пришлось кодировать рекурсивное решение, которое напрямую измеряло бы среднее количество дополнительных предположений, необходимых для получения решения, основанного на любом предположении, но это оказалось слишком много для моего компьютера, чтобы справиться с наивным методом грубой силы. . Здесь мы говорим о количестве компьютерного времени длиннее, чем возраст Вселенной. У меня есть реальная работа, над которой я должен работать, поэтому я оставлю это вам всем в качестве домашнего задания. Удачи! Пожалуйста, твитните мне, если вам удастся найти *фактическое* оптимальное решение.