stringtranslate.com

Мастермайнд (настольная игра)

Mastermind или Master Mind ( ивр . בול פגיעה , романизировано :  bul pgi'a ) — игра по взлому кодов для двух игроков, изобретенная в Израиле . [1] [2] Она напоминает более раннюю игру с карандашом и бумагой под названием «Быки и коровы» , которая, возможно, существует столетие.

История

Оригинальный игровой набор Invicta

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

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

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

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

Игровой процесс и правила

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

Два игрока заранее решают, сколько игр они будут играть, и это должно быть четное число . Один игрок становится шифровальщиком , другой — дешифровальщиком . [8] : 120  Кодовик выбирает шаблон из четырех кодовых штифтов. Игроки заранее решают, разрешены ли дубликаты и пробелы. Если да, то кодовик может выбрать до четырех кодовых штифтов одного цвета или четыре пробела. Если пробелы в коде не допускаются, дешифровщик не может использовать пробелы в своих догадках. Кодовик помещает выбранный шаблон в четыре отверстия, закрытые щитом, видимым кодовику, но не дешифровальщику. [9]

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

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

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

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

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

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

Алгоритмы и стратегии

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

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

При наличии четырех отверстий и шести цветов получается 6 · 4 = 1296 различных узоров (допускаются повторяющиеся цвета, но не пробелы).

Худший случай: алгоритм пяти попыток

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

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

Средний случай

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

Минимаксное значение теории игр

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

Генетический алгоритм

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

Алгоритм работает следующим образом, где P = длина решения, используемого в игре, X 1 = точные совпадения («красные кегли») и Y 1 = близкие совпадения («белые кегли»):

  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 | ≤ maxsize :
      1. Генерация новой популяции с использованием кроссинговера, мутации, инверсии и перестановки
      2. Рассчитать пригодность
      3. Добавить подходящие комбинации в E i
      4. Приращение ч
    5. Играйте, угадайте G i , который принадлежит E i
    6. Получить ответ X i и Y i

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

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

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

Вариации

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

Игра Invicta Electronic Master Mind

Существовала также версия под названием Super Code, выпускавшаяся в Восточной Германии компанией VEB Plasticart .

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

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

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

Обзоры

Смотрите также

Пояснительные записки

  1. ↑ Адаптировано для домашнего компьютера ZX81 компанией Vortex Software в 1981 году. [23]

Ссылки

  1. ^ ab Nelson, Toby (9 марта 2000 г.). "Краткая история настольной игры Master MindTM". Архивировано из оригинала 6 сентября 2015 г. Получено 6 августа 2014 г.{{cite web}}: CS1 maint: неподходящий URL ( ссылка )
  2. ^ ab "Mastermind Board Game". Board Game Geek . Получено 6 августа 2014 г.
  3. ^ "Invicta Toys and Games". 12 августа 2007 г. Архивировано из оригинала 12 августа 2007 г. Получено 26 декабря 2017 г.
  4. ^ Томпсон, К.; Ритчи, Д.М. (3 ноября 1971 г.). Руководство программиста Unix (1-е изд.). Мюррей-Хилл, Нью-Джерси, США: Bell Telephone Laboratories.
  5. ^ Фрэнсис, Джон (январь 2010 г.). «Стратегии игры в MOO, или «Быки и коровы»» (PDF) . Архивировано из оригинала (PDF) 25 апреля 2012 г. . Получено 26 декабря 2017 г. .
  6. ^ "Страница истории игрушек Invicta". Архивировано из оригинала 12 августа 2007 года . Получено 7 августа 2012 года .
  7. ^ "Знаменательное воссоединение для Mastermind Box Models". Invicta Plastics. Июнь 2003 г. Архивировано из оригинала 29 июня 2004 г.
  8. ^ ab Fullerton, Tracy (2008). Мастерская игрового дизайна (2-е изд.). Morgan Kaufmann Publishers . ISBN 978-0-240-80974-8.
  9. ^ "Industrious" . Получено 7 июля 2014 г. .
  10. ^ "Wolfram" . Получено 9 июля 2012 г. .
  11. ^ "Архимед" . Получено 7 октября 2012 г.
  12. ^ "Bulls and Cows & co" . Получено 7 июля 2012 г.
  13. ^ Кнут, Дональд (1976–1977). «Компьютер как высший разум» (PDF) . J. Recr. Math. (9): 1–6. Архивировано (PDF) из оригинала 4 марта 2016 г.
  14. ^ Кояма, Кэндзи; Лай, Тони (1993). «Оптимальная стратегия гениального гения». Журнал занимательной математики (25): 230–256.
  15. ^ Кнут, Дональд (2011). Избранные статьи о развлечениях и играх . Центр изучения языка и информации. стр. 226. ISBN 9781575865843.
  16. ^ Бергман, Лотте (2007–2008). «Эффективные решения для Mastermind с использованием генетических алгоритмов» (PDF) . KULeuven (1): 1–15. Архивировано из оригинала (PDF) 9 сентября 2014 г.
  17. ^ Merelo JJ; Mora AM; Cotta C.; Fernández-Leiva AJ (2013). «Поиск эволюционного решения для игры Mastermind с хорошим поведением масштабирования». В Nicosia, G.; Pardalos, P. (ред.). Обучение и интеллектуальная оптимизация . Конспект лекций по информатике. Том 7997. Springer. стр. 288–293. doi :10.1007/978-3-642-44973-4_31. ISBN 978-3-642-44973-4. Получено 22 декабря 2021 г. .
  18. ^ Де Бондт, Мишель К. (ноябрь 2004 г.), NP-полнота главного разума и сапера, Университет Радбауд в Неймегене
  19. ^ Чжан, Го-Цян; Стакман, Джефф (13 декабря 2005 г.). «Mastermind — это NP-полная задача». arXiv : cs.CC/0512049 .
  20. ^ "Бублики (1972)".
  21. ^ В Польше - авторские права Invicta, 1972 г., в сотрудничестве с Krajowa Agencja Wydawnicza "BoardGameGeek". boardgamegeek.com .
  22. ^ «Вдохновитель слова (1972)».
  23. ^ "Vortex Software – Company". Центр истории вычислений . 26 февраля 2018 г.
  24. ^ "Bulls and Cows Classic". Архивировано из оригинала 22 июля 2011 года.
  25. ^ Пизани, Джозеф (31 января 2022 г.). «Wordle Has People Digging Out Old Games. Mastermind или Jotto, Anyone?». The Wall Street Journal . Dow Jones & Company, Inc. Получено 19 февраля 2023 г. 31 января 2022 г. 9:00 по восточному времени Поклонники Wordle возвращаются к детским играм, включая Mastermind, которая проверяет логические навыки игроков с помощью цветовых кодов, подобно тому, как Wordle делает со словами и буквами.
  26. ^ "Nintendo делится удобной инфографикой, включающей все 51 классическую игру Clubhouse по всему миру". Nintendo Life . 25 мая 2020 г. Получено 21 июля 2020 г.
  27. ↑ "GAMES Magazine #3". Январь 1978.
  28. ^ "Games and Puzzles 1973-04: Iss 12". AHC Publications. Апрель 1973.
  29. ^ "GAMES Magazine #20". Ноябрь 1980.
  30. ^ "Games and Puzzles March-April 1974: Iss 23". AHC Publications. Март 1974.
  31. ^ «Руководство по настольным играм для победителей Playboy». 18 ноября 1979 г.
  32. ^ Лоудер, Джеймс (2010). Семейные игры: 100 лучших. Зеленый Ронин. ISBN 978-1-934547-21-2.

Внешние ссылки