Mastermind Directory

- The Game (The Java applet.)
- Implementation Instructions (Explains how to use the interface.)
- Mastermind Instructions (Basic rules for people who have never played.)
- Source Code and Discussion (Read the source code. See how it works!)

**
Implementation Instructions
**

To start the game, simply click on the link above which leads to the applet.

To play first choose how many colors and how wide the puzzle should be by using the pull-down boxes. Then press the Start button. The applet will draw the board on the screen. The computer determines how many turns to give you based on how wide the puzzle isand how many different colors can be in it.

To make your first guess, press on one of the color buttons. Then move the mouse to one of the light gray square slots that is in the row surrounded by a black rectangle. The black rectangle indicates which is the active row. After you have filled all the square slots with pegs hit the Submit Turn button. The computer will then award your turn the correct number of white and black pegs which will appear in the light gray rectangle. The computer will also make the next turn the active one.

If you are having a problem figuring out the answer, you can click the Reveal button, which will reveal the answer, but also ends the game. No cheating!

When the game is over click the Clear button and start all over again.

The Solve button gives you a chance to watch the computer work out the answer. No, it doesn't cheat. It follows an algorithm. Warning: For wide puzzles with many colors, the computer takes a while!

If none of this makes sense, just get started, the thing is fairly self-explanatory.

If you have never played Mastermind before, don't worry. An explanation of the game follows immediately.

**
How to play Mastermind
**

The object of the game is to discover a pattern of pegs of different colors, possibly including repititions of one or more of the colors, arranged in a sequence of slots. Colors may also be entirely omitted from the answer sequence.

The goal is accomplished by making a series of guesses, each of which is graded according to some simple rules. If the answer is discovered within the given number of turns, the game is won. If all the guesses are used without solving the puzzle, the game is lost.

The guesses are graded by awarding them either black or white grading pegs. These grading pegs are distinguished from the pegs in the answer in two ways. They are smaller, and are placed in a different place on the board. For each peg in the guess that matches the answer (e.g. a green peg appears in position two in both the answer and the guess) a black grading peg is awarded. If there is a color in the guess that occurs in the answer, but in a different position than in the answer, a white answer peg is awarded.

Note that each peg in the guess will always earn at most one grading peg. If, for instance, the guess has a yellow peg in the first slot and there are yellow pegs in both the first and second slots of the answer, only a single black grading peg will be awarded.

Furthermore, if there are two or more pegs of a certain color in the guess and only one of that color in the answer, this will only lead to one grading peg. For instance, if the guess has blue pegs in the third and fourth slots, and there is a blue peg in the first slot of the answer, the guess will receive only one white grading peg.

Again, if none of this makes any sense start a game with 4 slots and 4 colors and allow the computer to solve it, by clicking the Reveal button. Doing this a few times will soon make it clear how each turn is graded.

**
The Source Code
**

The Mastermind applet is written entirely in Java 1.1. I chose not to use any of the Swing components, as I wanted it to run on browsers without an up-to-date Java plug in.

The program is made up of eleven different class files. In them you will see that I have broken just about every rule of programming you can think of. The implementation of the game is mixed up with the implementation of the interface; there are magic numbers all over the place; things have goofy, unintuitive names. I did some editing and I think it makes some sense. There are even some helpful comments. I should have rewritten the whole thing, but I cannot be bothered. I make no claims about being worthy of the Donald Knuth Award for Beautiful Programming Style. I should rewrite the thing, now that I have some experience, but I am too lazy.

Here is a tarred, g-zipped file of the source code.

The masterApplet class is the one called to get things going. It creates an instance of the gamePanel, the controlPanel, and the colorPanel and lays them out within itself. The controlPanel contains a number of buttons for starting, clearing, etc. The colorPanel has one button for each of the colors used in the game. The gamePanel is where the playing actually takes place. After the initialization is over the applet starts a low priority thread to scan and respond to the buttons of the controlPanel. This thread is what runs the game. (I made it a low priority thread so that the virtual machine will draw what is going on first, and only then move on to doing work behind the scenes.)

The gamePanel contains the messagePanel and the submit button. When a game begins, the gamePanel draws a column of turnPanels within itself. Each of the turnPanels contains some number of slotPanels and a gradePanel. The slotPanels are where pegs are placed. When the clear button is pressed the gamePanel removes all the turnPanels. That about covers the interface.

Beginning a game also creates a guigame object. (Something of a misnomer, since it actually has nothing GUI about it. It got that name because I orginally wrote the game in a command line version entering numbers. When I wrote the graphical interface I had to rewrite the components, hence game became guigame.) The guigame object creates the puzzle to be solved, determines how many turns are to be given the player, and contains the methods for allowing the computer to play. When a guess is entered a new guiturn object is created by the guigame. The guiturn class contains a grade method which allows each turn to grade itself when passed the answer.

When the computer plays it adopts a very simple strategy. I originally wrote the game in command line form. Instead of using colored pegs the puzzle was a list of integers. The computer still thinks of the puzzle as a puzzle-width digit number of base number-of-colors with leading zeroes. (Got that?) All the computer does is guess the lowest possible number in each successive guess.

An example will illustrate matters.

Suppose a game is started with three colors and a puzzle width of three. Each place in the puzzle can therefore be one of three digits. So, the answer might be 021. The computer will first guess 000, the lowest possible number. That turn will of course receive the grade one black peg and no white pegs.

So, the computer starts counting. It tries the guess 001 and compares
that to its first guess 000. In fact, the computer *grades* the
next possible guess against the first guess just as if it were grading
a guess against the answer. Because the guess 001 grades to two black
pegs against 000, and the turn 000 received one black peg, the
computer rejects that guess. (Of course, the correct answer must
grade against any turn exactly the same way the actual answer did.)
The computer checks 002 which again grades to two black pegs compared
to 000. The computer then checks 010. Same problem. Then the
computer checks 011. This grades to one black peg and no white pegs
against the guess 000, so the computer makes that its second guess.

That turn receives the grade two black pegs and no white pegs. The computer then checks 012. This gets one black peg against 000 and two black pegs against 011. Bingo. The computer makes the third guess of 012. It receives the grade one black peg and two white pegs.

The computer keeps counting. The computer then checks the guess 020. This grades to two black pegs against 000, and is therefore rejected. The next possible guess is 021. It grades to one black peg against 000, two black pegs against 011, and a black and two whites against 012. Bingo. The computer makes the guess 021 and wins the game!

If you've watched the computer play, you will of course point out that the computer doesn't follow that algorithm. It does with one minor modification. The computer takes one completely random turn at the beginning. I have a feeling that that will make the computer get to the answer in a shorter number of turns, but haven't made strict test to determine whether or not this is actually so. The results appear dissappointing so far.

The theoretical question of what is the most efficient algorithm for solving the game seems difficult to me. The one I chose seemed to be the easiest to program. (To be honest I cannot think of many others.) It might make a good undergraduate thesis topic. If it turns out to be too easy, consider a two dimensional puzzle, graded with black pegs, white pegs (which have the same meanings as before) and additionally grey pegs if the correct color appears in the correct row or column but not in the right spot. Of course, you could then consider an n-dimensional puzzle with black pegs white pegs and n shades of gray pegs. This seems like a very difficult problem to me, but I haven't thought about it much.

As for the actually implementation of the algorithm that I wrote, I admit it is much sorrier than the algorithm itself. It burns a lot of computer time once a large number of colors and slots are in play. A better algorithm would quickly dispose of stupid guesses. Perhaps working on that would make a good undergraduate thesis with a more computer sciencey flavor.

On the other hand, maybe all this is trivially easy, and I'm just too ignorant to know it.