Winner Yi Cao (Buy a ticket)

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

oooh2

by Jin

Status: Failed
Results:

Based on: oooh (diff)

Comments
Please login or create a profile.
Code
function moves = solver(board)
tweak=rand(7,1);
[m,n] = size(board);
COUNT = sum(board(:)>0); % check the number of pegs on the board

fill = (COUNT-nnz(board<0))/(m*n);
if (COUNT< 280)&&(fill < 0.72)
    ntb=ones(m+4,n+4) * -1;
    ntb(3:end-2,3:end-2)= board;
    rows=m+4;
    count=0;
    dead_weight = 0.1 * mean(ntb(ntb>0));
    moves=solveri(ntb);
else
    %     board0 = board;
    %     [m,n] = size(board0); % find dims of input board
    [i,j]=find(ones(m,n)); % create an index listing of board elements

    I = [i;i;i;i];  % vector of 4 repeats of row coords
    J = [j;j;j;j]; % vector of 4 repeats of col coords
    K = [i;i;i-2;i+2]; % vector of row cords, row cords, 2 rows above, 2 rows below
    L = [j-2;j+2;j;j]; % vector of 2 cols before, 2 cols past, col cords, col cords
    % [I J K L] would be a matrix of ALL potential moves for this board

    K1=[i;i;i-4;i+4]; % vector of row cords, row cords, 4 rows above, 4 rows below
    L1=[j-4;j+4;j;j]; % vector of 4 cols before, 4 cols past, col cords, col cords
    % if a move from [I J] to [K L] were done, [K L K1 L1] is the potential next colinear moves

    K2=[i-2;i+2;i-2;i+2]; % vector of 2 rows above, 2 rows below repeated twice
    L2=[j-2;j+2;j+2;j-2];  % vector of 2 cols before, 2 cols past, 2 cols past, 2 cols before
    % if a move from [I J] to  [K L] were done, [K L K2 L2] is the half of the potential next orthogonal moves

    K3=[i+2;i-2;i-2;i+2]; % vector of 2 rows below, 2 rows above, 2 rows above, 2 rows below
    L3=[j-2;j+2;j-2;j+2]; % vector of 2 cols before, 2 cols past repeated twice
    % if a move from [I J] to [K L] were done, [K L K3 L3] is the other half of the potential next orthogonal moves

    h = (K>0 & K<=m & L>0 & L<=n); % find indexes of moves that stay within overall bounds of board after 1st jump
    I=I(h); % remove moves that jump off the board after 1st jump
    J=J(h); % remove moves that jump off the board after 1st jump
    K=K(h); % remove moves that jump off the board after 1st jump
    L=L(h); % remove moves that jump off the board after 1st jump
    K1=K1(h); % remove moves that jump off the board after 1st jump
    K2=K2(h); % remove moves that jump off the board after 1st jump
    K3=K3(h); % remove moves that jump off the board after 1st jump
    L1=L1(h); % remove moves that jump off the board after 1st jump
    L2=L2(h); % remove moves that jump off the board after 1st jump
    L3=L3(h); % remove moves that jump off the board after 1st jump

    F=I+(J-1)*m; % convert source spot coordinates [I J] into single index value
    T=K+(L-1)*m; % convert destination spot coordinates [K L] into single index value
    M=(F+T)*0.5; % calculate the index value of the spot that would be jumped if did move [I J K L]

    h=board(F)>=0&board(M)>=0&board(T)>=0; % find indexes of moves that don't involve offlimits (-1) areas
    I=I(h); % remove moves that involve offlimits areas
    J=J(h); % remove moves that involve offlimits areas
    K=K(h); % remove moves that involve offlimits areas
    L=L(h); % remove moves that involve offlimits areas
    F=F(h); % remove moves that involve offlimits areas
    T=T(h); % remove moves that involve offlimits areas
    M=M(h); % remove moves that involve offlimits areas
    K1=K1(h); % remove moves that involve offlimits areas
    K2=K2(h); % remove moves that involve offlimits areas
    K3=K3(h); % remove moves that involve offlimits areas
    L1=L1(h); % remove moves that involve offlimits areas
    L2=L2(h); % remove moves that involve offlimits areas
    L3=L3(h); % remove moves that involve offlimits areas


    % moveid1(k,:) are the moves (up to 4) which originate at location k
    % moveid2(k,:) are the moves (up to 4) which jump over location k
    % moveid3(k,:) are the moves (up to 4) which terminate at location k
    ni=max([max(M) max(F) max(T)]);
    nmove1=zeros(ni,1); nmove2=nmove1; nmove3=nmove1;
    moveid1=zeros(ni,4);    moveid2=moveid1;    moveid3=moveid1;
    for k=1:length(F);
        nmove1(F(k)) = nmove1(F(k))+1;
        moveid1(F(k),nmove1(F(k))) = k;

        nmove2(M(k)) = nmove2(M(k))+1;
        moveid2(M(k),nmove2(M(k))) = k;

        nmove3(T(k)) = nmove3(T(k))+1;
        moveid3(T(k),nmove3(T(k))) = k;
    end

    h1 = (K1>0 & K1<=m & L1>0 & L1<=n); % find indexes of moves that stay within overall bounds of board after 2nd colinear jump
    h2 = (K2>0 & K2<=m & L2>0 & L2<=n); % find indexes of moves that stay within overall bounds of board after 2nd orthogonal jump
    h3 = (K3>0 & K3<=m & L3>0 & L3<=n);% find indexes of moves that stay within overall bounds of board after 2nd orthogonal jump

    T1=T;T2=T;T3=T; % create dups of 1st jump destination spot coordinates
    T1(h1)=K1(h1)+(L1(h1)-1)*m; % convert 2nd colinear jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
    T2(h2)=K2(h2)+(L2(h2)-1)*m; % convert 2nd ortho jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
    T3(h3)=K3(h3)+(L3(h3)-1)*m; % convert 2nd ortho jump destination spot coordinates into single index value - note invalid jumps are kept in index but not converted
    M1=(T+T1)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K1 L1]
    M2=(T+T2)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K2 L2]
    M3=(T+T3)*0.5; % calculate the index value of the spot that would be jumped if did move [K L K3 L3]

    CV = zeros(size(M1)); % make a dup of colinear jumps
    N=COUNT; % count number of pegs
    MV = [I J K L]; % create first possible move list

    ddlist=1;%
    mv{1}=0;
    v1=0;    
    
        [mv{2},v2] = subsol(board,1); %  calculate moves and scores of moves with nested function
        [v1,i]=max([v1 v2]); %find best
        mv{1}=mv{i};
   
    moves=mv{1};

