Игра «Быки и коровы»

Как играть в «Быков и коров»

«Быки и коровы» предлагают угадать секретный код из четырёх цифр. После каждой попытки игра сообщает число быков, то есть цифр на правильных местах, и коров, то есть правильных цифр на других местах. Эти ответы позволяют не перебирать коды вслепую, а шаг за шагом исключать невозможные варианты.

В классическом режиме все четыре цифры различаются. В режиме с повторами секрет может выглядеть как 1122 или 7007. Код может начинаться с нуля: запись 0638 здесь считается полноценным кодом из четырёх позиций, а не числом, у которого отбросили первый знак.

Введите четыре цифры и нажмите «Проверить» либо клавишу Enter. Новая строка появится в истории. Игра продолжается без ограничения числа ходов. Четыре быка означают победу.

Кто придумал «Быков и коров»

У старой бумажной игры нет установленного автора. Она существовала до коммерческих настольных версий и передавалась как задача с карандашом и бумагой. Поэтому её история состоит из нескольких точных дат, но не начинается с фамилии одного изобретателя.

Первый хорошо датированный компьютерный след появился в августе 1968 года. Фрэнк Кинг написал для кембриджского компьютера Titan программу MOO с теми же правилами: четыре разные цифры, быки и коровы после каждой попытки. Кинг создал компьютерную версию, но сама головоломка была ему знакома раньше.

Летом 1970 года Джон Лармут привёз идею из Кембриджа в Массачусетский технологический институт, а Джерролд Грохоу сделал MOO для системы Multics. Игра быстро стала местным хитом. За первые два месяца в неё сыграли больше 75 человек и провели около 1000 партий. Примерно за полгода таблица результатов собрала больше 3000 партий от 150 игроков. Эти числа Грохоу привёл в своей статье 1972 года.

В ноябре 1971 года MOO уже была описана в первом руководстве Unix. Версию для Unix написал Кен Томпсон, один из создателей самой операционной системы. Короткое описание прямо сообщало, что игру привезли из Англии.

У настольной Mastermind автор известен. Израильский специалист по связи Мордекей Мейровиц показал свою игру с цветными фишками на Нюрнбергской ярмарке в 1971 году. Британская компания Invicta Plastics купила права и выпустила её в продажу. В Mastermind вместо десяти цифр использовались шесть цветов, а быков и коров заменили чёрные и белые отметки. Механика почти та же, но число возможных кодов и правила повторов отличаются. Поэтому Мейровица правильно называть автором Mastermind, а не исходных «Быков и коров».

Что означают быки и коровы на примерах

Возьмём секретный код 4271. Игра не показывает его до победы, но на нём удобно разобрать разные ответы.

Одна цифра на месте, две на чужих местах. Попытка 1234 получает 1 быка и 2 коровы. Цифра 2 уже стоит на второй позиции, поэтому это бык. Цифры 1 и 4 присутствуют в секрете, но находятся на других местах, поэтому это две коровы. Цифры 3 в коде нет.

Все четыре цифры найдены. Попытка 4721 получает 2 быка и 2 коровы. Цифры 4 и 1 стоят правильно, а 7 и 2 нужно поменять местами. Сумма быков и коров равна четырём, значит, набор цифр уже известен. Дальше следует менять только порядок.

Ноль быков и ноль коров. Попытка 8905 не совпадает с кодом 4271 ни одной цифрой. Такой ответ полезнее, чем кажется: 8, 9, 0 и 5 можно полностью исключить из следующих вариантов.

Почти победа. Попытка 4270 получает 3 быка и 0 коров. Первые три позиции верны, а нуля в секрете нет. Следующий ход должен сохранить 427 и заменить только последнюю цифру. Перемешивать весь код заново незачем.

Повторы считаются по количеству. В режиме с повторами секрет 1122 и попытка 1111 дают 2 быка и 0 коров. Две единицы совпали по местам, а лишние единицы не превращаются в коров: в секрете больше единиц нет. Каждая позиция может дать не более одного совпадения.

Четыре коровы ещё не победа. Для секрета 1122 попытка 2211 получает 0 быков и 4 коровы. Все цифры найдены, но каждая стоит не там. Нужно переставить их, пока ответ не станет «4 быка».

Комбинаторика «Быков и коров»

Здесь угадывается код, а не обычное четырёхзначное число. Ноль разрешён на первой позиции, поэтому для первой цифры подходят все десять знаков от 0 до 9.

Без повторов существует 5040 кодов. Для первой позиции есть 10 вариантов, для второй остаётся 9, затем 8 и 7. Получается 10 × 9 × 8 × 7 = 5040. В комбинаторике такой выбор называют размещением четырёх элементов из десяти.

В режиме с повторами каждая позиция снова получает все 10 вариантов. Поэтому кодов уже 10⁴ = 10 000. Если запретить ведущий ноль, числа изменятся: останется 4536 кодов без повторов или 9000 с повторами. Именно различие между кодом и числом часто объясняет разные ответы в задачах на эту игру.

Для длины четыре возможны 14 разных пар подсказок. Ответ «3 быка, 1 корова» получить нельзя. После трёх точных совпадений остаётся всего одна позиция. Если последние цифры равны, получится четвёртый бык. Если не равны, корове просто не с чем поменяться местами.

Есть и красивая связь с перестановками. Когда сумма быков и коров равна четырём, все нужные цифры уже найдены. Для четырёх разных цифр существует 4! = 24 порядка. Девять из них не оставляют ни одной цифры на прежнем месте, поэтому ответ «0 быков, 4 коровы» оставляет ровно 9 вариантов. Ровно один бык оставляют 8 порядков, два быка оставляют 6, три быка не оставляет ни один, а четыре быка даёт только правильный код.

Эту задачу изучают как поиск среди конечного множества. В 2007 году Шань Тай Чен и его соавторы компьютерно доказали важный результат для классических правил без повторов: существует стратегия, которая гарантирует разгадку любого кода не более чем за семь ходов, и гарантировать шесть ходов невозможно. Речь идёт об оптимальном дереве решений, а не о том, что любой случайный набор попыток уложится в семь. [Chen et al., 2007]

Как подсказка сокращает число вариантов

Каждая подсказка сокращает число допустимых кодов. Кандидат можно оставить только тогда, когда он дал бы точно такое же число быков и коров на каждую вашу попытку. Так работает обычное логическое исключение.

Например, стартовая попытка 0123 и ответ «0 быков, 0 коров» сокращают классический список с 5040 до 360 кодов. В секрете остаются только цифры 4, 5, 6, 7, 8 и 9, из которых нужно выбрать и расположить четыре. Ответ «1 бык, 2 коровы» на попытку 1234 оставляет 216 вариантов, а «0 быков, 4 коровы» всего 9 перестановок. Сам ответ ещё не раскрывает код, но хорошо показывает масштаб следующего шага.

Все 14 ответов встречаются с разной частотой. Для первого хода 0123 самый большой классический набор возникает при одной корове: после него остаётся 1440 кандидатов. Ответ «1 бык, 3 коровы» оставляет 8, а «4 быка» только один. Хороший ход старается разделить оставшиеся коды на небольшие группы, чтобы любой возможный ответ дал полезную информацию.

Теория информации помогает увидеть масштаб задачи. Двенадцать ответов «да» или «нет» различают не больше 2¹² = 4096 случаев, а этого мало для 5040 кодов. Тринадцать таких ответов уже различают до 8192 случаев. Подсказка в «Быках и коровах» богаче простого «да» или «нет», потому что сообщает один из 14 возможных результатов. Но эти результаты распределены не поровну, поэтому одного деления 5040 на 14 недостаточно для расчёта числа ходов.

Как компьютер выбирает сильный ход

Простой решатель сначала выписывает все допустимые коды. После ответа он удаляет каждый код, который противоречит хотя бы одной подсказке. Затем программа мысленно проверяет возможные следующие ходы и смотрит, на какие группы они разделят оставшихся кандидатов.

Один из подходов называется минимакс. Для каждого хода программа находит самый неудачный возможный ответ, то есть тот, после которого останется крупнейшая группа. Затем выбирает ход с наименьшей такой группой. Цель здесь не угадать немедленно, а гарантированно получить полезную подсказку.

Иногда лучший проверочный код уже исключён и точно не может быть секретом. Такой ход всё равно полезен, если он хорошо разделяет оставшиеся варианты. Это важное различие между попыткой угадать и экспериментом, который должен принести информацию.

В 1976 году Дональд Кнут описал знаменитый алгоритм для Mastermind. В той версии есть четыре позиции и шесть цветов с повторами, всего 6⁴ = 1296 кодов. Алгоритм Кнута гарантирует решение максимум за пять ходов. Переносить число пять на цифровые «Быки и коровы» нельзя: здесь десять знаков и другое пространство кодов. Общий принцип, сохранять совместимые варианты и делить их на небольшие группы, работает в обеих играх.

Стратегия: сначала цифры, потом места

Начните с четырёх разных цифр. Попытка вроде 0123 проверяет сразу четыре знака. Даже в режиме с повторами такой старт обычно даёт больше новой информации, чем 1111, потому что охватывает четыре разных возможных цифры.

Смотрите на сумму быков и коров. Она показывает, сколько цифр из попытки вообще присутствуют в секрете. Если сумма равна нулю, исключите весь набор. Если равна четырём, перестаньте добавлять новые цифры и займитесь их расположением.

Меняйте одну понятную часть. Когда между двумя ходами заменена одна цифра, изменение ответа легче объяснить. Если одновременно заменить весь код, новый результат может быть лучше, но вы не узнаете, какая именно замена помогла.

Отделяйте цифру от позиции. Корова подтверждает наличие цифры, но запрещает текущее место. Запишите это как два факта: «7 входит в код» и «7 не стоит второй». Такая формулировка полезнее общей мысли «где-то была семёрка».

Не повторяйте уже проверенный код. Та же попытка всегда даст тот же ответ и не сократит список кандидатов. Интерфейс поэтому останавливает повтор до добавления строки в историю.

Сверяйтесь с историей. Новый код должен учитывать все прежние ответы, а не только последний. Если ход противоречит хотя бы одной подсказке, он не приблизит к решению.

Используйте проверочный ход. Когда осталось несколько похожих вариантов, не обязательно сразу выбирать самый правдоподобный. Иногда лучше поставить цифры так, чтобы разные секреты дали разные ответы. Следующий ход после такой проверки станет почти очевидным.

Почему режим с повторами сложнее

В классическом режиме найденная цифра встречается ровно один раз. Если ответ подтвердил 7, искать вторую семёрку не нужно. В режиме с повторами приходится выяснять ещё и количество: секрет может содержать одну, две, три или четыре одинаковые цифры.

Сначала считаются быки. Затем игра сравнивает оставшиеся цифры и ограничивает число коров тем, сколько соответствующих цифр осталось в секрете. Поэтому код 0012 и попытка 0000 дают 2 быка и 0 коров, а не четыре совпадения. Такой порядок предотвращает двойной счёт одной позиции.

Переключение режима начинает новую партию и очищает историю. Старые ответы нельзя переносить: они были получены для другого секрета и другого набора допустимых кодов.

Что тренируется во время игры

Каждый ход похож на маленький эксперимент. Вы формулируете гипотезу в виде кода, получаете обратную связь и проверяете, какие варианты с ней совместимы. Так игрок практикуется отбрасывать противоречивые версии, отделять наличие цифры от её позиции и планировать следующий вопрос.

Игра задействует рабочую память: нужно держать в голове найденные цифры, запрещённые позиции и прежние ответы. В эксперименте Кадзунори Оцуки 143 студента играли в Mastermind с видимой историей ходов и без неё. Результаты показали, что рабочая память участвует в решении, а записи помогают вынести часть информации на экран. Это говорит о нагрузке во время партии, но не доказывает, что игра улучшает память.

В двух экспериментах психолога Джона Беста участники с практикой делали более точные и сложные выводы в Mastermind и осваивали полезный стратегический приём. При этом автор не обнаружил доказательств глубокой перестройки общего логического знания. Стратегия помогала создавать игровые ситуации, которые легче понять.

В другом исследовании участвовали 15 классов шестиклассников и восьмиклассников. Игровые группы занимались Mastermind восемь недель, два раза в неделю по 20 минут. По отдельному тесту формального рассуждения они не получили преимущества перед контрольными классами. Поэтому честный вывод звучит так: игра даёт практику дедукции и планирования внутри конкретной задачи, но не обещает рост IQ, памяти или общей логики. [Bright et al., 1983]

Куда перейти после разгаданного кода

Если нравятся последовательные исключения по нескольким условиям, попробуйте задачи Эйнштейна с логической матрицей. Чтобы проверить, откуда берутся 5040 классических кодов, пригодится калькулятор перестановок и размещений. А для собственной партии вдвоём можно случайно выбрать секретный код и записывать ответы на бумаге.

Похожие калькуляторы

Возможно вам пригодятся ещё несколько калькуляторов по данной теме:

• Игра «Задачи Эйнштейна». Решайте логические задачи Эйнштейна: отмечайте связи в матрице и проверяйте ответ.
• Крестики-нолики. Сыграйте онлайн в Крестики-Нолики с собой, другом или против компьютера.
• Рандомайзер: генератор случайных чисел. Выберите случайное число в нужном диапазоне для любых целей, в частности для розыгрышей и онлайн-лотерей в соцсетях.
• Калькулятор калорий при ходьбе. Рассчитайте, сколько калорий сжигается при ходьбе пешком, к примеру, за 1 км, 1 час или 10000 шагов. Учитывается тип ходьбы: быстрая, по лестнице, скандинавская.
• Калькулятор шашлыка. Рассчитайте на онлайн-калькуляторе, сколько нужно взять мяса для шашлыка.
• Калькулятор сна. Рассчитайте по фазам сна и «правилу 90 минут», во сколько лечь спать, чтобы выспаться.
• Калькулятор размеров одежды. Определите российский размер одежды и привычный ориентир S–XL для верха и низа по обхватам груди, талии и бёдер, а перед покупкой сверьтесь с таблицей бренда.
• Случайный выбор из списка. Добавьте варианты по одному в строке, укажите количество и выберите режим повторов.
• Перемешать список. Добавьте пункты по одному в строке и укажите, нужно ли сохранять одинаковые значения.
• Разделить список на группы. Добавьте участников, укажите число групп и выберите случайный либо исходный порядок.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.