Hacker News Digest

• Участники делятся книгами и ресурсами по теории информации и кодированию: труд Шеннона, новые учебники, PhD-диссертация о сжатии без потерь и связи с генеративным ИИ.
• «Coding» здесь — это кодирование/декодирование данных для защиты от ошибок, сжатия и передачи, а не «программирование».
• Рекомендуются вводные тексты Пирса и Стоуна, а также классика Петерсона–Уэлдона и МакКея.
• Тема считается математически плотной и факультативной даже для старших курсов CS.

Правила
Компьютер загадывает код из 4 шпилек 6 цветов. После каждой попытки он выдаёт:

• чёрный штырь — цвет и позиция угаданы;
• белый — цвет есть, но позиция неверна;
• ничего — цвета в коде нет.

Оптимальная стратегия
Игра — это сбор информации. Начинается с 1296 возможных кодов. Каждая попытка «отсекает» часть вариантов; эффективность измеряется в битах.

• 1 бит = сокращение вдвое.
• Энтропия попытки — среднее количество битов, которое она приносит:
  $$H = \sum_i p_i \log_2\frac{1}{p_i},$$
  где $p_i$ — доля кодов, дающих ответ $i$.

Алгоритм:

1. Для каждой возможной попытки посчитать, сколько кодов останется при каждом ответе.
2. Выбрать попытку с максимальной энтропией.
3. Повторять, пока код не угадан.

Результат
Среднее число попыток — 4.47 (σ = 0.75). Это совпадает с лучшими известными алгоритмами (Knuth, 1976 и др.).

• Участники делились личными историями: кто-то писал игру в 2007 для iPhone, кто-то играл с родителями и детьми, а кто-то вдохновился ею стать математиком.
• Обсуждали стратегии: MaxParts, «один цвет на строку» и информационно-теоретический подход.
• Отмечали, что современные LLM не справляются с Mastermind после нескольких ходов.
• Упоминали баг сайта, опечатку «Worlde» и сравнивали игру с Wordle.
• Кто-то критиковал статью за отсутствие формального доказательства оптимальности.