Solitaire, mid-contest Analysis

For this mid-contest analysis I will be referring to three different entries. First, the Darkness phase winner, "Spyder_20K" (entry number 38783) by Nick Howe. Nick just out edged other contest superstars such as Alan Chalker, Jan Langer and Yi Cao to claim the Darkness phase. Our second entry is "Friday_speed2" (entry number 39174) by Yi Cao. Yi Cao dominated the twilight phase with almost no competition. He even claimed this prize with an entry submitted more than eight hours before the Twilight deadline. Since the Daylight phase began there have been many improvements to the code. We'll just focus on one notable entry, "markus12" by Markus Buehren (entry number 40435), which helped win the Big Sunday Push.

First, we'll take look how the three entries evolved using the traditional English board. I was surprised to see that the tree solution leaves many pegs in the board.

board = 1-[1;1;0;0;0;1;1]*[ 2 2 0 0 0 2 2];
board(4,4)=0;
solitaireBOARD(board,'English Board')
solitaireBOARD(board,'Solution by Spyder_20K',solver_Spyder_20K_by_Nick_Howe(board))
solitaireBOARD(board,'Solution by Friday_speed2',solver_Friday_speed2_by_Yi_Cao(board))
solitaireBOARD(board,'Solution by markus12',solver_markkus12_by_Markus(board))

In our Peg Solitaire, we have made a twist to the original game using weighed pegs. This minor change makes the game much more interesting and challenging.. We encourage solutions that look more than just cleaning the board, but also doing it with the best set of moves. We particularly encourage moves that require "touching" the minimum number of marbles (or pegs). Under certain situations, it make be advantageous to make many moves, as long as you only lift low weight pegs.

mask = [1;1;0;0;0;1;1]*[ 1 1 0 0 0 1 1]~=1;
board = magic(7).*mask - ~mask;
board(4,4)=0;
solitaireBOARD(board,'Weighted English Board')
solitaireBOARD(board,'Solution by Spyder_20K',solver_Spyder_20K_by_Nick_Howe(board))
solitaireBOARD(board,'Solution by Friday_speed2',solver_Friday_speed2_by_Yi_Cao(board))
solitaireBOARD(board,'Solution by markus12',solver_markkus12_by_Markus(board))

Comparing Yi's solution to Nick's, Yi concentrated on clearing the board. Nick selected moves to reduce lifting penalties and maximize the value collected. We see that the Darkness winning solution is better that the Twilight solution with a weighted board. As expected, Markus combines both strategies to score better in both boards.

Using a graph created by Sidney and some graph theory algorithms, I found an even better solution to the weighted English board. Can some one beat me on this board?

myMoves = [2 4 4 4;3 6 3 4;1 5 3 5;4 5 2 5;6 5 4 5;3 3 3 5;3 1 3 3;5 7 5 5;5 4 5 6;
5 6 3 6;3 6 3 4;3 4 3 2;1 3 1 5;1 5 3 5;3 5 5 5;5 2 5 4;5 4 5 6;3 7 5 7;5 7 5 5;7 3 5 3;
4 3 6 3;7 5 7 3;7 3 5 3;5 1 3 1;3 1 3 3;2 3 4 3;4 3 4 5;4 5 6 5;6 5 6 3;6 3 4 3;4 3 4 1];
solitaireBOARD(board,'Lucio''s Solution',myMoves)

Best? Solution for the Weighted English board video

When I was preparing the code for the contest, I came across with the package and purge % approach for solving the classical Peg Solitaire. The idea is that one should pre-compute a set of potential multi-peg blocks with their clearing moves. Then it is possible to reduce the search from the peg-move space to the block space. For every block there are a number of pre-computed solutions that need to be evaluated. The final solution is given by joining the best solution of several packages. For example, using some graph theory (in the Bioinformatics Toolbox), I explore what the authors call the 6-purge block.

current_board = [1 0 0 -1;-1 1 1 1;-1 1 1 1];
desired_board = [1 0 0 -1;-1 0 0 0;-1 0 0 0];
[G,states] = findsolitairepackages(current_board,desired_board);
viewsolitairepackages(G,states,current_board);

I am sharing the function that searches possible solutions for a given block, in case someone may want to exploit this approach. The function graphtraverse is only available in the Bioinformatics Toolbox. If you do not have the BT available, you can easily program this function using the matrix propagation trick.

