Mastermind (board game)
Mastermind or Master Mind is a code-breaking game for two players. The modern game with pegs was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It resembles an earlier pencil and paper game called Bulls and Cows that may date back a century or more.
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 black, some white, which are flat-headed and smaller than the code pegs; they will be placed in the small holes on the board.
The codebreaker tries to guess the pattern, in both order and color, within eight to twelve 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 or black key peg is placed for each code peg from the guess which is correct in both color and position. A white key peg indicates the existence of a correct color code peg placed in the wrong position.
If there are duplicate colours in the guess, they cannot all be awarded a key peg unless they correspond to the same number of duplicate colours in the hidden code. For example, if the hidden code is white-white-black-black and the player guesses white-white-white-black, the codemaker will award two colored key pegs for the two correct whites, nothing for the third white as there is not a third white in the code, and a colored key peg for the black. No indication is given of the fact that the code also includes a second black.
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.
Traditionally, players can only earn points when playing as the codemaker. The codemaker gets one point for each guess the codebreaker makes. An extra point is earned by the codemaker if the codebreaker is unable to guess the exact pattern within the given number of turns. The winner is the one who has the most points after the agreed-upon number of games are played.
Other rules may be specified.
History
The game is based on an older, paper based game called Bulls and Cows. A computer adaptation of it was run on Cambridge University’s Titan computer system, where it was called 'MOO'. This version was written by Frank King. There was also another version for the TSS/8 time sharing system, written by J.S. Felton and finally a version for the Multics system at MIT by Jerrold Grochow.The modern game with pegs was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. Meirowitz presented the idea to many major toy companies but, after showing it at the Nuremberg International Toy Fair, it was picked up by a plastics company, Invicta Plastics, based near Leicester, UK. Invicta purchased all the rights to the game and the founder, Edward Jones-Fenleigh, refined the game further. It was released in 1971–2.
Since 1971, the rights to Mastermind have been held by Invicta Plastics. They originally manufactured it themselves, though they have since licensed its manufacture to Hasbro worldwide, with the exception of Pressman Toys and Orda Industries who have the manufacturing rights to the United States and Israel, respectively.
Starting in 1973, the game box featured a photograph of a well-dressed, distinguished-looking man seated in the foreground, with a woman standing behind him. The two amateur models reunited in June 2003 to pose for another publicity photo.
Algorithms and strategies
Before asking for a best strategy of the codebreaker one has to define what is the meaning of "best": The minimal number of moves can be analyzed under the conditions of worst and average case and in the sense of a minimax value of a zero-sum game in game theory.Best strategies with four pegs and six colors
With four pegs and six colours, there are 64 = 1296 different patterns.Worst case: 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 reduces the number of possible patterns.The algorithm works as follows:
- Create the set S of 1296 possible codes
- Start with initial guess 1122
- Play the guess to get a response of coloured and white pegs.
- If the response is four colored pegs, the game is won, the algorithm terminates.
- Otherwise, remove from S any code that would not give the same response if it were the code.
- Apply minimax technique to find a next guess as follows: For each possible guess, that is, any unused code of the 1296 not just those in S, calculate how many possibilities in S would be eliminated for each possible colored/white peg score. The score of a guess is the minimum number of possibilities it might eliminate from S. A single pass through S for each unused code of the 1296 will provide a hit count for each coloured/white peg score found; the coloured/white peg score with the highest hit count will eliminate the fewest possibilities; calculate the score of a guess by using "minimum eliminated" = "count of elements in S" - "highest hit count". From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible.
- Repeat from step 3.
Average case
Minimax value of game theory
The minimax value in the sense of game theory is 5600/1290 = 4.341. The minimax strategy of the codemaker consists in a uniformly distributed selection of one of the 1290 patterns with two or more colors.Genetic algorithm
A new algorithm with an embedded genetic algorithm, where a large set of eligible codes is collected throughout the different generations. The quality of each of these codes is determined based on a comparison with a selection of elements of the eligible set. This algorithm is based on a heuristic that assigns a score to each eligible combination based on its probability of actually being the hidden combination. Since this combination is not known, the score is based on characteristics of the set of eligible solutions or the sample of them found by the evolutionary algorithm.The algorithm works as follows:
- Set i = 1
- Play fixed initial guess G1
- Get the response X1 and Y1
- Repeat while Xi ≠ P:
- # Increment i
- # Set Ei = ∅ and h = 1
- # Initialize population
- # Repeat while h ≤ maxgen and |Ei| ≤ maxsize:
- ## Generate new population using crossover, mutation, inversion and permutation
- ## Calculate fitness
- ## Add eligible combinations to Ei
- ## Increment h
- # Play guess Gi which belongs to Ei
- # Get response Xi and Yi
Complexity and the satisfiability problem
The Mastermind satisfiability problem is a decision problem that asks, "Given a set of guesses and the number of colored and white pegs scored for each guess, is there at least one secret pattern that generates those exact scores?" In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an arXiv article that the Mastermind satisfiability problem is NP-complete.
Variations
Varying the number of colors and the number of holes results in a spectrum of Mastermind games of different levels of difficulty. Another common variation is to support different numbers of players taking on the roles of codemaker and codebreaker. The following are some examples of Mastermind games produced by Invicta, Parker Brothers, Pressman, Hasbro, and other game manufacturers:| Game | Year | Colors | Holes | Comments |
| Mastermind | 1972 | 6 | 4 | Original version |
| Royale Mastermind | 1972 | 5 colors × 5 shapes | 3 | |
| Mastermind44 | 1972 | 6 | 5 | For four players |
| Grand Mastermind | 1974 | 5 colors × 5 shapes | 4 | |
| Super Mastermind | 1975 | 8 | 5 | |
| Word Mastermind | 1975 | 26 letters | 4 | Only valid words may be used as the pattern and guessed each turn. |
| Mini Mastermind | 1976 | 6 | 4 | Travel-sized version; room for only six guesses |
| Number Mastermind | 1976 | 6 digits | 4 | Uses numbers instead of colors. The codemaker may optionally give, as an extra clue, the sum of the digits. |
| Electronic Mastermind | 1977 | 10 digits | 3, 4, or 5 | Uses numbers instead of colors. Handheld electronic version. Solo or multiple players vs. the computer. Invicta branded. |
| Walt Disney Mastermind | 1978 | 5 | 3 | Uses Disney characters instead of colors |
| Mini Mastermind | 1988 | 6 | 4 | Travel-sized version; room for only six guesses |
| Mastermind Challenge | 1993 | 8 | 5 | Both players simultaneously play code maker and code breaker. |
| Parker Mastermind | 1993 | 8 | 4 | |
| Mastermind for Kids | 1996 | 6 | 3 | Animal theme |
| Mastermind Secret Search | 1997 | 26 letters | 3-6 | Valid words only; clues are provided letter-by-letter using up/down arrows for earlier/later in the alphabet. |
| Electronic Hand-Held Mastermind | 1997 | 6 | 4 | Handheld electronic version. Hasbro. |
| New Mastermind | 2004 | 8 | 4 | For up to five players |
| Mini Mastermind | 2004 | 6 | 4 | Travel-sized self-contained version; room for only eight guesses |
The difficulty level of any of the above can be increased by treating “empty” as an additional color or decreased by requiring only that the code's colors be guessed, independent of position.
Computer and Internet versions of the game have also been made, sometimes with variations in the number and type of pieces involved and often under different names to avoid trademark infringement. Mastermind can also be played with paper and pencil.
There is a numeral variety of the Mastermind in which a 4-digit number is guessed.
The game was compiled into for the Switch under the name "Hit & Blow".