# How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?

Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:

1. Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
2. Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
3. For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values. Play the guess with the highest score (minimax).
4. Go back to step 2 until you have got it right.

I am curious: what would be the maximum number of guesses necessary to win a Mastermind-like game with 5 pegs instead of 4? How about 1,000 pegs, or a million?

• This paper surveys many relevant results. Mar 22, 2020 at 21:26