Cut The Knot!

Mastermind is a game played by two players, the codemaker and the codebreaker. The game begins with the codemaker selecting a code, a sequence of four colors (digits, pegs or other symbols) (c₁, c₂, c₃, c₄) chosen from a set of six colors (repetitions allowed). The codebreaker will then try to guess the code. After each guess (g₁, g₂, g₃, g₄), the codemaker responds with two numbers. The first, the number of exact matches, is the number of times c_k = g_k , k = 1, ... , 4. The second, the number of near matches, is the number of colors in the guess which are the right color, but in the wrong position. In the applet bellow the number of exact matches is indicated by small red dots, while white dots define the second number. In the real game the codemaker uses small pegs for the same purpose.

Mastermind is a game of deduction. The task is to uncover 1 secret code selected from a set numbering 1296 (= 6⁴) elements. With every judiciously chosen guess and a (frank) response, the set of possibilities shrinks. When only one element remains it is bound to be the secret code. If colors are represented by numbers starting with 0, then 0011 or 0012 are good candidates for the first guess. Afterwards, to come up with propitious guesses, the codebreaker may employ various problem-solving strategies [7], like pattern searching, establishing subgoals, or even proof by contradiction.

Mastermind relates to the language and body of mathematics in other respects too. To start from the beginning, have you noticed that the rules of the game as presented in the opening paragraph are ambiguous? If a guess contains the same color in more than 1 position, but the secret code contains it only once, an interesting situation may arise. For example, what should the correct response be to the guess 1123 if the secret code is 0145? Implicit in the rules are two assumptions:

1. Each response peg refers to one and only one color peg [7, p 88].
2. Evaluation of exact matches has precedence over evaluation of near, or color, matches.

Accordingly, in the example there is 1 exact match and no color matches. According to D. Knuth [5], the clearest way to state the rules exactly (at least when you speak to a mathematician or a computer) is to frame them into the mathematical language. Let n_i is the number of times color i is in the code, and m_i is the number of times color i is in the guess. Then color i is matched min(n_i, m_i) times. The total number of color matches is the sum of matches for all individual colors. Since exact matches are evaluated first, the number of near matches is calculated by:

Another little piece of mathematics comes from the question of how different are different secret codes. We suggested above that 0011 would be a good starting guess. Is 1122 any worse? Of course not. They are very much the same in that ordering of colors is to a great extent an arbitrary matter, as in fact is ordering of the positions. This device can be used by teachers [7, p xii] to invent seemingly different games. Better yet, students may be encouraged to look for patterns that make games equivalent.

Mastermind also admits meaningful modifications. The obvious one is to allow different number of colors and positions. In another variant, colors can't be repeated. This reduces the number of valid codes from 1296 to 360. Surprisingly [8], the game is hardly simplified: for a variety of strategies, the expected number of moves to solve either variant is very much the same. In yet another variant, the response may only contain the number of exact matches. This does make the game more difficult.

In [5] Knuth showed that the codebreaker can always succeed in five moves or less. That is, he has determined what the code is after at most four guesses. The strategy used by Knuth was found by choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities, over all 15 responses by the codemaker. If there is a tie, a consistent guess (one that has a chance of being the code) would be used (if possible). With ties remaining the first one in numeric order is selected. This procedure guarantees a win in five moves. The expected number of guesses using this strategy is 4.478. Koyama and Lai [6] determined the Mastermind's optimal strategy, for which the expected number of guesses is 4.34 guesses. They used recursive backtracking methods to discover this strategy. Their method requires six guesses in the worst case.

Two strategies are implemented in the applet below: Knuth's and a simple strategy of randomly picking a consistent guess, starting with 0012. The latter finds the code on average in under five guesses. This however will sometimes require seven guesses (but see a letter from Stephan Rafler).

Now, you are the codemaker. You must assist computer to arrive at the secret code by providing feedback to his/her guesses. To this end click on the two numbers to the right of every row. (In the game with only exact matches only one number is displayed.)

In [1], Chvatal mentions a problem, suggested by Pierre Duchet, of finding the minimum number of guesses the codebreaker needs to make all at once, without waiting for the answers, to determine the code. For example, if we consider a Mastermind game with two positions and three colors to choose from, then the responses to the two guesses (0, 2), (1, 2) will determine the code. You can see this by listing the 9 possible codes and the codemaker's responses to these two guesses to see that these response vectors are all distinct:

