Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Koen Vossen, posted on November 05, 2001




Image Description, by Koen Vossen



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]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
array

November 05, 2001, 12:33 PM

wow, nice job. Im currently a computer science student at DePaul University in Chicago, IL (USA), and I have to say great work.

 
Joshua Schpok

November 05, 2001, 12:43 PM

Good stuff, paco! CS and Math student at Purdue University, IN (USA)

 
lycium

November 05, 2001, 01:02 PM

love the background :)

i'm interested in the theory behind this... how can there be a defined minimum number of gueses? is there a certain minimum amount of information required to solve some simultaneous equations, or? perhaps it's more simple than that...

i'm off to learn how to play mastermind now ;)

 
Taharez

November 05, 2001, 01:08 PM

Nice. I think our CS department had this as a project in their Java class, we have had fractal generation, and game framework ( for creating snake and tetris like games ) as projects.

I'm an Information Engineering student at Chalmers University of Technology (Sweden), I guess I should say =)

So, do all of you guys have Java courses? Would be fun to know what they're called, mine's 'Foundations of Object Oriented Programming', almost all of our courses have hyped-up names, kinda lame me thinks..

 
Joshua Schpok

November 05, 2001, 01:34 PM

Here at Purdue, they hit us with Java first thing. They had for the basic intro course and had us building pretty sophisticated applets (word processor, chess game) by the next semester. The compilers class I'm taking this semester is too in Java. We're using a derivative called Generic Java that allows C++-like templates.

Basically everything here is taught in Java, until you get into the gritty algorithm and database courses, for which Purdue is known for. Those are typically C.

 
Ron Frazier

November 05, 2001, 01:34 PM

There is something not quite optimum in your algorithm. I tried it a few times, and one time got a strange result. I did computer generated, computer solved with optimal algorithm, on a 4 peg/6 color level.

Colors:
W = White/Gray
Y = Yellow
O = Orange
R = Red
G = Green
B = Blue

The solutions was
Y O G W

The computers guesses (results: black/white) were:
Guess 1: B W R W (1/0)
Guess 2: G Y O W (1/3)
Guess 3: Y G G W (3/0)
Guess 4: Y O G W (4/0)

The funny thing is, notice from step 2 to step 3, it put in a color that it already knew was wrong (ie: replaced the orange with a green). Doesnt seem like the optimal thing to do.

However, after thinking about it, it might be possible that this was part of its intended strategy...maybe it helped it narrow down the position of the last 3 pegs. So it may be right after all, but my initial gut instinct was that it was wrong. Thought I would flag it for you so you could investigate it (if you arent already aware of this behavior) and see whether or not there might be a bug in your AI.

 
fluffy

November 05, 2001, 01:38 PM

Wow, under 5 moves average for 6 colors? That's quite impressive. Whenever I play I have a brute-force approach which doesn't do quite that well.

My approach is that I start out iterating through all four of the same color until I get some 'hits'. Then I know how many of that color there are, so then I replace the remaining ones with the next color and shift stuff around until I break the code. The worst case for that is when there's four different colors and they're the last four that I pick. I haven't done a formal complexity analysis, though. :)

 
Morlith

November 05, 2001, 01:53 PM

Great Work!
I love puzzle solving techniques. Unfortunately, I'm not very good at it... =)

btw:
You're from Maastricht? I'm a Computer Science student at the University of Technology in Aachen, which is not very far away, hehe.

 
mstr

November 05, 2001, 02:29 PM

"When I ran this applet in linux (RedHat 7.1, KDE 2, JDK 1.3.1) the windows weren't resized properly."

I've seen this same problem. My application worked fine in Gnome, fwwm2 and Windows, but KDE2 messed it up.

 
Morgan

November 05, 2001, 02:44 PM

Swing is pretty lousy at platform independence. The JVMs themselves are pretty much rock solid. I've been looking at using Java on the back-end and C++ for GUI's in order to fix this... pretty ironic!

-m

 
Joshua Anderson

