Быки и коровы

Быки и коровы — логическая игра для двоих игроков. Для игры достаточно иметь бумагу, ручку и уметь считать. Также игра может называться «цифры» или "цвета".

Правила игры

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

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

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

Вариации игры

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

В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек^{[неавторитетный источник? 398 дней]}.

Существует вариант^{[неавторитетный источник? 398 дней]} игры со словами. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «балда»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка. Известное слово из 4 букв для подлавливания новичков — «эльф»: в нём три буквы из четырёх крайне редкие, и неопытный игрок может сделать много ходов, прежде чем добьётся хотя бы «коровы».

Алгоритм

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

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

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

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

Как показал Дональд Кнут, для игры Mastermind (6⁴ вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, и в среднем 4,34 попыток для отгадывания.

В классическом случае игры с четырьмя не повторяющимися цифрами для отгадывания любого номера требуется не более семи ходов. Средняя минимальная длина игры составляет 26274/5040=5.2131 попытки.

Реализации

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

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

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

Ссылки

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