Математика букв: Wordle и теория информации

Что общего между кроссвордом, тетрисом и пазлом? Все они являются играми-головоломками, которые заставляют игрока шевелить извилинами. Какие-то головоломки построены на применении внимания и усидчивости, какие-то тестируют знания и память, какие-то заставляют формировать стратегию. Но есть и такие, что кажутся на первый взгляд весьма случайными и полагающимися больше на удачу, нежели на точный расчет. К таким относиться Wordle — головоломка, в которой необходимо угадать слово из 5 букв за 6 попыток. Ученые из Бингемтонского университета (Вестал, штат Нью-Йорк, США), используя теорию информации, разработали стратегию для игры в Wordle, которая позволяет «угадывать» слова с точностью 99%. В чем секрет данной стратегии и насколько она сложна? Ответы на эти вопросы мы найдем в докладе ученых.

Основа исследования

Wordle — популярная онлайн-игра, разработанная Джошем Вордлом (Josh Wardle), в которой игроки пытаются угадать секретное слово из 5 букв, делая предположения. Для победы у игроков есть 6 попыток. После каждой попытки игроки получают обратную связь, указывающую, какие буквы отсутствуют в слове (выделены серым цветом), какие буквы присутствуют, но неправильно расположены (выделены желтым цветом), и какие буквы одновременно правильные и находятся на своих местах (выделены зеленым цветом). Используя эту информацию, игроки уточняют свои предположения, исключая неверные варианты и выбирая новые возможности для последующих попыток.

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

Изображение №1

Игра начинается с пустой сетки 6×5, как показано выше, где игроки выбирают начальное слово в качестве своей первой догадки. После отправки догадки игра выделяет буквы, как описано ранее, чтобы дать игроку подсказки. Например, если секретное слово — «plant», а игра ведется по слову «slate», то буквы слова «slate» будут выделены следующим образом: серый; зеленый; зеленый; желтый; серый. Здесь буквы S и E выделены серым цветом, потому что их нет в секретном слове. Буквы L и A выделены зеленым цветом, поскольку они есть в секретном слове и расположены правильно. Буква T выделена желтым цветом, потому что она есть в секретном слове, но находится в неправильном положении. Тщательное изучение выделенных букв позволяет игроку исключить потенциально неверные слова, в конечном итоге уменьшая пространство поиска.

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

В 1948 году Клод Шеннон опубликовал статью под названием «Математическая теория коммуникации» («A Mathematical Theory of Communication»). В ней была представлена возможность рассматривать информацию как четко определенную и измеримую величину. Информация устанавливает определенные, непреодолимые пределы того, сколько именно информации может быть передано между любыми двумя компонентами любой системы.

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

Если X — случайная величина, то информацию и энтропию, показанные в уравнениях 1 и 2, можно определить соответственно следующим образом:

где P [. . .] обозначает вероятность, а E [. . .] — математическое ожидание. Кроме того, учеными было принято 0log₂(0) = 0.

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

Данные

Wordle — это ежедневная головоломка, в которой каждый день в течение года предлагается одно уникальное секретное слово. В словаре Wordle содержится 12972 допустимых пятибуквенных слова, из которых 2315 слов являются кандидатами для ежедневных головоломок. Копия этих 12972 слов была получена и предоставлена авторами Wordle в свободном доступе в интернете.

Изображение №2

Выше показано распределение слов по уникальным буквам. Например, количество уникальных слов, содержащих букву «а», составляет 912. График показывает, что большинство пятибуквенных слов содержат хотя бы одну букву «е». Слова с повторяющимися буквами, такие как «steel», учитываются только один раз для каждой буквы (в данном случае буквы «е»).

Этот график пригодится позже, когда будет обсуждаться стратегия игры, основанная на распределении букв для выбора слова в качестве предположения. В целом, большинство слов состоят из букв «а», «е» и «р». Напротив, меньше слов содержат буквы «j», «q», «x» и «z». Сумма количества слов, в которых встречаются буквы от «а» до «z», не составит 12972, поскольку слова могут попадать в несколько буквенных категорий (например, слово «abode» попадает в 5 буквенных категорий).

