Associated Topics || Dr. Math Home || Search Dr. Math

Strategy for Playing Mastermind and Similar Games

```Date: 03/26/2007 at 10:45:56
From: Larry
Subject: Algorithm for guessing a 4 digit number with unique digits

I need to guess a 4 digit number that has a unique number in all 4
decimal places.  I will be told how many of my digits are correct and
in the right spot and also how many are correct but in the wrong spot.

Example number is 6527

I guess 1234 - I am told "1 number in the wrong spot"
I guess 5678 - I am told "3 numbers in the wrong spots"
I guess 6578 - I am told "2 numbers in the right spot and 1 in wrong"

At this point, I only switched the 5 and 6, so I know they are the
right numbers.

I guess 6581 - I am told "2 numbers in the right spots"

At this point, I know the 7 belongs in the right most spot because
I had three numbers when I had 6578 and now only 2 with 6581.

I guess 6547 - I am told "3 numbers in the right spot"

The reason I did not choose 6537 is that in the first guess of 1234
at the top, there were no numbers in the right spot and I am looking
for what belongs in the 3rd spot and it can't be the 3.

I guess 6527 - I am told I am correct.

By guessing in the order above, I got lucky.  There are only 10
guesses.  What I don't know what to do is how to guess so I can get it
in 10 guesses.

I don't know if I should brute-force and figure out which 2 in the
first guess?  I think this is a N-Complete problem but with getting
some results of how many numbers are correct, it makes it easier.  It
is harder though because there are only so many guesses.

The same game can be played with 5 digits.  Number = 13579.

I try 12345 - I am told "3 in wrong spots"

I know there are 2 digits left so I should not try 67890 because I
know the answer is 2 digits.  Should I try:

12346 and see that I now have "2 digits" so I now know 6 is not one?
But if I tried 12347 - I would still have 3 digits so I really would
not know that 5 was a good digit?  I am not told that 7 is good.
But if I try 12345, then 12346, then 12347 I would be able to figure
out that 5 is good and 7 is good.

The overall question is what is the approach?  Do I do one number at a
time?  And of course, If I can guess right and get 4 out of 5 in the
first try, it will make it much easier to switch out one at a time.

```

```

Date: 03/26/2007 at 12:43:14
From: Doctor Douglas
Subject: Re: Algorithm for guessing a 4 digit number with unique digits

Hi Larry.

This game is sometimes referred to as "Mastermind", and is the subject
of much artificial intelligence research.  It turns out that the
optimal strategy can always arrive at the solution in six guesses or
fewer, with an average number of moves around 4.34.  A non-optimal
strategy can be devised that always takes five moves or less (but the
average number is more than 4.34).  It starts with the first guess
AABB, where A and B are two of the choices.  Committing this strategy
to memory might be very tedious.

Another way to approach this problem is to use "heuristics", which are
rules of thumb that tell you what guesses might be good, but don't
necessarily tell you if a guess is absolutely the best.  Heuristics
are commonly used for difficult problems such as this.  Some
heuristics that I have heard used in Mastermind are:

1)  guess many different choices, especially in the beginning
(so your first guess is ABCD, and your next one probably
involves EFG).  First learn what choices are in the
problem, then work out their order/arrangement.

2)  never make a guess that is inconsistent with what you have
learned so far.

This is, I think, close to the strategy that you are using in your
example.  Heuristics aren't as fast as God's algorithm, but they are
sometimes helpful for us humans, as they tend to place fewer demands
on our brains' ability to put together complicated constraints or to
remember what to do next.  Here is another pretty good strategy:

1)  Make AABB your first guess.  In some mathematical sense, the
information you get from this guess gives the most information
about what to do next, and is the "best" starting guess in
some strategies that are optimal or nearly so.

2)  Thereafter, make a guess that doesn't repeat any previous
guess [that's obvious] and, when compared with the previous
pattern, gives the result that was actually obtained on the
previous pattern.  For example, if you guess AABB and you
get "two in the right spot and one in the wrong spot", then
your next guess could be ACBA, which would lead to that
response if AABB was the secret pattern (which it's not, of
course).  You can choose the next guess at random from among
all the possibilities that satisfy this.

I offer the following web resources to start with if you are
inclined towards learning more about the problem and seeing which
strategies will best meet your needs.

Delphi for Fun
http://www.delphiforfun.org/Programs/MasterMind.htm

Mathematical Association of America
http://www.maa.org/editorial/knot/Mastermind.html

Toby Nelson, Investigations into the Mastermind(TM) board game.
http://www.tnelson.demon.co.uk/mastermind/

I hope this helps.  Please write back if you have further questions.

- Doctor Douglas, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/