Быки и коровы
| Быки и коровы | |
 Скриншот компьютерной версии игры. Партия выиграна за семь ходов | |
| Игроков |
2 |
|---|---|
| Длительность партии |
5-30 минут |
| Сложность правил |
Низкая |
| Уровень стратегии |
Низкая |
| Влияние случайности |
Среднее |
| Развивает навыки |
Счёт, Память |
Быки и коровы — логическая игра, первоначально задуманная для двух игроков, но с появлением компьютерных версий стал превалировать вариант, когда один игрок отгадывает число, задуманное программой, то есть играет в одиночку. Для очной игры вдвоем достаточно иметь бумагу и ручку, кроме того, в электронных версиях очную или игру на расстоянии против противника обеспечивает функция многопользовательской игры (multiplayer). Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова.
Содержание
Правила игры
В классическом варианте игра рассчитана на двух игроков. Каждый из игроков задумывает и записывает тайное 4-значное число с неповторяющимися цифрами[1]. Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков). Например:
Задумано тайное число «3219».
Попытка: «2310».
Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции).
Игроки делают попытки угадать по очереди. Побеждает тот, кто угадает число первым, при условии, что он не начинал игру. Если же отгадавший начинал игру — его противнику предоставляется последний шанс угадать последовательность.
При игре против компьютера игрок вводит комбинации одну за другой, пока не отгадает всю последовательность.
Вариации игры
В игре «мастермайнд» (англ. Mastermind, возможный перевод: «Интеллектуал, умник») загадывается последовательность из 4 цветных фишек, причём цвета могут повторяться. В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек[2]
Существует вариант игры со словами. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «балда»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка. Однако, существует и вариант, когда возможно использование произвольного сочетания букв.
Алгоритм
В общем случае количество вариантов для k-значного числа в N-ричной системе счисления без повторений, будет равно числу размещений: <math> A_N^k = \frac{N!}{(N-k)!} </math>.
В случае варианта с повторениями количество вариантов будет равно <math> N^k </math>.
Большинство известных алгоритмов суть вариации алгоритма полного перебора с определённой эвристикой. В связи с тем, что количество вариантов не столь велико и схема прямого перебора элементарно реализуется, компьютер играет в «быки и коровы» намного сильнее человека. Чем больше знаков в числе, тем больше разница в силе игры человека и компьютера.
Как показал Дональд Кнут, для игры Mastermind (64 вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, а в среднем 4,321 попыток для отгадывания[3][4].
Алгоритм стратегии Кнута следующий:
- Построить множество S из 64 = 1296 возможных кодов (1111, 1112, ..., 6666).
- Сделать первый ход с кодом из двух совпадающих цифр, например, 1122 (Кнут приводит пример, показывающий, что другие начальные приближения, как то 1123 или 1234, не смогут всегда угадывать комбинацию за 5 попыток).
- Если комбинация угадана алгоритм завершается.
- Иначе, удалить из S все коды, которые будучи секретным дали бы результат, отличный от полученного.
- Сделать следующий ход по правилу минимакса:
- Для любой комбинации из 1296 первоначальных (включая те, которых нет в S) вычислить, сколько возможных кодов будет удалено из S в случае любого результата хода. Количество очков начисляемое возможному ходу равно минимальному количеству элементов, которые можно будет удалить из S.
- Один проход по множеству S для каждой неиспользовавшейся комбинации из 1296 возможных даст определённое количество коров и быков; комбинация быков и коров с наибольшим количеством совпадений удалит из множества меньше всего вариантов; количество очков начисляемое ходу будет равно количество элементов в 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.
Примечания
- ↑ [inf.1september.ru/2006/19/06.htm Игра «Быки и коровы» в среде Microsoft Excel]. В мир информатики, № 78.
- ↑ [www.tnelson.demon.co.uk/mastermind/ Investigations into the Master MindTM Board Game]
- ↑ [mathworld.wolfram.com/Mastermind.html Mastermind Optimal strategy] (англ.)
- ↑ Knuth Donald. Selected papers on fun and games. — Center for the Study of Language and Information, 2011. — P. 226. — ISBN 9781575865843.
- ↑ [ru.fallout.wikia.com/wiki/Взлом_терминала "Взлом терминала"].
Отрывок, характеризующий Быки и коровы
Князь Андрей, видя настоятельность требования отца, сначала неохотно, но потом все более и более оживляясь и невольно, посреди рассказа, по привычке, перейдя с русского на французский язык, начал излагать операционный план предполагаемой кампании. Он рассказал, как девяностотысячная армия должна была угрожать Пруссии, чтобы вывести ее из нейтралитета и втянуть в войну, как часть этих войск должна была в Штральзунде соединиться с шведскими войсками, как двести двадцать тысяч австрийцев, в соединении со ста тысячами русских, должны были действовать в Италии и на Рейне, и как пятьдесят тысяч русских и пятьдесят тысяч англичан высадятся в Неаполе, и как в итоге пятисоттысячная армия должна была с разных сторон сделать нападение на французов. Старый князь не выказал ни малейшего интереса при рассказе, как будто не слушал, и, продолжая на ходу одеваться, три раза неожиданно перервал его. Один раз он остановил его и закричал:– Белый! белый!
Это значило, что Тихон подавал ему не тот жилет, который он хотел. Другой раз он остановился, спросил:
– И скоро она родит? – и, с упреком покачав головой, сказал: – Нехорошо! Продолжай, продолжай.
В третий раз, когда князь Андрей оканчивал описание, старик запел фальшивым и старческим голосом: «Malbroug s'en va t en guerre. Dieu sait guand reviendra». [Мальбрук в поход собрался. Бог знает вернется когда.]
Сын только улыбнулся.
– Я не говорю, чтоб это был план, который я одобряю, – сказал сын, – я вам только рассказал, что есть. Наполеон уже составил свой план не хуже этого.
– Ну, новенького ты мне ничего не сказал. – И старик задумчиво проговорил про себя скороговоркой: – Dieu sait quand reviendra. – Иди в cтоловую.
В назначенный час, напудренный и выбритый, князь вышел в столовую, где ожидала его невестка, княжна Марья, m lle Бурьен и архитектор князя, по странной прихоти его допускаемый к столу, хотя по своему положению незначительный человек этот никак не мог рассчитывать на такую честь. Князь, твердо державшийся в жизни различия состояний и редко допускавший к столу даже важных губернских чиновников, вдруг на архитекторе Михайле Ивановиче, сморкавшемся в углу в клетчатый платок, доказывал, что все люди равны, и не раз внушал своей дочери, что Михайла Иванович ничем не хуже нас с тобой. За столом князь чаще всего обращался к бессловесному Михайле Ивановичу.
В столовой, громадно высокой, как и все комнаты в доме, ожидали выхода князя домашние и официанты, стоявшие за каждым стулом; дворецкий, с салфеткой на руке, оглядывал сервировку, мигая лакеям и постоянно перебегая беспокойным взглядом от стенных часов к двери, из которой должен был появиться князь. Князь Андрей глядел на огромную, новую для него, золотую раму с изображением генеалогического дерева князей Болконских, висевшую напротив такой же громадной рамы с дурно сделанным (видимо, рукою домашнего живописца) изображением владетельного князя в короне, который должен был происходить от Рюрика и быть родоначальником рода Болконских. Князь Андрей смотрел на это генеалогическое дерево, покачивая головой, и посмеивался с тем видом, с каким смотрят на похожий до смешного портрет.
– Как я узнаю его всего тут! – сказал он княжне Марье, подошедшей к нему.
Княжна Марья с удивлением посмотрела на брата. Она не понимала, чему он улыбался. Всё сделанное ее отцом возбуждало в ней благоговение, которое не подлежало обсуждению.
– У каждого своя Ахиллесова пятка, – продолжал князь Андрей. – С его огромным умом donner dans ce ridicule! [поддаваться этой мелочности!]
Княжна Марья не могла понять смелости суждений своего брата и готовилась возражать ему, как послышались из кабинета ожидаемые шаги: князь входил быстро, весело, как он и всегда ходил, как будто умышленно своими торопливыми манерами представляя противоположность строгому порядку дома.
В то же мгновение большие часы пробили два, и тонким голоском отозвались в гостиной другие. Князь остановился; из под висячих густых бровей оживленные, блестящие, строгие глаза оглядели всех и остановились на молодой княгине. Молодая княгиня испытывала в то время то чувство, какое испытывают придворные на царском выходе, то чувство страха и почтения, которое возбуждал этот старик во всех приближенных. Он погладил княгиню по голове и потом неловким движением потрепал ее по затылку.
– Я рад, я рад, – проговорил он и, пристально еще взглянув ей в глаза, быстро отошел и сел на свое место. – Садитесь, садитесь! Михаил Иванович, садитесь.
Он указал невестке место подле себя. Официант отодвинул для нее стул.
– Го, го! – сказал старик, оглядывая ее округленную талию. – Поторопилась, нехорошо!
Он засмеялся сухо, холодно, неприятно, как он всегда смеялся, одним ртом, а не глазами.
– Ходить надо, ходить, как можно больше, как можно больше, – сказал он.
Маленькая княгиня не слыхала или не хотела слышать его слов. Она молчала и казалась смущенною. Князь спросил ее об отце, и княгиня заговорила и улыбнулась. Он спросил ее об общих знакомых: княгиня еще более оживилась и стала рассказывать, передавая князю поклоны и городские сплетни.
– La comtesse Apraksine, la pauvre, a perdu son Mariei, et elle a pleure les larmes de ses yeux, [Княгиня Апраксина, бедняжка, потеряла своего мужа и выплакала все глаза свои,] – говорила она, всё более и более оживляясь.
По мере того как она оживлялась, князь всё строже и строже смотрел на нее и вдруг, как будто достаточно изучив ее и составив себе ясное о ней понятие, отвернулся от нее и обратился к Михайлу Ивановичу.
– Ну, что, Михайла Иванович, Буонапарте то нашему плохо приходится. Как мне князь Андрей (он всегда так называл сына в третьем лице) порассказал, какие на него силы собираются! А мы с вами всё его пустым человеком считали.
Михаил Иванович, решительно не знавший, когда это мы с вами говорили такие слова о Бонапарте, но понимавший, что он был нужен для вступления в любимый разговор, удивленно взглянул на молодого князя, сам не зная, что из этого выйдет.
