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

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

Если вы еще не знаете, Wordle — это игра на угадывание 5-буквенных английских слов, в которой игроки пытаются найти 5-буквенное слово за 6 или менее попыток. После каждого предположения игра предоставляет обратную связь для каждой буквы, используя систему цветового кодирования:

  • Зеленый цвет означает, что буква находится в целевом слове на той же позиции.
  • Желтый цвет означает, что буква находится в целевом слове, но в другой позиции.
  • Серый цвет указывает на то, что буквы вообще нет в целевом слове.

Вот пример из недавней игры, которая разыгралась за 4 попытки.

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

Wordle меня как игрока не особо интересует. Мне не очень нравятся словесные игры, но мне нравится язык и данные. Итак, я быстро погрузился в данные Wordle. Я узнал много интересного об этом 5-буквенном подпространстве английского языка. Например: в среднем после первого предположения вы уменьшили число возможных ответов в 25 раз! Одно предположение отфильтровывает в среднем 96% слов. Насколько это безумно?

Вот еще один. Используя стабильный алгоритм, невозможно решить следующие 5 слов менее чем за 5 попыток без удачи: EATER, PENAL, STILL, TRUSS и UNTIL. Все остальные слова могут быть решены (используя только умение) за 4 попытки или менее, при этом большинство может быть решено только за 3.

Чем это отличается от стратегических игр

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

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

Программисты много говорят о разметке, когда говорят о таких играх, как Wordle. Разделение — это взятие набора чего-либо и сокращение его на непересекающиеся подмножества. В этом случае эти подмножества будут не могут быть и могут быть.

То, как это делается в Wordle, основано на отзывах, которые вы получаете от игрового процесса. Для всех ранее определенных зеленых, желтых и серых букв вы можете оценить каждое возможное оставшееся слово из 5 букв:

  • Зеленые буквы в правильном месте? Если это так, добавьте его в может быть.
  • Есть ли в нем желтые буквы Инаходятся ли они на новых позициях? Если это так, добавьте его в может быть. (Это очень важно, потому что желтые буквы не просто говорят вам, какие буквы есть в слове, они говорят вам, где они не расположены.)
  • У него серые буквы? Если да, укажите не может быть.

Это хорошо для компьютеров, но люди так не работают, по крайней мере, большинство из нас. Разделение — это исключение, но то, как люди решают Wordle, больше зависит от воображения. Мы чаще думаем:

Какие слова здесь могут подойти?

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

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

Что вы должны знать о словарях Wordle

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

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

Лексикон Wordle разделен на правильные ответы и правильные предположения. Первый список включает возможные ответы. Он состоит из 2315 слов и включает часто используемые слова из 5 букв. Второй список состоит из 10 637 слов и включает только те слова, которые являются допустимыми в качестве предположений из-за их неясности (я смотрю на вас, «ycond»). В целом это означает, что 12952 слова доступны для угадывания до ответа, когда возможны только 2315 слов.

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

Первая догадка имеет большое значение

Независимо от того, человек вы или машина, успех игры зависит от качества первого предположения. Первая догадка всегда слепа, поэтому вы можете каждый раз начинать с одного и того же слова. Однако решение о том, что это за слово, вызвало немалые разногласия в тех уголках сети, где прячутся Wordlers.

Многие думают, что SALET — лучшее начальное слово. Wordle Bot от NYTimes претендует на то, чтобы CRANE был лучшим, что я нахожу сомнительным, и вы скоро поймете, почему.

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

Сортировка слов по частоте букв

При рассмотрении частоты букв недостаточно думать об относительной частоте букв во всех словах. Все, что имеет значение, — это частота букв в 5-буквенных словах, а точнее, 2315 ответов Wordle. Идя дальше, частота букв в определенных позициях важнее, чем частота букв в целом.

Я перебирал цифры и буквы и вот что нашел:

  • S — самая распространенная начальная буква, за которой следуют C и B.
  • А — самая распространенная вторая буква, за которой следуют О и Р.
  • А также является наиболее распространенной третьей буквой, за которой следуют I и O.
  • E — самая распространенная четвертая буква, за которой следуют N и S.
  • E также является наиболее распространенной 5-й буквой, за которой следуют Y и T.

Исходя из этого, мы можем присвоить словесную оценку всем словам в обоих наборах ответов, и вот пятьдесят слов с наивысшей оценкой по порядку:

