Mastermind — настольная игра на рассуждение, очень похожая на «Быков и коров». Название считается товарным знаком, поэтому здесь мы расскажем только об идее игры, насколько это можно подтвердить.
Что это за игра
Считается, что её придумали около 1970 года. Это настольная игра для двоих (об истории игр на угадывание чисел см. История игр на угадывание чисел).
- Один игрок выставляет несколько цветных колышков и прячет их как ответ.
- Второй выставляет ряд колышков как попытку.
- Тот, кто загадал, сообщает подсказку маленькими колышками. В самой известной версии они показывают число колышков, у которых и цвет, и место угаданы, и число колышков, у которых цвет угадан, а место нет.
Смысл подсказок тот же, что у быков и коров.
Главное отличие: цвета можно повторять
В самой известной версии в ответе цвет можно использовать сколько угодно раз. В «Быках и коровах» и ответ, и попытки состоят из разных символов.
Если цвета можно повторять, число вариантов меняется. Например, для четырёх мест и 6 цветов:
- если цвета можно повторять: 6 × 6 × 6 × 6 = 1296 вариантов;
- если нельзя: 6 × 5 × 4 × 3 = 360 вариантов.
При повторяющихся цветах нужно аккуратнее считать и тех, у кого цвет угадан, а место нет: сравнивают, сколько раз каждый цвет встречается в ответе и в попытке, и берут меньшее число.
Для 6 цветов и 4 мест хватает 5 попыток
Для 6 цветов и 4 мест (цвета можно повторять) мы перебрали все 1296 ответов и посчитали число попыток для одной стратегии. Для каждой попытки смотрим, как возможные подсказки делят варианты, и выбираем такой ряд, у которого самая большая оставшаяся группа наименьшая (первая попытка — «два одинаковых цвета и два других одинаковых»).
| Попыток | Ответов |
|---|---|
| 1 | 1 |
| 2 | 6 |
| 3 | 62 |
| 4 | 533 |
| 5 | 694 |
Любой ответ находится не больше чем за 5 попыток, а в среднем за 4,48. Эта стратегия и результат известны как открытие, которое в 1970-е годы показал учёный-компьютерщик Дональд Кнут.
Сравнение с «Быками и коровами»
| Игра | Символы | Вариантов |
|---|---|---|
| Mastermind (6 цветов, 4 места) | цвета можно повторять | 1296 |
| «Быки и коровы», 3 разряда | все разные | 720 |
| «Быки и коровы», 4 разряда | все разные | 5040 |
Для 4 разрядов «Быков и коров» вариантов много, 5040, и расчёт показывает, что любой ответ находится не больше чем за 7 попыток (в среднем около 5,3, в зависимости от стратегии) (Есть ли выигрышная стратегия в «Быках и коровах»?).
«Быки и коровы» с цветами
В приложении «Быки и коровы» правило такое: все символы разные, но внешний вид символов можно менять в «Стиле». Если выбрать цветные шары или камни, получится почти как угадывание ряда цветов. У цветных шаров есть узоры, чтобы их различали и те, кто иначе видит цвета (Играем не только цифрами).
