Blockbuster, Final Analysis

The Cyclist's winning entry was based on Hannes and Cobus' submission Chuck Norris 3. Chuck Norris 3 is the clear text version of sirroN kcuhC 3. We've asked Hannes and Cobus to walk us through their overall strategy. -The MATLAB Contest Team-

At the start of each move, a connectivity analysis is carried out on the current board. The function of this connectivity analysis is to find all the clusters on the board, and to find their associated values. Due to limited processing time, only a subset of these possible moves is selected for further evaluation. For this subset of moves, the list of available moves after the effects of the first move have rippled through are calculated. In effect, a brute-force search is performed to find the best two-move combination that is available. This is the crux of the algorithm. Some nice features such as swapping and estimation beyond two moves were added as the contest progressed.

The cornerstone of any implementation was the connectivity algorithm. This is a fairly time-consuming step, and has to be performed for every move that is evaluated. As much as 90% of total processing time was spent performing connectivity. Clearly this is the section of code that offers the most benefit if improved. It is here that the Chuck Norris entries gained a significant performance edge over the other leading entries.

function m=solver(tb,nM)
[m,b]=solveri(tb,nM,1);
sthis=sum(sum(b));
if (sthis > 800)
    [m2,b]=solveri(tb,nM,0.8);
    sthis2=sum(sum(b));
    if sthis2 < sthis
        m=m2;
    end
end;       

By speeding up the connectivity calculations, we gained a +-25% speed increase, while still remaining in the local minimum. However, since the timing penalty on the leading entries was fairly small we wished to convert this time advantage into points. We first took the obvious route and simply searched a wider selection of moves (by reducing choke_factor). This removed us from the local minimum and we ended up doing worse on the contest suite while doing 2000 points better on the test suite.

Consequently we changed our approach to execute some selected problems multiple times with different choke_factors, and selecting the best result. On the first iteration we would use the choke factor from the current leading entry. In this way we could improve the score without exiting the local minimum and losing the cumulative effect of thousands of parameter tweaks.

function [moves,board] =solveri(tboard,nMoves,z)
board=zeros(size(tboard,1)+1,size(tboard,2)+2);
board(2:end,2:end-1)=tboard;
[rows, cols] = size(board);

By padding the board with zeros to the sides and the top, we removed the need for boundary checks in our connectivity code.

moves = ones(nMoves,3);
count=0;

zz=zeros(1,floor(((rows-1)*(cols-2))/2));
i=1;
for r=rows:-1:2
 for cl=cols-2:-1:1
     if mod(r+cl,2)
         zz(i)=(cl*rows)+r;
         i=i+1;
     end
 end
end

zz is a set of one-dimensional indices into our enlarged board that need to be checked for connectivity. The order of these indices was adjusted to provide the list of connected regions in approximately the same order as the FindClusters algorithm by Markus. Any variation in the ordering of this list would remove us from the local minimum. We never got the exact same order (due to fundamental differences in how the algorithms work) but got close enough that we were within 100 points of the minimum. The zz indices form a checkerboard pattern, since any connected region would have to have at least one block on the pattern. This performance tweak, was suggested to us by Gerbert Myburgh, a colleague who quit the contest shortly after darkness ended.

% adjust block weights
board = nthroot(board,rot);

Markus originally introduced this line of code in his twilight winning entry. The purpose is to lend more weight to larger blobs rather than small blobs of high-valued blocks. By doing this, larger blobs would be popped first, resulting in a quicker reduction of the search-space.

We will not discuss the central loop of the program, which looked 2 moves ahead and picked the most promising combination, in any detail since we should all be quite familiar with it. However, one idea that deserves a mention was the summing of several of the highest available blocks after the first move to crudely simulate looking further than 2 moves ahead (not sure who came up with this nice trick!).

Next up is the accelerated version of CalculateMoves. Ironically this algorithm is closely related to the recursive findNeighbors function that was included with grade.m . In essence it is the same approach but we used an explicit stack (ibuf) to remove the need for recursion. We also got rid of the N matrix by simply clearing cells directly on the board as they were added to the stack.

function [new_cell_list,new_value_list,new_mask] = 
CalculateMoves(board);
[rows,cols]=size(board);
 
group_index=0;
ii=0;
prev=0;
readpoint=0;
writepoint=0;
c=0;
for zi=1:numel(zz)
    i=zz(zi);
    c=board(i);
    if c && (board(i+1)==c || board(i+rows)==c || board(i-1)==c ||
 board(i-rows)==c)
        group_index=group_index+1;
        ibuf(1)=i;
        board(i)=0;
        prev=i;
        readpoint=0;
        writepoint=1;
        while (writepoint-readpoint)
            readpoint=readpoint+1;
            ii=ibuf(readpoint);
            new_mask_l(ii)=prev;
            prev=ii;
            if board(ii+1)==c
                writepoint=writepoint+1;
                ibuf(writepoint)=ii+1;
                board(ii+1)=0;
            end
            if board(ii-1)==c
                writepoint=writepoint+1;
                ibuf(writepoint)=ii-1;
                board(ii-1)=0;
            end
            if board(ii+rows)==c
                writepoint=writepoint+1;
                ibuf(writepoint)=ii+rows;
                board(ii+rows)=0;
            end
            if board(ii-rows)==c
                writepoint=writepoint+1;
                ibuf(writepoint)=ii-rows;
                board(ii-rows)=0;
            end
        end
        valbuf(group_index)=c*readpoint;%+row_offset(i);
        celbuf(group_index)=ii;
    end
end
new_cell_list=celbuf(1:group_index);
new_value_list=valbuf(1:group_index);
new_mask=new_mask_l;

We won't discuss CheckForSwap here since we never really had a good look at it. Early on in the contest we expanded significant effort on implementing a swapping strategy and like everyone else we were disappointed by the small impact this had. It seems that pops are better than swaps in 99.9% of the cases.

Lastly we would like to throw some of our ideas that never made it to the big time out there. One idea that came out quite early on was to reduce the cost of computing connectivity by only recomputing the part of the board that was affected by a given move. Since we expected this area to be a small percentage of the total board, a fairly large improvement was expected. We had a version of this in the game close to the end of twilight, but for some reason the speedup was only about 20%.

When we first saw the depth trick that was used to approximate a deeper search, we were quite impressed. Our first reaction was that the blocks that are summed should theoretically be weighed with a decreasing function to reflect the reduced likelihood that they will still be available for popping after the preceding blocks were popped. This was implemented with an exponential decay and the results were positive on the test suite. As with so many other ideas, this didn't fly on the contest suite. The only explanation that makes sense to us is that the beneficial effect of weighing is outweighed by the negative effect of losing the local minimum. It is surprising that even with such a large contest suite, such a strong local minimum could still be found.

After reading the explanation given on the newsgroup for the significant (but tragic) difference made by nthroot vs. ^ precision differences, we came up with another idea that should make a significant difference to the final score. Rather than relying on blind luck and tweaking to select the correct branch when a very close call is encountered (that is if the first and second choice moves have values that are within rounding error of one another) one could save a list of such board positions and evaluate the alternative branch later. Of course this has additional execution cost, but when compared to our approach of redoing the entire problem with a different choke_factor it is quite efficient, since only a part of the problem will be redone.

Thanks for a great contest and see you all in 6 months.

Hannes Naudé & Cobus Potgieter

P.S. A note to all tweakers, but especially the cyclist. WE KNOW WHERE YOU LIVE!!!