November 05, 2001, 03:12 PM

Looks nice! I'm a CS and Physics major at MTU (in the UP Michigan), and the first year students do Java here. Then second year, they need to take C++ for Java programmers, as all the high-level CS courses are C++ based.

Swing is pretty lousy at platform independence.

Hehe. My friend found that one out the hard way halfway through a big software project. Different X-windows window managers would choose different fonts and font sizes, screwing up his layouts.

Josh

 
ReAL

November 05, 2001, 04:00 PM

Real cool, Next year probably my turn to make such a thing :)
if all goes well this I'm going to Hogeschool Utrecht next year

(informatica natuurlijk ;)

 
MdREV

November 05, 2001, 08:44 PM

I'm currently finishing my final year at Deakin University in Australia. Our programming intro in 1st year was in VB5.0. We then moved on to C, C++ and Eiffel in 2nd year. We didn't touch java until this year and the subject was entitled "Advanced Web Programming" and concentrated more on sockets and threads than application programming.

Our course seems like it is alot more general than most courses you guys speak of, we have covered everything from "Communication Skills for Information Technologists" to "Advanced Database" and not spent too much time on programming, especially since the course was titled "Computer Science / Software Development".

 
[-WD40-]

November 05, 2001, 10:16 PM

MdREV: same here in Laval University in Canada (Quebec), we spend more time studying abstract concepts than coding "usefull" stuff...

I'm in my second year out of three needed to obtain the diploma and about now we've studied stuff like:

Operating Systems
Algorythms (efficiency and stuff)
C/C++/ASM
Database Design and managment
Internal sturcture of computers (I/O devices, processor, memory, etc..in term of electronic components in general)
Linear Algebra / Probabilities and statistics
AI (the basis)


There are some more technical stuff to come but as of yet it's very general....we didn't even had 1st or 2nd year projects and that's a shame! Everything I know about programming languages and tricks I learned it by myself and I'm glad I did because I wouldn't feel very confidend otherwise going out of university with my diploma in hands and knowing only the basis of using a certain programming language...but anyway I think university is aimed at learning how to think abstract concepts rather than coding something like a machine.

But still I'm always amazed at what other people are doing in their university, some things are very impressive

 
Politik

November 05, 2001, 11:29 PM

I'm running the optimal algorithm on a 6 position, 6 color, 10 guess code and its been about 10 minutes and it still hasnt made its first guess. It IS however using all my processor.

 
Jeff Olson

November 06, 2001, 12:13 AM

Java taught from day one at my university also(western oregon university, oregon(USA)) and they later move you to MFC for the last year your there. Although, rumors around the place are that they will move the senior year stuff to .net next year. Oh well :/

I do know that Portland State University, Oregon(USA again, heh) does c++ then later to asm then let you use whatever you feel is needed for your senior year.

 
Shplorb

November 06, 2001, 01:29 AM

Here at Flinders it's all Java because Sun donated 100 odd xterms and a few meaty servers to the uni (though they strenuosly deny thats the reason they teach java now instead of ADA and C). We also got topics with buzz-word names that were thrown together to have something spiffy sounding to teach - even though they're all about crap. i.e. Information Technology Applications 2 - or how to write simple HTML and JavaScript (and the lecturer swears by the motto "graphics are evil and Java applets (for forms!!!) are great".)

 
Taharez

November 06, 2001, 03:44 AM

Thanks for your replies =)
I guess Java is popular as a teaching language because it's relativly easy, but mostly because all of the helper classes. Sad that we have such a bad IDE ( BlueJ ) =(

I'm curious of another couple of things, how long is your education and what kind of title do get after finishing it?
Mine's 4.5 years, and the title is 'Civilingenjör' ( or 'Master of Engineering' after running it through the translator ). Also, the first 3 years contain the basic courses, and are each terminated by a project, year 4 is for study of your choice, and the last year is the finishing project.

 
NinjaCross

November 06, 2001, 04:23 AM

Hey, really amazing stuff ! Can you send us your algorithms ? I WANNA read them ! ;)

