Darkness 2001-09-14 00:00:00 UTC
 
Twilight 2001-09-15 00:00:00 UTC
 
Daylight 2001-09-16 00:00:00 UTC
 
Finish 2001-09-21 00:00:00 UTC

Mastermind - Winners

The Winning Entry - Stijn Helsen

Stijn's fcol_a_05 entry won the contest, with 64.60 % for the black pegs. We've asked Stijn to explain the code used in the winning entry; here is his explanation+:

First a small explanation about the name. I started with a meaningful naming convention. When I had some trouble getting my program working (though it worked at home with the given testsuite), I submitted a lot of entries and my naming convention began to loose meaning. I started with 'find colors + color-by-color with binary tree', the meaning of this name is explained below. I made it shorter: 'fcol+cbc with bt' (with some version numbers). Then I switched to 'fcol with posfind' and 'fcols with posfind' (where the extra 's' stood for sort). Then I reduced it to fcol, with a number. That number was after a while changed to 'a' (as the 'something' after 'number'). (I also had a fcol_b, but that solution was not better then the fcol_a.)

The Algorithm

The program works by combining two different algorithms. One algorithm can be compared to the way people play mastermind. The other algorithm is based on an elimination system, which I don't think "normal" human beings could use for playing. The second algorithm is typically more efficient. The problem is that it has to list all the possible answers, and that is (even for computers today) not always possible. The time limit of 180 seconds also limited the instances in which this program could be used. The "human mastermind game" has only a small number of possible solutions. That can be handled by a computer, but the bigger test-cases were too large.

Editor's note: There is a lot of literature on solving the Mastermind problem. In fact, the "standard" game of 4 pegs with 6 colors can be solved in 5 or less guesses, regardless of the solution chosen; this work is attributed to Donald Knuth. An Internet search for "mastermind algorithms" will turn up some very interesting papers, programs, and online demonstrations of work in this problem. You can find one of those links here.

This program determines what algorithm to use by splitting the problem in to smaller patial problems. If the partial problem is small enough, it is solved by the other algorithm. The two algorithms can be credited to a combination of my own work and that of others, especially Paul Valiant. (See the earlier sections of the post-contest analysis for more information on the evolution of the contest entries)

First a test for a trivial case is done.:

 
  1 : if guessLimit==1 | numColors==1
  2 : 	finalAnswer=ones(1,numPegs);
  3 : 	return
  4 : end

If there is one color, the solution is simple.

If the puzzle is small (in this case less then 50000 possible solutions), the "pruning" method is used. First all the possible solutions are calculated. This is done with a (nice) recursive function 'make':

 
277 : function boards = make(np, nc)
278 : if (np <= 1), boards = 1:nc;
279 : else boards = [repmat(make(np-1, nc), 1, nc); reshape(repmat(1:nc, nc^(np-1),1), 1, nc^np)];
280 : end

The result of this function lists the possible solutions columnwise, for example:

 
[ 1  2  3 … nc  1  2  3….
  1  1  1  … 1   2  2  …
  1  1  1  … 1   1  1 …]

Starting with this result a random guess from the possible guesses is taken, and the score is calculated. Then all the guesses that have a different result (number of blacks and whites) compared with the used guess are thrown away. This is done in a function 'prune'.

Editor's note: The idea of scoring a potential guess against a guess already taken is typical in many Mastermind algorithms. It can be proven that a new guess is a possible solution if and only if, when scored against a previous guess, it receives the same score that the previous guess received when scored against the solution.

 
 91 : function boards = prune(black, white, guess, boards, nc)
 92 : nb = size(boards,2); 
 93 : boards(:, sum(repmat(guess,1,nb) == boards) ~= black) = [];
 94 : nb = size(boards,2);
 95 : if nb > 0
 96 :     w = sum(min(repmat(histc(guess, 1:nc),1,nb), histc(boards, 1:nc))) ~= (black+white);
 97 :     boards(:, w) = [];
 98 : end

(One possible speedup could be the replacement of repmat(guess,1,nb) by guess(:,ones(nb,1)).)

First the number of blacks is calculated. This is easily done by summing all the equals in each column. The boards which gives different numbers of blacks are deleted. If there are any guesses left (which is probably always the case), the same is done for the total number of correct colors (black+white). This is done in a similar way as the 'calculatepegs' function which was supplied by the Mathworks (which is also a very nice Matlab-calculation). The difference with the calculatepegs-routine is that, because the calculation is not done for just one guess, but for many at the same time, the use of sparse is replaced by the histc-function. This function reworks the board to a vector which says how many occurrences there are for each color. By taking the minimum of these between the guess and the different possible guesses, the number of correct colors is calculated.

