See what's going on with flipcode!




 


Submitted by , posted on 05 November 2001



Image Description, by


I'm currently studying Computer Science at Maastricht university, and this is the result of the first project of the first year: a simple Mastermind game in java.

The most interesting part was thinking up the algorithms to make the computer break a code. We came up with 2 solutions:

--- Heuristic ---
A random code is generated. We then compare our newly generated code to all the previous guesses we have already submitted. The evaluation we get from our new guess and an old guess has to be equal to the evaluation of that old guess and the secret code. If this is true for all the old guesses, the new guess is possibly the secret code and can be submitted. If not, we start over.

Efficiency: 4.64 guesses average over 10.000 games (code of 4 pegs and 6 colors).

--- Optimal ---
This algorithm calculates the usefulness of every code. This is done by calculating, for each marker, the probability this marker occurs with this code and multiplying this value by the amount of codes that are invalidated when that marker actually is received.

Efficiency: 4.38 guesses average over 1000 games (code of 4 pegs and 6 colors). This algorithm comes quite close to the theorethical minimum number of guesses needed: 4.34

We used a very modular and flexible design that separated the actual mastermind game from the interface used. As a result, it's very easy to implement eg. a textual interface if need be.

Remark: Java is not as system-independant as Sun would have you believe. When I ran this applet in linux (RedHat 7.1, KDE 2, JDK 1.3.1) the windows weren't resized properly. Additionaly, there were slight alignment differences of the GIU components. Might be a KDE problem, but I haven't tried it with another windowmanager.

You can download the zip file (including jar file, source code and javadoc) here (320k). To run the applet, open MastermindApplet.html in your browser. Enjoy!



[prev]
Image of the Day Gallery
www.flipcode.com

[next]


 


Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.