Using information theory to solve Mastermind
Правила
Компьютер загадывает код из 4 шпилек 6 цветов. После каждой попытки он выдаёт:
- чёрный штырь — цвет и позиция угаданы;
- белый — цвет есть, но позиция неверна;
- ничего — цвета в коде нет.
Оптимальная стратегия
Игра — это сбор информации. Начинается с 1296 возможных кодов. Каждая попытка «отсекает» часть вариантов; эффективность измеряется в битах.
- 1 бит = сокращение вдвое.
- Энтропия попытки — среднее количество битов, которое она приносит:
$$H = \sum_i p_i \log_2\frac{1}{p_i},$$
где $p_i$ — доля кодов, дающих ответ $i$.
Алгоритм:
- Для каждой возможной попытки посчитать, сколько кодов останется при каждом ответе.
- Выбрать попытку с максимальной энтропией.
- Повторять, пока код не угадан.
Результат
Среднее число попыток — 4.47 (σ = 0.75). Это совпадает с лучшими известными алгоритмами (Knuth, 1976 и др.).