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.
I recall burning three or four weeks of a sabbatical getting Saccade.com on the air with Wordpress. So much tweaking…