The idea is that the guesses from 'boards' for which w is nonzero are removed. It is done just by

 
boards(:,w)=[];

This calculation (in prune) is repeated until only one solution is left, or until the maximum number of guesses is reached. The final answer is calculated by taking a random guess from the possible answers. This calculation is as follows :

 
  8 : if (numColors^numPegs < 5e4) % a sieve for small puzzles
  9 :    boards = make(numPegs, numColors);
 10 :     nb = size(boards,2);
 11 :     nguess = 0;
 12 :     sg = 0;
 13 :     while (nb > 1) & (nguess <= guessLimit)
 14 :         guess = boards(:,ceil(rand * nb));
 15 :         [black,white,nguess]=scoreme(guess',puzzleID);
 16 :         boards = prune(black, white, guess, boards, numColors);   
 17 :         nb = size(boards,2);
 18 :     end
 19 :     finalAnswer = boards(:,ceil(rand * nb))';
 20 :     return
 21 : end % ifsmall

The use of the random guess at the end is for the situation where the number of guesses is reached before the solution is found.

If the problem size is not small, the combinatorics prevent the problem from being solved by enumeration and elimination. In this case, the problem is solved in two steps. First all the right colors are searched, together with the number of occurrences. This is done in a function findcols (explained later). The results of this routine are the following items:

  • cs : an array with the colors and the number of occurrences [col1 #col1;col2 #col2;…]
  • numCallsMade : the number of guesses done
  • fr : indexes of places in the answer which are not known
  • finalAnswer : the answer until now (more about this later)
  • lsr : the number of known pieces (this equals numPegs-length(fr))

Except when finding colors, findcols looks also for at least one color which is not used, or for which all the occurrences in the answer are known. All the unknown items in the answer are set to that color. It can be seen as a neutral color, because it does not give extra blacks or whites if the score is calculated. This last extra is done because the furtheralgorithm needs it.

After this routine, the correct places of the different colors are searched using a binary search method (more about this later).

Findcols

This routine has two main parts. First it finds colors, then, if necessary, it makes one "neutral" color. By using the free vector ('fr') and the ('lsure') number, only the "free places" are tested, and everytime a position for a color is found, the size of the problem is reduced.

The first part of the code searches for which colors occur together with the number of occurrences. At the same time the place of already known colors is searched. Therefore it looks first to the first color by testing the score of guesses with a guess with all the pegs with the same color. When the first color is found, one peg is put to that known color and the rest is put to a newly tested color. Since all the free places are filled with the same value except the one extra tested color, there are three possibilities:

  • the extra tested color is put in the right position, then there are no whites
  • the extra tested color is put on a position of the tested color, then there are two whites
  • the extra tested color is put on place of a not yet tested color, there is one white

That means that in two of the three cases, a position of a color is found. In these cases, that color is placed in the known position. This uses the following variables:

 
cols,ng,free,answ,lsure 

These are the same variables used earlier in the code, where they were called:

 
cs,numCallsMade,fr,finalAnswer,lsr

The variable names differ because some people changed the names of the variables when using their algorithms. My replacement of the findcols routine introduced these other names. There are other minor differences, for example consider the cols-matrix. In the first part of this routine it is a vector which gives the number of occurences (which are not 'placed') for each color. When all the colors are found, this is "reformed" to a matrix giving the color-number and the number of items.

There are also :

 
tot    : total numbers of found colors
k      : index in 'free' which points to the peg to put the extra tested color
l      : gives the extra tested color which (0 as long there is no "old" color)
nulcol : gives the "neutral color" if found (otherwise 0)

These variables are updated everytime no occurences of a color, or all the occurences of that color are found. That is faster then to test everytime if such a color is found.

The code also tests to see if all the "still to be tested places for the extra tested color" are equal to the number of occurrences of that color. If so, those colors are placed in those spaces. If all the occurrences of that extra color are found, a new color is taken. The color with the maximum number of occurrences is taken, because then there is the maximum chance to find places for it.

All the colors except the last one are tested unless the maximum number of allowed guesses is reached or all the colors are found. The last color gets the rest of the number of pegs.

In this code the cols-matrix is "reworked" to a matrix with number of colors and its number of occurrences. Together with this, it is test if there is not more then one color left. In that case the solution is found. If the maximum number of guesses is reached, the free places are filled with the known colors.

Because this routine has to give a guess where the free places are filled with a "neutral color", it must find a free color. If nulcol is nonzero, its value is the free color. Otherwise, the linear search which is started in the first part of this routine is continued to find a free color. The choice for this color is not so obvious. Here the color with the maximum number of occurrences is taken (this is explained later).

So there are now two colors: l and r1. From k,which points to the first position to be tested for color l, all the positions are tested until all the occurrences of one of the colors is found. It is for this reason that the choice of the second color is not so obvious. On the one hand you want to give the highest chance to find occurrences of that second color (to obtain as many occurrences as possible). On the other hand you want to find all the occurrences of that color so the search can be stopped. Because it is not always possible to find all occurrences (because occurrences of that second color can be before position k), trying to find all the occurrences can be a wrong guess.

Therefore the color with the most or the least number of occurrences could be used. The first one seemed to be the best for the real testcases, while the second for the supplied set. There could be a more complex decision process for making this choice. For example, the choice could depend of the value of k (far to the end, the maximum could be better, while for to the beginning, the minimum could be better).

The rest of this routine is similar to the first part. After this search the cols matrix has to be corrected, and it is checked to see if the solution is found.

At the end of this routine the colors are sorted beginning with the maximum number of occurrences because that gave the best solutions for the next part.

ffc

(The original name for this was "findcol" - "findcols" to find the colors and "findcol" to find the position for each color. I admit that this is not, but I don't know what the ffc means, and I also don't know why the name was changed.)

This function finds the positions of a color in the free set of the answer using a binary search. To do this, the code splits the problem by checking the number of occurrences in the first half of the free set. The problem is then split again into two smaller problems, one for the first half and one for the second half (which has the rest of the number of occurrences). This solving of the smaller problems is done by recursively calling this function.

If the number of colors to be put in the supplied region is equal to the size of the region, the solution for this partial problem is found.

If the size of the partial problem is small (length lower then 14), another routine is used. This routine is similar to to the pruning method used in solving small problems. Since the binary search is also optimal if only one peg has to be found, the pruning method is not used if n==1.

 
51   function [ind,numCallsMade] = ffc(gs,x,n,col,b0,gsLim,puzzleID)
52   if length(x) == n, 
53       ind = 1:n; 
54       numCallsMade = 0; 
55       return; 
56   end;
57   if (length(x)<14) & (n~= 1)
58       [ind,numCallsMade]  =  ffclp(gs,x,n,col,b0,gsLim,puzzleID);
59       return;
60   end
61   i = floor(length(x)/2); 
62   g = gs; 
63   g(x(1:i)) = col; 
64   [black,white,numCallsMade]  =  scoreme(g,puzzleID);
65   nv = n-black+b0;
66   if black>b0, 
67       if numCallsMade>= gsLim, 
68           ind = [1:black-b0,(i+1:i+nv)]; 
69           return; 
70       end;
71       [i1,numCallsMade] = ffc(gs,x(1:i),black-b0,col,b0,gsLim,puzzleID);
72       if numCallsMade>= gsLim, 
73           ind = [i1,(i+1:i+nv)]; 
74           return; 
75       end
76   elseif numCallsMade>= gsLim, 
77       ind = i+1:i+nv; 
78       return;
79   else
80       i1 = [];
81   end
82   if nv, 
83       [i2,numCallsMade] = ffc(gs,x(i+1:end),nv,col,b0,gsLim,puzzleID); 
84       i2 = i2+i;
85   else
86       i2 = []; 
87   end;
88   
89   ind = [i1 i2];
ffclp

This routine searches for the positions of a color using a "pruning" method. A difference between this routine and the "prune" routine is that the tested guesses are not necessarily guesses which are found in the list of possible guesses.

First a list of guesses is calculated (over different calls) using a persistent variable. This list contains arrays where the rows contain all the possible combinations of zeros and ones:

 
243  function [ind,numCallsMade] = ffclp(gs,index,n,cl,b0,guessLimit,puzzleID)
244  persistent guessesCache
245  numCallsMade = 0;
246  l = length(index);
247  oneToL=1:l;
248  if isempty(guessesCache) | length(guessesCache) < l | isempty(guessesCache{l})
249     twoexp = 1;
250     guesses = zeros(1, 0);
251     for i = oneToL
252        guesses = [guesses zeros(twoexp, 1);guesses ones(twoexp, 1)];
253        twoexp = twoexp * 2;
254     end;
255     guessesCache{l} = guesses; 
256  else
257     guesses = guessesCache{l};
258  end

(It is not necessary to have a list of matrices since the biggest matrix can be used a the base : A(1:2^l,1:l) gives a correct partial array. This could be useful when concerned about memory usage. Since this routine is called only for problems where length(index)<14, the maximum size of the matrix is known.

This matrix can also be made without loops :

 
    i=(0:n-1)';
    j=2.^(0:l-1);
    guessesCache=bitand(i(:,ones(l,1)),j(ones(1,n),:))~=0;
)

These matrices are used as a starting point for determining the possible positions of the colors. The matrix where the number of columns equals the size of the number of free places in the answer is used.

From this matrix, the rows with a number of ones equal to the desired number of occurrences of the color are held. That matrix is also transposed so that the columns hold the possible guesses:

 
259  answers = guesses(sum(guesses,2) == n,:)';

In the first step, the score is calculated for a guess where the color is put in the second half of the free area (similar to the binary search). From this result the possible answers with a different number of blacks are deleted. This is done in a nice way by the matrix multiplication of matrices of zeros and ones:

 
260  count = 0;
261  while (size(answers,2)~= 1) & (numCallsMadel/2;
265      elseif count == 2
266          bestguess = (oneToL <= l/4)+(oneToL > l*0.75);
267      else
268          [m,bestguessn] = min(sum(histc(guesses*answers,0:n,2).^2,2));
269          bestguess = guesses(bestguessn,:);
270      end
271      g = gs; g(index(find(bestguess))) = cl;
272      [black,white,numCallsMade] = scoreme(g,puzzleID);
273      answers = answers(:,find(bestguess*answers == black-b0));
274  end

bestguess is a row with ones in the places where the new color is put. answers has in its columns possible guesses. bestguess*answers is a row where its elements gives the number of correct places, and so the number of blacks it would give. Comparing this with the calculated number of black pegs shows which possibilities can be removed.

The next step (count==2) involves putting the new color in the first and last quarters of the free area. This can be thought of as two simultaneous steps of a binary search. For this the invalid guesses in the answers list are removed.

For the next steps (count>2) a best guess from the guesses-list is calculated. This is done with:

 
268           [m,bestguessn] = min(sum(histc(guesses*answers,0:n,2).^2,2));

In this line all the possible guesses (with and without the correct number of occurences) are compared with the possible answers. histc(guesses*answers,0:n,2) gives, in each column, how many of the answers have the number of blacks pegs equal to the column-number minus one. sum(histc(guesses*answers,0:n,2).^2,2) gives a number which is lowest where the numbers of black pegs is spread out over as many different possibilities. This means that the minimum of this vector points to a guess which has the best chance that many guesses can be deleted after this iteration (ie, fewer possibilities remain in the set of possible solutions).

This iteration is done until just one answer is left, or when the maximum number of guesses is reached:

 
275  ind = find(answers(:,1+floor(rand(1)*size(answers,2))))';

And this is how it all works ...

I can't stop without giving some thought I had about further improvements:

  • fcol_a_07 has an improvement over fcol_a_05 but was not better because of other changes. This change uses the knowledge that after the colors are found, there is some additional info known about one color (color l). This info is used if no free color is found, but it isn't when there is. In fcol_a_07 this info is used by using the ffc-routine for the range "free(k:end)".
  • Another thing which improved the algorithm in fcol_a_07 (at least with the supplied testcase), is a change in the beginning of the linear search. If k is not pointing far in the free area, it is possible that it is better to from the beginning with a color with a lower number of items (so that the chance that the linear search finishes quickly is higher.
  • After finding the positions of some colors the pruning method could be used for the complete rest problem.

Stijn also had these thoughts about the contest that we'd like to share with you:

When I was writing this, I imagined a lot of people would ask why there are so many possible additions while the ideas were there. The main reason for that is the way the contest works. If you start working on a nice algorithm it is not always easy (and maybe not always good) to optimize the program's speed. A disadvantage of high optimizations is that it is more difficult to do further changes to the algorithm.

If you send algorithms with "all your thoughts" early, it is more likely that a lot of people try to do very small changes to your code, so that you loose your winning position. If you don't send them early, you can't test so much for yourself. Therefore, together with the much more busy actions in the end then expected, not all the prepared changes were put in the winning code.

This is not meant as a comment to the way the contest is organized. It is just a thought about one possible disadvantage. But I like it the way it is. It also makes it more exciting, and it gives more "game-feeling".

Thank you for the contest,

Stijn Helsen



* Some edits were made to the original author's description

Mastermind is a registered trademark of Pressman Toy Corporation.