From the sci.math FAQ: Archive-Name: sci-math-faq/mastermind Last-modified: December 8, 1994 Version: 6.2 Master Mind For the game of Master Mind it has been proven that no more than five moves are required in the worst case. One such algorithm was published in the Journal of Recreational Mathematics; in '70 or '71 (I think), which always solved the 4 peg problem in 5 moves. Knuth later published an algorithm which solves the problem in a shorter number of moves - on average - but can take six guesses on certain combinations. In 1994, Kenji Koyama and Tony W. Lai found, by exhaustive search that 5625/1296~= 4.340 is the optimal strategy in the expected case. This strategy may take six guesses in the worst case. A strategy that uses at most five guesses in the worst case is also shown. This strategy requires 5626/1296~= 4.341 guesses. References Donald E. Knuth. The Computer as Master Mind. J. Recreational Mathematics, 9 (1976-77), 1-6. Kenji Koyama, Tony W. Lai. An optimal Mastermind Strategy. J. Recreational Mathematics, 1994. [The reference is: K. Koyama and T. W. Lai, An optimal Mastermind strategy, J. Rec. Math. Vol. 25(4) 251-256, 1993. Other references provided by Tim Chow follow. --djr] R.W.Irving, Towards an optimum Mastermind strategy, J. Recreational Math. 11 (1978-79), 81-87. E.Newirth, Some strategies for Mastermind, Zeitschrift fur Operations Research 26 (1982), 257-278. V. Chvatal, Mastermind, Combinatorica 3 (1983), 325-329. ============================================================================== From: spp@bob.eecs.berkeley.edu (Steve Pope) Newsgroups: sci.math,sci.crypt Subject: Re: Basic MasterMind decryption Date: 19 Mar 1995 23:02:30 GMT The following may not be optimal, but it is straightforward. By making the first three moves all single-color moves, each move using a different color, we have determined how many times each color is used. This leaves us with the following cases: (1) Only once color is used. (2) Two colors are used -- one of color A , and three of color B. (3) Two each of colors A and B are used. (4) Three colors are used -- two of color A, and one each of B and C. (5) All four colors are used. Case (1) has only one solution, so we are done. (3 moves total) Case (2) has 4 possibilities, and Case (3) has 6 possibilities. In either case, by using moves 4, 5, and 6 to determine if color A is in position 1, 2, and/or 3 respectively, we have solved either of these cases in 6 moves total. For Case (4), similarly use the 4th, 5th and 6th moves to determine which two positions color A is in; and the 7th move to determine which of the remaining two positions color B is in, and we are done in 7 moves. Case (5) is the most difficult. By making the 4th move "AAAB" and, if necessary, the 5th move "CCCD" we have identified which color is in the 4th position. WLOG let's say the color in the fourth position is color D. We then make as the 6th move "AABD". We will get either 1, 2, or 3 positional matches. One match means A is in position 3; Two matches means C is in position 3; and three matches means B is in position 3. In each case, a 7th move will resolve which of the remaining colors is in each of the first two positions. So, the game is solvable in 7 moves, or 8 moves if the rules require you to lay down the solution as your final move (as opposed to just knowing what it is). Steve ============================================================================== From: hwatheod@gate.net (Theodore Hwa) Newsgroups: sci.math Subject: MASTERMIND game - fewest moves Date: 2 May 1995 00:39:00 GMT In the game of MASTERMIND, one player secretly constructs a sequence of k colors chosen from a set of n colors, with repetitions allowed. Then the second player attempts to guess the code. With each guess the first player provides the following information: i) the number of colors in the guess that are in the correct position in the code ii) the number of colors in the guess that are in the code but not in the correct position In the version that is commercially avalable, k=4, n=8, and the player has 10 moves to guess the code. Is there a strategy that always ensures this? This sounds like a difficult question to answer, so let's consider a simpler case when n=2. What is the fewest number of moves required to guess a k-element code? I believe that it's k+1, but am unable to explicitly write down a general strategy that works for all k, although for the values of k I've tried, I have found a strategy that always solves the problem in k+1 moves. The strategies I have found for n=2 are all begin with a string of k A's (I will denote the 2 colors by A and B). This guess reveals the number of A's and B's in the code, and the remaining guesses are all used to determine the position. Then the second guess is a string of m A's followed by k-m B's (where m was the number of A's as revealed by the 1st guess.) From here, depending on what information was given, the strategy branches out into several cases, but in all cases it seems that in k+1 moves or sooner the code can be discovered with certainty. Does anybody have any idea how to prove something like this? One part of the problem that I don't have much idea at all how to approach is to show that k+1 (or whatever the bound is) is *necessary* (for sufficiency one merely needs to exhibit a strategy, so I have a place to start). I was thinking along the very vague lines of considering how many possible codes are eliminated by each guess and such things, but haven't had much success. ============================================================================== From: dsavitt@unixg.ubc.ca (David Savitt) Newsgroups: sci.math Subject: Re: MASTERMIND game - fewest moves Date: 2 May 95 07:46:45 GMT hwatheod@gate.net (Theodore Hwa) writes: >With each guess the first player provides the following information: >i) the number of colors in the guess that are in the correct position in the >code >ii) the number of colors in the guess that are in the code but not in the >correct position This doesn't quite completely specify the rules...presumably, if there are, say, n pegs of color A in the correct answer, and the guesser guesses more than n pegs of color A, then the information in (i) and (ii) will only count up to a maximum of n for A. (Thus if a player guesses all A, then (i) will report the number of A's in the correct position and (ii) will be zero.) >This sounds like a difficult question to answer, so let's consider >a simpler case when n=2. What is the fewest number of moves required to >guess a k-element code? I believe that it's k+1, but am unable to >explicitly write down a general strategy that works for all k, although >for the values of k I've tried, I have found a strategy that always >solves the problem in k+1 moves. I think the following works: first, guess all A's. If you don't win, there is a B in the correct answer. So, if you were to guess all A's except for one B, there are two possibilities. If the B is correct, the first player will report none of the right color in the wrong position, but if the B is incorrect the first player will report (at least) one in the wrong position. Thus one can tell what the correct color of that position is. If you do this for positions 1,...,k-1, however, you can infer what the kth position must be--you know from the first guess exactly how mant A's there are. So, on the (k+1)st guess, you can enter the correct solution. This doesn't strike me as terribly efficient, though. On the other hand, it's pretty easy to see that no strategy of length <=k work for k=1,2. (For k=2, if the first guess is AA or BB, you can't distinguish between AB and BA, and vice versa.) ============================================================================== From: dsavitt@unixg.ubc.ca (David Savitt) Newsgroups: sci.math Subject: Re: MASTERMIND game - fewest moves Date: 2 May 95 08:38:33 GMT dsavitt@unixg.ubc.ca I wrote: >On the other hand, it's pretty easy to see that no strategy of length <=k >work for k=1,2. (For k=2, if the first guess is AA or BB, you can't >distinguish between AB and BA, and vice versa.) It is, however, possible to exhibit a strategy of length 3 for k=3. Guess BAA first. If it's not correct and the response is (0,2) or (1,0), the correct solution is ABB or BBB respectively. If it's (1,2), it's either AAB or ABA, so guess one then the other. The last 3 possibilities are AAA, BAB, and BBA, both yielding (2,0). Guess BAB. If it's not right, the response of (1,2) tells you it's BBA, (1,0) indicates AAA. ============================================================================== From: hwatheod@gate.net (Theodore Hwa) Newsgroups: sci.math Subject: Re: MASTERMIND game - fewest moves Date: 3 May 1995 00:39:25 GMT David Savitt (dsavitt@unixg.ubc.ca) wrote: : hwatheod@gate.net (Theodore Hwa) writes: : >With each guess the first player provides the following information: : >i) the number of colors in the guess that are in the correct position in the : >code : >ii) the number of colors in the guess that are in the code but not in the : >correct position : This doesn't quite completely specify the rules...presumably, if there : are, say, n pegs of color A in the correct answer, and the guesser : guesses more than n pegs of color A, then the information in (i) and (ii) : will only count up to a maximum of n for A. (Thus if a player guesses all : A, then (i) will report the number of A's in the correct position and : (ii) will be zero.) You're right. I should say that the total number of pegs reported by (i) and (ii) combined (with respect to a particular color) should be equal to the number of that color in the code or in the guess, whichever is smaller. Also, (i) should take precedence over (ii) in all cases. For example, if the code is ABBC and the guess is BDBB then (i) should be 1 because of the B in the 3rd position +and (ii) should be 1 because of the B's in the 1st and 4th position of the guess (but there is only one other B in the code, so only one of them counts.) ==============================================================================