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
%P=board(:)>0; % search for all pegs on board
N=sum(board(:)>0); % count number of pegs
MV = [I J K L]; % create first possible move list
RX = 2*(rand(4,1)-0.5);
master_list(1).list=[ 6.8 4 2.1 1+0.1*RX(1) 0.592 0.4762 0.254 0.1 0.05];
master_list(2).list=[ 6.8 5 2.1 1+0.1*RX(2) 0.7692 0.592 0.4762 0.254 0.1];
master_list(3).list=[ 4 2.1 1+0.1*RX(3) 0.7692 0.4762 0.254];
master_list(4).list=[ 2.1 1+0.1*RX(4) 0.592];
shh=min(ceil(COUNT/102.5), 4);
ddlist=master_list(shh).list;
[mv(1).mv,v1]=subsoltweak(board);
for dd = ddlist % repeat over the iteration weightings
[mv(2).mv,v2] = subsol(board,dd); % calculate moves and scores of moves with nested function
[v1,i]=max([v1 v2]); %find best
mv(1).mv=mv(i).mv;
end
moves=mv(1).mv;
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
function [moves,v]=subsoltweak(board)
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
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);
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); % 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
|
