Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Вдохновитель
Mastermind.jpg
Завершенная игра Mastermind
Дизайнер (ы)Мордехай Мейровиц
Активные годы1970, чтобы представить
Жанр (ы)Настольная игра Игра с
бумагой и карандашом [root]
Игроки2
Время установки<5 минут
Время игры10–30 минут
Случайный шансНезначительный
Возрастной диапазон8 и старше

Mastermind или Master Mind - этоигра с взломом кода для двух игроков. Современная игра с колышками была изобретена в 1970 году Мордехаем Мейровицем , израильским почтмейстером и экспертом по телекоммуникациям. [1] [2] Она напоминает более раннюю игру с карандашом и бумагой под названием « Быки и коровы», которая, возможно, датируется столетием.

Геймплей и правила [ править ]

В игре используются:

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

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

Взломщик кода пытается угадать узор, как по порядку, так и по цвету, за восемь-двенадцать ходов. Каждое предположение делается путем размещения ряда кодовых меток на плате декодирования. После размещения разработчик кода обеспечивает обратную связь, помещая от нуля до четырех ключевых стержней в небольшие отверстия в ряду с предположением. Цветной или черный ключевой стержень помещается для каждого кодового стержня из предположения, которое является правильным как по цвету, так и по положению. Белый штифт указывает на наличие штифта с правильным цветовым кодом, установленного в неправильном положении. [4]

Скриншот программной реализации (ColorCode), иллюстрирующий пример.

Если в предположении присутствуют повторяющиеся цвета, все они не могут быть награждены ключевой привязкой, если они не соответствуют одинаковому количеству повторяющихся цветов в скрытом коде. Например, если скрытым кодом является красный-красный-синий-синий, а игрок угадывает красный-красный-красный-синий, производитель кода присудит два цветных колышка для ключей за два правильных красных, ничего за третий красный, так как нет третий красный в коде и цветной ключ для синего. Нет никаких указаний на то, что код также включает второй синий цвет. [5]

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

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

Могут быть указаны другие правила. [6]

История [ править ]

Игра основана на старой бумажной игре под названием Bulls and Cows . Компьютерная адаптация этого была запущена в 1960 - х годах на Кембриджском университете «s Titan компьютерной системы, где его называли„ИМ“. Эта версия была написана Фрэнком Кингом. Была также другая версия для системы разделения времени TSS / 8, написанная Дж. С. Фелтоном, и, наконец, версия для системы Multics в Массачусетском технологическом институте Джеррольдом Грохоу. [7]

Современная игра с колышками была изобретена в 1970 году Мордехаем Мейровицем , израильским почтмейстером и экспертом по телекоммуникациям. Мейровиц представил идею многим крупным компаниям по производству игрушек, но после демонстрации ее на Международной выставке игрушек в Нюрнберге ее подхватила пластмассовая компания Invicta Plastics , базирующаяся недалеко от Лестера , Великобритания . Invicta приобрела все права на игру, а ее основатель Эдвард Джонс-Фенли усовершенствовал игру. Он был выпущен в 1971–2002 годах. [1] [2] [8]

С 1971 года права на Mastermind принадлежат Invicta Plastics. (Invicta всегда называла игру Master Mind .) Изначально они производили ее сами, хотя с тех пор лицензировали ее производство для Hasbro по всему миру, за исключением Pressman Toys и Orda Industries, которые имеют права на производство в США и Израиле соответственно. [9]

Начиная с 1973 года, на коробке с игрой была фотография мужчины в белом пиджаке, сидящего на переднем плане, с молодой азиатской женщиной из высшей касты, стоящей позади него, с золотыми символами должности, видимыми на ее сари, обозначающими силу и интеллект позади него. трон. Две модели-любители (Билл Вудворд и Сесилия Фанг) воссоединились в июне 2003 года, чтобы позировать для еще одной рекламной фотографии. [10]

Алгоритмы и стратегии [ править ]

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

Лучшие стратегии с четырьмя колышками и шестью цветами [ править ]

С четырьмя колышками и шестью цветами получается 6 4 = 1296 различных узоров (что позволяет дублировать цвета).

Худший случай: алгоритм пяти предположений [ править ]

В 1977 году Дональд Кнут продемонстрировал, что взломщик кода может решить шаблон за пять или меньше ходов, используя алгоритм, который постепенно уменьшает количество возможных шаблонов. [11] Алгоритм работает следующим образом:

  1. Создайте набор S из 1296 возможных кодов (1111, 1112 ... 6665, 6666)
  2. Начните с первоначального предположения 1122 (Кнут приводит примеры, показывающие, что другие первые предположения, такие как 1123, 1234, не дают результата при пяти попытках для каждого кода)
  3. Сыграйте в догадку, чтобы получить ответ из цветных и белых колышков.
  4. Если ответ - четыре цветных колышка, игра выиграна, алгоритм завершается.
  5. В противном случае удалите из S любой код, который не дал бы такой же ответ, если бы это (предположение) был код.
  6. Примените технику минимакса , чтобы найти следующее предположение, следующим образом: для каждого возможного предположения, то есть для любого неиспользуемого кода 1296, а не только кода в S, вычислите, сколько возможностей в S будет исключено для каждого возможного значения цветного / белого колышка. Оценка предположения - это минимальное количество возможностей, которые оно могло бы исключить из S. Один проход через S для каждого неиспользованного кода 1296 предоставит счетчик совпадений для каждого найденного показателя цветного / белого колышка; оценка цветного / белого колышка с наибольшим количеством попаданий устраняет наименьшее количество возможностей; рассчитать оценку предположения, используя «минимальное исключенное количество» = «количество элементов в S» - (минус) «максимальное количество совпадений». Из набора догадок с максимальнойоценки, выберите одно в качестве следующего предположения, по возможности выбирая члена S. (Кнут следует соглашению о выборе предположения с наименьшим числовым значением, например, 2345 ниже, чем 3456. Кнут также приводит пример, показывающий, что в некоторых случаях ни один член S не будет среди предположений с наибольшим количеством очков, и, таким образом, предположение не может выиграть при следующий ход, но еще будет необходимо обеспечить победу через пять.)
  7. Повторите с шага 3.

Средний случай [ править ]

Последующие математики находили различные алгоритмы, которые уменьшали среднее количество оборотов, необходимых для решения модели: в 1993 году Кенджи Кояма и Тони В. Лай провели исчерпывающий поиск в глубину, показав, что оптимальный метод решения случайного кода может обеспечить в среднем 5625/1296 = 4,3403 хода для решения с наихудшим сценарием из шести ходов. [12]

Минимальная ценность теории игр [ править ]

Минимаксное значение в смысле теории игр составляет 5600/1290 = 4,341. Минимаксная стратегия кодмейкера заключается в равномерно распределенном выборе одного из 1290 шаблонов с двумя или более цветами. [13]

Генетический алгоритм [ править ]

Новый алгоритм со встроенным генетическим алгоритмом , в котором большой набор подходящих кодов собирается от разных поколений. Качество каждого из этих кодов определяется на основе сравнения с выбранными элементами подходящего набора. [14] [15] Этот алгоритм основан на эвристике, которая присваивает балл каждой подходящей комбинации на основе ее вероятности того, что она действительно является скрытой комбинацией. Поскольку эта комбинация неизвестна, оценка основывается на характеристиках набора подходящих решений или их выборки, найденной эволюционным алгоритмом.

Алгоритм работает следующим образом:

  1. Установить i = 1
  2. Играть фиксированное начальное предположение G 1
  3. Получите ответ X 1 и Y 1
  4. Повторите, пока X i ≠ P :
    1. Приращение i
    2. Положим E i = ∅ и h = 1.
    3. Инициализировать популяцию
    4. Повторите, пока h ≤ maxgen и | E i | ≤ макс. Размер :
      1. Создание новой популяции с помощью кроссовера, мутации, инверсии и перестановки
      2. Рассчитать фитнес
      3. Добавить подходящие комбинации к E i
      4. Приращение h
    5. Играть угадай G i, принадлежащий E i
    6. Получить ответ X i и Y i

Проблема сложности и выполнимости [ править ]

В ноябре 2004 года Мишель де Бондт доказал, что решение доски Mastermind является NP-полной задачей при игре с n колышками в каждом ряду и двумя цветами, показав, как представить в ней любую задачу 3SAT один из трех . Он также продемонстрировал то же самое для Consistent Mastermind (играя в игру так, чтобы каждое предположение было кандидатом на секретный код, который согласуется с подсказками в предыдущих предположениях). [16]

Проблема выполнимости Mastermind - это проблема принятия решения, которая задает вопрос: «Учитывая набор предположений и количество цветных и белых колышков, набранных для каждого предположения, существует ли хотя бы один секретный шаблон, который генерирует эти точные оценки?» (Если нет, то разработчик кода, должно быть, неправильно оценил хотя бы одно предположение.) В декабре 2005 года Джефф Стакман и Го-Цян Чжан показали в статье arXiv, что проблема выполнимости Mastermind является NP-полной. [17]

Варианты [ править ]

Варьируя количество цветов и количество лунок, вы получаете целый спектр игр Mastermind разного уровня сложности. Другой распространенный вариант - поддержка разного количества игроков, берущих на себя роли кодмейкера и кодировщика. Ниже приведены некоторые примеры игр Mastermind, выпущенных Invicta , Parker Brothers , Pressman , Hasbro и другими производителями игр:

