Быки и коровы

Быки и коровы — логическая игра для двоих игроков. Для игры достаточно иметь бумагу, ручку и уметь считать.

Также игра может называться «цифры» или «цвета». В настольном варианте известна как «Mastermind».

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

Например: Задумано тайное число «3219». Попытка: «2310». Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции). Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым.

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

В общем случае количество вариантов для k-значного числа в N-ричной системе счисления без повторений, будет равно числу размещений: Akn = n!/(n-k)!. В случае варианта с повторениями количество вариантов будет равно n^k. Большинство известных алгоритмов суть вариации алгоритма полного перебора с определённой эвристикой. В связи с тем, что количество вариантов не столь велико и схема прямого перебора элементарно реализуется, компьютер играет в «быки и коровы» намного сильнее человека. Чем больше знаков в числе, тем больше разница в силе игры человека и компьютера.

Как показал Дональд Кнут, для игры Mastermind (64 вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, и в среднем 4,34 попыток для отгадывания. В классическом случае игры с четырьмя не повторяющимися цифрами для отгадывания любого номера требуется не более семи ходов. Средняя минимальная длина игры составляет 26274/5040=5.2131 попытки.

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

• классическая (на бумаге), четыре неповторяющиеся цифры.
• обычная, 4 места для фишек 6 цветов с повторениями.
• продвинутая, 5 мест для фишек 8 цветов.

Игра "Быки и коровы" в Википедии