Теория информации на практике: как энтропия помогает решать Wordle

> Спикер: 3Blue1Brown | Длительность: 30:38

Ключевые идеи

1. Информация — это сокращение неопределённости — каждое наблюдение ценно настолько, насколько сужает пространство вариантов. Уполовинивание — это один бит.
2. Формула информации: I = -log₂(p) — логарифм от обратной вероятности. Интуитивно: сколько раз пространство разрезано пополам.
3. Энтропия = ожидаемая информация — математическое ожидание бит по всем возможным исходам. Чем равномернее распределение, тем выше энтропия.
4. Маловероятное = информативное — редкие паттерны дают много бит, но на них нельзя рассчитывать. Частые паттерны предсказуемы и малоинформативны.
5. Лучшая догадка максимизирует энтропию — слово SLATE (~5.8 бит) лучше WEARY (~4.9 бит), потому что его распределение паттернов более плоское.
6. Частотность букв — неточный метод — не учитывает позиции и комбинации букв. Формальный подход через энтропию точнее.
7. Энтропия = «плоскость» + «размер» — 6 бит энтропии эквивалентны 64 равновероятным исходам.
8. Жадный алгоритм даёт ~4.12 хода — перебор 13 000 слов с максимизацией энтропии на каждом шаге.
9. Информация складывается — 2 бита + 3 бита = 5 бит. Это свойство логарифмов делает энтропию удобной мерой.
10. Учёт частотности слов — ключ к улучшению — наивный бот не различает «abyss» и экзотические слова; добавление весов по частотности улучшает эндшпиль.
11. Термин «энтропия» — от фон Неймана — предложен Шеннону как название для ожидаемой информации, с ироничной мотивацией: «никто не знает, что это такое».

Транскрипт

Что такое Wordle?

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

Автор создал бота, который играет в Wordle, максимизируя получаемую информацию на каждом шаге. Демонстрация: бот предлагает начать с CRANE, после паттерна серый-жёлтый-зелёный-серый-серый переходит к SHTIK, затем сужает варианты до двух (SHARD и SHARP) и угадывает за 3 хода. Четыре хода считается «паром», три — «бёрди».

Первые идеи: частотность букв

Первый наивный подход — выбрать слова с самыми частыми буквами английского языка. Например, пара OTHER + NAILS покрывает 10 самых частых букв. Даже все серые ответы информативны, потому что слова без этих букв крайне редки.

Но этот метод не учитывает порядок букв: NAILS и SNAIL содержат одни буквы, но дают разную информацию. Нужен формальный количественный критерий.

Устройство игры: 13 000 допустимых слов

Wordle принимает ~13 000 допустимых слов в качестве догадок, но ответами могут быть только ~2 300 распространённых слов (список курировала девушка создателя игры). Автор ставит задачу: создать бота, не использующего этот список, — более универсального и не «жульничающего».

Анализ качества догадки

Для слова WEARY: если выпадет паттерн с W на месте — останется всего 58 вариантов из 13 000 (огромное сужение). Но вероятность такого паттерна — лишь 58/13 000. Самый вероятный паттерн — все серые (~14%) — наименее информативен.

Распределение вероятностей по всем 3⁵ = 243 возможным паттернам — ключ к оценке слова. Нужна мера ожидаемой информации.

Теория информации: биты

Единица информации — бит. Наблюдение, сужающее варианты вдвое — 1 бит, вчетверо — 2 бита, в 8 раз — 3 бита. Формула: I = log₂(1/p) = -log₂(p).

Почему логарифмы? Две причины: (1) удобство для малых вероятностей — проще сказать «20 бит», чем «0.0000095»; (2) информация складывается, когда вероятности перемножаются — 2 бита + 3 бита = 5 бит.

Энтропия: ожидаемая информация

Энтропия = Σ p(x) × (-log₂(p(x))). Для WEARY энтропия ≈ 4.9 бит, для SLATE ≈ 5.8 бит. SLATE лучше, потому что его распределение паттернов более плоское — даже худший случай (все серые) имеет вероятность лишь 6%.

Клод Шеннон разработал теорию информации в 1940-х в Bell Labs. Фон Нейман предложил назвать ожидаемую информацию «энтропией» — отчасти из-за связи со статмеханикой, отчасти ради стратегического преимущества в дебатах.

Алгоритм Wordle-бота (версия 1)

