JOIN
Get Time
long_comps_topcoder  Match Editorials
Marathon Match 2
06.07.2006 - 06.14.2006

by lbackstrom
and venco
TopCoder Members


MasterMind

Many of us probably played MasterMind as children. However, the MasterMind we played had no more than 6 pegs, and about 6 colors. While this may be fun for a person, it represents little challenge for a computer. To make things interesting, this problem required competitors to write a program that would play with as many as 100 pegs and 20 colors, or as few as 5 pegs and 5 colors.

A quick search on the internet will reveal that this problem has a long history, going back to the 1970's, when Knuth showed a simple greedy strategy which solves the classic 4 peg, 6 color version in an average of 4.478 moves. However, to generalize his method, we would have to enumerate far too many possibilities in the larger cases. Luckily, an even simpler strategy does almost as well. Consider all possible codes which would give the response to guesses seen so far. Call this set of codes the consistent codes. From these consistent codes, pick one at random -- this gives an average of 4.638 moves, almost as good, but with much less computation.

Of course, with 100 pegs and 20 colors, there are 20100 possible codes, so we won't be able to enumerate all consistent codes and then pick one at random. But, if we could just find one that was consistent, that would be almost as good as picking one at random (maybe even better if we got lucky). Unfortunately, it has recently been shown that finding a consistent guess given a set of previous guesses is an NP-Hard problem (read the paper).

At first, this may sound like pretty bad news. It says that even if we have all the information we need from the guesses, it might be computationally hard to put the pieces together and come up with the answer. However, one should always keep in mind that, while an NP-Hard problem may be hard in some cases, simple heuristics will often perform well in the average case.

Furthermore, we don't have to solve the NP-Hard problem in order to eventually arrive at the right answer. If we are having a hard time coming up with a consistent guess, we can always ask for more information, which will only make things easier.

With this background we can now sketch the basic algorithm used by the top two competitors:
  • Make some initial guesses: Many competitors chose to make solid color guesses to exactly determine the number of pegs of each color. Other competitors (notably venco) chose to essentially skip this phase.
  • Somehow find a guess that is consistent. If this proves too hard, find a guess that is as close to consistent as possible (for some definition of close).
Of course, the key to doing well is all in the details. How much processing time should one spend trying to find a consistent guess? What function should be used to evaluate closeness? What information can be logically deduced from the guesses to help find a consistent guess? The list of potential tricks is almost limitless.

Venco's solution

My first thought about how to solve the problem was to generate any guess consistent with the results of all previous guesses. It's known that in the regular MasterMind game with just a few colors and pegs there are better algorithms. One can make special inconsistent guesses that reduce the possible number of secret keys further than any of the consistent guess would. Of course, it was clear that these sorts of algorithms were infeasible here, as there were far too many colors and pegs. So, I used the sub-optimal, but still reasonably good approach of simply finding any consistent guess. It turns out this problem is also too complex (NP-Hard), probably with complexity similar to number of possible orders of all the pegs. So, in theory, this approach is no better than the optimal one. But in practice we can be satisfied with almost consistent guesses which are much easier to achieve.

MasterMind
venco's solution (top) beats out vdave by avoiding the solid color guesses (15 colors, 20 pegs).


From the very beginning I had two stages to my guesses. The first stage tries to find the exact number of pegs of each color, not taking into account whether the peg was in the right place or not. If we call the first number in the results hits, and the second number misses, then total number of correctly guessed colors can be calculated by adding hits and misses together. This number can be computed more efficiently than it is by the algorithm given in the problem, which has O(L2) complexity. Instead, I always preprocess all my guesses by counting the number of each color in the guess. After that, the number of matching colors between two guesses can be calculated in O(K) time:
    int match = 0;
    for ( int k = 0; k < K; ++k )
        match += min(cnt1[k], cnt2[k]);

My first submission for the first stage tried to make some reasonable initial guess, and then optimized it by switching pegs from one color to another. In optimizing, I tried to find guesses that were as consistent as possible with the previous guesses, just in terms of the number of correct colors (ignoring location). More specifically, when evaluating a guess g I examined each previous guess g'. I computed the value of hits+misses that I would have received for g' if g were the correct code. The error for g from g' is the difference between this computed value and the actual value I received. The total error for g was simply the sum of the errors over all g'.

I did the obvious thing of starting with a random guess and then changing one color at a time to improve the error. I restarted a few times, and picked the best guess (lowest error) as my final guess. To avoid timeout, I often did not find completely consistent guesses. Eventually, I would get a guess that would have all the right colors in it, and then I'd advance to the second stage of my algorithm.

However, my tests showed that this approach failed to find the answer for large L. It turns out that it failed to find the correct color counts for a long time, hundreds of guesses. I added an obvious fix for this by issuing unicolored guesses for K-1 color just to find the color counts. I did this for L >= 15, and the code started to work reasonably well.

For the second stage, when I knew how many of every color were present, I simply assigned hits pegs randomly based on the guess with the most hits so far, and filled the rest randomly according to the known numbers of pegs of each color. This version score 62.11 which was quite good at the moment, although not the best.

