Winner Yi Cao (Buy a ticket)

Finish 2007-05-16 12:00:00 UTC

End game 35

by Alan Chalker

Status: Passed
Results: 65653.18 (cyc: 7)
CPU Time: 54.2536
Score: 6595.46
Submitted at: 2007-05-16 11:57:03 UTC
Scored at: 2007-05-16 14:38:00 UTC

Current Rank: 2951st
Based on: End game 1 (diff)

Comments
Alan Chalker
16 May 2007
Hope this works
Please login or create a profile.
Code
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