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

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

Problem Description

Program as "seeker" (Human scores computer guesses.)
Human as "seeker" (Program scores human guesses.)

Mastermind is a commercial board game with an interesting history.   It was invented in 1970-71 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 code-breaker (or seeker), to guess the secret code chosen by the other player, the code-maker (the hider).   The code is a sequence of 4 colored pegs chosen from six colors available.  The code-breaker makes a series of pattern guesses - after each guess the code-maker 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 code-breaker guesses the correct pattern in 10 or fewer turns, he wins, otherwise the code-maker 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.)

Non-programmers 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 & Techniques

I wrote the Delphi version of this game couple of  years ago when Kristen,  then a 9-year 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  code-breaker.   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 min-max 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.

Level 3: "Smarter than you" improves the next guess by going one step further. Understand that the eligible patterns described in the preceding step are unique to that score.  For any guess, for each score there is a corresponding set of patterns that would produce that score, lets call it a scoreset.  The set of all possible scoresets  partition the eligible of patterns into groups with respect to a specific guess.    We can use scoreset information to maximize the pruning that will occur.  Since the solution lies in one of these, it seems that it would be good to choose and answer that makes all the scoresets as close as possible to the same size.  That's the idea of the min-max algorithm. 

 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):

Table of Scoreset counts for two possible next guesses 
Scores RRGB RGBG
(0,0) 25 15
(0,1) 4 84
(0,2) 6 0
(0,3) 0 0
(0,4) 0 0
(1,0) 15 0
(1,1) 10 0
(1,2) 0 0
(1,3) 5 0
(2,0) 5 0
(2,1) 3 0
(2,2) 2 0
(3,0) 24 0
(4,0) 1 1
Max 25 84


The min-max heuristic says to compute all of the scoresets for all eligible patterns and select as a guess the one whose maximum scoreset size is smallest.   In he above sample, RRGB would be a better guess than RGBG because it is very likely that the score from RGBG guess will be (0,1) and reduce our eligible pattern space from 100 only down to 84.  If we chose RRGB on the other hand, the eligible search space will be reduced to a number no larger than 25.    Got it?  If not, check out some of these links for more information. 

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.doc

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 peg-6 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 mini-max 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 mini-max 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 

 

bulletBrowse source extract
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

It would be interesting to provide a user login and then track performance over time.  You definitely get better with practice.  Then you could also include a "top 10" list etc.  
(Done May 1, 2004)  Adding colors and number of pegs makes the game more complicated very quickly.   Pressman  now markets an "Advanced Mastermind" version that looks like it has 5-peg patterns and 8 colors.  I wonder if the solving algorithms included here would scale up that far.    It wouldn't be too difficult to generalize the program to accept a variable number of pegs and colors, except for scaling the graphical elements.    The rest would be largely a matter of converting some arrays to dynamic arrays and replacing some constants with variables.    

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2014, Gary Darby    All rights reserved.