Изображение №3

Также был рассмотрен относительный процент слов по количеству уникальных букв, и было замечено, что чуть менее 70% слов содержат пять уникальных букв, как показано выше. По мере уменьшения количества уникальных букв наблюдается значительное снижение относительного процента слов.

Методология

Как говорилось ранее, после начала игры в Wordle используется цветовая подсветка, чтобы обозначить, принадлежат ли буквы угаданного слова к секретному слову. В частности, были описаны три различных состояния, которые может принимать буква при каждом произнесении слова: «серый», «желтый» и «зеленый». Поскольку существует пять позиций, каждая из которых принимает три различных состояния, в конечном итоге для каждого произнесенного слова существует 243 возможных состояния букв, как показано на ниже.

Изображение №4

Изображение №5

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

Пусть «Слова» — это множество из 12972 пятибуквенных слов, а ∼ обозначает, что слово w соответствует шаблону s.

Уравнение выше дает вероятность для каждого состояния буквы для данного слова. Таким образом, будет 243 вероятности, сумма которых равна 1. Если вероятности отсортировать в порядке возрастания, распределение вероятностей можно проиллюстрировать, как показано ниже.

Изображение №6

Ось x на графике обозначает состояние буквы, а ось y — вероятность появления этого состояния буквы. Сортировка вероятностей в порядке возрастания — произвольное решение, и оно не меняет интерпретацию. Ученые отмечают, что некоторые состояния будут иметь очень низкую вероятность, в то время как другие будут относительно выше. Ярким примером состояния буквы с чрезвычайно низкой вероятностью будет состояние буквы, состоящей из всех «зеленых» выделенных букв; в этом конкретном примере должно быть только 1 слово, соответствующее такому шаблону, следовательно, вероятность будет 1/12972. Ярким примером состояния буквы с относительно высокой вероятностью будет состояние буквы, состоящей из всех «серых» выделенных букв.

Далее было вычислено информационное содержание для каждого возможного варианта исхода буквенного состояния при угадывании. Здесь «информация» (в битах) измеряет, насколько уменьшается неопределенность при наблюдении конкретного исхода. Анализ всех серых букв в исходе выявляет важные данные, поскольку исключает из рассмотрения множество потенциальных решений. Используя определение информации (уравнение №1) для каждого исхода s:

Энтропия H(S) предположения представляет собой ожидаемую информацию по всем возможным исходам. Этот результат следует из:

где S включает в себя все возможные варианты расположения букв при угадывании слова, в Wordle таких результатов 243. Угадывание конкретного слова раскрывает определенное количество информации, которое можно ожидать; это ожидание измеряется в битах.

Буквальное толкование энтропии — это ожидаемое количество битов, полученных при произнесении соответствующего слова. Термин «ожидаемое» относится к статистическому ожиданию, он не подразумевает, что будет получено именно это количество информации. Фактическое количество полученной информации зависит от состояния букв, выделенных Wordle после произнесения слова; на этом этапе будет известно, к какому из 243 возможных состояний букв привело угаданное слово. Причина, по которой это нельзя узнать заранее, заключается в том, что секретное слово действительно является секретом, и игра не дает никаких предварительных подсказок о секретном слове; его можно найти только путем произнесения слов.

Изображение №7

Для более полного понимания распределения вероятностей состояний букв для данного слова были выбраны два случайных слова: «audio» и «tares», и наложены их распределения вероятностей, как показано выше. Стоит отметить, что распределение вероятностей для слова «audio» имеет большую высоту, чем для слова «tares». Поскольку информация обратно пропорциональна вероятности, распределение показывает, что более высокая информация имеет меньшую вероятность и наоборот. Следовательно, выбирая слова с более высоким ожидаемым уровнем информации (т.е. энтропией), мы сталкиваемся с более редкими ситуациями и получаем значительно больше информации.

Изображение №8

После того как была известна энтропия для каждого из 12972 слов, слова были отсортированы в порядке убывания таким образом, чтобы слово с самой высокой энтропией имело наивысшее значение. Это слово содержит наибольшее количество ожидаемой информации, которую можно получить, используя это слово. Фрагмент с 10 словами с самой высокой энтропией, полученный на основе вычислений, показан выше.

