Mastermind
Game of Mastermind in progress
Players	2
Age range	8 and up
Setup time	< 5 minutes
Playing time	20 minutes
Random chance	Some
Skills required	Deduction

Mastermind or Master Mind is a simple code-breaking board game for two players, invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It was played as a pencil and paper game called bulls and cows at least as far back as the early 1960's. Download high resolution version (600x637, 160 KB) Wikipedia does not have an article with this exact name. ... Look up deduction in Wiktionary, the free dictionary. ... Look up mastermind in Wiktionary, the free dictionary. ... In communications, a code is a rule for converting a piece of information (for example, a letter, word, or phrase) into another form or representation, not necessarily of the same type. ... A board game is a game played with counters or pieces that are placed on, removed from, or moved across a board (a premarked surface, usually specific to that game). ... Mordecai Meirowitz was an Israeli postmaster and telecommunications expert who invented the code-breaking board game Mastermind. ... Bulls and Cows, also known as Cows and Bulls, is an old code-breaking paper and pencil game for two players, similar to Mastermind. ...

Gameplay and rules

The game is played using:

• a decoding board, with a shield at one end covering a row of four large holes, and twelve 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, so 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. In mathematics, the parity of an object refers to whether it is even or odd. ...

The codebreaker tries to guess the pattern, in both order and color, within twelve (sometimes ten or eight) 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 twelve incorrect guesses are made.

The codemaker gets one point for each guess a codebreaker makes. The colored key pegs are what give you your score, so if you have 5 colored key pegs on the game board, your score is 5. An extra point is earned by the codemaker if the codebreaker doesn't guess the pattern exactly in the last guess. The winner is the one who has the most points after the agreed-upon number of games are played.

History

Since 1971, the rights to Mastermind have been held by Invicta Plastics of Oadby, near Leicester, UK. They originally manufactured it themselves, though they have since licensed its manufacture to Hasbro in most of the world, and two other manufacturers who have the United States and Israel manufacturing rights. , Oadby is a town within the borough of Oadby and Wigston, in Leicestershire, England. ... This article discusses Leicester in England. ... Hasbro (NYSE: HAS) is an American toy and game company. ...

Starting in 1973, the game box featured a photograph of a well-dressed, distinguished-looking white man seated in the foreground, with an attractive Asian woman standing behind him. The connection between these people and the game of Mastermind was not explained. The two models (Bill Woodward and Cecilia Fung) reunited in June 2003 to pose for another publicity photo.^[1]

Algorithms

With 4 pegs and 6 colours, there are 6⁴ = 1296 different patterns.

Six guess algorithm

The following algorithm solves the game in 6 or fewer guesses.^{[citation needed]} It has a general procedure and a few listed exceptions. In this section the six colours are referred to as letters a through f.

Divide the 1296 possible games into 4 categories:

• 0 duplicates (eg abcd)
• 1 duplicate (eg aabc)
• 2 duplicates (eg aabb or aaab)
• 3 duplicates (eg aaaa)

The general process is to list all the games that could be correct with the data so far. The list should be sorted by ascending number of duplicates and within each duplicate level alphabetically. Before guess 1, the list is all 1296 games; thus guess 1 is always "abcd." If the reply to guess 1 is "0 0," for example, then the list afterwards comprises the 16 games involving only e and f. Each subsequent guess is the first game remaining in the list, with the following exceptions:

• Guess 2 is always "bcde"
• Guess 3 is always "cdef"
• If the list for guess 4 starts with a game on the left side of the list below, then use the game to its right instead:
  • "acfb" → "dcad"
  • "aebf" → "edfd"
  • "aefb" → "eacc"
  • "afbe" → "bfcd"
  • "bafe" → "eadc"
  • "beaf" → "edae"
  • "befa" → "eeda"
  • "eabf" → "fdfb"
  • "aadb" → "babd"
  • "abae" → "bbcc"
  • "aeaf" → "cffd"
  • "cafa" → "fdfa"
  • "aaee" → "dddf"

Five guess algorithm

In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduced the number of possible patterns.^[2] The algorithm works as follows: Also: 1977 (album) by Ash. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ...

1. The first guess is aabb.
2. Calculate which possibilities (from the 1296) would give the same score of colored and white pegs if they were the answer. Remove all the others.
3. For each possible guess (not necessarily one of the remaining possibilities) and for each possible colored/white score, calculate how many possibilities would be eliminated. The score of the guess is the least of such values. Play the guess with the highest score (minimax).
4. Go back to step 2 until you have got it right.

 while coloredScore != 0 if numberOfTries == 0 guess("aabb") else maximumGuess = "" maximumGuessScore = 0 foreach possibleGuess thisScore = 9999 foreach possibleScore number_of_removals = count_removals(guess, score) thisScore = min(number_of_removals, thisScore) if thisScore > maximumGuessScore maximumGuessScore = thisScore maximumGuess = guess guess(maximumGuess) 

Subsequent mathematicians have been finding various algorithms that reduce the average number of turns needed to solve the pattern: in 1993, Kenji Koyama and Tony W. Lai found a method that required an average of 4.340 turns to solve, with a worst case scenario of six turns.^[3] “Minmax” redirects here. ...

Variations

Varying the number of colors and the number of peg positions results in a spectrum of Mastermind games of different sizes and shapes. A common variation is with 8 different colors, which can also be played as 9 different colors using an empty slot as the ninth "color".

The moves required when the number of colors varies was studied in [1].

In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an arXiv article that the Mastermind Satisfiability Problem is NP-complete, thus explicating the computational property that makes the game intrinsically interesting to play. Year 2005 (MMV) was a common year starting on Saturday (link displays full calendar) of the Gregorian calendar. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Computer and Internet versions of the game have also been made, sometimes with variations in the number and type of pieces involved. It can also be played with paper and pencil. Online skill-based games are a growing genre of browser-based games. ... Games that can be played with only pencil and paper: Battleship was played as a pencil and paper game, long before Hasbro came out with a board game version. ...

Exactly the same game is also sold with other names, at least "Secret Code" by the Danish company Top-Toy As, possibly to circumvent the trademark of the original name.

Moo and Bulls and Cows

Main article: Bulls and cows.

Mastermind is similar to moo, a computer program written in the late 1960s by J. M. Grochow at MIT in the PL/I computer language for the Multics operating system. It, in turn, is similar to a game called Bulls and Cows that may date back a century or more. Bulls and Cows, also known as Cows and Bulls, is an old code-breaking paper and pencil game for two players, similar to Mastermind. ... “MIT” redirects here. ... PL/I (Programming Language One, pronounced pee el one) is an imperative computer programming language designed for scientific, engineering, and business applications. ... Multics (Multiplexed Information and Computing Service) was an extraordinarily influential early time-sharing operating system. ... Bulls and Cows, also known as Cows and Bulls, is an old code-breaking paper and pencil game for two players, similar to Mastermind. ...

References

1. ^ Landmark Reunion for Mastermind Box Models. Retrieved on 2006-10-05.
2. ^ Knuth, Donald (1976-77), "The Computer as a Master Mind", Journal of Recreational Mathematics (no. 9): 1-6
3. ^ Koyama, Mami & Lai, Tony (1993), "An Optimal Mastermind Strategy", Journal of Recreational Mathematics (no. 25): 251-256

Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... For other uses, see 5th October (Serbia). ...

External links

• Online simulation of the board game
• Invitation to MasterMind
• Investigations into Mastermind
• Mathworld article on Mastermind
• Mastermind Online Games Directory
• Mastermind at Boardgamegeek