type findsolitairepackages

function [G,ps] = findsolitairepackages(current_board,desired_board)
% [G,N]=FINDSOLITAIREPACKAGES(CB,DB) Find a directed graph representing a solitaire package.
%
% CB and DB are the current and the desired board layouts, use -1 for off
% board positions, use 0's and 1's to represent the absence or presence of
% a peg or use NaNs to include in the analysis both states. G is a directed
% graph representing a solitaire package and N is the board state. 
%
% NOTE: Uses graph theory functions in the Bioinformatics Toolbox. 
%
%  The MATLAB Contest Team
%  May 2007

board = -(current_board == -1);
hs = find(~board);
bin2state = (2.^(numel(hs)-1:-1:0));
[m,n] = size(board);
s = @(i,j) sub2ind([m,n],i,j);
[current_board,cs] = boardnans2boardcell(current_board,hs);
[desired_board,ds] = boardnans2boardcell(desired_board,hs);

[i,j] = find(board>=0);
I = [i;i;i;i]; J = [j;j;j;j];
K = [i;i;i-2;i+2]; L = [j-2;j+2;j;j];
h = find(K>0 & K<=m & L>0 & L<=n);
h = h(board(s(K(h),L(h)))>=0);
I = I(h);J = J(h);K = K(h);L = L(h);

G = sparse(1,1,false,sum(bin2state)+1,sum(bin2state)+1);
for e = 0:sum(bin2state)
    board(hs) = dec2bin(e,numel(hs))=='1';
    hh = find(board(s(I,J))>0 & board(s(K,L))==0 & board(s((K+I)/2,(L+J)/2))>0);
    for f=1:numel(hh)
        g = hh(f);
        board(I(g):-2*(I(g)>K(g))+1:K(g),J(g):-2*(J(g)>L(g))+1:L(g)) = [0 0 1];
        G(e,bin2state * board(hs)) = true;
        board(I(g):-2*(I(g)>K(g))+1:K(g),J(g):-2*(J(g)>L(g))+1:L(g)) = [1 1 0];
    end
end

pcs = [];
for i = 1:numel(cs)
  pcs = union(pcs,graphtraverse(G,cs(i)));
end

pds = [];
for i = 1:numel(ds)
  pds = union(pds,graphtraverse(G',ds(i)));
end

ps =  intersect(pcs,pds);
G=G(ps,ps);
end

function [b,states] = boardnans2boardcell(b,hs)
   h = find(isnan(b));
   b = repmat({b},2^numel(h),1);
   for i =1:numel(b)
      b{i}(h) = dec2bin(i-1,numel(h))=='1';
   end
   states = setdiff(cellfun(@(x) (2.^(numel(hs)-1:-1:0))*x(hs),b),[0;2^numel(hs)-1]);
end

Observe that we only showed the solution for the 6-purge block which starts and ends with a peg in the upper-left corner. Using NaNs we can explore other start and end boards that can also be "usable" blocks. For example, the whole set of solutions to the 6-purge block which starts and ends in the top row are:

current_board = [NaN NaN NaN NaN;-1 1 1 1;-1 1 1 1];
desired_board = [NaN NaN NaN NaN;-1 0 0 0;-1 0 0 0];
[G,states] = findsolitairepackages(current_board,desired_board);
h = viewsolitairepackages(G,states,current_board);
set(h.up.hgFigure,'Position',[100,100,1300,500])

The blocks given by Berlekamp et. al. are not as useful for our problem, since most of them are dead-end blocks. We need to find blocks that can be useful for moving forward in large boards. For this example, I show one 4x3 block that can help us to move forward in a bigger problem:

current_board = [-1 1 1 1;-1 1 1 1;-1 1 1 1;-1 0 0 1];
desired_board = [-1 NaN NaN NaN;-1 0 0 0;-1 0 0 0;-1 0 0 0];
[G,states] = findsolitairepackages(current_board,desired_board);
viewsolitairepackages(G,states,current_board);

I hope this analysis gives you some ideas to try out. In all my experience with the MATLAB contest, this has been one of the most interesting problems. Please feel free to e-mail me with your comments.

Published with MATLAB® 7.5