Winner Yi Cao (Buy a ticket)

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

End game 28

by Alan Chalker

Status: Passed
Results: 39360.72 (cyc: 10)
CPU Time: 46.3366
Score: 3956.36
Submitted at: 2007-05-16 11:44:49 UTC
Scored at: 2007-05-16 13:04:22 UTC

Current Rank: 375th
Based on: End game 1 (diff)

Comments
Alan Chalker
16 May 2007
Hope this works
Please login or create a profile.
Code
function [moves,score] = collaborationSover(board)
%
% Note in the interest of collaboration I'm documenting
% the leading code as much as possible.  Instead of going the
% obscufation route with this, I invite everyone to
% document / take credit for their particular changes
% as the codes get modified.
%
% At a minimum, please don't remove the existing comments
% so someones doesn't have to start from scratch on commenting
% updated code again
%
% Alan Chalker
%

% Set up the random number generator so it produces a favorable sequence.
rand('state',10);
rand(57,1);

[m,n] = size(board); % find the dims of the board
pegCount = sum(board(:)>0); % check the number of pegs on the board
rows = m+4; % expand the height by 4 rows
rv = 5:rows; % create a new row index starting at 5th row
cols = n+4; % expand the width by 4 cols
cv = 5:cols; % create a new col index starting at 5th col

% calculate the peg to off limit areas ratio of board
fill = (pegCount-nnz(board<0)) / (m*n);

    i = repmat(rv',[n 1]); % create an index of all the new board row coordinates except for the 1st 4 rows
    j = reshape(repmat(cv,[m 1]),[m*n 1]); % create an index of all the new board col coordinates except for the 1st 4 cols
    % note [i j] would be a list of all original board coordinates in the
    % new board created below

    mm = m+8; % expand the original height by 8 rows
    nn = n+8;  % expand the original width by 8 cols
    ppBoard = -ones(mm, nn); % create a new board with 4 extra rows / cols of offlimits all the way around the board
    ppBoard(rv,cv) = board; % populate the new board with the original board values

    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

    F = I+(J-1)*mm; % convert source spot coordinates [I J] into single index value
    T = K+(L-1)*mm; % 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]

    % find indexes of moves that don't involve off limits (-1) areas
    bogusMoves = (ppBoard(F) < 0) | (ppBoard(M) < 0) | (ppBoard(T) < 0);

    % remove moves that involve off limits areas
    I(bogusMoves) = [];
    J(bogusMoves) = [];
    K(bogusMoves) = [];
    L(bogusMoves) = [];
    F(bogusMoves) = [];
    T(bogusMoves) = [];
    M(bogusMoves) = [];
    K1(bogusMoves) = [];
    K2(bogusMoves) = [];
    K3(bogusMoves) = [];
    L1(bogusMoves) = [];
    L2(bogusMoves) = [];
    L3(bogusMoves) = [];

    [moveid1,moveid2,moveid3] = createMoves(M,F,T);

    % convert 2nd jump destination spot coordinates into single index value
    % note invalid jumps are kept in index but not converted
    T1 = K1+(L1-1)*mm; % colinear
    T2 = K2+(L2-1)*mm; % ortho
    T3 = K3+(L3-1)*mm; % ortho
    TT = [T1 T2 T3];

    % calculate the index value of the spot that would be jumped if did move
    M1 = (T+T1)*0.5; % [K L K1 L1]
    M2 = (T+T2)*0.5; % [K L K2 L2]
    M3 = (T+T3)*0.5; % [K L K3 L3]
    MM = [M1 M2 M3];

    % create first possible move list
    MV = [I J K L]; 
    MV1 = [K L K1 L1];  
    MV2 = [K L K2 L2]; 
    MV3 = [K L K3 L3];
    MVV = {MV1, MV2, MV3};

    % run the subsolver function
    [moves,score] = subsoltweak( ...
        ppBoard, ...
        F,T,M, ...
        pegCount, ...
        TT,MM,MV,MVV, ...
        moveid1,moveid2,moveid3);

    % calculate the max possible score as 81% of the sum of the pegs
