function moves=solver(board)
moves1=solverrecgood(board);
score1=grade(board,moves1);
moves2=solverrecgoodmetric(board);
score2=grade(board,moves2);
moves3=solvertwibak(board);
% moves3=winnertwi(board);
score3=grade(board,moves3);
if (score1 < score2) && (score1 < score3)
moves=moves1;
elseif (score2 < score1) && (score2 < score3)
moves=moves2;
else
moves=moves3;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = solvertwibak(board)
% % MOVES = SOLVER(BOARD) Solitaire solver.
% %
% % MOVES -> [row_from,column_from,row_to,column_to]
% %
% % The MATLAB Contest Team
% % April, 2007
% moves2=solverHannes(board);
% if (size(moves1)~=size(moves2)) || (moves1~=moves2)
% display('different');
% end
rand('state',0);
movesBest=solverMe(board,0);
scoreBest=grade(board,movesBest);
for i=1:3
moves=solverMe(board,0.05);
score=grade(board,moves);
if (score<scoreBest)
scoreBest=score;
movesBest=moves;
end
end
moves=movesBest;
function moves=solverMe(board,perc)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;
dest=find(padBoard==0);
maybe=[];
moves=[];
moveCnt=0;
for i=1:size(dest,1)
this=dest(i);
% Format of valid
% valid(2)/not(anything else) src jump_over dest score direction_from(1 fron top, 2 from right etc)
maybe=[maybe; padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
maybe=[maybe; padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
maybe=[maybe; padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
maybe=[maybe; padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
end
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
prevPeg=0;
doAgain=1;
totalScore=0;
restoreScore=0;
restorePoint=1;
while doAgain
% Make best move
[scores,indices]=sort(valid(:,5),'descend');
if ~isempty(scores)
if (rand(1)<perc && size(scores,1) > 1)
scores(1)=scores(2);
indices(1)=indices(2);
end
if (scores(1)<0) && (totalScore>restoreScore)
restoreScore=totalScore;
restorePoint=size(moves,1);
end
if (scores(1) > 8000)
scores(1)=scores(1)-10000;
end
totalScore=totalScore+scores(1);
thisInd=indices(1);
from = valid(thisInd,2);
over = valid(thisInd,3);
to = valid(thisInd,4);
rpadsrc=mod(from,mp)-2;
cpadsrc=(from-rpadsrc-2)/mp-1;
rpaddest=mod(to,mp)-2;
cpaddest=(to-rpaddest-2)/mp-1;
moves = [moves; rpadsrc cpadsrc rpaddest cpaddest];
padBin(from)=0;
padBin(over)=0;
padBin(to)=1;
padBoard(to)=padBoard(from);
padBoard(from)=0;
padBoard(over)=0;
% Remove entries in valid move table that are no longer possible
for x = 1 : size(valid,1)
if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
valid(x,1)=0;
end
end
% Add all valid moves into spot where move is made from
valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
% Add all valid moves into spot that is jumped over
valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
% Add all valid moves out of destination
valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
% Add all moves jumping over destination
valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
% Remove all invalid entries
valid=valid(find(valid(:,1)==2),:);
else
doAgain=0;
end
end
if totalScore>restoreScore
return
else
moves=moves(1:restorePoint,:);
return
end
function score = grade(board,moves)
[m,n] = size(board);
tb = @(p) all([p>0 p<=[n m] ~rem(p,1)]);
moves = round(moves(1:min(nnz(board>0),end),:));
score = sum(board(board(:)>0));
lastPeg = [-1 -1];
for i = 1:size(moves,1)
f = moves(i,[2 1]);
t = moves(i,[4 3]);
if tb(f) && board(f(2),f(1))>0 % valid pick
score = score + any(lastPeg-f).*board(f(2),f(1));
lastPeg = f;
mp = (f+t)/2;
if tb(t) && board(t(2),t(1))==0 && all(sort(abs(f-t))==[0 2]) ...
&& board(mp(2),mp(1))>0 % valid move
lastPeg = t;
score = score - board(mp(2),mp(1));
board(t(2),t(1)) = board(f(2),f(1));
board([f(2) mp(2)],[f(1) mp(1)]) = 0;
end
else
lastPeg = [0 0];
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = solverrecgood(board)
moves=dorec(board);
function moves = dorec(board)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;
dest=find(padBoard==0);
maybe=zeros(4*size(dest,1),6);
moveCnt=1;
for i=1:size(dest,1)
this=dest(i);
% Format of valid
% valid(2)/not(anything else) src jump_over dest score direction_from(1 fron top, 2 from right etc)
maybe(moveCnt,:)=[padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
maybe(moveCnt+1,:)=[padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
maybe(moveCnt+2,:)=[padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
maybe(moveCnt+3,:)=[padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
moveCnt=moveCnt+4;
end
restoreScore=0;
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
restoreMoves=[0 0 0 0];
score=0;
totJumps=0;
totChains=0;
while ~isempty(valid)
[chainMoves,scoreRet]=clearChain(padBoard,padBin,valid,mp,np,1);
totJumps=totJumps+size(chainMoves,1);
totChains=totChains+1;
if (scoreRet<0) && (score>=restoreScore)
% scoreRet=scoreRet-1;
% if (scoreRet<0) && (score>=restoreScore)
restoreScore=score;
restoreMoves=moves;
end
[padBoard,padBin,valid,chainMoves]=doMoves(padBoard,padBin,valid,chainMoves);
moves=[moves; chainMoves];
score=score+scoreRet;
end
avgChainLength=totJumps/totChains;
if (score>restoreScore)
moves=moves(find(moves(:,1)>0),:);
else
moves=restoreMoves(find(restoreMoves(:,1)>0),:);
end
function [chainMoves,scoreRet,depthRet]=clearChain(padBoard,padBin,valid,mp,np,depth)
scoreMax=-10000;
chainMoves=[0 0 0];
nextMoves=zeros(4,4);
for i=1:size(valid,1)
scoreChain=0;
newBin=padBin;
newBoard=padBoard;
source=valid(i,2);
over=valid(i,3);
dest=valid(i,4);
newBin([source;over])=0;
newBin(dest)=1;
scoreThis=newBoard(over)-newBoard(source);
newBoard([source;over;dest])=0;
% scoreThis=newBoard(over)/newBoard(source);
% newBoard(dest)=newBoard(source);
% newBoard([source;over])=0;
nextMoves(1,:)=[newBin(dest-1)+3*newBin(dest-2) dest dest-1 dest-2];
nextMoves(2,:)=[newBin(dest+1)+3*newBin(dest+2) dest dest+1 dest+2];
nextMoves(3,:)=[newBin(dest-mp)+3*newBin(dest-2*mp) dest dest-mp dest-2*mp];
nextMoves(4,:)=[newBin(dest+mp)+3*newBin(dest+2*mp) dest dest+mp dest+2*mp];
nextMoves=nextMoves(find(nextMoves(:,1)==1),:);
depthRet=depth;
if ~isempty(nextMoves)
[chainMoves,scoreChain,depthRet]=clearChain(newBoard,newBin,nextMoves,mp,np,depth+1);
end
scoreTotal=scoreThis+scoreChain;
if scoreTotal>scoreMax
scoreMax=scoreTotal;
bestMoves=[source over dest; chainMoves];
bestDepth=depthRet;
end
end
if (depth==1)
chainMoves=bestMoves(1:bestDepth,:);
else
chainMoves=bestMoves;
end
scoreRet=scoreMax;
depthRet=bestDepth;
function [padBoard,padBin,valid,retMoves]=doMoves(padBoard,padBin,valid,chainMoves)
retMoves=[0 0 0 0];
[mp,np]=size(padBoard);
for i=1:size(chainMoves,1)
from = chainMoves(i,1);
over = chainMoves(i,2);
to = chainMoves(i,3);
rpadsrc=mod(from,mp)-2;
cpadsrc=(from-rpadsrc-2)/mp-1;
rpaddest=mod(to,mp)-2;
cpaddest=(to-rpaddest-2)/mp-1;
retMoves = [retMoves; rpadsrc cpadsrc rpaddest cpaddest];
padBin(from)=0;
padBin(over)=0;
padBin(to)=1;
padBoard(to)=padBoard(from);
padBoard(from)=0;
padBoard(over)=0;
% Remove entries in valid move table that are no longer possible
for x = 1 : size(valid,1)
if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
valid(x,1)=0;
end
end
% Add all valid moves into spot where move is made from
valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
% Add all valid moves into spot that is jumped over
valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
% Add all valid moves out of destination
valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
% Add all moves jumping over destination
valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
% Remove all invalid entries
valid=valid(find(valid(:,1)==2),:);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = solverrecgoodmetric(board)
moves=dorec2(board);
function moves = dorec2(board)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;
dest=find(padBoard==0);
maybe=zeros(4*size(dest,1),6);
moveCnt=1;
for i=1:size(dest,1)
this=dest(i);
% Format of valid
% valid(2)/not(anything else) src jump_over dest score direction_from(1 fron top, 2 from right etc)
maybe(moveCnt,:)=[padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
maybe(moveCnt+1,:)=[padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
maybe(moveCnt+2,:)=[padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
maybe(moveCnt+3,:)=[padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
moveCnt=moveCnt+4;
end
restoreScore=0;
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
restoreMoves=[0 0 0 0];
score=0;
totJumps=0;
totChains=0;
while ~isempty(valid)
[chainMoves,scoreRet]=clearChain2(padBoard,padBin,valid,mp,np,1);
totJumps=totJumps+size(chainMoves,1);
totChains=totChains+1;
scoreRet=scoreRet-1;
% if (scoreRet<0) && (score>=restoreScore)
if (scoreRet<0) && (score>=restoreScore)
restoreScore=score;
restoreMoves=moves;
end
[padBoard,padBin,valid,chainMoves]=doMoves2(padBoard,padBin,valid,chainMoves);
moves=[moves; chainMoves];
score=score+scoreRet;
end
avgChainLength=totJumps/totChains;
if (score>restoreScore)
moves=moves(find(moves(:,1)>0),:);
else
moves=restoreMoves(find(restoreMoves(:,1)>0),:);
end
function [chainMoves,scoreRet,depthRet]=clearChain2(padBoard,padBin,valid,mp,np,depth)
scoreMax=-10000;
chainMoves=[0 0 0];
nextMoves=zeros(4,4);
for i=1:size(valid,1)
scoreChain=0;
newBin=padBin;
newBoard=padBoard;
source=valid(i,2);
over=valid(i,3);
dest=valid(i,4);
newBin([source;over])=0;
newBin(dest)=1;
% scoreThis=newBoard(over)-newBoard(source);
% newBoard([source;over;dest])=0;
scoreThis=newBoard(over)/newBoard(source);
newBoard(dest)=newBoard(source);
newBoard([source;over])=0;
nextMoves(1,:)=[newBin(dest-1)+3*newBin(dest-2) dest dest-1 dest-2];
nextMoves(2,:)=[newBin(dest+1)+3*newBin(dest+2) dest dest+1 dest+2];
nextMoves(3,:)=[newBin(dest-mp)+3*newBin(dest-2*mp) dest dest-mp dest-2*mp];
nextMoves(4,:)=[newBin(dest+mp)+3*newBin(dest+2*mp) dest dest+mp dest+2*mp];
nextMoves=nextMoves(find(nextMoves(:,1)==1),:);
depthRet=depth;
if ~isempty(nextMoves)
[chainMoves,scoreChain,depthRet]=clearChain2(newBoard,newBin,nextMoves,mp,np,depth+1);
end
scoreTotal=scoreThis+scoreChain;
if scoreTotal>scoreMax
scoreMax=scoreTotal;
bestMoves=[source over dest; chainMoves];
bestDepth=depthRet;
end
end
if (depth==1)
chainMoves=bestMoves(1:bestDepth,:);
else
chainMoves=bestMoves;
end
scoreRet=scoreMax;
depthRet=bestDepth;
function [padBoard,padBin,valid,retMoves]=doMoves2(padBoard,padBin,valid,chainMoves)
retMoves=[0 0 0 0];
[mp,np]=size(padBoard);
for i=1:size(chainMoves,1)
from = chainMoves(i,1);
over = chainMoves(i,2);
to = chainMoves(i,3);
rpadsrc=mod(from,mp)-2;
cpadsrc=(from-rpadsrc-2)/mp-1;
rpaddest=mod(to,mp)-2;
cpaddest=(to-rpaddest-2)/mp-1;
retMoves = [retMoves; rpadsrc cpadsrc rpaddest cpaddest];
padBin(from)=0;
padBin(over)=0;
padBin(to)=1;
padBoard(to)=padBoard(from);
padBoard(from)=0;
padBoard(over)=0;
% Remove entries in valid move table that are no longer possible
for x = 1 : size(valid,1)
if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
valid(x,1)=0;
end
end
% Add all valid moves into spot where move is made from
valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
% Add all valid moves into spot that is jumped over
valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
% Add all valid moves out of destination
valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
% Add all moves jumping over destination
valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
% Remove all invalid entries
valid=valid(find(valid(:,1)==2),:);
end
|
