Библиотека Ad Astras' Site book.adastras.de - Главная страница

Mastermind - Мастермайнд

НАВИГАЦИЯ

   Главная > Игры > На отгадывание > Mastermind

Происхождение

Правила

Варианты игры

Пример игры

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

HangmanHelper

Игры off-line
Игры on-line
 
Счётчики

Counter CO.KZ


Мастермайнд
– относится к группе логических (стратегических, настольных) игр на отгадывание. Чтобы играть в неё, достаточно карандаша и бумаги (желательно в клеточку).Это одна из наиболее популярных игр во многих странах мира. Развивает логическое мышление.

Замечание. В "фирменной" игре используется специальная доска с отверстиями и колышки разных цветов:



Но, при желании, их нетрудно заменить таблицей на бумаге и буквами.

"Фирменная" игра стоимостью 9долларов 95 центов :


Замечание. Если вам не по душе такое суррогатное решение, поиграйте в другой вариант этой игры, который называется "Быки и коровы" и больше распространён в России, чем Мастермайнд. В нём нужно отгадать задуманное 4-значное число, а не комбинацию цветных фишек. Вот тут уж вполне можно обойтись карандашом и бумагой!

Происхождение игры

Игру придумал в 1973 году проживавший тогда в Париже израильтянин Марко (Мордекай) Мейровиц (Marco (Mordecai) Meirovitz). В основе её лежит компьютерная (!) игра moo, написанная ещё в 60-х годах. По другой версии, Мастермайнд - только разновидность старой английской игры игры "Быки и коровы" (bulls and cows).'
Её называют также "
Mastermind" (оригинальное название) и "Мыслитель", "Мастер мысли" (русское переложение предыдущего названия). Поскольку название "Mastermind" является торговой маркой фирмы Invicta Plastics, то игра известна и под другим названием - Mind Game. Немцы называют её так – "Superhirn" или "Variablo".

Правила игры

Играют двое. Один загадывает комбинацию цветных фишек (или колышков).