maxsum = sum(board(board>0));
    maxscore = 0.81*maxsum;
    % repeat over the iteration weightings
    for dd = getDdlist(pegCount)
        % if the solver results is more than the maxscore or less than 3 moves long then stop
        if (size(moves,1) <= 3) || (score > maxscore)
            % correct moves due to board padding
            moves = moves - 4;
            return
        end
        % calculate moves and scores of moves with subfunction
        [newMoves,newScore] = subsol( ...
            ppBoard, ...
            dd,0, ...
            F,T,M, ...
            pegCount,  ...
            TT,MM,MV, ...
            moveid1,moveid2,moveid3);
        % if it is better, update the move list.
        if (newScore > score)
            score = newScore;
            moves = newMoves;
        end
    end
    % repeat with randomisation
k = 1;
    while k <=(min((pegCount*0.0078125)+1,3)*(score < maxsum*0.79))
        % calculate moves and scores of moves with nested function
        [newMoves,newScore] = subsol( ...
            ppBoard, ...
            1.0,1.16, ...
            F,T,M, ...
            pegCount, ...
            TT,MM,MV, ...
            moveid1,moveid2,moveid3);
        % If it is better, update the move list.
        if (newScore > score)
            score = newScore;
            moves = newMoves;
        end
k = k+1;
    end

    % correct moves due to board padding
    moves = moves - 4;
% end
% check if the # pegs or fill ratio is less than set values
if (pegCount < 272) && (fill < .96)*(score < maxsum*0.775)
    % run the initial solver routine
    [newMoves,newScore] = solveri(board,rows,cols);
        if (newScore > score)
            score = newScore;
            moves = newMoves;
        end
end

end   % close function solver

%======================================================================
function ddlist = getDdlist(pegCount)

% create a vector of 4 random values between -1 and 1
RX = 2*(rand(4,1)-0.5);

switch ceil(pegCount/102.5)
    case 1
        ddlist = [1+0.1*RX(1) 0.05];
    case 2
        ddlist = [6.8 5 2.1 1+0.1*RX(2) 0.6+0.1*RX(2) 0.45];
        % burn 750 random numbers from the sequence
        %rand(750,1);
    case 3
        ddlist = [0.05 2.1 1+0.1*RX(3) 0.6+0.1*RX(3) 0.4+0.1*RX(3) 0.254];
    case 5
        ddlist = [0.05 2.1 0.6+0.1*RX(4) 0.18];
    otherwise
        ddlist = [0.05 2.1 1+0.1*RX(4) 0.592];
end

% if (pegCount > 400 && pegCount < 560)
%     % add an element to the iteration weights list
%     ddlist(end+1) = 0.18;
% end
end

%======================================================================
function [moveid1,moveid2,moveid3] = createMoves(M,F,T)

ni = max([max(M) max(F) max(T)]); % find the index of the lower right most possible move spots

% create three copies of a vector long enough to contain all possible move
% position indexes
nmove1 = zeros(ni,1);
nmove2 = nmove1;
nmove3 = nmove1;

% create three copies of a matrix long enough to contain all possible moves
moveid1 = zeros(ni,4);
moveid2 = moveid1;
moveid3 = moveid1;

for k = 1:numel(F) % repeat for the number of starting positions
    nmove1(F(k)) = nmove1(F(k))+1; %populate the 1st move position vector with the # of times that source spot is in the possible moves
    moveid1(F(k),nmove1(F(k))) = k; % populate the 1st move list vector with the index value of the corresponding source spots in each col
    % Note: if the 10th position on the board is a peg that could make 3
    % possible moves (i.e. up, down, right), that nmove1(10)=3 and
    % nmoveid1(10,:) = [x y z 0] where x,y,x are the index values in
    % vector F where 10 appears

    % Repeat the above for the spots that could be jumped
    nmove2(M(k)) = nmove2(M(k))+1;
    moveid2(M(k),nmove2(M(k))) = k;

    % Repeat the above for the destination spots
    nmove3(T(k)) = nmove3(T(k))+1;
    moveid3(T(k),nmove3(T(k))) = k;
end
end

%======================================================================
function [moves,last_score] = solveri(board,rows,cols)

% create a new board with 2 extra rows / cols of offlimits all the way
% around the board
pBoard = -ones(rows,cols);
pBoard(3:end-2,3:end-2) = board;