ИграГодЦветаОтверстияКомментарии
Вдохновитель1972 г.64Оригинальная версия
Бублики [18]1972 г.10 цифр3Также можно играть в словесную игру с 2- или 3-значными числами.
Королевский вдохновитель1972 г.5 цветов × 5 форм3
Вдохновитель441972 г.65Для четырех игроков
Великий гений1974 г.5 цветов × 5 форм4
Super Mastermind (он же Deluxe Mastermind ; он же Advanced Mastermind )1975 (в Польше - Copyright Invicta 1972 в сотрудничестве с Krajowa Agencja Wydawnicza [19] )85
Word Mastermind1975 г.26 букв4Только допустимые слова могут использоваться в качестве шаблона и угадываться каждый ход.
Мини-вдохновитель1976 г.64Версия для путешествий; комната только для шести догадок
Number Mastermind1976 г.6 цифр4Использует числа вместо цветов. Изготовитель кода может дополнительно указать сумму цифр в качестве дополнительной подсказки.
Электронный вдохновитель (Invicta)1977 г.10 цифр3, 4 или 5Использует числа вместо цветов. Портативная электронная версия. Один или несколько игроков против компьютера. Фирменный Invicta.
Уолт Дисней вдохновитель1978 г.53Использует персонажей Диснея вместо цветов
Мини-вдохновитель (также известный как вдохновитель путешествий )1988 г.64Версия для путешествий; комната только для шести догадок
Вызов вдохновителя1993 г.85Оба игрока одновременно играют в составитель кода и взломщик кода.
Паркер вдохновитель1993 г.84
Вдохновитель для детей1996 г.63Тема животных
Секретный поиск вдохновителя1997 г.26 букв3-6Только допустимые слова; подсказки даются буква за буквой с использованием стрелок вверх / вниз для более раннего / более позднего в алфавите.
Электронный ручной вдохновитель (Hasbro)1997 г.64Портативная электронная версия. Hasbro.
Новый вдохновитель2004 г.84До пяти игроков
Мини-вдохновитель2004 г.64Автономная версия для путешествий; комната только для восьми догадок

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

Также были созданы компьютерные и интернет-версии игры, иногда с различными количествами и типами задействованных элементов и часто под разными названиями, чтобы избежать нарушения прав на товарный знак. В Mastermind также можно играть с бумагой и карандашом . Существует несколько разновидностей Mastermind, в которых угадывается 4-значное число. [20]

Игра была скомпилирована в Clubhouse Games: 51 Worldwide Classics for the Switch под названием «Hit & Blow». [21]

Ссылки [ править ]

  1. ^ a b Нельсон, Тоби (9 марта 2000 г.). «Краткая история настольной игры Master Mind» . Проверено 6 августа 2014 .
  2. ^ а б «Настольная игра вдохновителя» . Компьютерщик настольной игры . Проверено 6 августа 2014 .
  3. ^ "Трудолюбивый" . Проверено 7 июля 2014 .
  4. ^ "Вольфрам" . Проверено 9 июля 2012 .
  5. ^ «Архимед» . Проверено 7 октября 2012 .
  6. ^ «Быки и коровы и компания» . Проверено 7 июля 2012 .
  7. ^ Фрэнсис, Джон (январь 2010 г.). «Стратегии игры в MOO, или« Быки и коровы » » (PDF) . Архивировано из оригинального (PDF) 25 апреля 2012 года . Проверено 26 декабря 2017 .
  8. ^ "Игрушки и игры Invicta" . 2007-08-12. Архивировано из оригинала на 2007-08-12 . Проверено 26 декабря 2017 .
  9. ^ "Страница истории игрушек Invicta" . Архивировано из оригинала на 2007-08-12 . Проверено 7 августа 2012 .
  10. ^ "Знаковое воссоединение для моделей коробки идейного толка" . Проверено 5 октября 2006 .
  11. ^ Кнут, Дональд (1976–77). «Компьютер как главный разум» (PDF) . J. Recr. Математика. (9): 1–6.
  12. ^ Кояма, Кендзи; Лай, Тони (1993). «Оптимальная стратегия вдохновителя». Журнал развлекательной математики (25): 230–256.
  13. ^ Кнут, Дональд (2011). Избранные статьи о развлечениях и играх . Центр изучения языка и информации. п. 226. ISBN. 9781575865843.
  14. ^ Berghman, Lotte (2007-2008). «Эффективные решения для Mastermind с использованием генетических алгоритмов» (PDF) . KULeuven (1): 1–15.
  15. ^ Мерело, JJ; Мора, AM; Cotta, C .; Рунарссон, Т.П. (2012). «Экспериментальное исследование исчерпывающих решений головоломки Mastermind». arXiv : 1207.1315 . Bibcode : 2012arXiv1207.1315M . Цитировать журнал требует |journal=( помощь )
  16. ^ De Bondt, Михель С. (ноябрь 2004). «NP-полнота Мастера Разума и Сапера» . Radboud University Nijmegen. Цитировать журнал требует |journal=( помощь )
  17. ↑ Mastermind - NP-Complete Проверено 2 сентября 2010 г.
  18. ^ https://www.mobygames.com/game/bagels
  19. ^ "BoardGameGeek" . boardgamegeek.com .
  20. ^ "Быки и коровы Classic" . Архивировано из оригинала на 2011-07-22.
  21. ^ «Nintendo публикует удобную инфографику обо всех 51 всемирно классических клубных играх» . Nintendo Life . Проверено 21 июля 2020 .

Внешние ссылки [ править ]

  • Вдохновитель: подход дополненной реальности, перенос устаревшей игры на новую парадигму взаимодействия
  • Статья Mathworld о Mastermind