Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/