Mastermind is a simple two-player code-breaking board game invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It may have been inspired by moo, a program developed by J. M. Grochow at MIT in the late 1960s.
In the game, one player is the codemaker and the other is the codebreaker. The codemaker secretly selects a code consisting of an ordered sequence of four colors 
, each chosen from a set of six possible colors,
with repetitions allowed. The codebreaker then tries to guess the code by repeatedly
proposing a sequence of colors 
. After each guess, the codemaker tells the
codebreaker two numbers 
:
the number of correct colors in the correct positions (
) and the number of colors that are part of the code but not
in the correct positions (
).
For example, if the code is (1,2,3,3) and the codebreaker's guess is (3,2,4,3), then
the codemaker's response would be (2,1), since the codebreaker has guessed the 2
and the second 3 correctly and in the correct positions, while having guessed the
first three correctly but in the wrong position.
The codebreaker continues guessing until he guesses the code correctly or until he reaches a maximum allowable number of guesses without having correctly identified the secret code.
Interestingly, 
can be computed as
 |
where 
is the number of times the color 
is in the code and 
is the number of times it is in the guess.
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.
The "static" problem of finding the minimum number of guesses the codebreaker can make all at once at the beginning of the game without waiting for the answers,
and then upon receiving the answers, completely determine the code in the next "guess"
(Chvatal 1983), can be solved with six initial guesses (Greenwell 1999-2000). One
particular combination that allows the codebreaker to know the code after six guesses
(and so require a seventh to reveal his knowledge of the solution) is (1, 2, 2, 1),
(2, 3, 5, 4), (3, 3, 1, 1), (4, 5, 2, 4), (5, 6, 5, 6), (6, 6, 4, 3). It is not known
if this number can be reduced to five (exhaustive checking would require 
computations), although
it is believed not.
Swaszek (1999-2000) gives an analysis of practical strategies that do not require complicated record-keeping or use of a computer. Making a random guess from the set of remaining candidate code sequences gives a surprisingly short average game length of 4.638, while interpreting each guess as a number and using the next higher number consistent with the known information gives a game of average length 4.758.