Стратегию игры можно кратко описать следующим образом:

• Выбираем и разыгрываем слово с наибольшей энтропией в качестве первой попытки (например, «tares»). Затем Wordle сообщит буквенные состояния этого слова (например, «зеленый», «серый», «серый», «желтый», «серый»);

• Используя буквенное состояние, сообщенное Wordle, получаем все слова, соответствующие этому буквенному состоянию для сыгранного слова. Стоит помнить, что были рассчитаны вероятности 243 буквенных состояний для каждого из 12972 слов. Также были сохранены слова, соответствующие этим буквенным состояниям. Таким образом, в этом примере получается список слов для «tares», соответствующих состояниям: «зеленый», «серый», «серый», «желтый», «серый»;

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

• Продолжаем эту схему до конца игры (то есть, пока не найдем секретное слово или не исчерпаем все шесть попыток).

Изображение №9

Изображение №10

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

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

• Выбираем и разыгрываем любое слово, содержащее буквы «a», «e» и «r», поскольку эти буквы присутствуют в большинстве слов из списка 12972 слов. По совпадению, «tares» — пример такого слова. Затем Wordle сообщает состояния букв (например, «зеленый», «серый», «серый», «желтый», «серый»).

• Собираем буквы, которые отмечены как «зеленый» и «yello желтый w» как обязательные, и буквы, отмеченные как «серый» как необязательные. Если количество обязательных букв меньше пяти, выбираем любое слово, содержащее текущий набор обязательных букв, не содержащее ни одной необязательной буквы и содержащее букву, не входящую ни в список обязательных, ни в список необязательных букв, которая имеет следующую по частоте встречаемости в слове.

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

Изображение №11

Выше представлен пример работы такой стратегии, когда начальной догадкой было слово «tares», а секретное слово было «crypt». Игра была выиграна за четыре попытки.

Результаты исследования

Изображение №12

Метод, основанный на энтропии, был оценен в сравнении с базовым методом распределения букв. Это было проверено двумя способами.

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

Было проведено исчерпывающее моделирование с использованием всех 2315 возможных слов-решений Wordle в качестве секретных слов. Игра проводилась с каждым секретным словом, и для угадывания слова использовались обе стратегии. Для обеих стратегий каждый раз использовалась одна и та же первая попытка — «tares», слово с наивысшей энтропией, и игра продолжалась до тех пор, пока слово не было найдено или не было исчерпано шесть попыток. Затем подсчитывалось количество попыток, сделанных каждой стратегией, и каждая игра отмечалась как победа или поражение. Результаты затем анализировались для оценки эффективности в разных играх (графики ниже).

Изображение №13/№14

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

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

Стратегия игры, основанная на угадывании букв, может попасть в замкнутый круг, если несколько слов содержат одни и те же пять букв. В качестве примера рассмотрим буквы слова «stale». Эта стратегия может застрять на одном из следующих слов: «least», «stale», «slate» или «steal». Хотя стратегия игры, основанная на энтропии, имеет высокий процент побед в среднем, она не выигрывает каждую игру в 100% случаев.

Для более детального ознакомления с нюансами исследования рекомендую заглянуть в доклад ученых.

Эпилог

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

Wordle — это одна из самых популярных головоломок в мире. Суть игры довольно проста: необходимо угадать слово из 5 букв. Во время угадывания буквы предложенного слова отмечаются определенным цветом: серый — буквы нет в секретном слове; желтый — буква есть, но ее положение неверно; зеленый — букв есть и ее положение верно. У игрока есть 6 попыток, чтобы угадать секретное слово.

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

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

Для оценки разработанной методики ученые сравнили ее с более традиционной стратегией Wordle, которая делает акцент на часто используемых буквах (например, «A», «E», «R»). В компьютерных симуляциях метод, основанный на теории информации, успешно решил 99% головоломок Wordle. Традиционный подход решил около 90%.

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

Немного рекламы

Спасибо, что остаетесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Maincubes Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 - 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB - от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?