(0, 0) - (10 00)
(0, 1) - (10 01)
(0, 2) - (20 10)
(1, 0) - (01 10)
(1, 1) - (00 10)
(1, 2) - (10 20)
(2, 0) - (02 01)
(2, 1) - (01 02)
(2, 2) - (10 10).

We call such a game static Mastermind. The game is reminiscent of two coin weighing problems. The first is the famous 12 coins problem (known also as the the Oddball Problem): to determine with three weighings a single counterfeit coin from a set of 12 otherwise identical coins. Coins are split into groups that are weighed against each other on a balance scale. There is a solution in which the groups are determined up-front with the result of three weighings leading to the counterfeit coin in a unique manner.

The second problem is on an altogether different scale of difficulty: Suppose we are given n coins, which look quite alike, but some of which are counterfeit. A scale is given which will allow any number of the coins to be weighed together. By weighing a subset of the n coins we are able to determine the number of good coins in the subset. The question is: what is the minimal number of weighings that will determine which are the good coins. (Subsets have to be identified ahead of time, before anything is weighed.) The problem was posed by Erdİs and RĈnyi [2] in 1963. Their paper gives asymptotic results. Think of the desired subsets as sequences of zeros and ones, the ones indicating which coins are in the subset. Determining the number of good coins in the subset is the response giving the number of exact matches for the ones.

In the first applet at the top of the page, you may try the static variant by checking the Static box. The applet always displays responses to the same sequence of guesses and the codebreaker is given only one chance to come up with the secret code.

The applet below can be used to discover those sequences of guesses we used in the static Mastermind game for various numbers of positions and colors. For small numbers, the applet shows a table of responses to various guesses (the top row) and the (potentially) secret codes (the left column.) Click on the color vectors in the top row that you want to try. These will be highlighted in blue. As you do this, the color vectors that become shaded in red are the ones that are not as yet determined by the blue guesses. Add to or modify your selection (clicking on a selected vector will unselect it) to try to get rid of all the red ones. Try this with the example above (set the colors to 3 and pegs to 2). Try to find solutions for other cases. For larger numbers, the applet only displays the possible guesses. As before, the selected guesses appear in blue, the undetermined ones in red.

For the standard Mastermind game of four positions and six colors we know from Knuth's result that at least four static guesses will be needed to determine the code. It is not hard to argue that, for this static problem, at least five guesses are needed. The work of Knuth, and Koyama and Lai's, sited above, strongly suggests that the static problem can't be done in five guesses, but no proof of this is known.

Greenwell [3] has found six guesses that always determine the Mastermind code:

(In September 2002, Andy Lewicki, University of Nebraska - Lincoln, furnished two more six guess combinations:

With such an uneven distribution of numbers these sixlets seem very strange indeed.)

You can verify this by using the applet above. Select the six guesses given above and you will notice that all 1296 possible codes are determined by this set. Try to find another solution. Is there a solution with five guesses? Try to find one and let us know if you do!

Our current knowledge on the number of static guesses depending on the number of pegs and colors is summarized in the following table:

Colors\Pegs	2	3	4	5	6	7	8
2	2	2	3	3?	4?	5?	5?
3	2	3	3	4?	4?	5?
4	3	3	4?	5?
5	4	4	5?
6	4	5?	6?
7	5	6?
8	6?
9	6?
10	7?

Entries without the question mark have been verified by exhaustive search. Those with the question mark have been found with the help of the above applet. We thus do not have complete confidence that they are optimal.

The table affords a few observations. In view of the Strong Law of Small Numbers [4] and especially one of its consequences - You can't tell by looking, we must be cautious drawing conclusions from such a short table. (Well, having a bigger table would not help either.)

Let's define complexity of the game as the minimal number of static guesses needed to solve it. We then observe (but also can actually prove) that the game with two pegs is not only more interesting than the game with one peg and the same number of colors, it's also simpler. (Think of how many static guesses are needed to solve the puzzle with one peg.) We can also safely assert that complexity of the game does not necessarily grow with the size of the game. Although of course the time needed to fill the corresponding entries in the table depended heavily on the latter. To prove this statement, we need just one example. The table provides plenty of them, its small size notwithstanding.

A stronger assertion, namely that complexity grows at most by 1 when either number of colors or positions increases by 1, can't be proven that easily. This is a conjecture in fact, as we do not have a proof for it, simple though it sounds. Additional table entries may support or refute this conjecture. They may also help envisage other properties of the complexity function. We shall be grateful for any help in filling up the table.

