|
|
|
|
|
|
|
|
|
 |
Cut The Knot!An interactive column using Java appletsby Alex Bogomolny |
 |
Invitation to MasterMind(tm) Don Greenwell |
December 1999
|
Mastermind is a game played by two players, the codemaker and the codebreaker. The game begins with the codemaker selecting a code, a sequence of four colors (digits, pegs or other symbols) Mastermind is a game of deduction. The task is to uncover 1 secret code selected from a set numbering In other respects too Mastermind relates to the language and body of mathematics. To start from the beginning, have you noticed that the rules of the game as presented in the opening paragraph are ambiguous? If a guess contains the same color in more than 1 position, but the secret code contains it only once, an interesting situation may arise. For example, what should the correct response be to the guess 1123 if the secret code is 0145? Implicit in the rules are two assumptions:
Accordingly, in the example there is 1 exact match and no color matches. According to D. Knuth [5], the clearest way to state the rules exactly (at least when you speak to a mathematician or a computer) is to frame them into the mathematical language. Let ni is the number of times color i is in the code, and mi is the number of times color i is in the guess. Then color i is matched 
Another little piece of mathematics comes from the question of how different are different secret codes. We suggested above that 0011 would be a good starting guess. Is 1122 any worse? Of course not. They are very much the same in that ordering of colors is to a great extent an arbitrary matter, as in fact is ordering of the positions. This device can be used by teachers [7, p xii] to invent seemingly different games. Better yet, students may be encouraged to look for patterns that make games equivalent. Mastermind also admits meaningful modifications. The obvious one is to allow different number of colors and positions. In another variant, colors can't be repeated. This reduces the number of valid codes from 1296 to 360. Surprisingly [8], the game is hardly simplified: for a variety of strategies, the expected number of moves to solve either variant is very much the same. In yet another variant, the response may only contain the number of exact matches. This does make the game more difficult. In [5] Knuth showed that the codebreaker can always succeed in five moves or less. That is, he has determined what the code is after at most four guesses. The strategy used by Knuth was found by choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities, over all 15 responses by the codemaker. (Note: We are grateful to Mark Weber for the remark that there are only 14 valid responses. Under no circumstances may the codemaker reply with three red and one pink dot.) If there is a tie, a consistent guess (one that has a chance of being the code) would be used (if possible). With ties remaining the first one in numeric order is selected. This procedure guarantees a win in five moves. The expected number of guesses using this strategy is 4.478. Koyama and Lai [6] determined the Mastermind's optimal strategy for expected number of guesses to be 4.34 guesses. They used recursive backtracking methods to discover this strategy. Their method requires six guesses in the worst case. Two strategies are implemented in the applet below: Knuth's and a simple strategy of randomly picking a consistent guess, starting with 0012. The latter finds the code on average in under five guesses. This however will sometimes require seven guesses (but see a letter from Stephan Rafler). Now, you are the codemaker. You must assist computer to arrive at the secret code by providing feedback to his/her guesses. To this end click on the two numbers to the right of every row. (In the game with only exact matches only one number is displayed.) In [1], Chvatal mentions a problem, suggested by Pierre Duchet, of finding the minimum number of guesses the codebreaker needs to make all at once, without waiting for the answers, to determine the code. For example, if we consider a Mastermind game with two positions and three colors to choose from, then the responses to the two guesses (0, 2), (1, 2) will determine the code. You can see this by listing the 9 possible codes and the codemaker's responses to these two guesses to see that these response vectors are all distinct:
(0, 0) - (10 00) We call such a game static Mastermind. The game is reminiscent of two coin weighing problems. The first is the famous 12 coins problem (known also as the the Oddball Problem): to determine with three weighings a single counterfeit coin from a set of 12 otherwise identical coins. Coins are split into groups that are weighed against each other on a balance scale. There is a solution in which the groups are determined up-front with the result of three weighings leading to the counterfeit coin in a unique manner. The second problem is on an altogether different scale of difficulty: Suppose we are given n coins, which look quite alike, but some of which are counterfeit. A scale is given which will allow any number of the coins to be weighed together. By weighing a subset of the n coins we are able to determine the number of good coins in the subset. The question is: what is the minimal number of weighings that will determine which are the good coins. (Subsets have to be identified ahead of time, before anything is weighed.) The problem was posed by Erdös and Rényi [2] in 1963. Their paper gives asymptotic results. Think of the desired subsets as sequences of zeros and ones, the ones indicating which coins are in the subset. Determining the number of good coins in the subset is the response giving the number of exact matches for the ones. In the first applet at the top of the page, you may try the static variant by checking the Static box. The applet always displays responses to the same sequence of guesses and the codebreaker is given only one chance to come up with the secret code. The applet below can be used to discover those sequences of guesses we used in the static Mastermind game for various numbers of positions and colors. For small numbers, the applet shows a table of responses to various guesses (the top row) and the (potentially) secret codes (the left column.) Click on the color vectors in the top row that you want to try. These will be highlighted in blue. As you do this, the color vectors that become shaded in red are the ones that are not as yet determined by the blue guesses. Add to or modify your selection (clicking on a selected vector will unselect it) to try to get rid of all the red ones. Try this with the example above (set the colors to 3 and pegs to 2). Try to find solutions for other cases. For larger numbers, the applet only displays the possible guesses. As before, the selected guesses appear in blue, the undetermined ones in red. For the standard Mastermind game of four positions and six colors we know from Knuth's result that at least four static guesses will be needed to determine the code. It is not hard to argue that, for this static problem, at least five guesses are needed. The work of Knuth, and Koyama and Lai's, sited above, strongly suggests that the static problem can't be done in five guesses, but no proof of this is known. Greenwell [3] has found six guesses that always determine the Mastermind code: (In September 2002, Andy Lewicki, University of Nebraska - Lincoln, furnished two more six guess combinations: (0, 3, 4, 0), (2, 2, 5, 0), (3, 2, 0, 3), (4, 1, 4, 1), (4, 4, 0, 5), (5, 5, 2, 3) With such an uneven distribution of numbers these sixlets seem very strange indeed.) You can verify this by using the applet above. Select the six guesses given above and you will notice that all 1296 possible codes are determined by this set. Try to find another solution. Is there a solution with five guesses? Try to find one and let us know if you do! Our current knowledge on the number of static guesses depending on the number of pegs and colors is summarized in the following table:
Entries without the question mark have been verified by exhaustive search. Those with the question mark have been found with the help of the above applet. We thus do not have complete confidence that they are optimal. The table affords a few observations. In view of the Strong Law of Small Numbers [4] and especially one of its consequences - You can't tell by looking, we must be cautious drawing conclusions from such a short table. (Well, having a bigger table would not help either.) Let's define complexity of the game as the minimal number of static guesses needed to solve it. We then observe (but also can actually prove) that the game with two pegs is not only more interesting than the game with one peg and the same number of colors, it's also simpler. (Think of how many static guesses are needed to solve the puzzle with one peg.) We can also safely assert that complexity of the game does not necessarily grow with the size of the game. Although of course the time needed to fill the corresponding entries in the table depended heavily on the latter. To prove this statement, we need just one example. The table provides plenty of them, its small size notwithstanding. A stronger assertion, namely that complexity grows at most by 1 when either number of colors or positions increases by 1, can't be proven that easily. This is a conjecture in fact, as we do not have a proof for it, simple though it sounds. Additional table entries may support or refute this conjecture. They may also help envisage other properties of the complexity function. We shall be grateful for any help in filling up the table. Everyone is welcome. An Update (March 4, 2002)We were notified of several interesting developments in response to this page. But first, let's mention an elegant contribution to the Oddball Problem by Jack Wert. Inherently inductive, Jack's approach immediately expands to
On Feb 12, 2003, Petr Felzmann pointed out that the entry for Here is a new neat table with entries partially proven and partially verified by exhaustive search.
References
On Internet
MasterMind is a registered trademark of Invicta Plastics, Ltd.
Copyright © 1996-2008 Alexander Bogomolny |
5
| 29706936 |  |
|