 |
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!
|
|