Everyone is welcome.

An Update (March 4, 2002)

We were notified of several interesting developments in response to this page. But first, let's mention an elegant contribution to the Oddball Problem by Jack Wert. Inherently inductive, Jack's approach immediately expands to (3ⁿ - 3)/2 coins.

1. Stephan Rafler produced a sequence of 10 random guesses for the standard Mastermind (6 colors, 4 pegs) none of whose subsequences is sufficient to solve the puzzle. This overrides our estimate that 7 guesses should suffice.

2. Wayne Goddard has verified with an exhaustive search program all table entries (except the one for 3 colors and 7 pegs) whose assertiveness was weakened by a question mark. The search took about a week for the standard case.

3. Wayne also reported two results: for k colors, the optimal number of static guesses in games with 3 (k 5) and 4 (k sufficiently large) pegs equals (k - 1).

4. Guenther Rosenbaum gave exact estimates for the case of two pegs: the optimal number of static guesses equals 2k, if the number of colors is either (3k - 1) or 3k, and is (2k + 1), if the number of colors is (3k + 1), k 1. As recorded in the On-Line Encyclopedia of Integer Sequences, the resulting sequence 2, 2, 3, 4, 4, 5, 6, 6, 7, ... appears in several other circumstances.

5. Guenther has also proven an upper estimate of 3k for 3k colors and 3 pegs (k 1) and a lower estimate of (m·(n-1)/n) - (n-1)/2 for n colors and m pegs, where n 2 and m n²/2.

6. Guenther notes that from the latter bound the least number of static guesses needed in the puzzle with 60 colors and 4 pegs is 44, whereas the optimal number of guesses for 60 colors and 2 pegs is just 40, which refutes our conjecture that the difference between two adjacent table entries is at most 1. This is yet another validation of the Strong Law of Small Numbers. (And an additional one follows from a combination of Wayne's and Guenther's results. Compare the first two columns below.)

On Feb 12, 2003, Petr Felzmann pointed out that the entry for 4 colors / 3 pegs must be 3 instead of the original 4. For example, the set of guesses (0, 0, 1), (0, 2, 2), (3, 1, 2) determines the code uniquely. There are six such indepent sequence of which more can be obtained by permutation.

Here is a new neat table with entries partially proven and partially verified by exhaustive search.

Colors\Pegs	2	3	4	5	6	7	8
2	2	2	3	3	4	5	5
3	2	3	3	4	4	5?
4	3	3	4	5
5	4	4	5
6	4	5	6
7	5	6
8	6	7
9	6	8
10	7	9

References

1. V. Chvatal, Mastermind, Combinatorica 3 (1983), 325-329.
2. P. Erdİs and C. RĈnyi, On Two problems in Information Theory, Magyar Tud. Akad. Mat. Kut. Int. Kİzl. 8 (1963), 229-242
3. D. L. Greenwell, Mastermind, Journal of Recreationsl Mathematics (submitted)
4. R. Guy, The Strong Law of Small Numbers, in The Lighter Side of Mathematics, R. Guy and R. Woodrow (eds), MAA, 1994
5. D. E. Knuth, The Computer as a Master Mind, Journal of Recreational Mathematics 9 (1976-77), 1-6.
6. K. Koyama and T. W. Lai, An Optimal Mastermind Strategy, Journal of Recreational Mathematics 25 (1993), 251-256.
7. M. Mitchell, MasterMind^(R) Mathematics, Key Curriculum Press, 1999
8. E. Neuwirth, Some Strategies for Mastermind, Zeitschrift fÉ Operations Research, Band 26, 1982, B257-B278

1. Mastermind by Don Greenwell
2. Static Mastermind by Don Greenwell
3. Mastermind, ObjectFusion
4. Windows Mastermind Simulator
5. Mastermind by Mohamed Jeragh
6. Mastermind by Lyndsey McCollam

MasterMind is a registered trademark of Invicta Plastics, Ltd.

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Don Greenwell is Professor of Mathematical Sciences and Foundation Professor at Eastern Kentucky University. During his thirty years in teaching he has taught mathematics or computer science at Louisiana State Universtiy, Auburn University, Iowa State University, Emory University, and Arkansas State University. He holds M.S. and Ph.D. degrees from Vanderbilt University. He can be reached via his Homepage.

Copyright ½ 1996-2002 Alexander Bogomolny