Mastermind (board game)
|
|
Template:Infobox Game Mastermind is a simple code-breaking board game for two players, invented in 1970 by Mordecai Meirowitz, an Israeli postmaster.
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.
In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or less, using an algorithm that progressively reduced the number of possible patterns. 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.
Since 1971, the rights to Mastermind have been held by Invicta Plastics of Leicester, England. 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.
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.
Solving the game
Here is a simple brute-force greedy algorithm to solve the game:
Given previous guesses and its results (if any):
- 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.
- 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.
External links
- Invitation to MasterMind (http://www.cut-the-knot.org/ctk/Mastermind.shtml)
- Investigations into Mastermind (http://www.tnelson.demon.co.uk/mastermind/)
- Mathworld article on Mastermind (http://mathworld.wolfram.com/Mastermind.html)
- Mastermind Online Games Directory (http://freewebarcade.com/board/mastermind/index.html)
- Mastermind Contest, MATLAB Programming Contest (http://www.mathworks.com/contest/mastermind.cgi/home.html)de:Mastermind