Бот перебирает все 13 000 слов, для каждого считает энтропию распределения паттернов, выбирает слово с максимальной энтропией. После получения паттерна — сужает список и повторяет. Лучшее первое слово (без учёта частотности) — TARES (~5.8 бит). Средний результат на 2 315 тестовых словах — 4.124 хода.

Слабость: бот не знает, какие слова распространены. При 50/50 выборе между SHARD и SHARP или двумя экзотическими словами он не отдаёт предпочтение обычным. Следующий шаг — учёт частотности слов.

Практические задания

Задание 1: Вычисли информацию от простого события
Возьми монету. Бросок монеты имеет вероятность 1/2. Рассчитай информацию: I = -log₂(1/2) = 1 бит. Теперь рассчитай информацию для броска кубика (p = 1/6): I = -log₂(1/6) ≈ 2.58 бита. Проверь интуицию: результат кубика действительно «удивительнее» монеты примерно в 2.5 раза.

Задание 2: Построй распределение паттернов для слова
Выбери любое пятибуквенное слово (например, CRANE). Возьми список из 20-30 пятибуквенных слов. Для каждого «ответа» определи паттерн цветов (серый/жёлтый/зелёный). Подсчитай, сколько ответов дают каждый паттерн. Ты получишь распределение — основу для расчёта энтропии.

Задание 3: Рассчитай энтропию распределения вручную
Используя распределение из предыдущего задания, рассчитай энтропию: H = Σ p(x) × (-log₂(p(x))). Для каждого паттерна умножь его вероятность на количество бит информации. Сложи все произведения. Сравни результат для 2-3 разных стартовых слов.

Задание 4: Проверь свойство максимума энтропии
Возьми два распределения: (A) четыре исхода по 1/4 и (B) четыре исхода с вероятностями 1/2, 1/4, 1/8, 1/8. Рассчитай энтропию обоих. Убедись, что равномерное (A) даёт ровно 2 бита, а неравномерное (B) — меньше.

Задание 5: Напиши простой Wordle-бот
На Python реализуй упрощённый алгоритм: загрузи список пятибуквенных слов, для каждого кандидата рассчитай энтропию распределения паттернов, выбери слово с максимальной энтропией. Начни с маленького списка (100-500 слов) для скорости.

Задание 6: Сравни стратегии
Составь топ-5 стартовых слов по двум критериям: (1) суммарная частотность букв и (2) энтропия паттернов. Сравни списки и объясни различия.

Пошаговые инструкции применения

1. Освой формулу информации: Запомни I = -log₂(p). Потренируйся на простых вероятностях: 1/2, 1/4, 1/8.
2. Научись считать энтропию: H = Σ p(x) × log₂(1/p(x)). Начни с монеты и кубика.
3. Примени к Wordle: Для стартового слова смоделируй все паттерны ответов и подсчитай энтропию.
4. Сравни слова по энтропии: Рассчитай для CRANE, SLATE, AUDIO, WEARY — выбери лучшее.
5. Реализуй жадный алгоритм: Python-скрипт с перебором слов и максимизацией энтропии.
6. Добавь веса частотности: Присвой распространённым словам больший вес через корпусные данные.
7. Протестируй: Прогони по 2 315 ответам Wordle, цель — средний результат ≤ 4.0.
8. Перенеси принцип в жизнь: При принятии решений задавайте вопрос, максимально сужающий варианты.

Лучшие цитаты

> «Паттерн с большим количеством информации по своей природе маловероятен. По сути, быть информативным — значит быть маловероятным» — 3Blue1Brown

> «Так же как вероятности любят перемножаться, информация любит складываться» — 3Blue1Brown

> «Называй это энтропией: во-первых, название уже занято в статфизике, а во-вторых — никто толком не знает, что такое энтропия, так что в споре ты всегда в выигрыше» — Джон фон Нейман

> «Это просто очень интуитивная идея — подсчитать, сколько раз вы разрезали пространство возможностей пополам» — 3Blue1Brown

> «Если энтропия равна 6 битам — это как 64 равновероятных исхода» — 3Blue1Brown

> «Даже все серые — это тоже много информации, потому что слово без этих букв найти трудно» — 3Blue1Brown

> «Наиболее вероятные исходы одновременно являются наименее информативными» — 3Blue1Brown

> «Очевидно, нам нужна лучшая стратегия для эндшпиля» — 3Blue1Brown