% allocate buffers
nNonHoles = nnz(pBoard);
moves = zeros(nNonHoles,4); 
cellbuf = zeros(nNonHoles*4,1);
valbuf = cellbuf;
movebuf = cellbuf;
hopbuf = cellbuf;
hop_list = cellbuf;

% initialize various variables
dead_weight = 0.1 * mean(board(board>0));
count = 0;
last_move = 0;
score = 0;
last_pos = 0;
last_score = 0;
depth = 10;
hop_max = 0;
hop_cnt = 0;

% calculate all possible moves
[lJumpers,lValues,lLandings] = CalculateMoves(pBoard);

while true
    % find highest value moves

    % if no moves returned, stop
    if isempty(lJumpers)
        break
    end

    % calculate the max consecutive hops
    FindHops(pBoard,lJumpers,lLandings,lValues);

    % check if any moves have multiple hops
    if (hop_max ~= 0) && (hop_cnt > 2)
        for zh = 1:hop_cnt-1
            lJumpers = [lJumpers;hop_list(zh)]; % update move list with number of hops
            lLandings = [lLandings;hop_list(zh+1)];  % update move list with number of hops
            lValues = [lValues;hop_max]; % update value list with value of hops
            DoMove(numel(lJumpers)); % do the actual hop moves
        end
    else
        % find moves that create hops
        [hop_values,pos] = sort(lValues,'descend'); % find best scoring hops
        lValues = hop_values; % update value list
        lJumpers = lJumpers(pos); % eliminate all nonhop moves from list
        lLandings = lLandings(pos); % eliminate all nonhop moves from list
        for zh = 1:min(depth,numel(lJumpers))
            [newB,newC,newM,newV] = ...
                ProcessMove(pBoard,zh,lJumpers,lLandings,lValues);
            FindHops(newB,newC,newM,newV); % find possible hops
            hop_values(zh) = hop_values(zh) + hop_max; % update value list with best hop
        end
        [max_val,pos] = max(hop_values); % find the best hop move
        DoMove(pos) % do the best hop move
    end

end

% truncate the move list to the best moves
moves(last_pos+1:end,:) = [];

