Что это за игра
Быки и коровы — это гонка двух шифровальщиков. Каждый загадал четыре разные цифры, и оба одновременно пытаются вскрыть чужой код раньше, чем вскроют их собственный.
Всего таких кодов ровно 5040. Кажется, что это много, но правильно заданный вопрос отсекает сразу большую их часть: каждый ответ «столько-то быков, столько-то коров» делит оставшееся множество на группы, и вам достаётся ровно одна. Хорошо сыгранная партия — это пять-шесть ходов, плохо сыгранная тянется вдвое дольше.
Правила
- Каждая сторона загадывает код из четырёх разных цифр от 0 до 9. Ноль в начале разрешён, так что 0421 — законный код.
- Сначала вы вводите свой код — вручную или кнопкой «Случайно» — и нажимаете «Начать». Компьютер свой уже загадал.
- Ход — это назвать четыре разные цифры. Ответ приходит сразу: столько быков и столько коров.
- Бык — верная цифра на верном месте. Корова — верная цифра, но не на своём месте. Цифра считается один раз: либо быком, либо коровой.
- Четыре быка означают, что код разгадан.
- Ходы чередуются: сначала вы, потом компьютер. Ваши попытки копятся в левом столбце, его — в правом; ваш собственный код всё время виден над правым столбцом, чтобы вы могли проверять его ответы.
- Побеждает тот, кто первым получит четыре быка. Вы ходите первым, поэтому при равном числе ходов победа ваша.
- На карточке слева — счётчики сделанных ходов, ваш и компьютера.
Как играть лучше
- Не мучайтесь над первым ходом. До первого ответа все догадки равноценны: переименование цифр переводит любую в любую, так что первый ход можно называть не думая.
- Сумма быков и коров говорит не о местах, а о составе: сколько ваших цифр вообще входит в код. Пока состав не найден, гоняйтесь именно за этой суммой, а не за быками.
- Разбейте задачу надвое. Сначала выясните, какие четыре цифры в коде, потом расставляйте их по местам — эти две подзадачи почти не мешают друг другу.
- Ответ «0 быков, 0 коров» — самый ценный из всех: он одним махом вычёркивает четыре цифры из десяти.
- Называйте только то, что ещё возможно. Комбинация, противоречащая любому из прошлых ответов, — это выброшенный ход.
- Когда состав известен, не переставляйте цифры наугад. Выбирайте перестановку, на которую оставшиеся варианты ответят по-разному: догадка, делящая их поровну, стоит двух случайных.
Немного истории
Быки и коровы — игра на бумаге, и она заметно старше своего самого известного потомка. В неё играли задолго до того, как её механику выпустили в коробке.
Коробка появилась в 1970 году: Mastermind, придуманный Мордехаем Мейровичем, заменил цифры цветными колышками, а быков и коров — чёрными и белыми штырьками. Игра разошлась миллионами экземпляров и заодно превратилась в задачу, которую всерьёз изучали математики.
В середине 1970-х Дональд Кнут опубликовал работу «The Computer as Master Mind» с алгоритмом, который вскрывает Mastermind не более чем за пять ходов. Идея простая и сильная: на каждом ходу перебрать все возможные догадки, для каждой посмотреть, на сколько групп она делит оставшиеся варианты, и выбрать ту, у которой самая большая группа наименьшая. То есть готовиться к худшему ответу. Именно этот приём работает здесь на уровне «Эксперт».
Эта версия сделана по мотивам апплета, который работал на сайте с 2005 года, и сохраняет его главную особенность: это не угадывание в одну сторону, а дуэль. Компьютер взламывает ваш код теми же ходами, которыми вы взламываете его, и право первого хода решает ничьи в вашу пользу.
Про уровни
Уровень определяет ровно одно: насколько умно компьютер сужает множество кодов, ещё совместимых со всеми полученными ответами. Отсеивать несовместимое он умеет на всех трёх — разница в том, что он делает с остатком.
Простой берёт из совместимых кодов случайный. Он никогда не назовёт заведомо невозможную комбинацию, но и выбирать среди возможных не пытается.
Сложный выбирает догадку, которая в среднем оставит меньше всего вариантов: для каждого кандидата он раскладывает остаток по группам ответов и берёт того, у кого сумма квадратов размеров групп минимальна. Смотрит он при этом только на сами возможные коды, и если их слишком много для бюджета в миллион пар за ход, берёт случайную выборку.
Эксперт играет по Кнуту: оценивает догадку не по среднему, а по худшему случаю — по самой большой группе — и выбирает ту, где худший случай наименьший. Бюджет у него в восемь раз больше, поэтому он проверяет не только возможные коды, но и «зондирующие» комбинации, которые сами кодом быть уже не могут, зато делят остаток лучше. При равном счёте он предпочтёт догадку, которая ещё может оказаться кодом, — вдруг повезёт выиграть сразу.
Первый ход у всех трёх уровней случайный, и это не поблажка: пока ни одного ответа не получено, выбирать действительно не из чего.