Поклонники Wordle: этот пост в блоге ответит на этот вопрос.
Введение
Wordle — это ежедневная игра [1]. Каждый день есть общее слово из 5 букв, которое каждый должен открыть для себя. Вам дается 6 попыток. Для каждой попытки вам необходимо ввести 5-буквенное английское слово. После каждого предположения для каждой буквы вы знаете, появляются ли они и в нужном месте (зеленые), появляются, но не в том месте (желтые) или не появляются (серые). Цель состоит в том, чтобы угадать слово за наименьшее количество попыток.
Теперь я уверен, что все поклонники Wordle и поклонники должны спросить себя, с какого слова лучше всего начать, и какова лучшая стратегия игры. Чтобы ответить на эти вопросы, я использовал английские слова в NLTK [2]. Английский словарь NLTK состоит из 236 736 слов. Сначала я отфильтровал только слова длиной пять, и у меня осталось 10 422 слова. Это наше пространство поиска.
Начнем с простого
Чтобы ответить на первый вопрос, с каким словом лучше начать игру, я решил начать с этой простой эвристики: допустим, я ищу слово, которое даст мне максимальное количество «желтых» квадратов (правда, но в не в том месте) и внутри них хочу тот, который максимально увеличит «зеленые» квадраты (правда в нужном месте). Конечно, это военно-морской подход, но давайте начнем с него.
Мы хотим выбирать слова на основе наиболее часто встречающихся букв в пятибуквенных словах английского языка. Основываясь на принципе MLE, давайте воспользуемся нашим набором данных для подсчета букв:
Из этого распределения мы узнаем, что, начиная со слов, содержащих символы: «а», «е», «р», «о», «с», с наибольшей вероятностью выпадают «желтые» квадраты (верно, но не в том месте). ). Давайте поищем в нашем словаре возможные слова, содержащие все эти пять букв:
arose oreas
Теперь предположим, что мы хотим выбрать из двух слов слово, которое будет иметь наибольшую вероятность для «зеленых» (истинных в нужном месте) квадратов. Мы снова воспользуемся принципом MLE для p (буква | позиция) и подсчитаем частоту появления буквы в определенной позиции на основе словарного запаса из 5 букв. Позже мы нормализуем количество каждой буквы, чтобы получить вероятность.
Давайте построим тепловую карту расположения каждой из пяти букв:
давайте предположим, что буквы являются i.i.d, учитывая их место и определение, и что у нас нет окончательного словаря. Мы можем рассказать эту порождающую историю. Слово из пяти букв генерируется с учетом следующего:
p(слово из пяти букв с 'a', 'e', 'r', 'o', 's') = p(буква|позиция=0)*p(буква|позиция=1)*p(буква|позиция =2)*p(буква|позиция=3)*p(буква|позиция=4)
p('возникла') = 0,0004
p('руда') = 0,000007
p('возник)›p('ореи')
В соответствии с этой простой эвристикой я рекомендую начинать игру со слова возникла.
Можем ли мы сделать лучше?
Обратите внимание, что наша эвристика разделила частоту букв («желтые») и порядок букв («зеленые») на два последовательных шага, что явно неоптимально. Давайте теперь попробуем смоделировать «зеленый», «желтый» и «серый» вместе. Помните, что мы хотим выбрать слово, которое поможет нам уменьшить неопределенность и, следовательно, минимизировать энтропию. Но как мы будем вычислять энтропию каждого слова?
Мы можем думать об ответе Wordle на наше предположение как о дереве глубины 5 + 1. Каждый уровень соответствует положению буквы в слове, и каждый узел разбит на три: «зеленый», «желтый», «серый». ” согласно возможным результатам Wordle. Это приводит к 3⁵ листьям на дереве. Каждая ветвь представляет собой ответ Wordle на наше предположение.
Для каждого предположения мы можем подсчитать в каждой ветви возможные английские слова, соответствующие правилам. Для каждого листа мы вычисляем вероятность, спрашивая, сколько слов следует правилу пути, деленное на общее количество слов (10 422), обратите внимание, что вероятность листьев должна равняться единице.
Давайте удостоверимся, что вы все следите. На этой диаграмме самый правый лист всегда будет иметь только одно слово из 5 точных совпадений, следовательно, вероятность 1/10442, а самый левый лист будет иметь все возможные слова без пяти букв в нашем предположении, деленные на общее количество слов.
Теперь мы можем запустить эти деревья распределения для всех наших пятибуквенных слов (10 422) и вычислить энтропию каждого слова, рассчитав энтропию листьев, слово с наименьшей энтропией даст нам наилучшее слово, чтобы начать игру.
Этот метод можно легко расширить до метода построения деревьев условной вероятности на основе предыдущих предположений.
Использованная литература:
[1] Wordle Game — https://www.powerlanguage.co.uk/wordle/
[2] Bird, Steven, Edward Loper and Ewan Klein (2009),Natural Обработка языка с помощью Python. О'Рейли Медиа Инк.
