function moves=solver(board)
% SOLVER Solver for the Peg Solitaire contest.
%
% Author: Ken Eaton
% Last modified: 5/16/07
nDepth=1;
nSimultaneousMoves=5;
moves=reshape([],0,4);
nTentative=0;
cost=0;
%diffEO=0;
diffEO=init_diffEO(board); % Different Init!!
while true,
[r,c]=find_movable(board);
if isempty(r),
moves=moves(1:(end-nTentative),:);
break;
end
[r,c,alt_r,alt_c]=separate_even_odd(r,c,diffEO);
% [r,c,alt_r,alt_c]=separate_even_odd(r,c,0); % Turns off EO selection
[newMoves,moveNum,newCost,newDiffEO]=find_jumps(board,r,c,nDepth);
% [alt_newMoves,alt_moveNum,alt_newCost,alt_newDiffEO]=...
% find_jumps(board,alt_r,alt_c,nDepth);
if any(newCost>0),
[newMoves,moveNum,newCost,newDiffEO]=...
remove_moves(newMoves,moveNum,newCost,newDiffEO,find(newCost<=0));
end
[newMoves,moveNum,newCost,newDiffEO]=...
select_moves(board,newMoves,moveNum,newCost,newDiffEO);
if (~isinf(nSimultaneousMoves)),
[junk,index]=sort(newCost,'descend');
index=index((nSimultaneousMoves+1):end);
if (~isempty(index)),
[newMoves,moveNum,newCost,newDiffEO]=...
remove_moves(newMoves,moveNum,newCost,newDiffEO,index);
end
end
board=apply_moves(board,newMoves);
moves=[moves; newMoves];
cost=cost+sum(newCost);
if (cost<0),
nTentative=nTentative+size(newMoves,1);
else
cost=0;
nTentative=0;
end
diffEO=diffEO+sum(newDiffEO);
end
end % end solver
function li=rc2li(R,rc)
% Change a set of [row column] indices to a linear index
if isempty(rc),
li=[];
else,
li=rc(:,1)+R.*(rc(:,2)-1);
end
end
function diffEO=init_diffEO(board)
% Initialize diffEO
[R,C]=size(board);
clusterMatrix=diag(true(1,R*C));
[r,c]=find(board>=0);
rCenter=[r; r; r; r];
cCenter=[c; c; c; c];
rSide=[r; r-1; r; r+1];
cSide=[c-1; c; c+1; c];
index=((rSide>0)&(rSide<=R)&(cSide>0)&(cSide<=C));
indexCenter=rc2li(R,[rCenter(index) cCenter(index)]);
indexSide=rc2li(R,[rSide(index) cSide(index)]);
index=(board(indexSide)>=0);
indexCenter=indexCenter(index);
indexSide=indexSide(index);
clusterMatrix(rc2li(R*C,[indexCenter indexSide]))=true;
clusterMatrix=clusterMatrix|(clusterMatrix');
index=symrcm(clusterMatrix);
clusterMatrix=clusterMatrix(index,index);
[junk,indexCluster]=max(clusterMatrix,[],1);
for i=1:length(indexCluster),
indexCluster(i)=min(indexCluster(i:end));
end
indexCluster=find([(indexCluster==(1:R*C)) true]);
diffEO=0;
for i=1:(length(indexCluster)-1),
indexMat=(indexCluster(i):(indexCluster(i+1)-1));
if any(board(indexMat)==0),
r=rem(indexMat,R);
r(r==0)=R;
c=floor(indexMat./R);
c(c==0)=1;
diffEO=diffEO+2*sum(rem(r+c,2)==0)-length(r);
end
end
end
function [r,c]=find_movable(board)
% Find all movable pegs
[R,C]=size(board);
[r,c]=find(board>0);
rPrey=[r; r-1; r; r+1];
cPrey=[c-1; c; c+1; c];
rTurn=[r; r-2; r; r+2];
cTurn=[c-2; c; c+2; c];
index=((rTurn>0)&(rTurn<=R)&(cTurn>0)&(cTurn<=C));
indexPrey=rc2li(R,[rPrey(index) cPrey(index)]);
indexTurn=rc2li(R,[rTurn(index) cTurn(index)]);
index(index)=((board(indexPrey)>0)&(board(indexTurn)==0));
index=find(any(reshape(index,length(r),4),2));
r=r(index);
c=c(index);
end
function [r,c,alt_r,alt_c]=separate_even_odd(r,c,diffEO)
% Separate pegs in [r,c] into even and odd and pick one to start with
alt_r=[];
alt_c=[];
index=(rem(r+c,2)==0);
if (any(index)&&(~all(index))),
switch sign(diffEO),
case -1,
alt_r=r(~index);
alt_c=c(~index);
r=r(index);
c=c(index);
case 1,
alt_r=r(index);
alt_c=c(index);
r=r(~index);
c=c(~index);
end
end
end
function [rTurn,cTurn,indexPrey]=find_moves(board,r,c)
% Find possible moves for peg at [r,c]
[R,C]=size(board);
rPrey=[r; r-1; r; r+1];
cPrey=[c-1; c; c+1; c];
rTurn=[r; r-2; r; r+2];
cTurn=[c-2; c; c+2; c];
index=((rTurn>0)&(rTurn<=R)&(cTurn>0)&(cTurn<=C));
rTurn=rTurn(index);
cTurn=cTurn(index);
indexPrey=rc2li(R,[rPrey(index) cPrey(index)]);
index=((board(indexPrey)>0)&(board(rc2li(R,[rTurn cTurn]))==0));
rTurn=rTurn(index);
cTurn=cTurn(index);
indexPrey=indexPrey(index);
end
function [moves,num,cost,diffEO]=find_jumps(board,r,c,nDepth)
% Find optimum move information for pegs in [r c]
moves=reshape([],0,4);
num=[];
cost=[];
diffEO=[];
[R,C]=size(board);
val=board(rc2li(R,[r c]));
for i=1:length(r),
[pointMove,pointCost]=optimum_move(board,r(i),c(i),-val(i),nDepth);
moves=[moves; pointMove];
nPrey=size(pointMove,1);
num=[num; (max([num; 0])+1).*ones(nPrey,1)];
cost=[cost; pointCost];
diffEO=[diffEO; (2*rem(r(i)+c(i)+1,2)-1)*nPrey];
end
end
function [moves,maxScore]=optimum_move(board,r,c,currentScore,nDepth)
% Find move with maximum score for peg at [r,c]
moves=reshape([],0,4);
maxScore=-Inf;
[rTurn,cTurn,indexPrey]=find_moves(board,r,c);
for i=1:length(indexPrey),
tempBoard=board;
newScore=currentScore+tempBoard(indexPrey(i));
tempBoard(rTurn(i),cTurn(i))=tempBoard(r,c);
tempBoard(indexPrey(i))=0;
tempBoard(r,c)=0;
newMoves=[];
if (nDepth>1),
[newMoves,tempScore]=optimum_move(tempBoard,rTurn(i),cTurn(i),...
newScore,nDepth-1);
if (~isempty(newMoves)),
newScore=tempScore;
end
end
if (newScore>maxScore),
maxScore=newScore;
moves=[[r c rTurn(i) cTurn(i)]; newMoves];
end
end
end
function [moves,num,cost,diffEO]=remove_moves(moves,num,cost,diffEO,index)
% Remove moves matching move number in index
cost(index)=[];
diffEO(index)=[];
index=ismember(num,index);
num(index)=[];
num=cumsum([1; sign(diff(num))]);
moves(index,:)=[];
end
function [moves,num,cost,diffEO]=select_moves(board,moves,num,cost,diffEO)
% Select a subset of moves that don't interfere and maximize the score
[R,C]=size(board);
nMoves=size(cost,1);
indexMoves=[rc2li(R,moves(:,[1 2])) rc2li(R,moves(:,[3 4]))];
index=(indexMoves(2:end,1)~=indexMoves(1:(end-1),2));
indexStart=indexMoves([true; index],1);
indexEnd=indexMoves([index; true],2);
indexPrey=mean(indexMoves,2);
indexTurn=indexMoves([false; (~index)],1);
if all(cost<=0),
cost=cost-1;
end
intMatrix=diag(cost);
compute_interference;
solve_interference;
[moves,num,cost,diffEO]=remove_moves(moves,num,cost,diffEO,index);
indexMoves(index,:)=[];
if all(cost<0),
cost=cost+1;
end
function compute_interference
% Fill in intMatrix for a set of moves
temp=sort(indexStart);
temp=unique(temp([(diff(temp)==0); false]));
for i=1:length(temp),
index=unique(num(indexMoves(:,1)==temp(i)));
intMatrix(index,index)=diag(2.*cost(index))-...
ones(size(index))*cost(index)';
end
temp=sort(indexEnd);
temp=unique(temp([(diff(temp)==0); false]));
for i=1:length(temp),
index=unique(num(indexMoves(:,2)==temp(i)));
intMatrix(index,index)=diag(2.*cost(index))-...
ones(size(index))*cost(index)';
end
temp=sort(indexPrey);
temp=unique(temp([(diff(temp)==0); false]));
for i=1:length(temp),
index=unique(num(indexPrey==temp(i)));
intMatrix(index,index)=diag(2.*cost(index))-...
ones(size(index))*cost(index)';
end
temp=find(ismember(indexPrey,indexStart));
for i=1:length(temp),
index=unique(num((indexMoves(:,1)==indexPrey(temp(i)))|...
(indexPrey==indexPrey(temp(i)))));
intMatrix(index,index)=diag(2.*cost(index))-...
ones(size(index))*cost(index)';
end
% Rewrite below, giving precedence to turn before end!!!
temp=find(ismember(indexTurn,indexEnd));
for i=1:length(temp),
index=unique(num((indexMoves(:,1)==indexTurn(temp(i)))&...
ismember(indexMoves(:,1),indexEnd)));
intMatrix(index,index)=diag(2.*cost(index))-...
ones(size(index))*cost(index)';
end
end
function solve_interference
% Solve intMatrix to maximize cost
indexBWM=symrcm(intMatrix);
intMatrix=intMatrix(indexBWM,indexBWM);
[junk,indexCluster]=max((intMatrix~=0),[],1);
for i=1:length(indexCluster),
indexCluster(i)=min(indexCluster(i:end));
end
indexCluster=find([(indexCluster==[1:nMoves]) true]);
index=false(1,nMoves);
for i=1:(length(indexCluster)-1),
nCluster=indexCluster(i+1)-indexCluster(i);
if nCluster>1,
indexMat=[indexCluster(i):(indexCluster(i+1)-1)];
if (nCluster*(2^nCluster)>(2^26)),
nCluster=21;
[junk,indexTrim]=sort(diag(intMatrix(indexMat,indexMat)),...
'descend');
index(indexMat(indexTrim((nCluster+1):end)))=true;
indexMat=indexMat(indexTrim(1:nCluster));
end
combos=zeros(2^nCluster,nCluster);
for j=1:nCluster,
nRows=2^(nCluster-j);
nColumns=2^(j-1);
temp=[ones(nRows,nColumns); zeros(nRows,nColumns)];
combos(:,j)=temp(:);
end
comboCost=sum((combos*intMatrix(indexMat,indexMat)).*combos,2);
if all(cost<0),
comboCost(comboCost>=0)=-Inf;
[junk,maxIndex]=max(comboCost);
else,
[junk,maxIndex]=max(comboCost);
end
index(indexMat)=(~combos(maxIndex,:));
end
end
index(indexBWM)=index;
index=find(index);
end
end
function board=apply_moves(board,moves)
% Apply moves in newMoves to the current board
[R,C]=size(board);
indexMoves=[rc2li(R,moves(:,[1 2])) rc2li(R,moves(:,[3 4]))];
index=find([true; (indexMoves(2:end,1)~=indexMoves(1:(end-1),2)); true]);
for i=1:(length(index)-1),
currentMove=indexMoves(index(i):(index(i+1)-1),:);
indexStart=currentMove(1,1);
indexEnd=currentMove(end,2);
if (indexStart~=indexEnd),
board(indexEnd)=board(indexStart);
board(indexStart)=0;
end
board(mean(currentMove,2))=0;
end
end
|