% nested functions follow
    function DoMove(pos)
        max_cell = lJumpers(pos); %extract the move to do from the move list
        max_move = lLandings(pos); %extract the move to do from the move list
        count = count+1; % increment the move count
        moves(count,:) = [mod(max_cell-2,rows),ceil(max_cell/rows)-2,mod(max_move-2,rows),ceil(max_move/rows)-2]; % update the move list with the move

        brem = (max_cell+max_move)/2; % calculate the move score
        score = score + pBoard(brem); % update the score total
        if (max_cell ~= last_move) % check if it was a hop
            score = score - pBoard(max_cell); % if it wasn't a hop, subtract the jumping peg
        end
        if (score > last_score) % check if the score improves
            last_pos = count; % update the best move list
            last_score = score; % update the best score
        end;

        [pBoard,lJumpers,lLandings,lValues] = ProcessMove(pBoard,pos,lJumpers,lLandings,lValues); % check the move
        last_move = max_move; % find the position of the best move
    end

    function FindHops(pBoard,lJumpers,lLandings,lValues)
      hop_max = 0;

      if ~isempty(lJumpers)
	dst=lLandings(1:numel(lJumpers));

	tmp=(~pBoard(dst+2)&pBoard(dst+1));
	tmp=(~pBoard(dst-2)&pBoard(dst-1))|tmp;
	tmp=(~pBoard(dst-2*rows)&pBoard(dst-rows))|tmp;
	tmp=(~pBoard(dst+2*rows)&pBoard(dst+rows))|tmp;

	idx=find(~tmp); 
	if ~isempty(idx)
	  tmp2=lValues(idx); [hop_max,tmp2]=max(tmp2); tmp2=idx(tmp2);
	  hop_cnt=2; hop_list(1)=lJumpers(tmp2); hop_list(2)=lLandings(tmp2);
	end;

	idx=find(tmp)';
	for ii=idx
	  hopbuf(1)=lJumpers(ii);
	  FindHopTree(pBoard,lJumpers(ii),lLandings(ii),lValues(ii),2);
	end;
      end;
    end

    function FindHopTree(pBoard,src,dst,hop_value,count)

      % Update the board position

      pBoard(dst) = pBoard(src);
      pBoard((src+dst)/2) = 0;
      pBoard(src) = 0;

      % save hop
      hopbuf(count) = dst;

      % jump down
      if ~pBoard(dst+2) && pBoard(dst+1)>0
        FindHopTree(pBoard,dst,dst+2,hop_value+pBoard(dst+1),count+1);
      end

      % jump up
      if ~pBoard(dst-2) && pBoard(dst-1)>0
        FindHopTree(pBoard,dst,dst-2,hop_value+pBoard(dst-1),count+1);
      end

      % jump right
      if ~pBoard(dst+2*rows) && pBoard(dst+rows)>0
        FindHopTree(pBoard,dst,dst+2*rows,hop_value+pBoard(dst+rows),count+1);
      end

      % jump left
      if ~pBoard(dst-2*rows) && pBoard(dst-rows)>0
        FindHopTree(pBoard,dst,dst-2*rows,hop_value+pBoard(dst-rows),count+1);
      end

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

    end

    function n = CalculateBall(pBoard,src,dst,n)
        POP = pBoard((src+dst)*0.5); % extract the jumped position peg
        if POP>0 && ~pBoard(dst) && pBoard(src)>0 % check if source is peg, dest is hole, and jumped is peg
            n = n+1; % update index
            if sum(pBoard([dst+1 dst-1 dst+rows dst-rows])>0) == 1 % check to see if there is only 1 more peg to jump next
                valbuf(n) = POP-pBoard(src)-dead_weight; % if so, add weighted score to buffer
            else
                valbuf(n) = POP-pBoard(src); % if not, add full score
            end
            cellbuf(n) = src; % update move buffers
            movebuf(n) = dst;
        end
    end

    function n = CalculateHole(pBoard,dst,src,n)
        pop = (src+dst)/2; % extract the jumped position index
        if pBoard(pop)>0 && pBoard(src)>0 %check to make sure source and jumped position are pegs
            n = n+1; % update index
            if sum(pBoard([dst+1 dst-1 dst+rows dst-rows])>0) == 1 % check to see if there is only 1 more peg to jump next
                valbuf(n) = pBoard(pop)-pBoard(src)-dead_weight; % if so, add weighted score to buffer
            else
                valbuf(n) = pBoard(pop)-pBoard(src); % if not, add full score
            end
            cellbuf(n) = src; % update move buffers
            movebuf(n) = dst;
        end
    end

    function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(pBoard)
        zb = find(pBoard>0); %find indexes of all pegs on pBoard
        zz = find(~pBoard); % find indexes of all holes on pBoard
        n = 0;
        if numel(zz)<numel(zb) % if more holes than pegs
            for zi = 1:numel(zz) % repeat for each hole position
                i = zz(zi);
                %check for holes in all 4 possible destination spots
                %away from current hole
                n = CalculateHole(pBoard,i,i-2,n);
                n = CalculateHole(pBoard,i,i+2,n);
                n = CalculateHole(pBoard,i,i-rows*2,n);
                n = CalculateHole(pBoard,i,i+rows*2,n);
            end
        else
            for zi = 1:numel(zb) % repeat for each peg position
                i = zb(zi);
                %check for pegs in all 4 possible destination spots
                %away from current peg
                n = CalculateBall(pBoard,i,i-2,n);
                n = CalculateBall(pBoard,i,i+2,n);
                n = CalculateBall(pBoard,i,i-rows*2,n);
                n = CalculateBall(pBoard,i,i+rows*2,n);
            end
        end

        %update buffers
        new_cell_list = cellbuf(1:n);
        new_value_list = valbuf(1:n);
        new_move_list = movebuf(1:n);
    end

    function [pBoard,lJumpers,lLandings,lValues] = ProcessMove(pBoard,pos,lJumpers,lLandings,lValues)
        src = lJumpers(pos); %extract the source position
        dst = lLandings(pos); % extract the destination position
        pop = (src+dst)/2; % calculate the jumped position
        
        % update the pBoard
        pBoard(dst) = pBoard(src); % copy the source peg to destination spot
        pBoard(pop) = 0; % zero out the jumped spot
        pBoard(src) = 0; % zero out the source spot

        % check if a horizontal or vertical jump
        u = src-pop;
        if (abs(u) == 1)
            v = rows;
        else
            v = 1;
        end

        % eliminate the moves from move list that involve these
        % coordinates
        lLandings(logical(lLandings == dst)) = 0;
        lLandings(logical(lJumpers == src)) = 0;
        lLandings(logical(lJumpers == pop)) = 0;

        % eliminate moves that are 1 peg away from source
        rem_src = find(lJumpers == src-v);
        lLandings(rem_src(lLandings(rem_src) == src+v)) = 0;
        rem_src = find(lJumpers == src+v);
        lLandings(rem_src(lLandings(rem_src) == src-v)) = 0;
        rem_src = find(lJumpers == src-v-u);
        lLandings(rem_src(lLandings(rem_src) == src+v-u)) = 0;
        rem_src = find(lJumpers == src+v-u);
        lLandings(rem_src(lLandings(rem_src) == src-v-u)) = 0;

        % sort remaining moves and update other lists with the indexes
        [lLandings,rem_dst] = sort(lLandings,'descend');
        lJumpers = lJumpers(rem_dst);
        lValues = lValues(rem_dst);
        ncnt = find(~lLandings,1,'first');

        % truncate lists at point where moves involve off limits areas
        lJumpers = lJumpers(1:ncnt-1);
        lValues = lValues(1:ncnt-1);
        lLandings = lLandings(1:ncnt-1);

        % check all the new possible moves based upon updated pBoard
        n = 0;
        n = CalculateBall(pBoard,src-3*u,src-u,n);
        n = CalculateBall(pBoard,src+2*v-u,src-u,n);
        n = CalculateBall(pBoard,src+2*v,src,n);
        n = CalculateBall(pBoard,src+2*u,src,n);
        n = CalculateBall(pBoard,src-2*v,src,n);
        n = CalculateBall(pBoard,src-2*v-u,src-u,n);
        n = CalculateBall(pBoard,dst,dst-2*u,n);
        n = CalculateBall(pBoard,dst,dst-2*v,n);
        n = CalculateBall(pBoard,dst,dst+2*v,n);
        clf = src-v-2*u;
        crt = src+v-2*u;
        if ~pBoard(clf)
            n = CalculateBall(pBoard,crt,clf,n);
        end
        if ~pBoard(crt)
            n = CalculateBall(pBoard,clf,crt,n);
        end

        % if updated moves exist than update moves list
        if (n > 0)
            if (ncnt > 1)
                lJumpers = [lJumpers; cellbuf(1:n)];
                lLandings = [lLandings; movebuf(1:n)];
                lValues = [lValues; valbuf(1:n)];
            else
                lJumpers = cellbuf(1:n);
                lValues = valbuf(1:n);
                lLandings = movebuf(1:n);
            end
        end
    end

