## Investigations into the Master MindTM Board Game

by Toby Nelson (5 Feb 1999)
www.tnelson.demon.co.uk

### 0. Contents

1. Introduction
2. Some Computational Questions (and Answers)
3. How to win at "Master Mind"
4. Puzzles
5. Some Mathematics
6. References and Links

### 1. Introduction

The following information is the result of my investigations into Master Mind over a few days in early February 1999.

Several versions of the actual game have been produced. See the Box Art pages for details.

As a quick memory refresher, in the game of Master Mind your job as the "codebreaker" is to deduce a hidden configuration of 4 coloured pegs ("the solution") chosen by another person ("the codemaker"), by making guesses at it. The pegs come in six different colours. For the purposes of argument, B=Black, C=Cyan, G=Green, R=Red, Y=Yellow, W=White.

After each guess is played, the puzzle setter 'marks' the guess, using some smaller, slimmer black and white pegs, which I shall call "markers". A black marker tells you that one of your pegs (but you don't know which one) is the right colour and in the right position. A white marker tells you that one of your pegs (again you don't know which one) is of a colour which is in the solution, but it's in the wrong position.

The player is given ten guesses to try to find the solution.

### 2. Some Computational Questions (and Answers)

Question: How many ways are there of marking a guess?
Answer: If you list them, it turns out that there are just fourteen different ways of marking a guess, which I will number zero to thirteen for use later on:

```(0) No markers
(1) 1 white marker
(2) 1 black marker
(3) 2 white markers
(4) 1 black marker, 1 white marker
(5) 2 black markers
(6) 3 white markers
(7) 1 black marker, 2 white markers
(8) 2 black markers, 1 white marker
(9) 3 black markers
(10) 4 white markers
(11) 1 black marker, 3 white markers
(12) 2 black markers, 2 white markers
(13) 4 black markers [This means you have got the solution!]
```

Question: How many ways are there of choosing four pegs, where each one is chosen from six colours?
Answer: 6x6x6x6 = 1296 ways.

Question: What should the first guess be?
Answer: When the first guess is chosen, nothing is known about what colours are in the solution, so one might think that any choice is just as good as any other. But this is not quite true. For instance, if the first guess is 4 red pegs (RRRR) it can only be marked in five ways (only the ways that use no white markers) i.e. (0), (2), (5), (9), and (13). However, if the first guess uses more than one colour (e.g. BBCC), then it can be marked in several more ways, which gives more logical information about the solution.

There are only five essentially different first moves: BBBB, BBBC, BBCC, BBCG, and BCRG. (Each has a different number of repeated colours). Before you play the first guess, there are 1296 possible solutions. After the first guess is marked, the number of possible solutions left is reduced. Computer analysis shows the number of solutions left in each case is as follows:

```         |           First guess:           |
| BBBB | BBBC | BBCC | BBCG | BCGR |
---------+------+------+------+------+------+
First  0 |  625 |  256 |  256 |   81 |   16 |
Mark:  1 |    0 |  308 |  256 |  276 |  152 |
2 |  500 |  317 |  256 |  182 |  108 |
3 |    0 |   61 |   96 |  222 |  312 |
4 |    0 |  156 |  208 |  230 |  252 |
5 |  150 |  123 |  114 |  105 |   96 |
6 |    0 |    0 |   16 |   44 |  136 |
7 |    0 |   27 |   36 |   84 |  132 |
8 |    0 |   24 |   32 |   40 |   48 |
9 |   20 |   20 |   20 |   20 |   20 |
10 |    0 |    0 |    1 |    2 |    9 |
11 |    0 |    0 |    0 |    4 |    8 |
12 |    0 |    3 |    4 |    5 |    6 |
13 |    1 |    1 |    1 |    1 |    1 |
```

For instance, if the first move is BBCC, and the mark is (3) (=Two white markers), then logically there are only 96 possible solutions left. As a special case, note that if your first move is BBCC, and you are lucky enough to get marked (10) (=Four white markers), then there is only one possible solution, (CCBB), so you can win in just two moves.

