Mastermind: логическая игра по подбору кода¶

Mastermind — это настольная логическая игра для двух игроков, в которой один игрок (кодмейкер) загадывает секретную комбинацию из цветных колышков, а второй (кодбрейкер) пытается её отгадать за ограниченное число ходов, получая после каждой попытки оценку в виде чёрных и белых ключевых колышков. Игра относится к классу комбинаторных головоломок и является классическим примером задачи об угадывании кода с обратной связью.

¶Правила игры

Стандартный набор Mastermind включает игровую доску с двумя полями (защищённым экраном для кода и открытым полем для попыток), колышки шести цветов (как правило, красный, синий, зелёный, жёлтый, белый и оранжевый) и ключевые колышки чёрного и белого цвета.

Кодмейкер выбирает четыре цветных колышка и размещает их в ряд за экраном, скрывая от противника. Цвета могут повторяться, что увеличивает число возможных комбинаций. Кодбрейкер делает ход, выставляя на открытом поле свою пробную комбинацию из четырёх колышков. В ответ кодмейкер оценивает попытку, размещая на специальной шкале ключевые колышки: чёрный колышек означает, что один из цветов совпадает с секретным кодом и находится на правильной позиции; белый — что цвет присутствует в коде, но стоит на другой позиции. Порядок ключевых колышков не сообщает, какие именно позиции совпали, — это лишь количественная оценка.

Игра продолжается до тех пор, пока кодбрейкер не выставит комбинацию, полностью совпадающую с кодом (четыре чёрных колышка), либо не исчерпает лимит ходов. В классической версии кодбрейкеру предоставляется 12 попыток. По итогам партии игроки меняются ролями, и победа присуждается тому, кто затратил меньше ходов на разгадывание кода.

¶История создания

Игра была изобретена израильским телекоммуникационным инженером Мордехаем Меиром (Mordecai Meirowitz) в начале 1970-х годов. Первоначально Меиру отказали в патентовании, посчитав игру слишком простой, однако после демонстрации на международной выставке игрушек в Нюрнберге в 1971 году права на неё приобрела компания Invicta Plastics. В 1972 году Mastermind поступил в продажу в Великобритании, а затем и в США, где быстро завоевал популярность. К концу 1970-х годов было продано более 50 миллионов экземпляров игры, что сделало её одной из самых успешных настольных игр своего времени.

Существует версия, что Меир создал игру на основе более ранней бумажной головоломки «Быки и коровы», известной в Европе с XIX века, однако в отличие от неё Mastermind использует цветовые коды и специальную игровую доску, что сделало игру более наглядной и доступной.

¶Математический анализ

Mastermind стал объектом пристального изучения математиков и специалистов по теории игр. В стандартной версии с шестью цветами и четырьмя позициями общее число возможных кодов составляет 6⁴ = 1296 комбинаций (с учётом повторений цветов).

Задача поиска оптимальной стратегии угадывания была решена в 1993 году Дональдом Кнутом, который доказал, что кодбрейкер может гарантированно угадать код не более чем за пять ходов, используя алгоритм, основанный на принципе минимакса. Стратегия Кнута предполагает выбор на каждом шаге такой пробной комбинации, которая в худшем случае сокращает множество возможных кодов максимально. Позднее были найдены стратегии, позволяющие сократить среднее число ходов до 4,34, а в 2018 году исследователи Джефф Иссинг и Тим Райс доказали, что минимальное возможное количество ходов для гарантированного решения составляет пять.

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

¶Стратегии игры

Для практической игры выработаны эвристические стратегии, не требующие сложных вычислений. Одна из распространённых тактик — начинать с комбинации, содержащей все различные цвета, например, красный-синий-зелёный-жёлтый. Это позволяет быстро получить информацию о составе кода. Далее игрок фиксирует цвета, подтверждённые чёрными и белыми колышками, и варьирует их позиции.

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

¶Компьютерные реализации и варианты

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

Существуют многочисленные варианты игры: Mastermind с большим числом цветов (например, 8 цветов и 5 позиций), версии с буквенными или цифровыми кодами, а также трёхмерные и электронные модификации. В 1973 году была выпущена версия для двух игроков-кодмейкеров — «Super Mastermind», а в 2004 году — «Mastermind for Kids» с упрощёнными правилами. Игра также используется в педагогике для развития логического мышления у детей и в курсах информатики для иллюстрации алгоритмов поиска и теории информации.

¶Влияние на культуру

Название игры стало нарицательным: в английском языке слово «mastermind» также означает «гениальный ум» или «руководитель сложной операции». В русскоязычной среде игра известна под названием «Быки и коровы» в бумажном варианте, однако именно Mastermind закрепился как коммерческая настольная версия этой логической задачи. Игра получила множество наград, включая премию «Игра года» в Великобритании в 1973 году, и остаётся одной из самых узнаваемых логических игр в мире.