end

%======================================================================
function [moves,v] = subsol( ...
    board, ...
    d, ...
    rfac, ...
    F,T,M, ...
    pegCount, ...
    TT,MM,MV, ...
    moveid1,moveid2,moveid3)

rrr = rfac*rand(5000,1); % create a vector of 5000 random values
moves = zeros(pegCount-1,4); % preallocate maximum possible move list based on number of pegs
v0 = zeros(pegCount-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
Bmax = max(board, 0); % create board with offlimits as holes

% search for moves where source is peg, destination is hole and jumped spot is peg
validMoves = (Bpos(F) & Bzero(T) & Bpos(M));
% extract indexes of valid moves
h = find(validMoves);

C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
if d
    CV = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
else
    CV = 0;
end
% add jumped peg to 2nd jump and find best 2 move jump
[v,k] = max( (1+rrr(1:length(C0))).*(C0+CV*d) );
v0(1) = C0(k); % extract score of best 1st jump score
k = h(k);  % extract index of best 2 move jump
moves(1,:) = MV(k,:); % add best move (1st jump) to movelist
T0 = T(k); % extract 1st jump destination spot
F0 = F(k); % extract source spot
M0 = M(k); % calculate jumped spot
t = 2; % increment move count

% Update board.
Bmax(T0) = board(F0); % copy the jumping peg value
Bmax(F0) = 0; % zero out the jumping spot peg
Bmax(M0) = 0; % zero out the jumped spot peg
board(T0) = board(F0); % update destination spot with source spot peg
Bzero(T0) = false; % set the destination spot peg
Bpos(T0) = true; % set the destination spot peg
board(F0) = 0; % zero out source spot peg
Bzero(F0) = true; % create updated inverse board
Bpos(F0) = false; % zero out the source spot peg
board(M0)=0; % zero out jumped spot peg
Bpos(M0) = false;  % zero out the jumped spot peg
Bzero(M0) = true; % create updated inverse board

% assemble list of moves affected by the current move
FF=[F0 M0 T0];
originatingMoves = moveid1(FF,:);
originatingMoves = originatingMoves(originatingMoves > 0);
jumpedMoves = moveid2(FF,:);
jumpedMoves = jumpedMoves(jumpedMoves > 0);
terminatingMoves = moveid3(FF,:);
terminatingMoves = terminatingMoves(terminatingMoves > 0);
allMoves = [originatingMoves; jumpedMoves; terminatingMoves];
% search for valid moves in new board (original method)
validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves));

