[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]


Problem Description
Mastermind is a commercial board game with an interesting history. It was invented in 197071 by Mordecai Meirowitz, an Israeli Postmaster / Telecommunications expert After many rejections by leading toy companies, the rights were obtained by a small British firm, Invicta Plastics Ltd. Over 50 million copies later, the game is still marketed today. (Thanks to Toby Nelson's Mastermind site for this information. Mastermind is a registered trademark of Pressman Toy Corporation, by agreement with Invicta Toys and Games, Ltd., UK.) Here's a link to the official website for the Mastermind board game: http://www.mastermindboardgame.com/. The idea of the game is for one player, the codebreaker (or seeker), to guess the secret code chosen by the other player, the codemaker (the hider). The code is a sequence of 4 colored pegs chosen from six colors available. The codebreaker makes a series of pattern guesses  after each guess the codemaker gives feedback in the form of 2 numbers, the number of pegs that are of the right color and in the correct position, and the number of pegs that are of the correct color but not in the correct position  these numbers are usually represented by small colored pegs. If the codebreaker guesses the correct pattern in 10 or fewer turns, he wins, otherwise the codemaker wins. (Note: In version 2 of my program, I added 5 and 6 peg patterns and eliminated the "scoring pegs". Unlike the board game, can computers accept actual numbers and that is the now way we get or give scores.) Nonprogrammers are welcome to read on, but may want to skip to the bottom of this page to download an executable version of the program. Background & TechniquesI wrote the Delphi version of this game couple of years ago when Kristen, then a 9year old precocious granddaughter, introduced me to the game and beat me consistently . This computerized version has three IQ levels and, at level 2 or 3, is essentially unbeatable. As with most problems on this site, understanding and implementing the solution algorithms was the most fun. Donald Knuth, the father of the study of computer algorithms, published a paper titled "The Computer as a Mastermind" in the Journal of Recreational Mathematics in 1976. Unfortunately, it isn't widely available and I haven't been able to locate a copy. There are several discussion sites though that reference Knuth's techniques and allowed me to figure out the algorithms involved (I think). (November 2010  a viewer recently pointed out that the paper is currently available at http://www.dcc.fc.up.pt/~sssousa/RM09101.pdf.) Here are the basics: Since there are 4 pegs, each of 6 possible colors, there are 6X6X6X6 or 1296 patterns. The score of a guess can be represented as an ordered pair of integers (n, m) where n= # of pegs in correct location and correct color compared to the secret pattern, and m=# of pegs of correct color but in incorrect location compared to the secret pattern. Each number of the pair can range from 0 and 4. Of the 25 possible guesses, only 14 are valid. Any guess with the sum of n and m greater than 4 is invalid  there are 10 of these, In addition the guess (3,1) is invalid. Why? The interesting part of the program is as codebreaker. A Patterns array of TPatRec is built to hold the 1276 possible patterns. Each TPatRec contains an array of 4 digits representing the peg colors and a Boolean flag indicating whether this pattern is still eligible as a solution. An array, Guesses, of TGuessRec is also kept with a history of guesses. Each TGuessRec contains the index into Patterns for the pattern and the two score numbers, NbrInPos and NbrOutOfPos representing n and m as defined above. In order to keep this discussion to a reasonable size, I'll just touch on the two trickiest items here: the pruning technique for IQ level 2 and 3, and the minmax technique used in IQ level 3 to converge the pruning a little faster. These are not intuitive, at least to me, and it took nearly as long to get up to speed this time around as it did when the code was originally written. But really cool if you stick to it until the mental light bulb comes on. As an aid, I've just added a "Verbose" form to the program that can be activated to show some intermediate results. There are 3 levels of "intelligence" in Mastermind's solver: Level 1: "Not real smart"  Uses 3 "dumbed down" heuristics to determine which patterns remain eligible as solutions. See code for details. I wanted to get it smart enough to succeed most of the time, but still lose occasionally.
Level 2: "Pretty Smart"  Levels 2 and 3 use a trick that prunes the possible solutions fairly quickly. It takes advantage of the surprising fact that
scoring is symmetric, i.e. Score( secret pattern, guess) = Score(
guess, secret pattern). This implies that given any guess and the resulting score, we can pass through all eligible patterns and select
those that produce the same score as the score we were given. The solution is guaranteed to be among these. Level 2 selects the first
of these eligible patterns as the next guess. As a hypothetical example, assume we have 100 eligible patterns remaining and two of the guesses return results as follows (in practice we would do this for all 100 patterns):
http://www.tnelson.demon.co.uk/mastermind/ http://www.maa.org/editorial/knot/Mastermind.html
I also found a couple of draft Word documents regarding the algorithms that I seem to have written last year. I have no recollection, but MSWord says that I'm the author and I can't find any similar documents on the web that I could have plagiarized, so maybe I did. As they say, the only thing worse than getting older is the alternative. Anyway, here they are: Mastermind Algorithm Example.doc
Addendum May 1, 2004: Version 2 posted today extends the game to 5 and 6 peg versions. Users now have control over number of pegs in the pattern (3 to 6) and the number of colors to choose from (also 3 to 6). The 6 peg6 color version of the game has over 46,000 possible patterns and the "Smarter than you" level will take a few seconds to do its minimax analysis.
Addendum January 10, 2010: A university student implementing Mastermind in Java for a class project recently wrote asking for help in understanding the Level 3 IQ level. In trying to use the "Verbose" option of my program to help make the minimax algorithm clear, I realized that the detail display was being cleared for each guess. This made it difficult to view the details for an entire solution. Version 2.1 posted today fixes that problem and, as usual, also includes a few other minor enhancements.
Running/Exploring the Program
Suggestions for Further Explorations

[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 20002014, Gary Darby
All rights reserved.
