Подсказка сужает поиск, но не всегда приближает победу. На примерах Wordle и Mastermind разберём, как измерить информацию, выбрать момент помощи и отличить среднее число попыток от гарантии. Основатель «Школы траблшутеров» Олег Брагинский и Антон Бессарабов объясняют, как проверить бюджет бит на реальной игре.
Рис. 1. Между знанием ответа и победой остаётся ход
Бит как единица незнания
Клод Шеннон в работе A Mathematical Theory of Communication, опубликованной в 1948 году в Bell System Technical Journal, предложил энтропию как меру неопределённости. Для исходов с вероятностями pᵢ она равна H = −Σ pᵢ log₂ pᵢ; слагаемое при нулевой вероятности принимают равным нулю.
При N равновероятных вариантах остаётся H = log₂ N. Для 2’315 ответов Wordle это 11,18 бита, для 6⁴ = 1’296 кодов Mastermind – 10,34. Двадцать вопросов с ответами «да» или «нет» различают не более 2²⁰ = 1’048’576 вариантов: миллион требует двадцати ответов, но содержит около 19,93 бита.
Рис. 2. Миллион загадок помещается в двадцать двоичных развилок
Один бит снимается идеальным двоичным вопросом, который делит равновероятный остаток пополам. Энтропия зависит от распределения вероятностей: знакомое слово и редкий термин не обязаны иметь одинаковый вес. Размер списка сам по себе ещё не описывает знания игрока. Если ответ уже известен, его неопределённость равна нулю.
Расчёт задаёт модель неопределённости, а не возможности человеческой памяти. Игрок может не знать часть слов, забывать исключённые варианты или по-разному доверять подсказкам. Поэтому информационную сложность проверяют вместе с ошибками, временем и ощущением продвижения.
Потолок попытки и нижняя граница
В Wordle каждая из пяти клеток получает один из трёх цветов: формально это 3⁵ = 243 рисунка ответа. Пять сочетаний невозможны: при четырёх зелёных клетках оставшаяся не может стать жёлтой. Поэтому универсальная оценка числа ответов – не более 238, а их энтропии – не более log₂ 238 ≈ 7,89 бита.
Это верхняя граница, а не обещание для выбранного слова. Достичь её можно было бы только при равных вероятностях всех 238 ответов. Конкретная проба и текущий список дают другое разбиение: часть рисунков недоступна, группы имеют разные размеры. При повторяющихся буквах нужно учитывать и их количество.
Деление H на этот потолок даёт слабую нижнюю оценку среднего числа запросов: для Wordle около 1,42. Округлять её до двух как границу среднего нельзя: среднее бывает дробным. Для фиксированной глубины дерева ответов требуется целое число уровней, но это уже другая характеристика.
Рис. 3. Нижняя оценка оставляет много места правилам игры
В Mastermind возможны 14 пар «точное совпадение; верный цвет на другом месте»: пара «три точных и один переставленный» невозможна. Потолок ответа равен log₂ 14 ≈ 3,81 бита, а отношение 10,34 / 3,81 ≈ 2,72 также лишь оценивает среднюю длину поиска снизу.
Победа требует назвать ответ, а не только определить его по последней подсказке. Поэтому информационная граница сама по себе не даёт готовой стратегии. Ограничения словаря, будущие развилки и заключительный ход объясняют, почему число попыток нельзя получить одним делением.
Кнут: гарантия пяти попыток
Классический Mastermind предлагает угадать четыре позиции из шести цветов с разрешёнными повторами. Дональд Кнут разобрал эту задачу в The Computer as Master Mind, опубликованной в Journal of Recreational Mathematics, том 9, № 1 за 1976–1977 годы. Его стратегия гарантирует победу не более чем за пять попыток.
На каждом шаге минимакс выбирает пробу с наименьшей самой большой группой оставшихся кодов. Первый ход 1-1-2-2 оставляет в худшем случае 256 из 1’296 вариантов. При равновероятных кодах среднее для стратегии Кнута составляет около 4,478 попытки; это отдельная величина, не сама гарантия.
Среднее – сумма длин всех 1’296 партий, делённая на число кодов.
Кэндзи Кояма и Тони Лай в работе 1993 года нашли оптимум среднего: 5’625/1’296 ≈ 4,340 попытки при максимуме шесть. Модификация с гарантией пяти требует в среднем 5’626/1’296 ≈ 4,341. Ранее стратегия Эрнста Нойвирта давала 5’656/1’296 ≈ 4,364; оптимальная стратегия Коямы и Лая начинается с 1-1-2-3.
Минимакс уменьшает худший остаток после хода. Максимум энтропии выбирает наибольшую ожидаемую информацию от ближайшего ответа. Минимум среднего числа ходов учитывает всё дерево продолжений. Эти критерии могут предпочесть разные пробы, поэтому обещание «большинству будет быстро» требует отдельной проверки.
Wordle: уравнение Беллмана вместо эвристики
Жадный выбор по энтропии оценивает пользу ближайшей попытки. Однако информативное слово может оставить неудобные группы, для которых следующие ходы малоэффективны. Чтобы минимизировать всю игру, нужно оценивать не только нынешнее разбиение, но и стоимость решения каждой возникшей подзадачи.
Рис. 4. Жёлтая буква нашлась, но её место ещё предстоит угадать
Димитрис Бертсимас и Алекс Пасков применили точное динамическое программирование и уравнение Беллмана: стоимость текущего хода складывается с ожидаемой стоимостью лучших продолжений. Состояние задают оставшиеся возможные ответы; допустимый пробный словарь шире множества ответов.
Для исследованной модели обычного режима с 2’315 равновероятными ответами оптимальный первый ход – SALET. Среднее равно 3,421 попытки, все ответы находятся не более чем за пять. Это результат для фиксированной модели и словарей работы, а не обещание для любой версии Wordle или человека.
Отношение 11,18 / 3,421 ≈ 3,27 бита на попытку можно использовать как сводный показатель стратегии. Но ходы приносят разное количество информации, а последний может лишь ввести уже известное слово. Сравнение этого отношения с потолком 7,89 не доказывает, что каждый ход использует ровно 41% возможностей.
Цена подсказки в битах
Для уже полученной однозначной подсказки в равновероятной модели информация равна log₂(N/N′), где N′ – число совместимых вариантов. Если осталась половина, получен один бит; если отсечена четверть и осталось 75%, получено −log₂ 0,75 ≈ 0,415 бита. Важно считать оставшуюся долю.
До ответа на вопрос считают среднюю информацию. Для признака с вероятностью p она равна двоичной энтропии h₂(p) = −p log₂ p − (1 − p) log₂(1 − p). При p = 0,9 получается 0,469 бита, при p = 0,99 – 0,081. Это ожидание по двум ветвям, а не ценность любого конкретного ответа.
Рис. 5. Редкий ответ может оказаться самой сильной подсказкой
Если признак есть у 90% вариантов, ответ «да» оставляет 90% списка и даёт около 0,152 бита. Ответ «нет» оставляет 10% и даёт 3,322 бита. Их взвешенное среднее равно 0,469. Поэтому вопрос о частом признаке в среднем слабее сбалансированного, но его редкий ответ бывает очень полезен.
Баланс пополам максимизирует среднюю информацию двоичного вопроса, когда оба ответа правдивы и доступны. Для заранее выбранной подсказки важна именно сообщаемая ветвь. Фразу «в слове есть гласная» оценивают по текущему списку и определению гласной, а не по впечатлению, что она всегда очевидна.
Бюджет бит удобно переводить в размер остатка. В учебной модели из 256 равновероятных вариантов подсказки в два, четыре и шесть бит оставят соответственно 64, 16 и 4. Но переводить этот выигрыш в ходы Wordle делением на 3,27 нельзя: после подсказки меняются состав списка и лучшие продолжения.
В квесте подсказка может исключить неверные комнаты, в обучении – уточнить следующее действие, в поиске цели – сузить направление. Единица измерения общая, но время, усилия и удовольствие от открытия различаются. Поэтому дозировку проверяют на игроках и для конкретной задачи.
Что запомнить?
- Энтропия равна log₂ N только при равновероятных вариантах: для 2’315 ответов Wordle это около 11,18 бита.
- Число возможных ответов ограничивает информацию за попытку: не более 238 цветовых рисунков дают потолок около 7,89 бита.
- Информационная оценка 1,42 и оптимальное среднее 3,421 – разные уровни анализа. Гарантия пяти относится к худшему случаю.
- Среднее отношение 3,27 бита на ход не является постоянной отдачей: оно не позволяет линейно предсказать пользу подсказки в попытках.
- При вероятности признака 90% вопрос даёт в среднем 0,469 бита. Его ответы «да» и «нет» несут около 0,152 и 3,322 бита соответственно.
Заключение
Кнут показал силу гарантии, Кояма и Лай уточнили оптимум среднего, а решение Wordle связало текущий ход со всем продолжением. Для дизайнера это разные инструменты: один ограничивает затяжные партии, другой оценивает типичную длину поиска, третий помогает понимать информационную пользу подсказки.
У дозировки нет универсального оптимума без цели. Можно минимизировать число ходов, снижать долю отказов или сохранять самостоятельное открытие. Сначала выбирают измеримый результат, затем проверяют, как подсказка меняет поведение; одинаковое число бит не гарантирует одинакового игрового опыта.
Практический порядок работы:
- зафиксировать возможные ответы и их вероятности; использовать log₂ N, если равновероятность обоснована;
- описать доступные вопросы и обратную связь; отличать теоретический потолок от информации реального хода;
- для вопроса оценить среднюю информацию по ветвям, а для полученной подсказки – изменение распределения вариантов;
- проверить всю стратегию после подсказки: среднее число попыток, худший случай, время и долю успешных завершений;
- выбрать момент помощи и испытать её на игроках: частоту признака нельзя превращать в универсальный порог бесполезности.
Начните с измерения остатка и понятной цели помощи. Энтропия показывает неопределённость в выбранной модели, правила определяют доступные способы поиска, а испытание на игроках связывает расчёт с ощущением продвижения. Полезная подсказка должна работать во всех трёх измерениях.