% extract indexes of valid moves
h = find(validMoves);
while ~isempty(h)
    if (numel(h) > 1)
        c = find(F(h) == T0); % find indexes of jumps with source peg that is same as last one moved             
        if ~isempty(c) % if any current 2 jump moves contain the last peg
            h = h(c); % extract the jump index
            C0 = board(M(h)); % seed possible 2nd jumps board with jumped peg value for all jumps the match last jump end
        else
            C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
        end
        
        if d
            CV = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
        else
            CV = 0;
        end

        % add jumped peg to 2nd jump and find best 2 move jump
        [v,k] = max( (1+rrr(1:length(C0))).*(C0+CV*d) );
        v0(t) = C0(k); % extract score of best 1st jump score
        k = h(k);  % extract index of best 2 move jump
    else
        k = h(1); % extract the move position
        v0(t) = board(M(k))-board(F(k)); % calculate the jump score
    end
    moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
    T0 = T(k); % extract 1st jump destination spot
    F0 = F(k); % extract source spot
    M0 = M(k); % calculate jumped spot
    t = t+1; % increment move count

    % Update board.
    Bmax(T0) = board(F0); % copy the jumping peg value
    Bmax(F0) = 0; % zero out the jumping spot peg
    Bmax(M0) = 0; % zero out the jumped spot peg
    board(T0) = board(F0); % update destination spot with source spot peg
    Bzero(T0) = false; % set the destination spot peg
    Bpos(T0) = true; % set the destination spot peg
    board(F0) = 0; % zero out source spot peg
    Bzero(F0) = true; % create updated inverse board
    Bpos(F0) = false; % zero out the source spot peg
    board(M0)=0; % zero out jumped spot peg
    Bpos(M0) = false;  % zero out the jumped spot peg
    Bzero(M0) = true; % create updated inverse board

    % assemble list of moves affected by the current move
    FF=[F0 M0 T0];
    originatingMoves = moveid1(FF,:);
    originatingMoves = originatingMoves(originatingMoves > 0);
    jumpedMoves = moveid2(FF,:);
    jumpedMoves = jumpedMoves(jumpedMoves > 0);
    terminatingMoves = moveid3(FF,:);
    terminatingMoves = terminatingMoves(terminatingMoves > 0);
    allMoves = [originatingMoves; jumpedMoves; terminatingMoves];
    % search for valid moves in new board (original method)
    validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves));

    % extract indexes of valid moves
    h = find(validMoves);
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

%======================================================================
function [moves,v] = subsoltweak( ...
    board, ...
    F,T,M, ...
    pegCount, ...
    TT,MM,MV,MVV, ...
    moveid1,moveid2,moveid3)

