function [moves] = collaborationSover(board)
% score: 3946.38
% results: 39266.8103
% time: 45.14
%
% 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
PARA1 = 136;
PARA2 = 3;
PARA11 = 1/PARA1;
% Set up the random number generator so it produces a favorable sequence.
rand('state',0);
rand(7,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
fill = (pegCount-nnz(board<0)) / (m*n);
i = rv'*ones(1,n);% create an index of all the new board row coordinates except for the 1st 4 rows
i = i(:);
cv_ = ones(m,1)*cv;
j = cv_(:);
% 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
goodMoves = (ppBoard(F) >= 0) & (ppBoard(M) >= 0) & (ppBoard(T) >= 0);
% remove moves that involve off limits areas
I = I(goodMoves);
J = J(goodMoves);
K = K(goodMoves);
L = L(goodMoves);
F = F(goodMoves);
T = T(goodMoves);
M = M(goodMoves);
K1 = K1(goodMoves);
K2 = K2(goodMoves);
K3 = K3(goodMoves);
L1 = L1(goodMoves);
L2 = L2(goodMoves);
L3 = L3(goodMoves);
[moveid1,moveid2,moveid3] = mycreateMoves(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;
% 128,3
% for k = 1:max(ceil(pegCount/128),3)
while k <=(max((pegCount*PARA11)+1,PARA2)*(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
% % calculate the peg to off limit areas ratio of board
% fill = (pegCount-nnz(board<0)) / (m*n);
% check if the # pegs or fill ratio is less than set values
% if (pegCount < 272) && (fill < .9)
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.4762];
% 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 [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
tboard = board(board>0);
dead_weight = 0.1 * sum(tboard,1)/size(tboard,1);
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
pd = pBoard(dst+1);
if ~pBoard(dst+2) && pd>0
FindHopTree(pBoard,dst,dst+2,hop_value+pd,count+1);
end
pd = pBoard(dst-1);
% jump up
if ~pBoard(dst-2) && pd>0
FindHopTree(pBoard,dst,dst-2,hop_value+pd,count+1);
end
pd = pBoard(dst+rows);
% jump right
if ~pBoard(dst+2*rows) && pd>0
FindHopTree(pBoard,dst,dst+2*rows,hop_value+pd,count+1);
end
pd = pBoard(dst-rows);
% jump left
if ~pBoard(dst-2*rows) && pd>0
FindHopTree(pBoard,dst,dst-2*rows,hop_value+pd,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,psrc,pdst,POP,n,src,dst)
% POP = pBoard((src+dst)*0.5); % extract the jumped position peg
% psrc = pBoard(src);
if POP>0 && ~pdst && psrc>0 % check if source is peg, dest is hole, and jumped is peg
n = n+1; % update index
% sum_1 = sum(pBoard([dst+1 dst-1 dst+rows dst-rows])>0); % check to see if there is only 1 more peg to jump next
if (pBoard(dst+1)>0) + (pBoard(dst-1)>0) + ...
(pBoard(dst+rows)>0) + (pBoard(dst-rows)>0) == 1
valbuf(n) = POP-psrc-dead_weight; % if so, add weighted score to buffer
else
valbuf(n) = POP-psrc; % 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
ppop = pBoard(pop);
psrc = pBoard(src);
if ppop>0 && psrc>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
if (pBoard(dst+1)>0) + (pBoard(dst-1)>0) + ...
(pBoard(dst+rows)>0) + (pBoard(dst-rows)>0) == 1
valbuf(n) = ppop-psrc-dead_weight; % if so, add weighted score to buffer
else
valbuf(n) = ppop-psrc; % 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
pi = pBoard(i);
pi1 = pBoard(i-2);
m1 = pBoard((i+i-2)*0.5);
pi2 = pBoard(i+2);
m2 = pBoard((i+(i+2))*0.5);
pi3 = pBoard(i-rows*2);
m3 = pBoard((i+(i-rows*2))*0.5);
pi4 = pBoard(i+rows*2);
m4 = pBoard((i+(i+rows*2))*0.5);
n = CalculateBall(pBoard,pi,pi1,m1,n,i,i-2);
n = CalculateBall(pBoard,pi,pi2,m2,n,i,i+2);
n = CalculateBall(pBoard,pi,pi3,m3,n,i,i-rows*2);
n = CalculateBall(pBoard,pi,pi4,m4,n,i,i+rows*2);
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)*0.5; % 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
keep1 = lLandings~=dst & lJumpers~=src & lJumpers~=pop;
lLandings = lLandings(keep1);
lJumpers = lJumpers(keep1);
lValues = lValues(keep1);
% eliminate moves that are 1 peg away from source
keep2 = ...
(lJumpers~=src-v | lLandings~=src+v) & ...
(lJumpers~=src+v | lLandings~=src-v) & ...
(lJumpers~=src-v-u | lLandings~=src+v-u) & ...
(lJumpers~=src+v-u | lLandings~=src-v-u); ...
lLandings = lLandings(keep2);
lJumpers = lJumpers(keep2);
lValues = lValues(keep2);
[lLandings inds] = sort(lLandings, 'descend');
lJumpers = lJumpers(inds);
lValues = lValues(inds);
% check all the new possible moves based upon updated pBoard
n = 0;
u2 = 2*u;
v2 = 2*v;
src_u = src-u;
src_v = src-v2;
s_3u = pBoard(src-3*u);
s_u = pBoard(src_u);
m1 = pBoard((src-3*u+src_u)*0.5);
sv2_u = pBoard(src_u+v2);
m2 = pBoard((src_u+v2+src_u)*0.5);
sv2 = pBoard(src+v2);
s = pBoard(src);
m3 = pBoard((src+v2+src)*0.5);
su2 = pBoard(src+u2);
m4 = pBoard((src+u2+src)*0.5);
sv = pBoard(src_v);
m5 = pBoard((src_v+src)*0.5);
s_v_u = pBoard(src_v-u);
m6 = pBoard((src_v-u+src_u)*0.5);
d = pBoard(dst);
d_u2 = pBoard(dst-u2);
m7 = pBoard((dst+dst-u2)*0.5);
d_v2 = pBoard(dst-v2);
m8 = pBoard((dst+dst-v2)*0.5);
dv2 = pBoard(dst+v2);
m9 = pBoard((dst+dst+v2)*0.5);
n = CalculateBall(pBoard,s_3u,s_u,m1,n,src-3*u,src_u);
n = CalculateBall(pBoard,sv2_u,s_u,m2,n,src_u+v2,src_u);
n = CalculateBall(pBoard,sv2,s,m3,n,src+v2,src);
n = CalculateBall(pBoard,su2,s,m4,n,src+u2,src);
n = CalculateBall(pBoard,sv,s,m5,n,src_v,src);
n = CalculateBall(pBoard,s_v_u,s_u,m6,n,src_v-u,src_u);
n = CalculateBall(pBoard,d,d_u2,m7,n,dst,dst-u2);
n = CalculateBall(pBoard,d,d_v2,m8,n,dst,dst-v2);
n = CalculateBall(pBoard,d,dv2,m9,n,dst,dst+v2);
% n = CalculateBall(pBoard,src-3*u,src_u,n);
% n = CalculateBall(pBoard,src+v2-u,src_u,n);
% n = CalculateBall(pBoard,src+v2,src,n);
% n = CalculateBall(pBoard,src+u2,src,n);
% n = CalculateBall(pBoard,src_v,src,n);
% n = CalculateBall(pBoard,src_v-u,src_u,n);
% n = CalculateBall(pBoard,dst,dst-u2,n);
% n = CalculateBall(pBoard,dst,dst-v2,n);
% n = CalculateBall(pBoard,dst,dst+v2,n);
crt = pBoard(src+v-u2);
clf = pBoard(src-v-u2);
mm = pBoard(src-u2);
if ~clf
n = CalculateBall(pBoard,crt,clf,mm,n,src+v-u2,src-v-u2);
end
if ~crt
n = CalculateBall(pBoard,clf,crt,mm,n,src-v-u2,src+v-u2);
end
% if updated moves exist than update moves list
if (n > 0)
ind = 1:n;
if (~isempty(lJumpers))
lJumpers = [lJumpers; cellbuf(ind)];
lLandings = [lLandings; movebuf(ind)];
lValues = [lValues; valbuf(ind)];
else
lJumpers = cellbuf(ind);
lValues = valbuf(ind);
lLandings = movebuf(ind);
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.
boardF0 = board(F0);
Bmax(T0) = boardF0; % 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) = boardF0; % 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)
Fh = F(h);
c = find(Fh == 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(Fh); % 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.
boardF0 = board(F0);
Bmax(T0) = boardF0; % 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) = boardF0; % 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
% t = 1; % init move list index
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
M0=M(k);
FF=[F0 M0 T0];
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)
Fh = F(h);
c = find(Fh==T0);
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(Fh); % 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
M0=M(k);
if ~cv
T0=T(k); % extract 1st jump destination spot
FF=[F0 M0 T0];
else
T0=TT(k,kc);
M00=MM(k,kc);
moves(t,:)=MVV{kc}(k,:);
FF=[F0 M0 M00 T0];
v0(t)=cv;
board(M00)=0;
Bzero(M00)=true;
Bpos(M00)=false;
Bmax(M00)=0;
t=t+1;
end
boardF0 = board(F0);
Bmax(T0)=boardF0;
Bmax(F0)=0;
Bmax(M0)=0;
board(T0) = boardF0; % 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
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 [moveid1,moveid2,moveid3] = mycreateMoves(M,F,T)
ni = max(T);
% create three copies of a vector long enough to contain all possible move
% position indexes
nmove1 = zeros(ni,1);
nmove2 = zeros(ni,1);
nmove3 = zeros(ni,1);
% create three copies of a matrix long enough to contain all possible moves
moveid1 = zeros(ni,4);
moveid2 = zeros(ni,4);
moveid3 = zeros(ni,4);
len = length(F);
d = F(2:end) - F(1:end-1);
i = find(d<0);
i1 = 1:i(1);
i2 = i(1)+1:i(2);
i3 = i(2)+1:i(3);
i4 = i(3)+1:len;
F1 = F(i1);
F2 = F(i2);
F3 = F(i3);
F4 = F(i4);
M1 = M(i1);
M2 = M(i2);
M3 = M(i3);
M4 = M(i4);
T1 = T(i1);
T2 = T(i2);
T3 = T(i3);
T4 = T(i4);
nmove1(F1) = nmove1(F1)+1;
moveid1(F1 + (nmove1(F1)-1)*ni) = i1;
nmove1(F2) = nmove1(F2)+1;
moveid1(F2 + (nmove1(F2)-1)*ni) = i2;
nmove1(F3) = nmove1(F3)+1;
moveid1(F3 + (nmove1(F3)-1)*ni) = i3;
nmove1(F4) = nmove1(F4)+1;
moveid1(F4 + (nmove1(F4)-1)*ni) = i4;
nmove2(M1) = nmove2(M1)+1;
moveid2(M1 + (nmove2(M1)-1)*ni) = i1;
nmove2(M2) = nmove2(M2)+1;
moveid2(M2 + (nmove2(M2)-1)*ni) = i2;
nmove2(M3) = nmove2(M3)+1;
moveid2(M3 + (nmove2(M3)-1)*ni) = i3;
nmove2(M4) = nmove2(M4)+1;
moveid2(M4 + (nmove2(M4)-1)*ni) = i4;
nmove3(T1) = nmove3(T1)+1;
moveid3(T1 + (nmove3(T1)-1)*ni) = i1;
nmove3(T2) = nmove3(T2)+1;
moveid3(T2 + (nmove3(T2)-1)*ni) = i2;
nmove3(T3) = nmove3(T3)+1;
moveid3(T3 + (nmove3(T3)-1)*ni) = i3;
nmove3(T4) = nmove3(T4)+1;
moveid3(T4 + (nmove3(T4)-1)*ni) = i4;
end
|