end;

    function moves=solveri(scores)

        board = scores;
        zz = find(board>0);
        balls=numel(zz);
        moves = zeros(balls,4);

        bufsize = balls*4;
        cellbuf = zeros(bufsize,1);
        valbuf = zeros(bufsize,1);
        movebuf = zeros(bufsize,1);
        hopbuf = zeros(bufsize,1);

        last_move = 0;
        score = 0;
        last_pos = 0;
        last_score = 0;
        depth = 10;

        hop_max = 0;
        hop_cnt = 0;
        hop_list=hopbuf;

        [cell_list,value_list,move_list] = CalculateMoves(board);

        while 1
            % find highest value moves
            if isempty(cell_list),break;end

            FindHops(board,cell_list,move_list,value_list);
            if (hop_max~=0)&&(hop_cnt>2)
                for zh=1:hop_cnt-1
                    cell_list = [cell_list;hop_list(zh)];
                    move_list = [move_list;hop_list(zh+1)];
                    value_list = [value_list;hop_max];
                    DoMove(numel(cell_list));
                end
            else
                %find moves that create hops
                [hop_values,pos]=sort(value_list,'descend');
                value_list = hop_values;
                cell_list=cell_list(pos);
                move_list=move_list(pos);
                for zh=1:min(depth,numel(cell_list))
                    [newB,newS,newC,newM,newV] = ProcessMove(board,scores,zh,cell_list,move_list,value_list);
                    FindHops(newB,newC,newM,newV);
                    hop_values(zh) = hop_values(zh) + hop_max;
                end
                [max_val,pos]=max(hop_values);
                DoMove(pos);
            end

            %             if (count==balls)
            %                 break;
            %             end
        end

        moves = moves(1:last_pos,:);

        function DoMove(pos)
            max_cell = cell_list(pos);
            max_move = move_list(pos);
            count = count+1;
            moves(count,:) = [mod(max_cell-2,rows),ceil(max_cell/rows)-2,mod(max_move-2,rows),ceil(max_move/rows)-2];

            brem = (max_cell+max_move)/2;
            score = score + scores(brem);
            if (max_cell ~= last_move)
                score = score - scores(max_cell);
            end
            if (score > last_score)
                last_pos=count;
                last_score=score;
            end;

            [board,scores,cell_list,move_list,value_list] = ProcessMove(board,scores,pos,cell_list,move_list,value_list);
            last_move = max_move;
        end

        function FindHops(B,Lcells,Lmoves,Lvalues)
            hop_max=0;
            for zi=1:numel(Lcells)
                src=Lcells(zi);
                dst=Lmoves(zi);
                n=Lvalues(zi);
                hopbuf(1)=src;
                if B(dst+2)&&B(dst-2)&&B(dst+2*rows)&&B(dst-2*rows)
                    if n>hop_max
                        hopbuf(2)=dst;
                        hop_max = n;
                        hop_cnt = 2;
                        hop_list(1:2)=hopbuf(1:2);
                    end
                else
                    FindHopTree(B,src,dst,n,2);
                end
            end
        end

        function FindHopTree(B,src,dst,n,cnt)
            B(dst)=B(src);
            B((src+dst)/2)=0;
            B(src)=0;

            %save hop
            hopbuf(cnt)=dst;

            X = B(dst+2)==0 & B(dst+1)>0; if X
                FindHopTree(B,dst,dst+2,n+B(dst+1),cnt+1);
            end

            X = B(dst-2)==0 & B(dst-1)>0; if X
                FindHopTree(B,dst,dst-2,n+B(dst-1),cnt+1);
            end

            X = B(dst+2*rows)==0 & B(dst+rows)>0; if X
                FindHopTree(B,dst,dst+2*rows,n+B(dst+rows),cnt+1);
            end

            X = B(dst-2*rows)==0 & B(dst-rows)>0; if X
                FindHopTree(B,dst,dst-2*rows,n+B(dst-rows),cnt+1);
            end

            %end of hop chain -- check for max and save route
            if n>hop_max
                hop_max = n;
                hop_cnt = cnt;
                hop_list(1:cnt)=hopbuf(1:cnt);
            end

        end

        function n=CalculateBall(board,src,dst,n)
            pop=(src+dst)/2;
            if board(pop)>0 && ~board(dst) && board(src)>0
                pass=board(pop)-board(src);
                if sum(board([dst+1 dst-1 dst+rows dst-rows])>0) == 1
                    pass=pass-dead_weight;
                end
                n=n+1;
                valbuf(n)=pass;
                cellbuf(n)=src;
                movebuf(n)=dst;
            end
        end

        function n=CalculateHole(board,dst,src,n)
            pop=(src+dst)/2;
            if board(pop)>0 && board(src)>0
                pass=board(pop)-board(src);
                if sum(board([dst+1 dst-1 dst+rows dst-rows])>0) == 1
                    pass=pass-dead_weight;
                end
                n=n+1;
                valbuf(n)=pass;
                cellbuf(n)=src;
                movebuf(n)=dst;
            end
        end

        function Lmoves=EliminateMove(Lcells,Lmoves,src,dst)
            rem_src=find(Lcells==src);
            Lmoves(rem_src(logical(Lmoves(rem_src)==dst)))=0;
        end

        function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(board)
            zb = find(board>0);
            zz = find(board==0);
            n=0;
            if numel(zz)<numel(zb)
                for zi=1:numel(zz)
                    i=zz(zi);
                    n=CalculateHole(board,i,i-2,n);
                    n=CalculateHole(board,i,i+2,n);
                    n=CalculateHole(board,i,i-rows*2,n);
                    n=CalculateHole(board,i,i+rows*2,n);
                end
            else
                for zi=1:numel(zb)
                    i=zb(zi);
                    n=CalculateBall(board,i,i-2,n);
                    n=CalculateBall(board,i,i+2,n);
                    n=CalculateBall(board,i,i-rows*2,n);
                    n=CalculateBall(board,i,i+rows*2,n);
                end
            end
            new_cell_list=cellbuf(1:n);
            new_value_list=valbuf(1:n);
            new_move_list=movebuf(1:n);
        end

        function [B,S,Lcells,Lmoves,Lvalues]=ProcessMove(B,S,pos,Lcells,Lmoves,Lvalues)
            src = Lcells(pos);
            dst = Lmoves(pos);
            pop = (src+dst)/2;
            B(dst)=B(src);
            B(pop)=0;
            B(src)=0;
            S(dst)=S(src);
            S(pop)=0;
            S(src)=0;

            u = src-pop;
            if (abs(u)==1)
                v=rows;
            else
                v=1;
            end

            Lmoves(logical(Lmoves==dst))=0;
            Lmoves(logical(Lcells==src))=0;
            Lmoves(logical(Lcells==pop))=0;
            Lmoves=EliminateMove(Lcells,Lmoves,src-v,src+v);
            Lmoves=EliminateMove(Lcells,Lmoves,src+v,src-v);
            Lmoves=EliminateMove(Lcells,Lmoves,src-v-u,src+v-u);
            Lmoves=EliminateMove(Lcells,Lmoves,src+v-u,src-v-u);
            [Lmoves,rem_dst]=sort(Lmoves,'descend');
            Lcells=Lcells(rem_dst);
            Lvalues=Lvalues(rem_dst);
            ncnt=find(Lmoves==0);
            ncnt=ncnt(1);
            Lcells=Lcells(1:ncnt-1);
            Lvalues=Lvalues(1:ncnt-1);
            Lmoves=Lmoves(1:ncnt-1);

            n=0;
            n=CalculateBall(B,src-3*u,src-u,n);
            n=CalculateBall(B,src+2*v-u,src-u,n);
            n=CalculateBall(B,src+2*v,src,n);
            n=CalculateBall(B,src+2*u,src,n);
            n=CalculateBall(B,src-2*v,src,n);
            n=CalculateBall(B,src-2*v-u,src-u,n);
            n=CalculateBall(B,dst,dst-2*u,n);
            n=CalculateBall(B,dst,dst-2*v,n);
            n=CalculateBall(B,dst,dst+2*v,n);
            clf=src-v-2*u;
            crt=src+v-2*u;
            if ~B(clf)
                n=CalculateBall(B,crt,clf,n);
            end
            if ~B(crt)
                n=CalculateBall(B,clf,crt,n);
            end

            if (n>0)
                if (ncnt>1)
                    Lcells = [Lcells;cellbuf(1:n)];
                    Lmoves = [Lmoves;movebuf(1:n)];
                    Lvalues = [Lvalues;valbuf(1:n)];
                else
                    Lcells=cellbuf(1:n);
                    Lvalues=valbuf(1:n);
                    Lmoves=movebuf(1:n);
                end
            end
        end

    end

    function [moves,v]=subsol(board,d)
        moves=zeros(N-1,4); % preallocate maximum possible move list based on number of pegs
        v0=zeros(N-1,1); % preallocate maximum size of score list
        Bzero = ~board;  % create inverse board where 1 is a hole and every else is a zero, including offlimits
        Bpos  = board>0; % create board with pegs all as 1 and everything else 0
        hs = (Bpos(F) & Bzero(T) & Bpos(M)); % search for moves where source is peg, destination is hole and jumped spot is peg
        h = find(hs); % extract indexes of valid moves
        t=1; % init move list index
        while ~isempty(h)
            CV(:)=0; % init all possible 2nd jumps B to 0
            h0=hs&h1; % compare possible colinear jumps with valid 1st jumps
            Mtemp=M1(h0); %find indexes of 2nd jumped peg
            CV(h0)=board(Mtemp).*(Bpos(Mtemp)&Bzero(T1(h0))); %find 2nd jumped peg B score (colinear), check if dest is hole and jumped is peg
            h0=hs&h2; % compare possible ortho1 jumps with valid 1st jumps
            Mtemp=M2(h0); %find indexes of 2nd jumped peg
            CV(h0)=max(CV(h0),board(Mtemp).*(Bpos(Mtemp)&Bzero(T2(h0))));  %find 2nd jumped peg B score (ortho1), check if dest is hole and jumped is peg
            h0=hs&h3; % compare possible ortho2 jumps with valid 1st jumps
            Mtemp=M3(h0); %find indexes of 2nd jumped peg
            CV(h0)=max(CV(h0),board(Mtemp).*(Bpos(Mtemp)&Bzero(T3(h0)))); %find 2nd jumped peg B score (ortho2), check if dest is hole and jumped is peg
            if t>1
                c=h(F(h)==T0); % find indexes of jumps with source peg that is same as last one moved
            else
                c=[]; % else zero out c
            end
            if ~isempty(c) % if any current 2 jump moves contain the last peg
                C0=board(M(c)); % seed possible 2nd jumps B with jumped peg value for all jumps the match last jump end
                [v,k]=max(C0+CV(c)*d); % add jumped peg to 2nd jump and find best 2 move jump
                v0(t)=C0(k); % extract score of best 1st jump score
                k=c(k);  % extract index of best 2 move jump
            else
                V=board(M(h))-board(F(h)); % calculate score for all valid 1st moves
                [v,k]=max(V+CV(h)*d); % add 1st move score to 2nd jump scores and find best 2 move jump
                v0(t)=V(k); %extract score of best 1st double jump
                k=h(k); % extract index of first move
            end
            moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
            T0=T(k); % extract 1st jump destination spot
            t=t+1; % increment move count

            Fk=F(k);
            board(T0)=board(Fk); % update destination spot with source spot peg
            Bzero(T0) = false;
            Bpos(T0) = true;
            board(Fk)=0; % zero out source spot peg
            Bzero(Fk) = true; % create updated inverse board
            Bpos(Fk) = false;
            Mk=M(k);
            board(Mk)=0; % zero out jumped spot peg
            Bpos(Mk) = false;
            Bzero(Mk) = true; % create updated inverse board
            % assemble list of moves affected by the current move
            mF = moveid1([Fk Mk T0],:); mF=mF(mF>0);  % moves originating at spots involved in last move
            mM = moveid2([Fk Mk T0],:); mM=mM(mM>0);  % moves jumping over spots involved in last move
            mT = moveid3([Fk Mk T0],:); mT=mT(mT>0);  % moves terminating at spots involved in last move
            amoves=[mF;mM;mT];
            hs(amoves) = (Bpos(F(amoves)) &Bzero(T(amoves)) & Bpos(M(amoves))); % search for valid moves in new board (original method)

            h = find(hs); % extract indexes of valid moves
        end
        v0=cumsum(v0); % create cumulative sum of scores in movelist
        [v,t]=max(v0); % extract location of best cumulative score
        moves = moves(1:t,:); % output moves up to best location

    end
    
end