expected number of guesses in game of mastermind

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?

-
Are you assuming perfect play? – Peter Taylor Dec 13 '11 at 13:14

2 Answers

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.

-

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

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

-