moves = zeros(pegCount-1,4); % preallocate maximum possible move list based on number of pegs
v0 = zeros(pegCount-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
Bmax = max(board, 0); % create board with offlimits as holes

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
C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
[CV,kc] = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
[v,k] = max(C0+CV); % add jumped peg to 2nd jump and find best 2 move jump
v0(1) = C0(k); % extract score of best 1st jump score
k = h(k);  % extract index of best 2 move jump
moves(1,:) = MV(k,:); % add best move (1st jump) to movelist
F0 = F(k); % extract source spot
t = 2; % increment move count
T0=T(k); % extract 1st jump destination spot
FF=[F0 M(k) T0];
M0=M(k);
Bmax(T0)=board(F0);Bmax(F0)=0;Bmax(M0)=0;
board(T0) = board(F0); % update destination spot with source spot peg
Bzero(T0) = false; % set the destination spot peg
Bpos(T0) = true; % set the destination spot peg
board(F0) = 0; % zero out source spot peg
Bzero(F0) = true; % create updated inverse board
Bpos(F0) = false; % zero out the source spot peg
board(M0) = 0; % zero out jumped spot peg
Bpos(M0) = false; % zero out the jumped spot peg
Bzero(M0) = true; % create updated inverse board

% assemble list of moves affected by the current move
originatingMoves = moveid1(FF,:);
originatingMoves = originatingMoves(originatingMoves>0);  % moves originating at spots involved in last move
jumpedMoves = moveid2(FF,:);
jumpedMoves = jumpedMoves(jumpedMoves>0);  % moves jumping over spots involved in last move
terminatingMoves = moveid3(FF,:);
terminatingMoves = terminatingMoves(terminatingMoves>0);  % moves terminating at spots involved in last move
allMoves = [originatingMoves; jumpedMoves; terminatingMoves]; % combine the moves into 1 list
hs(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves)); % search for valid moves in new board (original method)

% extract indexes of valid moves
h = find(hs);
while ~isempty(h)
    c = find(F(h) == T0); % find indexes of jumps with source peg that is same as last one moved
    if ~isempty(c) % if any current 2 jump moves contain the last peg
        h = h(c); % extract the jump index
        C0 = board(M(h)); % seed possible 2nd jumps board with jumped peg value for all jumps the match last jump end
    else
        C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
    end

    [CV,kc] = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
    [v,k] = max(C0+CV); % add jumped peg to 2nd jump and find best 2 move jump
    v0(t) = C0(k); % extract score of best 1st jump score
    cv=CV(k);kc=kc(k);
    k = h(k);  % extract index of best 2 move jump

    moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
    F0 = F(k); % extract source spot
    t = t+1; % increment move count
    if ~cv
        T0=T(k); % extract 1st jump destination spot
        FF=[F0 M(k) T0];
    else
        T0=TT(k,kc);
        M0=MM(k,kc);
        moves(t,:)=MVV{kc}(k,:);
        FF=[F0 M(k) M0 T0];
        v0(t)=cv;
        board(M0)=0;Bzero(M0)=true;Bpos(M0)=false;Bmax(M0)=0;
        t=t+1;
    end
    M0=M(k);
    Bmax(T0)=board(F0);Bmax(F0)=0;Bmax(M0)=0;
    board(T0) = board(F0); % update destination spot with source spot peg
    Bzero(T0) = false; % set the destination spot peg
    Bpos(T0) = true; % set the destination spot peg
    board(F0) = 0; % zero out source spot peg
    Bzero(F0) = true; % create updated inverse board
    Bpos(F0) = false; % zero out the source spot peg
    board(M0) = 0; % zero out jumped spot peg
    Bpos(M0) = false; % zero out the jumped spot peg
    Bzero(M0) = true; % create updated inverse board

    % assemble list of moves affected by the current move
    originatingMoves = moveid1(FF,:);
    originatingMoves = originatingMoves(originatingMoves>0);  % moves originating at spots involved in last move
    jumpedMoves = moveid2(FF,:);
    jumpedMoves = jumpedMoves(jumpedMoves>0);  % moves jumping over spots involved in last move
    terminatingMoves = moveid3(FF,:);
    terminatingMoves = terminatingMoves(terminatingMoves>0);  % moves terminating at spots involved in last move
    allMoves = [originatingMoves; jumpedMoves; terminatingMoves]; % combine the moves into 1 list
    hs(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves)); % search for valid moves in new board (original method)

    % extract indexes of valid moves
    h = find(hs);
end

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

end