Бики та корови

*Бики та корови*
Кількість гравців	2
Час гри	5-30 хвилин
Вплив випадковості	Середній
Необхідні здібності	Вміння рахувати, Пам'ять

Бики та корови (також відома як Корови та бики, Свині та бики) — логічна гра, призначена для двох гравців, в основі якої закладено вгадування числа, задуманого суперником. З початку розвитку комп'ютерних технологій з'явилися варіації гри поодинці, коли задумане число вгадує або гравець, або комп'ютер. Для гри удвох достатньо мати папір та ручку. Крім цього, гра можлива при використанні функції багатокористувацької гри на відстані.

Правила гри

Настільний варіант гри Mastermind^[1] для 4 місць та 6 кольорів

Правила гри можуть залежати від типу вгадуваної послідовності — це можуть бути числа, слова, кольори, піктограми тощо. В класичній версії гра відбувається між двома гравцями. Також можуть грати дві команди по декілька гравців (з членами команди обговорюють свою стратегію, перш ніж вибрати крок).

Версія з числами

В чисельній версії опонент задумує чотиризначне число (можливі варіанти з використанням числа будь-якої довжини). Всі цифри повинні бути різні. Тоді ж, в свою чергу, гравці намагаються вгадати число противника. Гравець пропонує свій варіант, а опонент дає кількість збігів. Якщо збігається цифра в її правильній позиції, то це є «бик», якщо не в своїй позиції — це «корова».

Наприклад:

   Задумане число: 4271
   Спроба суперника: 1234
   Відповідь: 1 бика і 2 корови. (Бик "2", корови "4" і "1".)

Перший, хто запропонує супернику загадане число (4 бики) виграє гру.

Версія з словами

У словесну версію зазвичай грають в усній формі. Так само, як і в числовій версії, опонент задумує слово із чотирьох (або іншої кількості) літер. Це повинно бути реальне слово із якої-небудь мови світу.

   Задумане слово: СІНО
   Спроба суперника: СНІГ
   Відповідь: 1 бика і 2 корови. (Бик "С", корови "Н" та "І".)

Версія з кольорами

У грі Mastermind^[1] загадується послідовність з чотирьох кольорових фішок, при чому кольори можуть повторюватися. В ускладненому варіанті використовується більша кількість фішок.

Алгоритм

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

У разі варіанта з повтореннями кількість варіантів дорівнюватиме $N^{k}$ .

Найоптимальнішим алгоритмом вгадування числа є перебір чисел з відкиданням невідповідних варіантів. У зв'язку з тим, що можливих варіантів небагато і схема перебору елементарно реалізується, комп'ютер грає набагато сильніше людини. При чому, чим більше цифр (літер, фішок) у послідовності, тим більша різниця у силі гри людини та комп'ютера.

Наприклад, алгоритм для відгадування чотиризначного числа без повторень:

Побудувати множину S із $A_{10}^{4}={\frac {10!}{(10-4)!}}=5040$ варіантів.
Запропонувати будь-який варіант із множини.
Отримати кількість «биків» та «корів»
Виключити із множини S елементи, які мають іншу кількість «биків» та «корів» із запропонованим варіантом.
Порахувати кількість елементів у множині.
Повторювати алгоритм, починаючи з пункту 2, поки в множині не залишиться один елемент або не буде отримано 4 «бики».

Якщо після пункту 4 отриману порожню множину S, то гравець допустив помилку при підрахунку «биків» та «корів».

Реалізації

Існує безліч варіантів електронної реалізації гри, в тому числі для комп'ютерів та мобільних телефонів.

Fallout 3, Fallout New Vegas, та Fallout 4 — за допомогою міні-версії цієї гри здійснюється хакерський злом комп'ютера.
Sleeping Dogs включає в себе версію гри (з цифрами від 1 до 9) для злому камер безпеки.
Jotto42^[2] — подібна гра зі словами
Mastermind^[1] — подібна гра з кольоровими фішками.

Примітки

↑ ^а ^б ^в Mastermind - apps on Google Play. Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.
↑ Jotto42- apps on Google Play. Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.

Посилання

4digits, an Open Source version of Bulls and Cows [Архівовано 15 травня 2011 у Wayback Machine.]
Page with the PL/1 code for Moo by J.M. Grochow
Description of Bulls and Cows with numbers, and a Web playable version [Архівовано 2 лютого 2017 у Wayback Machine.]
Online version of Bulls and Cows game [Архівовано 10 березня 2016 у Wayback Machine.]
Knuth, D. E. "The Computer as a Master Mind". J. Recr. Math. 9, 1-6, 1976-77
Francis, J. "Strategies for playing MOO, or 'Bulls and Cows'"
Classical version of "Bulls and Cows" game [Архівовано 2 лютого 2017 у Wayback Machine.]
Version of "Bulls and Cows" game in russian [Архівовано 27 квітня 2014 у Wayback Machine.]
Android Play version of the "Bulls and Cows" game, suitable for android 2.1 or above [Архівовано 2 лютого 2017 у Wayback Machine.]
iOS version of the "Bulls and Cows" game + multiplayer mode [Архівовано 2 лютого 2017 у Wayback Machine.]
Atari 8 bit version. [Архівовано 2 лютого 2017 у Wayback Machine.]
"Bulls & Cows" Challenge game in Visual Basic [Архівовано 19 грудня 2021 у Wayback Machine.]
"Sayibul": Bulls and Cows for Windows, freeware, can be played against AI or human opponent in hot seat mode, via LAN or internet [Архівовано 12 серпня 2015 у Wayback Machine.]

Джерела

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