I ended up sticking with these essential two stages till the end. From here, I made a number of important optimizations to each of the two parts. First I coded a better optimization function for the second stage. After making an initial order, I counted how bad and how good each peg was in its place. For example, if some guess actually has 2 hits, but my guess would give it 5, all the matching pegs were given a negative score because they increased the difference between current and required number of hits. So I created two arrays kl_add, and kl_sub containing the difference in error function I can get by adding specific color k at the place l, and by removing this peg. My optimization routine was:
  1. Take several (2-8) pegs off the board so that the error is reduced as mach as possible.
  2. Add them back in the places so that error is as small as possible again.
  3. Repeat it until I cannot get any improvement in error for several times in a row.
Each time I remove or place a peg on the board I had to update kl_add and kl_sub arrays, because the whole situation changes, and some pegs which were in a good place, may now be in a bad place as the total number of hits for each guess changes. Fortunately, the change was usually small, and overall those arrays save time (as opposed to recalculating the error after each possible change). Unfortunately there are a lot of cases, the code is quite complex and not obvious, and it's easy to make a mistake. After implementing the above order optimization function, my second submission went on top with score 106.02.

Now, what else to do? Seeing the improvement from optimization of stage two I decided to implement a similar thing in stage one, so instead of moving one peg at a time from one color to another, I move several pegs. Again, I first remove several (2-8) pegs from the board, and take them back with another colors so that total error is minimized. In addition I have noticed that some information about color counts can be obtained analytically. Consider the example (we are talking about color counts here, so order doesn't matter):
guess 1: abbcccdef, 5 matched colors.
guess 2: aaabccedf, 4 matched color.
As we see, the number of matched colors decreased by 1. But if we consider each color separately, we see that number of pegs with color a increased by 2, while b and c both decreased by 1 and d, e and f stayed the same. Looking at individual colors, there are three ways to get an overall decrease of 1 match (columns represent change in number of matches for one color):
Change in
 a  b  c
---------
 0  0 -1
 0 -1  0
+1 -1 -1
From this, we can immediately conclude that there are at most 2 pegs of color a, since it could have increased by at most 1, and there could have been at most one match to begin with. In this case, we can actually get a bit more information, though my code does not do this. Assume there are 2 pegs of color a. Looking at the table, the number of b's and c's must have each decreased by 1. Thus, the number must have been at least 2 and 3, respectively (otherwise they wouldn't have gone down). But now, we have too many matches, since b's, three c's and an a add up to more than 5 matches. Thus, there can be at most one a.

Another example
guess 1: abbccc, 1 matched color.
guess 2: aaabcc, 3 matched colors.
Here things are simple, as the only color which increased was color a. Thus, the only way to get an increase of two is for there to be at least three a's. While there are many more complex rules and further deductions one might make, just this simple one usually lead to the right color counts quite quickly.

In reality, there is usually much less information that can be easily gleaned analytically, but if we consider all pairs of previous guesses we can deduce the exact number of colors in many fewer guesses. It turned out, with all those rules implemented, the stage of unicolor guesses is not needed at all. My code finds exact number of colors in about the same K-1 guesses on average. Although it may be seen as no improvement, but if we recall that with K-1 unicolor guesses we do not get any order information at all, the new approach takes a lead with a score of 142.99.

Later, I optimized my code a lot to avoid timeout in some rare cases, removed a lot of unused and debugging code, switched to standard random function, increased number of iterations to find the guess from original 2000/L to 50000000/(L*L*L), because for small cases I can run much more iterations in time. All this gives slight improvement on average, so I submitted 4th version, and even though it scored slightly less on 50 test cases, I'm sure it's better on average.

I think that the biggest advantage I had over the competition was that my initial stage gave me more information. While many people did a good job on the second stage, they used K-1 guesses to obtain the color counts in the first stage, and just the color counts. By contrast, I used an average of about that many, but also gained a significant amount of information about the ordering at the same time.

Second and Third Place Submissions

vdave used the same basic approach as venco, except that his discovery of the color counts gave him less information. He recognized that guessing solid colors was clearly not optimal though, and he did improve on it somewhat, but he probably still fell short of the amount of information venco gained with the first few guesses. In addition he worked hard to optimize his code so he could find the most consistent guess possible when working in the second stage. In the end though, the early guesses cost too much, especially on the cases where the number of colors was large compared to the number of pegs.

A more radical approach came from flagitious. I'm not sure I exactly understand how it works, but the basic idea seems to be to work on one color at a time. This strategy does quite poorly when there are just a few colors or pegs (with 10 pegs and 5 colors it makes at least twice as many guesses as venco). However, on the larger cases, it almost always wins. In fact, looking at the breakdown of which solutions won the most cases, we have:

CoderCases Won
venco158
vdave59
flagitious155
lyc197721
Psyho3


But, the way the scoring works, flagitious got only half as many points as venco on the easy cases, while venco -- though he took many more guesses -- got almost full points on the hard cases.