Analyzing guess (aka. Mastermind)

Guess is a simple code-breaking game where the player tries to determine a secret color combination. The player guesses a sequence of colors and gets two pieces of information back: (1) how many colors are correct and in the correct position, and (2) how many colors are correct but in the wrong position. With this information the player guesses again until the secret code is revealed.

In the standard game, the color code contains four places - each place can be assigned with one of six possible colors.

Following are a few Python methods to analyze the game.

Basic properties

To get the number of possible solutions for a specific game configuration (i.e. a combination of number of places and number of colors) the Python package itertools can be used.

1 def getSolutionSet(game):
2   return list(itertools.product(range(game.colors),
3                                 repeat=game.places))

This method returns a list of the cartesian product of the set of usable colors - multiplied number of places times.

The number of evaluation posibilities can be calculated as follows:

1 def blackWhite(game):
2   return [(b,w) for b in range(game.places+1)
3                 for w in range(game.places+1)
4                 if b+w <= game.places]

Returned is a list of tuples containing values for ‘black’ (= correct color at correct position) and ‘white’ (= correct color at wrong position).

Evaluation method

The core method is the evaluation method: given a specific guess and the solution - determine the ‘black’ and ‘white’ values.

 1 def evaluate(guess, solution):
 2   # number of correct colors at the right position
 3   black = 0
 4   for i in range(len(guess)):
 5     if guess[i] == solution[i]:
 6       black += 1
 7   # number of correct colors at the wrong position
 8   white = -black
 9   for c in set(guess):
10     white += min(guess.count(c), solution.count(c))
11   return (black, white)

Determining the number of colors at the correct position can be done straight forward (lines 3-6): compare every position and count the number of matches. Determining the number of colors at the wrong position is a little bit more effort. After playing around with different strategies based on list manipulation, I found the most elegant solution (lines 8-11) in a paper written 1976: “The computer as master mind” by Donald E. Knuth. Basically, the minimum numbers of occurrences of each color in guess and solution are added to the number of “relevant” (= either ‘black’ or ‘white’) positions. Now the number of ‘black’ guesses are subtracted. Simple.

Optimal game

With these basic components in place, methods for analyzing the game can be implemented.

First we need methods to reduce the set of possible solutions - based on a specific guess and an evaluation.

1 def reduceSolutionSet(guess, evaluation, solutionSet):
2   return [s for s in solutionSet if match(guess, evaluation, s)]
3 
4 def match(guess, evaluation, solution):
5   return evaluation == evaluate(guess, solution)

The method reduceSolutionSet selects those solutions from a list of potential solutions that have - compared to a specific guess - the given evaluation. In this way, starting with the list of all possible solutions, the number of solutions can be reduced with every guess.

To determine the best guess for a given list of possible solutions the following method can be used.

1 def bestGuess(game, solutionSet):
2   bestGuess = solutionSet[0]
3   remaining = len(solutionSet)+1
4   for guess in solutionSet:
5     r = maxRemainingSolutions(game, solutionSet, guess)
6     if r < remaining:
7       bestGuess = guess
8       remaining = r
9   return bestGuess

A guess is considered as “best” if it reduces the set of possible solutions the most - regardless of the actual evaluation. The helper method maxRemainingSolutions calculates for every possible evaluation how many solutions remain and returns the highest number.

The underlying assumptions of the bestGuess method is that (1) the best guess must be contained in the set of remaining possibilities and that (2) it can not occur that choosing not the best guess leads in the next step to an even greater reduction of possibilities. I have not tried to proof these assumptions.

Analogous to the “best guess” we can try to find the “best evaluation”. The best evaluation is the evaluation that keeps the most possibilities, assuming that the secret code is created during the game - not beforehand.

1 def bestEvaluation(game, solutionSet, guess):
2   result = (0,0)
3   remaining = -1
4   for evaluation in blackWhite(game):
5     r = len(reduceSolutionSet(guess, evaluation, solutionSet))
6     if r > remaining:
7       result = evaluation
8       remaining = r
9   return result

Again, every possible evaluation result is checked and the best evaluation is returned.

Now the optimal game can be calculated, that is: the best guess is always answered with the best evaluation.

 1: (0, 0, 1, 1) (0, 0) - 256 solutions remaining
 2: (2, 2, 3, 4) (1, 1) - 46 solutions remaining
 3: (2, 5, 2, 5) (0, 0) - 6 solutions remaining
 4: (3, 4, 3, 3) (0, 2) - 1 solutions remaining
 5: (4, 3, 4, 4) (4, 0)

As you can see, the standard game should always be solvable in five (or fewer) steps.

Conclusion

The described methods can be used to analyze the standard game of Mastermind. Analyzing different versions of the game (more places or more colors) quickly leads to large running times and a high memory consumption.

You can find the code at GitHub. I am sure that the implementation still leaves room for improvements.

If you want to play the game online, I recommend Guess - part of the great Portable Puzzle Collection by Simon Tatham.