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

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

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

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

Правила гри

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

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

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

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

Наприклад:

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

Реалізації

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

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

Примітки

1. . Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.
2. . Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.

Посилання

• 4digits, an Open Source version of Bulls and Cows [ 15 травня 2011 у Wayback Machine.]
• 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.]
• 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.