Быки и коровы

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Быки и коровы
4digits 0.4 screenshot.png
скриншот компьютерной версии игры. Партия выиграна за семь ходов
Кол-во игроков

2

Длительность партии

5-30 минут

Сложность правил

Низкая

Уровень стратегии

Низкая

Влияние случайности

Среднее

Необходимые навыки

Счёт, Память

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

Правила игры[править | править вики-текст]

В классическом варианте игра рассчитана на двух игроков. Каждый из игроков задумывает и записывает тайное 4-значное число с неповторяющимися цифрами[1]. Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков). Например:

Задумано тайное число «3219».

Попытка: «2310».

Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции).

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

При игре против компьютера игрок вводит комбинации одну за другой, пока не отгадает всю последовательность.

Вариации игры[править | править вики-текст]

В игре «мастермайнд» (англ. Mastermind, возможный перевод: «Интеллектуал, умник») загадывается последовательность из 4 цветных фишек, причём цвета могут повторяться. В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек[2]

Вариант игры с пиктограммами

Существует вариант игры со словами[источник не указан 290 дней]. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «балда»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка. Однако, существует и вариант, когда возможно использование произвольного сочетания букв.

Алгоритм[править | править вики-текст]

В общем случае количество вариантов для k-значного числа в N-ричной системе счисления без повторений, будет равно числу размещений:  A_N^k = \frac{N!}{(N-k)!} .

В случае варианта с повторениями количество вариантов будет равно  N^k .

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

Настольный вариант игры Mastermind для 4 мест и 6 цветов

Как показал Дональд Кнут, для игры Mastermind (64 вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, и в среднем 4,34 попыток для отгадывания[3]. Вполне очевидно, что игра с четырьмя не повторяющимися цифрами является упрощённым частным случаем и для отгадывания любой комбинации не должно требоваться большее количество попыток..

Реализации[править | править вики-текст]

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

Настольные игры Mastermind популярны во всём мире. Наиболее распространены вариации:

  • классическая, четыре не повторяющиеся цифры.
  • обычная, 4 места для фишек 6 цветов с повторениями.
  • продвинутая, 5 мест для фишек 8 цветов[источник не указан 815 дней].

В культуре[править | править вики-текст]

  • В компьютерной игре "Sleeping Dogs" игра "Быки и коровы" служит имитацией взлома компьютерных полицейских сетей.

Ссылки[править | править вики-текст]

  • Кандидат технических наук Е. Гик. Быки и коровы. «Наука и жизнь», № 2, 1978, с. 150—151; № 8, 1978, с. 142—143.
  • Чарльз Уэзерелл. Этюды по программированию, Великий комбинатор. М.: 1982, с. 140.


Примечания[править | править вики-текст]