Частотное распределение слов и расположение их символов может дать больше информации, которая поможет оптимизировать поиск правильных ответов.
Как и у большинства из вас, моя лента в социальных сетях недавно была заполнена странными зелеными, черными и желтыми квадратами с оценками Wordle. Сначала я понятия не имел, что это такое, но непрерывные потоки этого сделали меня достаточно любопытным, чтобы узнать, о чем идет речь.
Узнав об игре, это простой поворот к игре Mastermind, в которую мы играли в детстве. И следуя своей привычке терять друзей из-за систематизации ленивых решений игр (вы, наверное, помните, что я уже испортил некоторым игру в судоку), я решил проанализировать, существует ли эффективный способ угадывания, основанный на статистических измерениях.
В этой игре поле поиска состоит из английских слов длиной 5 символов. Возможно, вы уже знаете, что есть некоторые сайты, которые углубились в исходные коды Wordle и нашли использованный список слов. Для моего подхода я сохранил его в общем списке английских слов, используя инструментарий NLTK. Единственным недостатком этого подхода является то, что некоторые слова с высокой вероятностью могут быть отклонены, и вместо этого вам придется выбирать из списка рекомендуемых слов.
Первоначальный наивный подход кажется простым. Разбейте список слов на его символы и выполните простой анализ частотного распределения вхождений.
Глядя на диаграмму выше, 5 самых часто встречающихся алфавитов будут «a», «e», «s», «o», «r». И сразу же можно было бы подумать о слове «возник» как о подходящем слове для попытки.
Но этот наивный подход игнорирует позиции символов, а вместо этого только агрегирует подсчет по всему корпусу. Что, если мы вычислим частоты на основе каждой из 5 возможных позиций? Как видно из таблицы ниже, распределения различаются, как и следовало ожидать.
Например, самое распространенное 5-символьное слово начинается с «s» с распределением около 11,4%, в то время как «a» является наиболее распространенным вторым символом с 18%-м распределением среди всех 5-символьных слов.
Таким образом, альтернативный подход, который мы могли бы попробовать, будет следующим:
- вычислить распределения по каждой из позиций
- выберите позицию и символ с наибольшей частотой (например, в приведенном выше распределении мы видим, что «s» в последней позиции набирает наибольшее количество баллов — 19,8%)
- Отфильтруйте список слов как апостериорный при условии, что один из символов был заблокирован
- Повторите частотное распределение для оставшихся 4 позиций и выбор
Используя этот подход, приведенный выше анализ предполагает, что лучшим словом для начала в списке words_alpha будет слово «голые». Если бы он был загружен с использованием списка слов Wordle, полученного из исходного кода, вместо него было бы слово «специя».
Вы могли заметить, что я также пытался использовать слова с 5 уникальными символами в первых нескольких предположениях. Это увеличивает наши шансы на более быстрое сужение пространства поиска, а также позволяет избежать некоторых ошибочных реализаций, в которых повторяющиеся символы помечались непоследовательно (я еще не проверял это подробно).
После того, как каждое слово представлено как предположение, описанный выше подход просто повторяется путем пропускания списка слов через процесс фильтрации на основе:
- Известно, что персонажи занимают правильные позиции
- Персонажи, которых нет в слове
- Символы в неправильных местах (должны появиться, но не в том положении, в котором пробовали)
Затем процесс распределения частот повторяется до тех пор, пока головоломка не будет решена.
Заключение
В наших повседневных задачах мы часто могли решать проблемы методом грубой силы, который не всегда является самым эффективным или даже эффективным, если есть ограничения, ограничивающие нашу способность исчерпать все пространство поиска. В этом примере мы ограничены 6 попытками в нашем пространстве поиска, содержащем почти 10 тысяч слов для начала.
Этот анализ показывает, как мы могли бы использовать данные и логику, в данном случае частотное распределение букв лучше, чем случайное предположение. Используя такие дистрибутивы, мы можем значительно сузить пространство поиска с помощью некоторого Python и статистики.
Я надеюсь, что это вызвало некоторые идеи о том, как решать некоторые повседневные проблемы (или, в данном случае, весело, извините) с использованием данных и логики.
Код можно найти здесь — правда, это не производственный уровень, просто то, что работает для удовольствия.