SAINE, SOARE, SAICE, SLANE, SOILY, SLATE, SOAVE, SAMEY, SAUCE, SLICE, SHALE, SAVEY, SAUTE, SHARE, SOUCE, SHINE, SUITE, CRANE, SEITY, SLATY, SAINT, SLADE, SOAPY, SLIER, SONCE, БЛЕСТЯЩИЙ, СТАН, БРАН, САЛЕТ, СЛАК, ШАЙР, САЙРА, ДЕРЗКИЙ, ШЕРСТЬ, ИЗНОС, РАБ, ШАЛЫЙ, ИСПАНИЯ, ШИТЕ, САНЕР, CRINE, SNARE, STALE, CRATE, SARGE, SHORE, SUAVE, SOOEY, CRISE, SLIDE

В соответствии с этим подходом наилучшим начальным словом является SAINE.

Сортировка слов по степени их разделения

В математике есть целая область, посвященная таким задачам, и она началась в середине 1900-х годов с самой важной из когда-либо написанных магистерских диссертаций. Этот тезис был написан Клодом Шенноном, и он положил начало веку информации. Эта область называется теорией информации.

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

Если догадка делит возможные ответы на половину меньшего размера, чем раньше, то говорят, что она содержит 1 бит информации. Если он разбивает набор ответов с коэффициентом 4, говорят, что он имеет 2 бита (поскольку 2²=4) и так далее.

В среднем начальные слова содержат около 4,5 бит информации, что довольно поразительно, если подумать. Это означает, что в среднем одно слово из 5 букв сокращает число возможных ответов до двадцати пятых от исходного! (2 ^ 4,5 ≅ 25). В среднем остается всего 92 слова!

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

Чтобы найти это слово, я перебрал все возможные начальные слова (12952 слова из обоих наборов слов) и применил их к каждому слову ответа (2315 слов), измерив, насколько это начальное предположение уменьшило оставшиеся ответы на основе зеленого и желтого цветов. и серая обратная связь.

Позвольте представить вам слово с самой высокой скоростью разбиения: ROATE.

В среднем ROATE содержит 5,3 бита информации. Это означает, что оставшиеся ответы будут уменьшены в 38 раз, или на 97,4%. Вау, РОАТ, это потрясающе!

В среднем он отфильтрует 2255 слов, оставив только 60 возможных ответов. В лучшем случае он может отфильтровать несколько целевых слов до одного ответа (но все слова могут сделать это как минимум для 1 другого слова). В худшем случае, когда целевое слово БЛЕСТЯЩЕЕ, оно все равно сокращается до 195 слов. Это 3,6 бита информации и коэффициент уменьшения 11,87.

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

Итак, с чего мне начать? Должен ли я начать с SAINE или мне следует перейти на ROATE?

Что ж, не ненавидьте меня, но оказывается, что ни одно из этих слов не является лучшим исходным словом, если учесть эффективность остальных догадок.

Они оба хороши для начальных догадок, но последующие догадки, основанные на оставшихся доступных буквах, явно менее эффективны, чем начинать со слов, таких как SALET и SLATE. Оба этих слова имеют высокую частоту букв (№6 и №29 соответственно) и скорость разбиения (№23 и №27 соответственно). Из 50 лучших как по относительной частоте букв, так и по разделению они показали лучшие результаты в моих вычислениях.

Ранее я упоминал, что Wordle Bot от NYTimes объявляет CRANE лучшим начальным словом. CRANE показал себя хуже в обоих измерениях и в моих вычислениях пути к последнему слову, поэтому я не могу быть уверен, почему они считают это оптимальным начальным словом. Возможно, это как-то связано с тем, что Wordle Bot использует всего около 4500 слов, чтобы снизить требования к вычислительным ресурсам.

С этого момента мы будем двигаться вперед с SLATE, потому что в моих вычислениях SALET приводил к меньшему количеству слов, решенных при наибольшем количестве догадок (6), но SLATE приводил к более низкой общей средней скорости угадывания (3,676).

После первого предположения

После сокращения 2315 вариантов ответа до 71 в среднем есть два разных пути.

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

При выборе этого пути есть 25% шанс решить головоломку за 3 попытки и 80% шанс решить за 4 попытки. 10 слов вообще не разгадываются, а 57 требуют полных 6 догадок. Вот распределение в этом методе.

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

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

Опять же, мы задаем всеобъемлющий вопрос: какие слова мы можем придумать, чтобы использовать наибольшее количество этих букв?

Чтобы было понятнее, давайте посмотрим на целевое слово HOUND.

  • После угадывания SLATE остается 0 зеленых, 0 желтых и 5 серых букв, что дает 221 слово.
  • После угадывания CRONY остается 1 зеленая {N}, 1 желтая {O} и еще 3 серые буквы {C,R,Y}, что дает 9 слов: BOUND, POUND, FOUND, DOING, MOUND, GOING, WOUND, HOUND, OWING.

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

