Mastermind (board game)

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 (or ten, or eight, or six) additional rows containing four large holes next to a set of four small holes;
• code pegs of six different colors (or more; see Variations below), with round heads, which will be placed in the large holes on the board; and
• key pegs, some colored red (or black) and 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. Players decide in advance whether duplicates and blanks are allowed. If so, the codemaker may choose up to four same-colored code pegs or four blanks. If blanks are not allowed in the code, the codebreaker may not use blanks in their guesses. The codemaker places the chosen pattern in the four holes covered by the shield, visible to the codemaker but not to the codebreaker.

The codebreaker tries to deduce the pattern, in both order and color, within eight to twelve turns. Each attempt 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 key peg indicates a code peg that belongs in the solution but is incorrectly positioned.

If there are duplicate colors in the guess, they cannot all be awarded a key peg unless they correspond to the same number of duplicate colors in the hidden code. For example, if the hidden code is red-red-blue-blue and the codebreaker places red-red-red-blue, the codemaker will award three colored key pegs for the first two reds and the blue, but nothing for the third red. No indication is given of the fact that the code also includes a second blue.

Once feedback is provided, another attempt is made; tests and feedback continue to alternate until either the codebreaker deduces correctly, or all rows on the decoding board are full.

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 deduce the exact pattern within the given number of turns. (An alternative is to score based on the number of key pegs placed.) The winner is the one who has the most points after the agreed-upon number of games are played.

Other rules may be specified.

Algorithms and strategies

The best strategy for the codebreaker gives the minimal number of moves for worst and average case and in the sense of a minimax value of a zero-sum game in game theory.

Best strategies with four holes and six colors

With four holes and six colors, there are 6⁴ = 1,296 different patterns (allowing duplicate colors but not blanks).

Worst case: Five-guess algorithm

In 1976, 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. Described using the numbers 1–6 to represent the six colors of the code pegs, the algorithm works as follows:

1. Create the set S of 1,296 possible codes {1111, 1112, ... 6665, 6666}.
2. Start with initial guess 1122.
3. Play the guess to get a response of colored and white key pegs.
4. If the response is four colored key pegs, the game is won, the algorithm terminates.
5. Otherwise, remove from S any code that is not possible given that response of colored and white pegs.
6. The next guess is chosen by the minimax technique, which chooses a guess that has the least worst response score. In this case, a response to a guess is some number of colored and white key pegs, and the score of a response is defined to be the number of codes in S that are still possible even after the response is known. The score of a guess is pessimistically defined to be the worst (maximum) of all its response scores. From the set of guesses with the best (minimum) guess score, select one as the next guess, choosing a code from S whenever possible.
7. Repeat from Step 3.

Average case

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 performed an exhaustive depth-first search showing that the optimal method for solving a random code could achieve an average of 5,625 / 1,296 ≈ 4.340 turns to solve, with a worst-case scenario of six turns.

Minimax value of game theory

The minimax value in the sense of game theory is 5,600 / 1,290 ≈ 4.341. The minimax strategy of the codemaker consists in a uniformly distributed selection of one of the 1,290 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, with P = length of the solution used in the game, X₁ = exact matches ("red pins") and Y₁ = near matches ("white pins"):

1. Set i = 1
2. Play fixed initial guess G₁
3. Get the response X₁ and Y₁
4. Repeat while X_i ≠ P:
   1. Increment i
   2. Set E_i = ∅ and h = 1
   3. Initialize population
   4. Repeat while h ≤ maxgen and |E_i| ≤ maxsize:
      1. Generate new population using crossover, mutation, inversion and permutation
      2. Calculate fitness
      3. Add eligible combinations to E_i
      4. Increment h
   5. Play guess G_i which belongs to E_i
   6. Get response X_i and Y_i

Complexity and the satisfiability problem

In November 2004, Michiel de Bondt proved that solving a Mastermind board is an NP-complete problem when played with n pegs per row and two colors, by showing how to represent any 1-in-3-SAT problem in it. He also showed the same for Consistent Mastermind (playing the game so that every guess is a candidate for the secret code that is consistent with the hints in the previous guesses).

The Mastermind satisfiability problem (MSP) is a decision problem that asks, "Given a set of guesses and the number of colored and white key pegs scored for each guess, is there at least one secret pattern that generates those exact scores?" (If not, then the codemaker must have incorrectly scored at least one guess.) In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed that MSP 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:

There was also a version called Super Code produced in East Germany by VEB Plasticart.

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. In Mini Mastermind, the colored code pegs are the same size and shape as the colored or white key pegs so the difficulty can be increased by permitting the key pegs to be used as code pegs for two additional colors.

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 2021 web game Wordle has been compared to Mastermind; however, in Wordle a response to a guess indicates which letters (corresponding to code pegs) are correctly placed or incorrectly placed, whereas in Mastermind only the count of correctly and incorrectly placed code pegs are indicated.

The game was included in the compilation party video game Clubhouse Games: 51 Worldwide Classics for the Nintendo Switch under the name "Hit & Blow".

Reviews

• Games #3
• Games and Puzzles
• 1980 Games 100 in Games
• 1981 Games 100 in Games
• Games & Puzzles
• The Playboy Winner's Guide to Board Games
• Family Games: The 100 Best