Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:
- Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
- Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
- 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).
- 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?