Skip to content
16 May 32011 / Robin Wellner

Mastermind Solver

Last week, our assignment for Object Orientation was to implement a version of Mastermind in Java. The implementation of the AI was okay, but it could have been better. It was a strategy I wrote as a temporary solution. Sometimes it won — sometimes in four or five times — but other times it lost. This was the entire reasoning of the AI:

  1. Each position gets a list with all possible values (A, B, C, D, E, F).
  2. I choose a random value from each list to select the next attempt.
  3. If the score I get for attempt the attempt (for example ABCD) has no red points, I know that:
    • A cannot be in the first list, so I remove it.
    • B cannot be in the second list, so I remove it.
    • C cannot be in the third list, so I remove it.
    • D cannot be in the fourth list, so I remove it.
  4. If the score I get for the attempt has no white points either, I know that all the colours in the attempt must be removed from all the lists.
  5. If the right solution hasn’t been found yet, go to 2.

That’s it. That’s the whole of the algorithm. I didn’t think it would work. But sometimes, it did. It was more luck than wisdom, but still.

As you might know, our major is Artificial Intelligence, so I wanted to make it smarter, once we dealt with the annoyance of MVC — I can see how that can be useful in certain situations, but we never have practical assignments that do the pattern justice.

Anyway, the Wikipedia page I linked to earlier had an interesting section on algorithms. I wanted to implement one of them, but we soon abandoned the idea. Firstly, the computer playing a near-perfect game each time seemed boring. Secondly and more importantly, Java couldn’t let us do it easily or elegantly.

The problem seemed to be object orientation to me. It simply wasn’t cut out for this. I thought functional implementation would be much better. Java really sucks at this, so I made up my mind to write an implementation of Knuth’s five-guess algorithm in Python, using every functional trick I could think of.

That’s exactly what I did last weekend. The complete program, with CLI, is only 42 lines long (yes, that was intentional). And it works. You can supply a code as a command line argument, or enter it later. The first attempt is always AABB. The second attempt takes a while. Depending on the score at the first attempt, it may take twenty or forty seconds on my machine, but I have seen it take only three.

At first, it didn’t work. It took me some time to find the problem: the search space was too limited. Because of careless reading, I used the wrong function to generate the list of all possibilities. It actually generated a list of permutations of ABCDEF of length four, meaning codes containing duplicates (AABC or DABD, for example) could not be found. Using the right function solved all that.

I made a Gist, enjoy.

PS: I don’t like using a global to keep track of the number of attempts. If you know of an elegant and functional solution, please let me know!

Advertisements

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

%d bloggers like this: