expected number of guesses in game of mastermind

Question

Sequence X consists of N pegs each randomly assigned on of M colours. One each go, the player places N coloured pegs in a line. If they exactly match sequence X, the game terminates. Otherwise, the player is told how many pegs in their sequence are the same colour as the pegs in the same position in sequence X, and how many of their pegs have a colour which is one of the coulours contained in sequence X.

On average, after how many goes would the game end, assuming perfect play?

Answer 1

There is unlikely to be a simple formula for general $N$ and $M$ though there will be bounds.

The standard version has $N=4$ pegs drawn from $M=6$ colours, with repeats allowed. Koyama, K. and Lai, T. W. "An Optimal Mastermind Strategy." J. Recr. Math. 25, 251-256, 1993 provides an algorithm with an average of 4.340 guesses and a maximum of 6, and another with an average of 4.341 and a maximum of 5.

Answer 2

There is a paper by Chvatal that provides asymptotically tight bounds for $\ k \leq n^{(1-\epsilon)}$ .

There is a recent paper by Doerr et al that improves the upper bound for larger values of $\ k$ .

Answer 3

Conjecture: that, when $N$=$M$, the expected number of guesses is less than or equal to $N$ (for a perfect algorithm which is striving to minimise this expected number of guesses).

Obviously this is true when $N$=$M$ = 1 (it takes only one guess if there is just one colour).

When $N=M=2$, there are 4 possible codes. Regardless of whether you use '00' (isomorphism: 11) or '01' (isomorphism: 10) as your first guess, you have:

• a $\frac1 4$ chance of getting it in one go
• a $\frac1 4$ chance of getting a score which uniquely determines it, ensuring you get it in the second guess
• a $\frac1 2$ chance of getting a score which eliminates one code but still leaves two possibilities (such that you have a $\frac1 2$ chance of requiring 3 guesses)

Thus the overall expectation is 2 guesses.

When $N=M=3$, there are 27 possible codes. The situation is complex enough to introduce a helpful algorithm:

1. consider guessing a code (say '000')
2. Calculate how many possible master-codes there are which would result in each score of black and white pegs. For instance, there is 1 possible master-code that would result in a score of 3 black pegs (000) are 6 possible codes which would result in a score of two black pegs (001, 002, 010, 020, 100, 200). There are 12 possible codes which would result in a score of 1 black peg, and 8 possible codes that would result in a score of no pegs.
3. Calculate the 'points' of each guess by summing the squares from step 2. That is, in the above case $Points (000) = 1^2 + 6^2 + 12^2 + 8^2 = 245$
4. Repeat steps 1 - 3 with each possible code (in the case of the first guess, the only other codes are 001 and 012 - everything else is an isomorphism of one of these). Select the one with the smallest 'points' and guess it (in this case, 001 has the smallest points).
5. Repeat steps 1 - 4 until the master-code is guessed.

This algorithm yields an expected number of guesses of $\frac{72}{27} = 2.666...$

Would anyone with programming skills like to try investigating this algorithm for different $N,M$ ?