Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Are you assuming perfect play? – Peter Taylor Dec 13 '11 at 13:14
up vote 5 down vote accepted

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.

share|cite|improve this answer

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$ .

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.