A simple, naive implementation of a MasterMind solver

November 22, 2009 | Games and Diversions | By: Mark VandeWettering

Okay, I woke up this morning, and decided to code up a version of a MasterMind solver. About fifteen minutes later, I had this tremendously slow implementation, which nevertheless seems to solve patterns very pretty quickly (averaged just 4.71 guesses in the short run of 100 trials that I just ran. It’s tremendously slow though, for reasons which I should have guessed before I wrote it. Nevertheless, it does work fast enough that if you wanted to write a Mastermind solver, it would work just fine.

Here’s the idea. Start by simply trying to guess the code by picking one at random. Assuming that you didn’t win, you need to generate a new guess. Let’s generate one and pretend that it was the secret. If you evaluate it against all the previous guesses you make, it would need give the same results. If it doesn’t, it can’t be the secret, so don’t use it as your guess. Try a different one.

That’s it. Of course the reason it’s slow is that when you get to the end, very few of the random choices you’ll make will match all the previous results (there are 1296 possibilities in the 6,4 version of classic Mastermind), so you might have to try lots and lots and lots of guesses before you find the consistent one. The better way would be to use a list of all possible codes, and strike out the ones in each round that are inconsistent with the previous guesses. Then you can select among all consistent codes. I’ll write up that optimization shortly, which should speed up the code by several hundred times. But this one does work… check it out.

#!/usr/bin/env python
#
# A naive implementation of the game MasterMind, to test some ideas 
# that I learned in a brief scan of some of the known literature.
#

import random
from sets import Set

# traditional Mastermind uses six different colors, not exactly certain
# what they were, so I chose Red/Yellow/Blue/Orange/Green/Purple...

colors = ['R', 'Y', 'B', 'O', 'G', 'P']


# generate a random secret code (or guess)

def randomcode():
        return ''.join([random.choice(colors) for i in range(4)])

def evaluate(guess, secret):
        b, w = 0, 0
        gs, ss = Set([]), Set([])
        for i in range(4):
            if guess[i] == secret[i]:
                b = b + 1 
            else:
                gs.add(guess[i])
                ss.add(secret[i])
        return b, len(gs.intersection(ss))

def solve(secret):
        history = []
        guess = randomcode()
        nguesses = 1
        while True:
                b, w = evaluate(guess, secret)
                history.append((guess, b, w))
                print guess, b, w
                if b == 4:
                        break   # we solved it...
                # generate a new random guess, consistent with
                # all the previous guesses.
                nguesses = nguesses + 1 
                while True:
                        guess = randomcode()
                        consistent = True
                        for g, b, w in history:
                                nb, nw = evaluate(guess, g)
                                if nb != b or nw != w:
                                        # nope, not consistent
                                        consistent=False
                                        break
                        if consistent:
                                break
        print
        return nguesses

ROUNDS = 100
totalguesses = 0

for x in range(ROUNDS):
        totalguesses = totalguesses + solve(randomcode())

print "average number of guesses was %.2f" % (float(totalguesses)/ROUNDS)

Addendum: I coded up the optimization that I mentioned above, and it seemed not to help that much. Run time dropped from 21 seconds to 17 or so. Not very good. Perhaps I don’t know what’s going on here. Then again, I still haven’t had any caffeine this morning, so perhaps my puzzler isn’t quite up to speed yet.

Share Button
Be Sociable, Share!

Comments

Comment from D. Eppstein
Time 11/22/2009 at 11:45 am

How about: among the 1296 possible guesses, choose the one where the Shannon entropy of the answers you would get back (assuming all states of the puzzles consistent with what you’ve seen so far are equally likely) is maximized? Your heuristic amounts to choosing one where the entropy is nonzero but you should be able to do better. With this comment I’m not so much interested in runtime as in reducing the number of moves you need to win.

Comment from Pseudonym
Time 11/23/2009 at 9:59 pm

There are two possible metrics which are “optimal”. One is to minimise the average number of guesses, the other is to minimise the worst possible number of guesses. It is known that there is no strategy which simulaneously optimises both for 6,4 Mastermind. (See Kenji Koyama, Tony W. Lai, ‘An Optimal Mastermind Strategy’. Journal of Recreational Mathematics, 1993.)

At each stage in the game, you have a set of possible codes that haven’t yet been eliminated. Some cases are easy. For example, if you have one or two possible codes left, it’s clearly optimal to just pick one.

If you have more possible codes left, each potential guess partitions those codes into 11 groups (because there are 11 possible “responses”). A locally optimal strategy is to consider all possible codes, and guess the one that minimises the maximum size of each resulting group.

Intriguingly, though, this optimal choice is sometimes one of the codes that has already been eliminated. You should especially consider this possibility when you have 11 possible codes left.

Comment from Pseudonym
Time 11/23/2009 at 10:05 pm

Oh, one more thing.

The optimal opening guess turns out to be ABCC. Of course it doesn’t matter which colours you use for A, B and C, and it doesn’t matter how you permute them, as the symmetry group of Mastermind has order permutations and colour exchanges as subgroups.

Comment from Ed Collins
Time 8/28/2012 at 4:02 pm

Hi Mark,

I’m responding to this article almost three years late, but what the hell. Maybe someone else will stumble upon it just now, like I did.

1) As mentioned above, when you generate a random, initial first guess, your guess ideally should not quite be random. It should either be 1,2,3,4 or 1,2,3,3. (All four different colors or three different colors, with one duplicate.) Each of these are about the same and each is much better than a “random guess.” A random guess could, at times, include 1,1,1,1, (the same color four times) or 1,1,1,2, (the same color three times) which are terrible guesses. Your overall average solution per row will go down if you do this.

2) You’re right… your improved code should have sped it up tremendously. My Mastermind solver can solve tens of thousands of random codes in less than a second or two. You must not have coded it correctly.

Each subsequent random guess should only come from the list of all possible codes left. Each turn you could move all of these possible codes left to a new array, and then pick a random number from 1 to the length of the new array. That’s it. When you’re down to 1 possible code left, there is no searching. The program knows exactly what it is without having to search for it.

You’re certainly a better programmer now than you were three years ago. Give it another go and report back here.

Write a comment