Собрав буквы, мы можем увидеть, что есть 7 D, 6 Us, 3 G, 3 Is, 2 W, 2 H, 1 B, 1 F, 1 P и 1 M. Если мы переключим нашу стратегию на в первую очередь нацеливание на эти буквы, даже если нам приходится тратить место на ранее использованную букву, тогда наша скорость разбиения значительно возрастает.

Слово ВЛАЖНЫЙ в этом случае имеет все 5 этих букв и скорость разбиения 89% (чуть более 3-х бит информации), и это все, что нам нужно, чтобы перейти к последнему слову: HOUND.

Следуя этому маршруту, в среднем у нас есть 40% шанс разгадать слово за 3 попытки и 90% шанс решить его за 4. Все головоломки можно выиграть, и только 12 слов требуют полных 6 попыток. Общее среднее значение этого метода составляет 3,676 догадок на слово.

Надеюсь, гистограммы здесь ясно показывают, что второй метод значительно снизил верхнюю часть распределения.

Нахождение нижней границы возможного

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

Тем не менее, я должен был учитывать удачу, иначе кратчайший путь к слову был бы просто угадыванием целевого слова за 1 раз каждый раз, и это было бы неинтересно. Но как избежать удачи?

Для этого я решил, что допустимое решение должно соответствовать следующим условиям:

  1. Каждый раз он будет начинаться с одного и того же слова, в данном случае SLATE.
  2. Он никогда не приземлится на правильный ответ преждевременно. Этот метод не будет угадывать слово из списка ответов, пока этот список не будет сокращен до одного возможного ответа. Мы хотим угадать ответ только после того, как разделим все остальные возможности. Наша окончательная догадка должна быть достоверной на 100 %.

Эти строгие условия отлично подходят для всех слов, кроме 8. Для таких слов, как TRUSS и TRUST, доступные слова-угадывания закончатся до того, как список ответов достигнет 1. Это естественно, если вы понимаете, что оба слова пишутся одними и теми же 4 буквами. В какой-то момент угадывание новых слов не помогает, и ему приходится выбирать одно из оставшихся двух слов. Другими парами слов, подобными этой, являются ПАНЕЛЬ / УГОЛОВНЫЙ, НЕПОДВИЖНЫЙ / СТИЛЬТ и БЕЗ ОСВЕЩЕНИЯ / ДО.

Вот результаты:

Подавляющее количество слов можно разгадать всего за 3 попытки. Среднее количество догадок составляет 3,003. Хотя я сделал все возможное, чтобы учесть удачные ответы, я признаю, что каждый выбор, сделанный между первым предположением и окончательным ответом, не совсем оптимален статистически на основе частоты букв или скорости разбиения.

Тем не менее, довольно поразительно осознавать, насколько короткими являются пути большинства слов.

Давайте рассмотрим пример, используя целевое слово MEALY, которое имеет путь SLATE›GORMY›MEALY.

  • После угадывания SLATE есть 1 зеленая {A}, 3 желтых {E,L} и 2 серые буквы {M,Y} . Это одно предположение оставляет только 8 возможных ответов. 2307 слов пропали просто так!
  • После угадывания GORMY остается еще 1 зеленый {Y}, еще 1 желтый {M} и еще 3 серых {G,O,R}. Это оставляет только 1 возможный ответ: MEALY.

Хорошо, это было легко. Давайте попробуем наихудшую цель для SLATE с точки зрения 1-го предположения. Это будет КРОНИ.

  • После угадывания SLATE есть 0 зеленых, 0 желтых и 5 серых букв{C,N,O,R,Y}. Осталось еще 221 слово, что не очень хорошо.
  • Следующим предположением будет YCORD, для которого есть 2 зеленых {O,N}, 2 желтых {C,Y} и 1 серая буква {R}. Это все, что нужно, чтобы отфильтровать ответы до CRONY.

Для 5 слов, которые требуют 5 догадок, вот пути их слов:

  • SLATE›BUMPH›ZINCO›WATER›EATER
  • СЛАНЕЦ›ЗИКР›ФОГОУ›ПАНЕЛЬ›ПЕНАЛ
  • SLATE›DHOBI›MUZZY›SPILT›STILL
  • SLATE›YUCCH›POORI›TRUST›ФЕРМА
  • SLATE›VUGGY›HUMBO›БЕЗ ГОРЕНИЯ›ДО

Все идеи в этом посте были получены из моей работы над следующими проектами: