Быки и коровы (игра)¶

Быки и коровы — логическая игра на угадывание числа или слова, в которой один игрок (или компьютер) загадывает комбинацию, а другой пытается её восстановить по подсказкам о числе угаданных элементов и их позиций. Относится к классу игр с неполной информацией и обратной связью, близка к «Мастермайнду» и «Виселице» по механике последовательных догадок.

¶Правила

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

быки — количество цифр, угаданных и по значению, и по позиции;
коровы — количество цифр, которые присутствуют в секрете, но стоят не на своём месте.

Например, если загадано 1234, а предложено 1324, то результат — два быка (цифры 1 и 4 на своих местах) и две коровы (2 и 3 присутствуют, но переставлены). Цель — получить четыре быка за минимальное число ходов.

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

¶Происхождение и названия

Игра имеет народное происхождение и не имеет единственного установленного автора. Механика «угадай код по подсказкам» независимо возникала в разных культурах. В англоязычной традиции закрепилось название Bulls and Cows, в русскоязычной — «Быки и коровы». Название связано с метафорой: «бык» точно попадает в цель, «корова» лишь близка к ней, но стоит рядом.

В 1970-х годах на основе этой механики была выпущена настольная игра «Мастермайнд» (Mastermind), где вместо цифр используются цветные колышки. Это коммерческое воплощение сделало логику игры массовой, хотя сама идея к тому времени была известна давно.

¶История в вычислительной технике

Игра сыграла заметную роль в истории программирования. В 1970-х годах она стала популярным учебным заданием для демонстрации возможностей ЭВМ: программа-соперник загадывала число и оценивала ходы пользователя. Вариант под названием «BAGELS» вошёл в состав операционной системы UNIX и распространялся вместе с ней, что способствовало его известности среди программистов.

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

¶Стратегия и математическая основа

Пространство возможных секретов для классического варианта (четыре различные цифры, первая не ноль) составляет 9 × 9 × 8 × 7 = 4536 комбинаций. Это позволяет вести полный перебор на компьютере.

Оптимальная стратегия строится на двух подходах:

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

При грамотной игре секрет удаётся раскрыть в среднем за 5–6 ходов, а гарантированно — не более чем за 7 ходов при использовании полного дерева решений. Первый ход часто делают «зондирующим», например 1234, чтобы получить максимум сведений о составе цифр.

¶Применение в обучении

Игра широко применяется в педагогике и при обучении программированию:

как задача на написание алгоритма и работу с циклами;
как пример для изучения перебора, эвристик и оценки сложности;
в курсах по теории информации и криптографии — для демонстрации принципа обратной связи и постепенного раскрытия секрета.

Простота правил при нетривиальной логике делает её удобной для развития внимания и комбинаторного мышления у школьников.

¶Компьютерные и онлайн-реализации

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

¶Родственные игры

К той же семье логических игр относятся:

«Мастермайнд» — настольная версия с цветными колышками;
«Виселица» — угадывание слова по буквам;
«Морской бой» — поиск клеток на скрытом поле;
игры на угадывание кода в квестах и головоломках.

Общий принцип — последовательное сужение множества гипотез на основе ответов «да/нет» или их аналогов.

¶Интересные факты

В классическом варианте число 4536 возможных секретов делает полный перебор выполнимым даже на слабых вычислительных устройствах.
Игра вошла в набор стандартных программ UNIX и тем самым стала частью ранней компьютерной культуры.
Механика «быков и коров» используется в некоторых системах как метафора поэтапного уточнения гипотез.

Источники: материалы по истории компьютерных игр и операционной системы UNIX; публикации по теории информации и комбинаторике; описания настольной игры «Мастермайнд»; учебные пособия по алгоритмам и программированию.