Winner Yi Cao (Buy a ticket)

2007-05-16 12:00:00 UTC

# Lanny 7''

Status: Passed
Results: 39586.86 (cyc: 9)
CPU Time: 49.3831
Score: 3982.31
Submitted at: 2007-05-13 22:52:40 UTC
Scored at: 2007-05-13 22:54:33 UTC

Current Rank: 647th
Based on: Lanny 7' (diff)
Basis for: Lanny 7''' (diff)

Code
```function moves = solver(board)
rand('state',0);
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< 257)&&(fill < 0.81)
ntb = -1;
ntb = ntb(ones(m+4,n+4));
ntb(3:end-2,3:end-2)= board;
rows=m+4;
count=0;
moves=solveri(ntb);
else
[i,j]=find(ones(m,n)); % create an index listing of board elements

% pad board with -1 to avoid check for offlimits
mm = m+8;
nn = n+8;
board1 = -1;
board1 = board1(ones(mm, nn));
board1(5:m+4,5:n+4) = board;
i = i + 4;
j = j + 4;

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]

h=board1(F)>=0&board1(M)>=0&board1(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

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

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

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.1 0.05];
master_list(1).list=[    1+0.1*RX(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(2).list=[ 6.8 5 2.1    1+0.1*RX(2)    0.7692  0.4762  ];
master_list(3).list=[   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;
if shh==2;
rand(3000,1);rand(3000,1);rand(3000,1);rand(3000,1);rand(3000,1);
end
[mv(1).mv,v1]=subsoltweak(board1, F,T,M, COUNT, MV, moveid1,moveid2,moveid3);
DJY=COUNT > 425 & COUNT < 550;
if DJY
ddlist = [ddlist 0.18];
end
maxscore = 0.81*sum(board(board>0));
runs = min(ceil(COUNT/150),3);
for dd = ddlist % repeat over the iteration weightings
DJX=size(mv(1).mv,1)<=2 | v1>maxscore;
if DJX
runs=0;
break
end
[mv(2).mv,v2] = subsol(board1,dd,0, F,T,M, COUNT,  M1,M2,M3,MV, moveid1,moveid2,moveid3, T1,T2,T3 ); %  calculate moves and scores of moves with nested function
[v1,i]=max([v1 v2]); %find best
mv(1).mv=mv(i).mv;
end
for k = 1:runs   % repeat with randomisation
[mv(2).mv,v2] = subsol(board1,1.0,1.15, F,T,M, COUNT,  M1,M2,M3,MV, moveid1,moveid2,moveid3, T1,T2,T3); %  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;

moves = moves - 4; % correct moves due to board padding
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
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
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,1,'first');
% 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
end   % close function solver

function [moves,v]=subsol(board,d,rfac, F,T,M, COUNT,  M1,M2,M3,MV, moveid1,moveid2,moveid3, T1,T2,T3)
rrr = rfac*rand(5000,1);
moves=zeros(COUNT-1,4); % preallocate maximum possible move list based on number of pegs
v0=zeros(COUNT-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);
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)
if numel(h) > 1
if t>1
c=find(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
h = h(c);
C0=board(M(h)); % seed possible 2nd jumps B 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 =         Bmax(M1(h)) .* Bzero(T1(h));
CV = max(CV, Bmax(M2(h)) .* Bzero(T2(h)));
CV = max(CV, Bmax(M3(h)) .* Bzero(T3(h)));

[v,k]=max( (1+rrr(1:length(C0))).*(C0+CV*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=h(k);  % extract index of best 2 move jump
else
k = h(1);
v0(t)=board(M(k))-board(F(k));
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

Bmax(T0)=board(F0);
Bmax(F0)=0;
Bmax(M0)=0;
board(T0)=board(F0); % update destination spot with source spot peg
Bzero(T0) = false;
Bpos(T0) = true;
board(F0)=0; % zero out source spot peg
Bzero(F0) = true; % create updated inverse board
Bpos(F0) = false;
board(M0)=0; % zero out jumped spot peg
Bpos(M0) = false;
Bzero(M0) = true; % create updated inverse board
% assemble list of moves affected by the current move
mF = moveid1([F0 M0 T0],:); mF=mF(mF>0);  % moves originating at spots involved in last move
mM = moveid2([F0 M0 T0],:); mM=mM(mM>0);  % moves jumping over spots involved in last move
mT = moveid3([F0 M0 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, F,T,M, COUNT,  MV, moveid1,moveid2,moveid3)
moves=zeros(COUNT-1,4); % preallocate maximum possible move list based on number of pegs
v0=zeros(COUNT-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)
if t>1
c=find(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
h = h(c);
C0=board(M(h)); % seed possible 2nd jumps B 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

[v,k]=max(C0); % add jumped peg to 2nd jump and find best 2 move jump
v0(t)=C0(k); % extract score of best 1st jump score
k=h(k);  % extract index of best 2 move jump

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);
t=t+1; % increment move count
board(T0)=board(F0); % update destination spot with source spot peg
Bzero(T0) = false;
Bpos(T0) = true;
board(F0)=0; % zero out source spot peg
Bzero(F0) = true; % create updated inverse board
Bpos(F0) = false;
board(M0)=0; % zero out jumped spot peg
Bpos(M0) = false;
Bzero(M0) = true; % create updated inverse board
% assemble list of moves affected by the current move
mF = moveid1([F0 M0 T0],:); mF=mF(mF>0);  % moves originating at spots involved in last move
mM = moveid2([F0 M0 T0],:); mM=mM(mM>0);  % moves jumping over spots involved in last move
mT = moveid3([F0 M0 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

```