Master Mind Solver

Knuth [1] describes Master Mind as follows

In this game one player (the “codemaker”) conceals a four-symbol code, and the other player (the “codebreaker”) tries to identify all four symbols by trying appropriate test patterns. There are six symbols, represented by pegs of different colors, and repetitions are permitted, hence there are 6^4 = 1296 possible codewords. If the codemaker’s secret codeword is x1x2x3x4 and if the codebreaker gives the test pattern y1y2y3y4 , the codemaker tells him how close he is by announcing the number of “black hits,” í.e.,

  1. the number of positions such that xj=yj
  2. the number of “white hits,” i.e., the number of positions j such that xj!=yj but xj=yk for some k and yk has not been used in another hit.

For example,let the symbols be denoted by 0,1, 2, 3, 4, 5; if the codeword is 2532 and the test pattern is 3523, there are two white hits and one black hit.

Consider first how you would write a program that given a code word x and a test pattern y, outputs the number of white and black hits. This is more difficult than it appears. It is easy to calculate the black hits. To calculate the white hits is a bit more involved. The trick is to compute total of black and white hits and then subtract the black hits. The total is:

min(x(n1), y(n1)) + min(x(n2), y(n2)) +…+min(x(n6), y(n6))

where x(n1) is the number of pegs of color n1 in x and y(n1) is defined likewise.

Consider how to write an application that allows a human player to guess. To create a secret code it is required to generate a random number m such that 0 ≤ m < 1296. To compute x1, x2, x3 and x4 from m, realize that

m = (((x1*6 + x2)*6 + x3)*6 +x4

Thus

x4 = m mod 6;
x3 = (m/6) mod 6;

… and so on. Another interesting situation is: what happens if the code word cannot contain repeats? See an earlier blog for details. I digress…

To come back to the problem of designing an application that allows the human player to guess, all we need is to come up with the secret code and a way of computing the hits for any guess. We have covered both of those earlier and now we’ll address the problem of designing a program that guesses the code. The first guess can be any random collection of four symbols. Then:

  1. response = GetResponse(firstGuess)
  2. let currentGuess =0000
  3. if the response is all black the game is over.
  4. For each of the known (guess,response)
    1. if currentGuess were the code word would it yield the same response for the guess
    2. if not increment currentGuess and repeat loop
  5. response = GetResponse(currentGuess)
  6. got to step 3.

This is probably the simplest solution while ignoring minor optimisations. Knuth in the above mentioned paper gives another procedure that identifies the code in five guesses or less.

Min-Max Solution

In the above algorithm we took the first candidate that was consistent with the known responses. There could be more than one such candidate. Let us call that set S. Consider a random guess g. Let r be the response. Let S(g,r) be the set of all candidate guesses that are consistent with the known data and consistent with a response r for a given g. A given guess could potentially have 15 responses. The aim is find g such that

ming{maxr {|S(g,r)|}}

where |S| refers to the size of the set S. In other words for each g of the 1296 candidate guesses compute max{|S(g,r)|}over the 15 possible responses r. Find the g that minimises this vale.

Knuth shows that for an initial guess of 1122 the number of guesses to reach the correct result is at most five.

Ref:
[1]D.E.Knuth, “The Computer as Master Mind,” Journal of Recreational Mathematics, Vol. 9(1),1976-77, (available as on Sep. 20, 2015- http://www.dcc.fc.up.pt/~sssousa/RM09101.pdf)

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 Algorithm, Software Puzzle and tagged , . 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