If we choose BBCC as a first move, then no matter how unhelpfully it is marked, we will have at most 256 possible solutions left. We choose to play BBCC because it gives us the smallest peak figure. (Playing BBCG for instance gives a peak figure of 276). This method turns out to be a good strategy for choosing the best next move. After the second move is marked, the analysis shows that we are left with at most 46 possible solutions.

Repeating this procedure for each of the remaining guesses gives rise to this strategy table.

### 3. How to win at "Master Mind"

Question: How many moves would it take a perfect Master Mind player to find the solution?
Answer: In 1993, Kenji Koyama and Tony W. Lai calculated that the best strategy uses an average of 5625/1296 = 4.340 moves (with just one case needing a six move solution).

The strategy table shows a (non-optimal) strategy that always takes five moves or less. Your first guess is always BBCC (shown on the left hand side). The number in brackets after BBCC is the mark you receive for that guess (see the list of possible marks above). To the right of that mark is your next guess to play. Keep following the table in this way until you get to the solution.

### 4. Puzzles

The strategy table can be used to set logic puzzles. For example, if a game is started with the moves...

```BBCC - 1 white marker
CGRR - 1 white marker
CYBY - 1 white marker
BRWW - 2 white markers
```

...then there is only one possible solution. Can you work it out, without looking at the table?

### 5. Some Mathematics

Consider the game of N-Master Mind, which uses the rules of the standard Master Mind but with N colours. The number of guesses needed by the perfect algorithm ("God's Algorithm") is an increasing function G(N) of N. Obviously G(1) = 1. In 2-Master Mind, there are 16 possible solutions and only 14 possible marks, so a single move cannot distinguish every solution. Thus G(2) >= 3.

Notice that the standard game is 6-Master Mind, and the computer analysis above tells us that G(6) <= 5.

Five Move Theorem. G(6) = 5.
Proof: One move can only distinguish between 14 solutions, because there are only 14 possible marks. One of these marks indicates success (i.e. 4 black markers). Therefore two moves can only distinguish between at most (13x14) + 1=183 possible solutions.

However, computer analysis (see above) shows that no matter how good your first guess is, an unhelpful mark will leave you with at least 256 possible solutions left. So after two further moves you still cannot be sure of the solution. Therefore at least 5 moves are needed, ie G(6) >= 5. But we have already seen that G(6) <= 5 (above), so G(6)=5.

In the more general case of N-Master Mind, we have a theorem thanks to Graham Nelson:
High-Colour Theorem. For all N,

lig(N/4) <= G(N) <= lig(N/4) + 12 + G(4)

where lig(X) denote the least integer >= X.

Proof: Call the colours C1, ..., CN. Play as first guess C1, C2, C3, C4; then C5, C6, C7, C8; and so on, using up
lig(N/4) guesses. This reduces the number of colours which can be in the solution to at most 16, since at most four of those guesses received any pegs. We can now determine exactly which at-most-four of these sixteen are used with 12 guesses. For example suppose the move C1, C2, C3, C4 received M marks, where 1<=M<=4. M tells us how many of the four colours C1, C2, C3, C4 are in the solution. Then play:

```C1 C1 C1 C1
C2 C2 C2 C2
C3 C3 C3 C3
```

If any one of these moves gets a mark, then that colour is in the solution. The number of black marks in each case tells us how many of that colour is in the solution. So if the sum of the marks for these three moves is less than M, then C4 is in the solution also. Repeating this technique uses at most 12 moves.

This reduces the problem to [something slightly better than] 4-Master Mind and at most G(4) further guesses are needed; hence the right-hand inequality.

For the left-hand inequality, suppose not. Then God can guess in strictly less than N/4 guesses, but this means that God never plays as many as N different colours in any one game, and so cannot distinguish between the set { (c1 c1 c1 c1), ..., (cN cN cN cN), (c1 c2 c1 c2) }.

For instance, 250,000 <= G(1,000,000) <= 250,017.