Knuth’s Algorithm for Master Mind

Wikipedia gives a description of Knuth’s Mastermind solver which I think could do with some refinement. Here is how I would describe the algorithm:

  1. Create the set S of 1296 guesses: 1111,1112,.., 6666.
  2. Start with initial guess 1122 (See Note 1 below) to get a response of colored and white pegs.
  3. If the response is four colored pegs, the game is won, the algorithm terminates.
  4. Otherwise, remove from S any guess that would not give the same response if it (the guess) were the code.
  5. Apply minimax technique to find a next guess as follows:
    1. For each possible guess, that is, any unused code of the 1296 not just those in S,
      1. for each possible colored/white peg score. (There are 14 possibilities)
        1. calculate how many possibilities in S would be eliminated
      2. The score of a guess is the minimum number of possibilities it might eliminate from S.
    2. From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible.(See Note 2 below)
  6. Repeat from step 3.

Note 1: Some other first guesses such as 1123, 1234 do not win in five tries on every code.
Note 2: By convention choose the guess with the least lexicographic order e.g. 2345 is lower than 3456. In some cases no member of S will be among the highest scoring guesses and thus the guess cannot win on the next turn, yet will be necessary to assure a win in five.

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s