Для стандартной игры используют фишки 6 разных цветов - красные, жёлтые, синие, зелёные, белые и чёрные. Первый игрок (codemaker) составляет ряд из 4-х фишек (цвета фишек могут повторяться!). Второму игроку (codebreaker) , естественно, эта комбинация фишек неизвестна. Он старается отгадать её за наименьшее число ходов (это имеет смысл при игре вдвоём; если противником является компьютер или электронная игра, то на разгадывание даётся 10 ходов).
Ход состоит в том, что отгадчик называет свою комбинацию фишек, а загадчик объявляет результат хода. Тут также используются фишки (колышки) - двух цветов и меньшего размера. Чёрные фишки обозначают совпадение в цвете и позиции (в игре
"Быки и коровы" эта ситуация называется бык - bull), белые - только в цвете (корова - cow'). Количество этих фишек равно числу совпадений, а порядок их следования в ответе значения не имеет.
Например,
загадана такая комбинация фишек:



Сделав два хода, мы должны получить следующие результаты:

В первом случае две зелёные фишки стоят на своих местах, а остальных двух зелёных фишек в задуманной комбинации нет вообще! Иначе получилось бы, что загадано 4 зелёные фишки, из которых две стоят «правильно» и ещё две - «неправильно».
Во втором случае одна синяя фишка в нашей комбинации занимает неверное место, а остальных также нет.

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


Количество фишек в ответе - от 0 до 4. Если в ответе нет ни чёрных, ни белых фишек, то в комбинации-догадке нет ни одной из тех фишек, что имеются в загаданной комбинации. Если в ответ получена одна белая фишка, то одна из фишек в комбинации-догадке имеется и в загаданной комбинации, но стоит на другом месте. И так далее. Важно помнить, что порядок фишек в ответе произвольный, и если на первом месте выставлена чёрная фишка, это вовсе не значит, что фишки совпали именно в этой позиции!

Замечание. В компьютерных реализациях игры иногда просто указывают число чёрных и белых фишек, а не сами фишки... дабы не искушать.

Замечание. Правила игры по-английски и по-немецки:

For those of you who may not be familiar with the game of Mastermind, quite simply it's a codebreaking challenge. The first player uses colored pegs to set up a secret code. Their opponent tries to break the code using clues supplied by the codemaker. It's a game of strategy and perhaps a little luck. For two players ages 8 and up.
 

The game is played using:
  • a decoding board, with a shield at one end covering a row of four large holes, and ten additional rows containing four large holes next to a set of four small holes;
  • code pegs of six different colors, with round heads, which will be placed in the large holes on the board; and
  • key pegs, some colored, some white, which are flat-headed and smaller than the code pegs; they will be placed in the small holes on the board.

The two players decide in advance how many games they will play, which must be an even number. One player becomes the codemaker, the other the codebreaker. The codemaker chooses a pattern of four code pegs. Duplicates are allowed, i.e. the player could even choose four code pegs of the same color. The chosen pattern is placed in the four holes covered by the shield, visible to the codemaker but not to the codebreaker.

The codebreaker tries to guess the pattern, in both order and color, within ten turns. Each guess is made by placing a row of code pegs on the decoding board. Once placed, the codemaker provides feedback by placing from zero to four key pegs in the small holes of the row with the guess. A colored key peg is placed for each code peg from the guess which is correct in both color and position; a white peg indicates the existence of a correct color peg placed in the wrong position. Once feedback is provided, another guess is made; guesses and feedback continue to alternate until either the codebreaker guesses correctly, or ten incorrect guesses are made.

The codemaker gets one point for each guess a codebreaker makes. The winner is the one who has the most points after the agreed-upon number of games are played.

Der eine Spieler wählt zu Beginn einen vierstelligen Farbcode aus, wobei sechs verschiedene Farben zur Verfügung stehen, die auch mehrfach verwendet werden können. Der andere Spieler versucht den Code zu erraten. Als Hilfestellung bekommt er nach jedem Zug die Information, wie viele Stifte er in Farbe und Position richtig gesetzt hat, und wie viele Stifte zwar die richtige Farbe haben, aber an einer falschen Position stehen. Ein Treffer in Farbe und Position wird durch einen schwarzen Stift angezeigt, ein lediglich in der Farbe übereinstimmender Stift wird durch einen weißen Stift angezeigt.

(en.wikipedia.org)

Игра заканчивается, если

- загаданная комбинация найдена;
- отгадчик использовал все отведённые ходы, но комбинацию не назвал.

 

Варианты игры

В классическом варианте игры каждая комбинация содержит 4 из 6 возможных цветов. В игре Super MasterMind это 5 из 8 цветов.
Если через
L обозначить длину цепочки, а через N количество различных цветов, то в первом случае L = 4, N = 6, во втором - L = 5, N = 8.
Тогда число возможных комбинаций в игре легко вычислить по формуле
N L. Рассмотренные варианты, таким образом, имеют 1296 и 32768 различных  цепочек.

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

Замечание. Можно начислять очки и иначе. Из 10 вычитать количество сделанных ходов. Тогда, естественно, победит тот, у кого очков больше.

Пример игры

Продолжим игру, начатую ранее.

Beispiel-Stellung nach dem 2. Versuch

Gesucht ist der Farbcode:

grün - rot - blau - grün

1. Rateversuch: rot - gelb - rot - grün

Antwort: Einmal schwarz (weil an der vierten Position grün richtig ist), einmal weiß. (weil rot im gesuchten Code einmal vorkommt, aber nicht an der ersten oder dritten Stelle)

2. Rateversuch: grün - grün - orange - rot

Antwort: Einmal schwarz (weil grün diesmal an der ersten Position richtig ist), zweimal weiß. (weil 1. grün im gesuchten Code ein zweites mal vorkommt, aber nicht an der zweiten Position und 2. rot im gesuchten Code vorkommt, aber nicht an der vierten Position)

Wenn der gesuchte Farbcode richtig geraten wird, lautet die Antwort viermal schwarz.

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

Известно, что для отгадывания любой комбинации достаточно 5 ходов. Это было показано в статье в журнале Journal of Recreational  Mathematics. Затем Дональд Кнут (Donald E. Knuth. The Computer as Master Mind. J. Recreational  Mathematics, 9 (1976-77), 1-6) нашёл алгоритм с наименьшим числом ходов для решения всех 1296 комбинаций, но некоторые из них требовали 6 ходов (в среднем 4.478 хода). Этот результат улучшили Irving и Neuwirth - до 4.364. В 1994 году  Kenji Koyama и Tony W. Lai нашли другой алгоритм, позволяющий решить все цепочки за 5625/1296 = 4.340, однако для некоторых из них также было необходимо сделать 6 ходов. Лучшая стратегия с не более чем пятью ходами немного хуже - 5626/1296 = 4.341.

Knuth (1976-77) showed that the codebreaker can always succeed in five or fewer moves (i.e., knows the code after four guesses). His technique uses a greedy strategy that minimizes the number of remaining possibilities at each step, and requires 4.478 guesses on average, assuming equally likely code choice. Irving (1978-79) subsequently found a strategy with slightly smaller average length. Koyama and Lai (1993) described a strategy that minimizes the average number of guesses, requiring on average 4.340 guesses, although may require up to six in the worst case. A slight modification also described by Koyama and Lai (1993) increases the average to 4.341, but reduces the maximum number of guesses required to five.

В игре Super MasterMind можно обойтись максимум 6-ю (или 7-ю ?) ходами (точно не известно).
 

Solving the game

Here is a simple brute-force greedy algorithm to solve the game:

Given previous guesses and its results (if any):

  1. Calculate all possible secret combinations (secret combinations which don't conflict with the results of previous guesses), given previous guesses and their results. If there are no previous guesses, then all secret combinations are possible.
  2. If number of possible secret combinations calculated in last step is:
    • ... 0, then all secret combinations are impossible (all secret combinations conflict with the results of previous guesses), hence there's no solution to the puzzle. If this situation is reached, then either the puzzle, guesses, or both were invalid.
    • ... 1, then there's only one secret combination possible, which must be the answer to the puzzle. Enter the secret combination and win.
    • ... greater than 1, then find a guess which will reduce the amount of possible secret combinations to a number as close as possible to the lowest possible (1, that is), given any results of this guess. Enter this guess and return to step 1. For example, one could use a guess which will yield the highest number of different results if applied to all possible secret combinations, or maybe a guess, where the mean and standard deviation of the frequency of the results is the lowest, etc.

Chiao 2004

Подчеркнутые ячейки в Столе 10 представляют худший сценарий для всех возможных типов первых предположений. Согласно Knuth, AABB должен играться сначала, так как это минимизирует худший сценарий.

Стратегия 1. Хаотическая.

Так как число задуманных комбинаций конечно, то можно просто последовательно называть любые из них. Если повезёт, угадаете с первого хода. Вероятность выигрыша за 10 ходов при такой стратегии равна 10/1296= 0.0077 (7,7%). Иначе говоря, выигрышной будет примерно каждая 13-я партия. Конечно, думать при такой стратегии почти не нужно - но тогда уж лучше переходить на стрелялки...

Стратегия 2. Списочная.

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

Второй и последующие ходы  делаются так. Из всех допустимых комбинаций произвольно выбирают одну. Под допустимыми комбинациями понимают такие сочетания фишек, которые удовлетворяют результатам предыдущих ходов. Например, после первого хода вы получили ответ 01 - только одна фишка имеется в загаданной комбинации, но занимает в ней другое место. Теперь из всех 1296 возможных комбинаций отбираем те, которые на первый ход дадут такой же результат. Если первый ход был К(расная)К(расная)Ж(ёлтая)Ж(ёлтая), то вы получите список из 256 комбинаций. Совершенно очевидно, что среди них находится и та, которая была задумана. Таким образом, после первого хода вам нужно искать задуманную комбинацию только среди 256 кандидатов, а не среди 1296, как это было вначале. Также произвольно выбираете одну из этих комбинаций, получаете ответ, выбираете из этих 256 комбинаций те, которые удовлетворяют второму ходу, и так далее - до победы.

Эта стратегия игры реализована в программе Mind Game. Подробное описание игры и её исходный код вы найдёте в книге Большой самоучитель Delphi XE3.

Замечание. Лучше выбирать не произвольную комбинацию из полученных списков, а десятую (а если их меньше, то последнюю). В этом случае вы гарантированно выигрываете не более чем за 7 ходов (как вы помните, правила допускают 10 ходов). Всего на отгадывание всех 1296 комбинаций потребуется 7273 ходов, или в среднем 5,612 хода на игру. Следовательно, в большинстве игр вы будете находить задуманную комбинацию за 5-6 ходов.
Кстати, доказано (это сделал Д.Е. Кнут в 1976, что любую комбинацию можно отгадать не более, чем за 5 ходов. Эта стратегия в некоторых случаях требует 6 ходов, то есть она не является оптимальной. Трудно поверить, но ходы из составляемых списков - далеко не лучшие. Во многих случаях нужно ходить не так, то есть следует называть комбинации, которые заведомо не являются выигрышными. Безусловно, такие ходы - "холостые", так как не позволяют выиграть немедленно, зато они резко снижают число кандидатов на задуманное число. Как это делается, рассказано в следующей стратегии.

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

Стратегия 3. Минимизация групп (Стратегия Д.Э.Кнута, 1976-77).

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

Всего имеется 5 принципиально различных первых хода - AAAA, AAAB, AABB, AABC и ABCD. Это очевидно, так все 4 цвета совершенно равнозначны и безразлично, какие из них выбирать на первом ходу. Главное - количество фишек каждого цвета в названной комбинации, независимо от их положения в ней.

В результате ходы мы можем получить такие ответы - 00 (нет совершенно правильных фишек, то есть фишек совпадающих и по цвету и по положению в загадке и догадке - обозначаются в игре чёрными маленькими фишками, и нет "цвета", то есть фишек того же цвета, что и в загаданной комбинации, но стоящих на других местах, - обозначаются белыми фишками), 01, 02, 03, 04, 10, 11, 12, 13, 20, 21, 22, 30, 40. Для каждого ответа подсчитаем число комбинаций, которые ему удовлетворяют. Подробно эта процедура описана в Стратегии 2.

 

Догадка
Результат АAAA АAAB АABB АABC АBCD

00

625 256 256 81 16
01   308 256 276 152
02   61 96 222 312
03     16 44 136
04     1 2 9
10 500 317 256 182 108
11   156 208 230 252
12   27 36 84 132
13       4 8
20 150 123 114 105 96
21   24 32 40 48
22   3 4 5 6
30 20 20 20 20 20
40 1 1 1 1 1

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

Что делать дальше?
Если вам повезёт и вы получите ответ 04 или 40, то задуманная комбинация сразу отгадана - это BBAA (в первом случае) или AABB (во втором).

Во всех остальных случаях придётся делать, по крайней мере, ещё один ход.


Программа, помогающая играть в "Виселицу" - HangmanHelper

Нам осталось написать программу, которая будет играть по Стратегии 3. Как это сделать, - рассказ отдельный. Но вот она готова и называется HangmanHelper. Интерфейс программы - предельно прост.

В верхней строке находятся кнопки:

- Загрузить новый словарь. При запуске программы автоматически загружается Словарь Ожегова и Шведовой. Это обычный текстовый файл (в отличие от большинства других подобных программ с абракадаброй вместо словаря, - чтобы никто не мог им воспользоваться), который вы легко можете редактировать. Только имейте в виду, что слова в нём расположены в зависимости от длины, этот порядок вы нарушать не должны (или воспользуйтесь потом утилитой Fraction.exe - см. ниже)!

- Очистить протокол. Стереть информацию из окна протокола.

- Записать протокол на диск. Если вы хотите сохранить запись партии для последующего анализа, воспользуйтесь этой кнопкой.

- Остановить поиск. В этой версии программы не используется, так как выбор буквы происходит очень быстро.

- Выход из программы.

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

Еще ниже находится текстовое окно "Этих букв нет:". В него вы должны самостоятельно вписывать те буквы, которых не оказалось в слове (согласно ответу загадчика). Порядок и регистр букв значения не имеют.

Под ним расположено самое главное окно - "Шаблон слова:". В него вы должны - опять же сами - вписывать правильные буквы, в нужные позиции.

Кнопка "Найти букву" запускает поиск очередной буквы. Результат поиска отображается в окне протокола.

Две кнопки "Очистить" стирают всю информацию из этих двух текстовых окон.

Кнопки "3" - "13" служат для быстрого ввода пустого шаблона.

Строка в самом низу окна программы сообщает число угаданных и не угаданных букв и общее число попыток.

Рассмотрим работу с программой на конкретном примере.

Пусть, как и раньше, задумано слово ЖЕЛЕЗО. Запускаем программу. Все окна, кроме окна шаблона, пустые. В окне шаблона вы увидите 5 точек. Так как наше слово состоит из шести букв, то просто нажмите кнопку "6", чтобы в окне шаблона появилась исходная позиция:

Нам уже известно, что лучший первый ход для 6-буквенных слов - буква А. Можете сразу записать её в окно отсутствующих букв (вы ведь не знаете, что задумано слово ЖЕЛЕЗО!), а можете нажать кнопку "Найти букву". Тогда в окне протокола вы увидите:



То есть вам будет рекомендовано сходить именно так. Конечно, случайных ход может быть и другим:



Кроме того, в окне приведены данные по количеству слов с каждой буквой - вы можете выбрать букву и самостоятельно.

Итак, буквы А в слове не оказалось. Записываем её в отсутствующие и снова нажимаем кнопку "Найти букву":

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

Делаем следующий ход:

Если вы выберете лучшую букву, то загадчик (это вы и есть) должен вписать её в шаблон. Затем вы делаете следующий ход:

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

Если у вас есть какие-то догадки насчёт загаданного слова, вы можете сами выбрать его из списка и назвать букву из него. В данном же случае только буква Р имеется в двух словах, поэтому она и была выбрана для хода.

Ходим ещё раз:

Слово отгадано - это ЖЕЛЕЗО. Последовательно называете буквы Ж, Л, З в любом порядке, и вы - победитель. Как видите, мы сделали всего один неверный ход.

Игра закончена. Для следующей игры стираете поле отсутствующих букв и так далее.

Замечание 13. В архиве с программой вы найдёте ещё 3 дополнительных словаря. Попробуйте воспользоваться ими, если вам придётся разгадывать трудные, редкие слова. Не забывайте также пополнять свой словарный запас, он пригодится вам и в других играх!
Все слова в словарях должны быть рассортированы по длине. В архив добавлена утилита Fraction.exe, с помощью которой вы сможете переписать любой словарь (исходный файл не будет изменён!) так, чтобы его можно было использовать с программой HangmanHelper. Регистр букв значения не имеет, но лучше использовать заглавные буквы, так как их легче различать на экране.

* В словаре makarov_frc.txt буква Ё везде заменена на Е, имейте это в виду.

(0,9 М) Скачать программу HangmanHelper v.1.0.0 и 4 словаря (не требует установки).

 

Программы для игры в Mastermind

1. "Мастер мысли". Версия 1.0.0. Автор В.Рубанцев, 1998. Версия игры, имеющая несколько существенных отличий от Мастермайнда: длина цепочки цветных шариков от 5 до 10, шарики 4-х цветов, в ответе указывается число только правильно стоящих шариков (то есть "цвета" во внимание не принимаются). Имеется исходный код на Visual Basic, так что можно кое-что посмотреть и переделать под собственные интересы.

(0,2 М) Скачать программу Мастер мысли (не требует установки).

2. "Быки и коровы". Интерлайн Про, 2002. Флэш-игра, довольно симпатичная, с музыкой и танцующей коровой. Почти настоящая одноимённая игра, но цифр нет, а цвета могут повторяться (в догадке, в загадке-то они разные, поэтому ответ в этом случае будет неверным)...
Вы можете скачать игру или поиграть прямо здесь:

Играть во флэш-игру 'Быки и коровы'

<Скачать игру в формате SWF (170 К)

3."Mind Game". Версия 1.0.0. 

Интернет-игры в "Виселицу"

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

1. Виселица - games.germany.ru. Здесь можно почитать правила (которые к самой игре отношения не имеют), посмотреть, кто сейчас играет, полюбоваться таблицей лучших результатов (наверх вы поднимитесь только через несколько лет, крепитесь).



Получив эту не очень полезную информацию, щёлкните по надписи "комната "Эшафот" (справа указано число игроков в сети), загрузится Java-апплет, и вы можете приступать к игре.

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



Для вас сразу же вроют столб и звёздочками покажут, сколько букв в загаданном слове. Как играть, мы уже подробно разобрали. С программой HangmanHelper проблем у вас не будет, так что набранные очки - только дело времени (правда, система начисления очков на сайте весьма причудлива и достоверно не известна никому; говорят, что количество очков зависит от сложности слова, но кем и чем она измеряется?).
Зато игра имеет мини-чат (справа от игрового поля), в котором можно обсудить наболевшее, а также узнать, кто и сколько набрал очков.
Игра ведётся по классическим правилам, только число неверных попыток всего 7, что, конечно, маловато при отгадывании коротких слов.
Ваши набранные очки сохраняются, так что вы всегда можете продолжить своё восхождение к вершинам славы. Заодно вы получите за активность некие билеты и сможете участвовать в розыгрыше призов (или просто в розыгрыше).

HangmanHelper решает задачу:



 

 В начало