[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 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 & TechniquesI 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. 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 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
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |