2
$\begingroup$

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?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.