Быки и коровы

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

Правила игры

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

Задумано тайное число «3219».

Попытка номер: «2310».

Результат: две «коровы» (две цифры: "2" и "3" — угаданы на неверных позициях) и один «бык» (одна цифра "1" угадана вплоть до позиции).

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

Реализации

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

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

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

Ссылки

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

Примечания

1. ↑ Игра «Быки и коровы» в среде Microsoft Excel. В мир информатики, № 78.
2. ↑ Mastermind boardgame
3. ↑ Mastermind rules and strategy
4. ↑ Мастермайнд (недоступная ссылка — история)
5. ↑ Mastermind Optimal strategy  (англ.)
6. ↑ Оптимальный алгоритм в игре быки-коровы  (рус.)