Бики і корови - логічна гра, спочатку задумана для двох гравців, але з появою комп'ютерних версій став превалювати варіант, коли один гравець відгадує число, задумане програмою, тобто грає поодинці. Для очної гри удвох досить мати папір і ручку, крім того, в електронних версіях очну або гру на відстані проти супротивника забезпечує функція багатокористувацької гри (multiplayer). Варіанти гри можуть залежати від типу відгадувати послідовності - це можуть бути числа, кольору, піктограми або слова.
У класичному варіанті гра розрахована на двох гравців. Кожен з гравців задумує і записує таємне 4-значний номер з неповторяющимися цифрами [1]. Гравець, який починає гру за жеребом, робить першу спробу відгадати число. Спроба - це 4-значний номер з неповторяющимися цифрами, повідомляється противнику. Противник повідомляє у відповідь, скільки цифр вгадано без збігу з їх позиціями в таємному числі (тобто кількість корів) і скільки вгадано аж до позиції в таємному числі (тобто кількість биків). наприклад:
Задумано таємне число «3219».
Результат: дві «корови» (дві цифри: «2» і «3» - вгадані на невірних позиціях) і один «бик» (одна цифра «1» вгадана аж до позиції).
Гравці роблять спроби вгадати по черзі. Перемагає той, хто вгадає число першим, за умови, що він не починав гру. Якщо ж відгадав починав гру - його противнику надається останній шанс вгадати послідовність.
При грі проти комп'ютера гравець вводить комбінації одну за одною, поки не відгадає всю послідовність.
Існує варіант гри зі словами [джерело не вказано 1331 день]. Тобто гравець загадує слово, зазвичай з 5 букв (в називному відмінку однині за правилами гри «балда»), і завдання противника - вгадати його, використовуючи в якості спроб такі ж коректні слова зі словника російської мови. Однак, існує і варіант, коли можливе використання довільного поєднання букв.
У загальному випадку кількість варіантів для k-значного числа в N-річної системі числення без повторень, буде дорівнює числу розміщень. A N k = N. (N - k). ^ = >>.
У разі варіанта з повтореннями кількість варіантів дорівнюватиме N k>.
Більшість відомих алгоритмів суть варіації алгоритму повного перебору з певною евристикою. У зв'язку з тим, що кількість варіантів не настільки велика і схема прямого перебору елементарно реалізується, комп'ютер грає в «бики й корови» набагато сильніше людини. Чим більше знаків в числі, тим більша різниця в силі гри людини і комп'ютера.
Настільний варіант гри Mastermind для 4 місць і 6 кольорів
Як показав Дональд Кнут. для гри Mastermind (6 4 варіантів) при запропонованої ним стратегії потрібно не більше 5 спроб, щоб відгадати будь-яку комбінацію, а в середньому 4,321 спроб для відгадування [3] [4].
Алгоритм стратегії Кнута наступний:
- Побудувати безліч S з 6 Перша 4 = 1296 можливих кодів (1111, 1112. 6666).
- Зробити перший хід з кодом з двох співпадаючих цифр, наприклад, 1122 (Кнут наводить приклад, що показує, що інші початкові наближення, як то 1123 або 1234, не зможуть завжди вгадувати комбінацію за 5 спроб).
- Якщо комбінація вгадана алгоритм завершується.
- Інакше, видалити з S все коди, які будучи секретним дали б результат, відмінний від отриманого.
- Зробити наступний хід за правилом минимакса.
- Для будь-якої комбінації з 1296 первинних (включаючи ті, яких немає в S) обчислити, скільки можливих кодів буде видалено з S в разі будь-якого результату ходу. Кількість очок нараховується можливого ходу одно мінімальній кількості елементів, які можна буде видалити з S.
- Один прохід по безлічі S для кожної невикористаної комбінації з одна тисяча двісті дев'яносто шість можливих дасть певну кількість корів і биків; комбінація биків і корів з найбільшою кількістю збігів видалить з безлічі найменше варіантів; кількість очок нараховується ходу дорівнюватиме кількість елементів в S мінус найбільшу кількість збігів.
- З усіх ходів з максимальною кількістю очок перевага віддається тому ходу, який є в S. Якщо таких варіантів декілька, то можна вибирати будь-який з них. Для спрощення процедури вибору варіанта, Кнут пропонує вибирати хід з найменшим числовим значенням (наприклад, 2345 менше, ніж 3456).
- Якщо найкращий хід не входить в S, то на наступному ходу гра точно не завершиться.
- Повторити, починаючи з пункту 3.
Настільні ігри Mastermind популярні в усьому світі. Найбільш поширені варіації:
- класична, чотири що не повторюються цифри.
- звичайна, 4 місця для фішок 6 кольорів з повтореннями.
- просунута, 5 місць для фішок 8 кольорів [джерело не вказано тисячу вісімсот п'ятьдесят шість днів].
- У комп'ютерній грі «Sleeping Dogs» гра «Бики і корови» служить імітацією злому комп'ютерних поліцейських мереж.
- В іграх Fallout 3. Fallout New Vegas і Fallout 4 процес злому комп'ютерних терміналів є різновидом гри «Бики і корови», в якій при невдалій спробі повідомляється тільки кількість "биків" [5].
- Кандидат технічних наук Е. Гик. Бики і корови. «Наука і життя», № 2, 1978, с. 150-151; № 8, 1978, с. 142-143.
- Чарльз Уезерелл. Етюди з програмування, Великий комбінатор. М. 1982, с. 140.