Просмотр кода страницы Быки и коровы

{{Настольная_игра| subject_name = Быки и коровы
| image_link = 4digits 0.4 screenshot.png
| image_caption = Скриншот компьютерной версии игры. Партия выиграна за семь ходов
| players = 2
| ages = 
| setup_time = 
| playing_time = 5-30 минут
| complexity= Низкая
| strategy = Низкая
| random_chance = Низкое
| skills = логичность мышления, счёт, память
| footnotes =
}}
'''Быки и коровы''' — логическая игра, в ходе которой за несколько попыток один из игроков должен определить, что задумал другой игрок. Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова. После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»). Роли участников игры не равнозначны — угадывающий должен анализировать сделанные попытки и полученные оценки, то есть его роль активна. Его партнёр лишь сравнивает очередной вариант с задуманным и выставляет оценку по формальным правилам, то есть его роль пассивна. Для уравновешивания ролей одновременно играют две встречные партии.

Первоначально игра была задумана для двух игроков, но с появлением компьютерных версий стал популярен вариант, когда игрок отгадывает число, задуманное программой, то есть играет в одиночку. Для игры вдвоем достаточно иметь бумагу и ручку. В электронных версиях игру на расстоянии против противника обеспечивает функция многопользовательской игры (multiplayer).

== Правила игры ==
В классическом варианте игра рассчитана на двух игроков. Каждый из игроков задумывает и записывает тайное 4-значное число с неповторяющимися цифрами<ref>[http://inf.1september.ru/2006/19/06.htm Игра «Быки и коровы» в среде Microsoft Excel] {{Wayback|url=http://inf.1september.ru/2006/19/06.htm |date=20090201022105 }}. ''В мир информатики'', № 78.</ref><!--в источнике не совсем так — Ldv1970, 02.02.2011-->. Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков). Например:

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

Попытка: «2310».

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

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

При игре против компьютера игрок вводит комбинации одну за другой, пока не отгадает всю последовательность.

== Вариации игры ==
В игре «мастермайнд» ({{lang-en|Mastermind}}, возможный перевод: «Интеллектуал, умник») загадывается последовательность из 4 цветных фишек, причём цвета могут повторяться. В усложнённом варианте может использоваться последовательность из 5, 6 или большего количества фишек<ref>{{Cite web |url=http://www.tnelson.demon.co.uk/mastermind/ |title=Investigations into the Master MindTM Board Game |access-date=2013-09-21 |archive-date=2013-10-28 |archive-url=https://web.archive.org/web/20131028040435/http://www.tnelson.demon.co.uk/mastermind/ |deadlink=no }}</ref>

Существует вариант игры со словами<ref>Д. В. Любич, ''Лингвистические игры'', 1998, стр. 47</ref><ref>Алеф, вып. 1990, стр. 45</ref><ref>Т. Н. Образцова, ''Логические игры для детей'', 2005</ref>. То есть игрок загадывает слово, обычно из 5 букв (в именительном падеже единственном числе по правилам игры «[[Балда (игра)|балда]]»), и задача противника — угадать его, используя в качестве попыток такие же корректные слова из словаря русского языка. Однако, существует и вариант, когда возможно использование произвольного сочетания букв. С распространением персональных компьютеров появились программные реализации игры «Быки и коровы» со словами<ref>Г. Е. Сенкевич, ''Компьютер для людей с ограниченными возможностями'', 2014, стр. 218</ref>. Игра используется в [[специальная педагогика|специальной педагогике]]<ref>Ж. М. Глозман, А. Е. Соболева (ред.), ''Комплексная коррекция трудностей обучения в школе'', 2014, стр. 242</ref> и при обучении информатике<ref>Л. Босова, Н. Нателаури (ред.), ''Актуальные проблемы методики обучения информатике в современной школе'', 2020</ref>. В 2021 году в мире распространилась компьютерная реализация игры с пятибуквенными словами английского языка [[Wordle]], привлёкшая внимание прессы.

== Алгоритм ==
В общем случае количество вариантов для k-значного числа в N-ричной [[Система счисления|системе счисления]] без повторений, будет равно числу [[размещение|размещений]]:
<math> A_N^k = \frac{N!}{(N-k)!} </math>.

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

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

[[Файл:Mastermind.jpg|thumb|upright|Настольный вариант игры Mastermind для 4 мест и 6 цветов]]

Как показал [[Кнут, Дональд Эрвин|Дональд Кнут]], для игры Mastermind (6<sup>4</sup> вариантов) при предложенной им стратегии нужно не более 5 попыток, чтобы отгадать любую комбинацию, а в среднем 4,321 попыток для отгадывания<ref>[http://mathworld.wolfram.com/Mastermind.html Mastermind Optimal strategy] {{Wayback|url=http://mathworld.wolfram.com/Mastermind.html |date=20080914005838 }} {{ref-en}}</ref><ref>{{книга |заглавие=Selected papers on fun and games |издательство=Center for the Study of Language and Information |год=2011 |isbn=9781575865843 |страницы=226 |язык=en |автор=Knuth, Donald}}</ref>.

Алгоритм стратегии Кнута следующий:
#Построить множество S из 6<sup>4</sup> = 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 цветов{{Нет АИ|14|4|2012}}.

== В культуре ==
{{неупорядоченный список|дата=2020-04-21}}
* В ряде компьютерных игр (например, [[Sleeping Dogs]], серии игр [[Fallout (серия игр)|Fallout]] и других) различные вариации игра «Быки и коровы» являются головоломками в ходе игрового процесса. Это может быть как обязательной задачей, так и необязательной веткой прохождения или получения дополнительных бонусов.

== См. также ==
* [[Wordle]]

== Примечания ==
{{примечания|2}}

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

[[Категория:Игры на бумаге]]
[[Категория:Игры на отгадывание]]
[[Категория:Логические игры]]