Strategy for Playing Mastermind and Similar GamesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/