В Wordle принято начинать с «хороших» слов – с частыми гласными и согласными. Однако анализ показывает, что менее очевидные варианты иногда дают больше информации. Возникает простой, но неудобный вопрос, можно ли доказать, что одно стартовое слово лучше другого. Краткий ответ – да. Я рассмотрел Wordle как задачу теории информации и количественно оценил каждый ход, используя Excel и официальный словарь игры. Эту статью я публикую в блоге ЛАНИТ, чтобы обсудить полученные результаты с техническим сообществом.
Что такое Wordle и почему это интереснее, чем кажется
В Wordle загадывают слово из пяти букв (возможны повторы), и у игрока есть шесть попыток, чтобы его угадать. Результат хода – изменение цвета букв: зеленые – буквы угаданы точно, желтые – присутствуют в слове, но стоят не на своих местах, серые – нет в загаданном слове.
Вопрос приводит к десяткам различных ответов, и каждый из них по-разному сужает круг возможных слов. Поэтому Wordle интересен не только как игра со словами, но и как аналитическая задача. Значит, можно рассмотреть Wordle не как угадывание, а как последовательность информационных запросов.
Как обычно играют в Wordle и почему это разумно
Большинство игроков начинают со слова, в котором много «частых» букв без повторов, чтобы за один ход проверить как можно больше символов. На полном корпусе русского языка таким словом оказывается «осина».
Любопытный обмен мнениями состоялся в комментариях к заметке Wordle или как выиграть за 6 ходов. Сначала предложили «осина», потом «камин», и в какой-то момент загадочный «кроат».
Частотный анализ вполне хорош, но он не учитывает позиции букв и разбиение ответов на паттерны.
Если ход в Wordle – это вопрос, то сколько информации в среднем дает ответ на него? И можно ли измерить это так, чтобы сравнивать разные слова не на уровне ощущений, а формально? Именно здесь частотная интуиция упирается в свой предел, и появляется необходимость в более строгой мере. В теории информации для этого уже давно существует подходящий инструмент. Однако прежде, чем перейти к нему, важно разобраться с базой слов, чтобы анализировать не абстрактный словарь, а реальный, используемый в игре.
Словари Wordle: вопросы и загаданные слова
В части статей и разборов Wordle используется список слов, скачанный с GitHub или собранный вручную. Это позволяет провести анализ, но оставляет его приблизительным, так как база слов не соответствует конкретной реализации игры.
Поскольку я интересовался русской версией с доступным словарем, то остановил свой выбор на https://wordly.org/ru. Чтобы скачать словарь, перейдите на сайт, нажмите F12. В окне Developer Tools (Инструменты разработчика браузера) перейдите на вкладку Network, поставьте галочку Preserve log, нажмите кнопку 🚫 (Очистить) в левом верхнем углу Network, обновите страницу (Ctrl+Shift+R), установите фильтр json:
Оказалось, что wordly.org использует два словаря:
dictionary – слова, которые можно вводить как попытку (более 4000);
targets – слова, которые могут быть загаданы в игре (около 600).
Далее я буду называть эти словари соответственно Allowed (Dictionary) и Answers (Targets). Игрок задает вопросы из первого множества, а информацию получает о втором. Словарь Allowed используется для валидации ввода, а Answers – для генерации загадки.
Чтобы получить URL словаря, дважды кликните на нем в столбце Name. В новой вкладке браузера откроется страница словаря. Например, для Answers это https://wordly.org/files/wordle/ru/targets.json?v45.12. Для скачивания словарей я воспользовался Power Query в Excel 365. Код для Answers:
let Url = "https://wordly.org/files/wordle/ru/targets.json", Raw = Web.Contents(Url), Json = Json.Document(Raw), // если это просто список слов WordsList = if Value.Is(Json, type list) then Json else error "Неожиданная структура JSON", Tbl = Table.FromList(WordsList, Splitter.SplitByNothing(), {"Word"}), // некоторые слова начинаются с прописной, поэтому приводим к нижнему регистру Lower = Table.TransformColumns(Tbl, {{"Word", Text.Lower, type text}}), // фильтр: ровно 5 букв Len5 = Table.SelectRows(Lower, each Text.Length([Word]) = 5), #"Сортированные строки" = Table.Sort(Len5,{{"Word", Order.Ascending}}), // странно, но словари содержали дубли #"Удаленные дубликаты" = Table.Distinct(#"Сортированные строки") in #"Удаленные дубликаты"
На момент публикации заметки использовалась версия словаря 45.12. При обновлении версии код отработает корректно.
Зачем здесь энтропия, и что именно она измеряет
Если посмотреть на Wordle с математической точки зрения, каждый ход в игре – это вопрос, а каждый ответ – паттерн B/Y/G: какие буквы совпали по позиции (G), какие присутствуют (Y), а какие отсутствуют вовсе (B). Именно этот паттерн и несет информацию.
Любой выбранный ход из Allowed разбивает все возможные слова из Answers на группы: по одному набору слов на каждый возможный паттерн ответа. Поскольку вероятности встретить одно из слов Answers одинаковы, вероятность ответа зависит только от числа слов, отвечающих паттерну.
Хороший ход в Wordle – слово, которое в среднем как можно сильнее сокращает неопределенность. Здесь возникает ключевой вопрос, как измерить это сокращение количественно.
В теории информации существует стандартная мера – энтропия Шеннона. Она измеряет ожидаемое количество информации, которое мы получаем, наблюдая результат случайного события. Если возможные исходы равновероятны, энтропия максимальна. Если какие-то ответы существенно более вероятны, информации мало.
В контексте Wordle это означает следующее. Для выбранного слова мы можем перечислить все возможные паттерны ответа и посчитать, сколько слов приводит к каждому из них. Это распределение вероятностей и есть результат нашего «вопроса». Энтропия этого распределения показывает, сколько информации мы в среднем получим, сделав ход.
Энтропия позволяет сравнивать ходы между собой. Если энтропия одного слова выше, чем у другого, это означает, что в среднем оно сильнее сокращает неопределенность. Посмотрите на распределение слов по паттернам ответов для двух первых вопросов.
Обратите внимание: «норка» дает больше вариантов ответов (больше значений по оси Х), и они распределены более равномерно, а максимум существенно ниже.
По определению энтропия
где: H − энтропия (в битах), pi – вероятность i-го исхода, n – число возможных исходов.
Интуитивная интерпретация: если все исходы равновероятны, энтропия максимальна; если существует всего один исход, энтропия равна нулю (ответ на вопрос не дает новой информации). Энтропия показывает ожидаемое количество информации.
В контексте Wordle:
исходы – это возможные паттерны ответа (G/Y/B);
pi – доля слов из словаря ответов (Answers), дающих данный паттерн;
энтропия измеряет, насколько хорошо выбранное слово в среднем сокращает неопределенность о загаданном слове.
От слов к битам: реализация в Excel
Чтобы удобно считать энтропию, я написал несколько функций в Excel на основе LAMBDA (не без помощи ИИ). Вы их также найдете в приложенном Excel-файле.
CHARS5
Преобразует строку – слово из 5 букв – в массив из 5 букв.
=LAMBDA(w;ПСТР(w;ПОСЛЕД(5);1))
W_PATTERN
Реализует правило ответа Wordle. Для заданных слов guess (вопрос) и target (одно из загаданных слов) возвращает строковый паттерн из символов G, Y и B, соответствующий зеленым, желтым и серым клеткам. Функция корректно обрабатывает повторяющиеся буквы и полностью воспроизводит официальную логику Wordle.
=LAMBDA(guess;target; LET( g; CHARS5(guess); t; CHARS5(target); gr; g=t; rem0; ОБЪЕДИНИТЬ("";ИСТИНА; ФИЛЬТР(t; НЕ(gr);"")); state; REDUCE( ГСТОЛБИК(""; rem0); ПОСЛЕД(5); LAMBDA(a;i; LET( pat; ИНДЕКС(a;1;1); rem; ИНДЕКС(a;1;2); ch; ИНДЕКС(g;i); ЕСЛИ(ИНДЕКС(gr;i); ГСТОЛБИК(pat & "G"; rem); LET( pos; ЕСЛИОШИБКА(НАЙТИ(ch;rem);0); ЕСЛИ(pos>0; ГСТОЛБИК(pat & "Y"; ЗАМЕНИТЬ(rem;pos;1;"")); ГСТОЛБИК(pat & "B"; rem) ) ) ) ) ) ); ИНДЕКС(state;1) ) )
ENTROPY_W
Вычисляет энтропию для хода guess относительно заданного множества возможных ответов Universe. Для каждого слова из переданного множества возможных загаданных слов функция строит паттерн ответа, группирует одинаковые паттерны, вычисляет их вероятности и считает энтропию распределения. Возвращает среднее количество информации (в битах), которое дает конкретный ход Wordle.
=LAMBDA(guess; Universe; LET( codes; MAP(Universe; LAMBDA(w; W_PATTERN(guess; w))); u; УНИК(codes); cnt; MAP(u; LAMBDA(pat; СУММ(--(codes=pat)))); n; ЧСТРОК(Universe); p; cnt / n; -СУММ(p * LOG(p; 2)) ) )
FILTER_BY_PATTERN
Возвращает все слова из списка Words, которые в ответ на ход guess дают pattern
=LAMBDA(Words;guess;pattern; FILTER(Words; MAP(Words; LAMBDA(w; W_PATTERN(guess; w)=pattern)) ) )
Оптимальный первый вопрос: «норка» бьет «кроат»
Откуда вообще взялся этот загадочный «кроат»? Я думаю, что это следствие его первого места в буквенно-частотной иерархии валидных вопросов:
Словарь Answers содержит 602 слова. Вероятность каждого из них быть загаданным одинакова. Таким образом, энтропия (неопределенность) в начале игры.
H0 = log2 602 = 9,23 бит
Хороший первый вопрос сокращает неопределенность более чем на 5,5 бит:
«Кроат» оказывается неплохим частотным словом, но с точки зрения информации – неоптимальным.
Еще один любопытный подход описан в комментарии к ранее упомянутой статье Wordle или как выиграть за 6 ходов. Евгений (Xneg) предложил алгоритм минимакса: для каждого слова-вопроса на массиве загаданных слов найти паттерн с максимально возможным числом ответов, выбрать слово–вопрос, для которого этот максимум минимален. Соответственно, даже при худшем раскладе такой вопрос максимально уменьшит выборку доступных слов. Сравнение с энтропийным подходом показывает, что минимакс весьма близок к оптимуму.
Итак, в среднем «норка» дает 5,69 бит информации. И средняя неопределенность после этого хода составит 9,23 – 5,69 = 3,54 бит. «Норка» позволит в среднем выигрывать за меньшее число ходов, чем любой иной первый вопрос. В худшем случае останется паттерн с 43 валидными словами, что составляет 5,43 бит неопределенности.
Любопытно, что аналогичный подход обсуждается и в статье Большой обзор стратегий решения для Wordle и подобных игр. Из нескольких рассмотренных стратегий наилучшие результаты показала стратегия максимальной энтропии – ровно та, к которой приводит формализация Wordle как информационной задачи.
Второй вопрос: адаптировать или подобрать заранее?
Некоторые решатели используют три или даже четыре заранее выбранных слова с максимальным покрытием букв. Такой подход очевидно не является оптимальным. Хотя это зависит от того, что понимать под оптимумом. Если цель – выигрыш за шесть ходов, то вполне себе рабочий вариант. Если же вы стремитесь угадывать за 3–4 вопроса, то вам нужно что-то более информационно насыщенное.
Я отсортировал паттерны ответов на первый вопрос «норка» по вероятности:
Для разработки стратегии второго хода я проанализировал, какие вторые вопросы дают максимум информации для нескольких наиболее вероятных паттернов. Меня интересовало, следует ли выбирать второй вопрос так, чтобы ответом могло быть загаданное слово, или лучше по максимуму задействовать новые буквы.
Код функции в ячейке В2 на рис. 11:
=LET( guess1; $A$1; pat; B1; Cand; FILTER_BY_PATTERN(Targets[Word]; guess1; pat); CandTwo; FILTER_BY_PATTERN(Words[Word]; guess1; pat); ent; MAP(Words[Word]; LAMBDA(g; ЕСЛИОШИБКА(ENTROPY_W(g; Cand); -1))); data; ГСТОЛБИК(Words[Word]; ent); sorted; СОРТ(data; 2; -1); top; ВЫБОРСТОЛБЦ(sorted; 1; 2); topFive; ВЗЯТЬ(top; 5); topWords; ВЫБОРСТОЛБЦ(topFive; 1); topEnt; ВЫБОРСТОЛБЦ(topFive; 2); canBeGGGGG; MAP( topWords; LAMBDA(w; НЕ(ЕОШИБКА(ПОИСКПОЗ(w; CandTwo; 0)))) ); ГСТОЛБИК(topWords; topEnt; canBeGGGGG) )
ИСТИНА означает, что ответ может вернуть GGGGG, ЛОЖЬ – нет. Видно, что для большинства паттернов лучшие вторые вопросы не могут быть загаданным словом. Как говорится, «ничего личного, только максимум информации».
Пока я разбирался с энтропией, словарями и формулами, получилось наиграть такую статистику.
Что еще?
Если вам понравился метод, можете исследовать реализацию игры Т-Банка. Словарь Allowed можно скачать отсюда. Словарь Answers не обнаружил.
Буду признателен за комментарии. Делитесь вашими идеями.