NinjaCross
www.ninjacross.it


 
Sampsa Lehtonen

November 06, 2001, 04:36 AM

??? Didn't you download the zip file?

 
Hydri

November 06, 2001, 06:13 AM

I'm studying Computer science at Umeå university (sweden).
Are we the only ones who learn ML as introduction language?
(we had a java course too of course).

I think it was a pretty good idea to start with ML, because you learn to think in new ways.

 
Koen Vossen

November 06, 2001, 06:47 AM

Thanks everybody for all the comments!

lycium
I downloaded if from EndEffect. They're really amazing! This wallpaper is called Micro.
Concerning the minumum number of guesses needed to break a code (4 pegs, 6 colors): in 1993, Kenji Koyama and Tony W. Lai calculated that the best strategy uses an average of 5625/1296 = 4.340 moves (with just one case needing a six move solution).

Ron Frazier
In the optimal algorithm, the guess that yields the most information about the secret code is submitted. It need not be correct (in the sense that it could be the secret code).

Politik
The optimal algorithm is quite slow. That's because it calculates the usefulness of every possible code each time it submits a guess. When you have 6 pegs and 6 colors, there are pow(6, 6) possible codes. For each of those 46656 codes the usefulness is calculated (we do not exclude codes that aren't possible anymore, because they still can yield a lot of information - see previous paragraph). This calculation again involves iterating over 46656 codes (this is needed to get the number of codes that are invalidated by our guess and a certain marker, and to calculate the chance we actually receive that marker when we submit the guess).
However, with a little tweaking (and, most importantly, rewriting it in a decent language :), it can probably be made a lot faster.

 
NinjaCross

November 06, 2001, 07:19 AM

Uops, sorry, little mistake :)

NinjaCross
www.ninjacross.it

 
Neil Edelman

November 06, 2001, 11:33 AM

Is everyone here in computer science? I guess that would make
sense, hehe. Here at McGill, in Montreal (Canada) I'm in physics and
math and there aren't really any serious programming classes at all
(which also makes sense :].) I love being able to prgram whatever I
want whenever I feel like it without having to do assigned projects
and learning what I need as I go along. The variety is nice too, so
I'm quite happy with not being in CompSci. Not that I wasn't
tempted . . .

 
Phantom

November 06, 2001, 11:35 AM

Koen,

Suppose you have two guesses that both yield the most information about the secret code, but one of them is guaranteed to be 'wrong', while the other could be 'right'. Wouldn't it improve the average efficiency of the algorithm if you picked the 'could be right' one in that case?

Interesting problem. :)

- Jacco.

 
Koen Vossen

November 06, 2001, 11:40 AM

That's already implemented. When there's a choice between a code that's still possible, and another that's not, the former is chosen.

 
TrapZZ

November 06, 2001, 01:36 PM

not too much to add to the cool comments, but it's great to see an IOTD having to do with logic.... nothing against pretty pictures of course ;)

 
Ron Frazier

November 06, 2001, 01:59 PM

OK, I did some detailed analysys of the example I posted yesterday, and it turns out that your algo was right. I was indeed chosing the best worst-case action it could take. Based on the example I gave, using all of the information available after the computers second guess, here is what I came up with.

Had the computer used all 4 correct colors, its success rate is:
25% chance it will get it on the 3rd guess
25% chance it will get it on the 4th guess
50% chance it will get it on the 5th guess

However, with the scenario the AI used (purposely throwing in one wrong color), the success rate is:
0% chance it will get it on the 3rd guess
100% chance it will get it on the 4th guess

So congrats on this. After detailed examination, your AI did indeed pick the best guess for minimizing the worst case scenario.

 
klaudius

November 07, 2001, 04:59 AM

Have you think to train a neural network to solve this problem ?

 
Koen Vossen

November 07, 2001, 07:49 AM

That could be nice to do indeed.
I have been thinking of a genetic approach, that would be cool too.

 
This thread contains 30 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.