function [moves,score] = collaborationSover(board)
rand( 'state', 0 );
rand( 57, 1 );
[m,n] = size( board );
pegCount = sum( board( : )>0 );
rows = m + 4;
rv = 5:rows;
cols = n + 4;
cv = 5:cols;
fill = (pegCount - nnz( board<0 ))/(m*n);
i = repmat( rv', [ n, 1 ] );
j = reshape( repmat( cv, [ m, 1 ] ), [ m*n, 1 ] );
mm = m + 8;
nn = n + 8;
ppBoard = zeros( mm, nn );
ppBoard( : ) = -1;
ppBoard( rv, cv ) = board;
I = [ i; i; i; i ];
J = [ j; j; j; j ];
K = [ i; i; i - 2; i + 2 ];
L = [ j - 2; j + 2; j; j ];
K1 = [ i; i; i - 4; i + 4 ];
L1 = [ j - 4; j + 4; j; j ];
K2 = [ i - 2; i + 2; i - 2; i + 2 ];
L2 = [ j - 2; j + 2; j + 2; j - 2 ];
K3 = [ i + 2; i - 2; i - 2; i + 2 ];
L3 = [ j - 2; j + 2; j - 2; j + 2 ];
F = I + (J - 1)*mm;
T = K + (L - 1)*mm;
M = (F + T)*0.5;
bogusMoves = (ppBoard( F )<0) | (ppBoard( M )<0) | (ppBoard( T )<0);
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 );
T1 = K1 + (L1 - 1)*mm;
T2 = K2 + (L2 - 1)*mm;
T3 = K3 + (L3 - 1)*mm;
TT = [ T1, T2, T3 ];
M1 = (T + T1)*0.5;
M2 = (T + T2)*0.5;
M3 = (T + T3)*0.5;
MM = [ M1, M2, M3 ];
MV = [ I, J, K, L ];
MV1 = [ K, L, K1, L1 ];
MV2 = [ K, L, K2, L2 ];
MV3 = [ K, L, K3, L3 ];
MVV = { MV1, MV2, MV3 };
[moves,score] = subsoltweak( ppBoard, F, T, M, pegCount, TT, MM, MV, MVV, moveid1, moveid2, moveid3 );
maxsum = sum( board( board>0 ) );
maxscore = 0.81*maxsum;
for dd = getDdlist( pegCount )
if (size( moves, 1 )<=3) || (score>maxscore)
moves = moves - 4;
return
end
[newMoves,newScore] = subsol( ppBoard, dd, 0, F, T, M, pegCount, TT, MM, MV, moveid1, moveid2, moveid3 );
if (newScore>score)
score = newScore;
moves = newMoves;
end
end
k = 1;
while k<=(min( (pegCount*0.0078125) + 1, 3 )*(score<maxsum*0.79))
[newMoves,newScore] = subsol( ppBoard, 1.0, 1.16, F, T, M, pegCount, TT, MM, MV, moveid1, moveid2, moveid3 );
if (newScore>score)
score = newScore;
moves = newMoves;
end
k = k + 1;
end
moves = moves - 4;
if (pegCount<272) && (fill<.96)*(score<maxsum*0.775)
[newMoves,newScore] = solveri( board, rows, cols );
if (newScore>score)
score = newScore;
moves = newMoves;
end
end
end
function ddlist = getDdlist(pegCount)
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 ];
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
end
function [moveid1,moveid2,moveid3] = createMoves(M,F,T)
ni = max( F );
nmove1 = zeros( ni, 1 );
nmove2 = nmove1;
nmove3 = nmove1;
moveid1 = zeros( ni, 4 );
moveid2 = moveid1;
moveid3 = moveid1;
for k = 1:numel( 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
end
function [moves,last_score] = solveri(board,rows,cols)
pBoard = zeros( rows, cols );
pBoard( : ) = -1;
pBoard( 3:end - 2, 3:end - 2 ) = board;
nNonHoles = nnz( pBoard );
moves = zeros( nNonHoles, 4 );
cellbuf = zeros( nNonHoles*4, 1 );
valbuf = cellbuf;
movebuf = cellbuf;
hopbuf = cellbuf;
hop_list = cellbuf;
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;
[lJumpers,lValues,lLandings] = CalculateMoves( pBoard );
while true
if isempty( lJumpers )
break
end
FindHops( pBoard, lJumpers, lLandings, lValues );
if (hop_max~=0) && (hop_cnt>2)
for zh = 1:hop_cnt - 1
lJumpers = [ lJumpers; hop_list( zh ) ];
lLandings = [ lLandings; hop_list( zh + 1 ) ];
lValues = [ lValues; hop_max ];
DoMove( numel( lJumpers ) );
end
else
[hop_values,pos] = sort( lValues, 'descend' );
lValues = hop_values;
lJumpers = lJumpers( pos );
lLandings = lLandings( pos );
for zh = 1:min( depth, numel( lJumpers ) )
[newB,newC,newM,newV] = ProcessMove( pBoard, zh, lJumpers, lLandings, lValues );
FindHops( newB, newC, newM, newV );
hop_values( zh ) = hop_values( zh ) + hop_max;
end
[max_val,pos] = max( hop_values );
DoMove( pos )
end
end
moves( last_pos + 1:end, : ) = [ ];
function DoMove(pos)
max_cell = lJumpers( pos );
max_move = lLandings( 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)*0.5;
score = score + pBoard( brem );
if (max_cell~=last_move)
score = score - pBoard( max_cell );
end
if (score>last_score)
last_pos = count;
last_score = score;
end
[pBoard,lJumpers,lLandings,lValues] = ProcessMove( pBoard, pos, lJumpers, lLandings, lValues );
last_move = max_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)
pBoard( dst ) = pBoard( src );
pBoard( (src + dst)*0.5 ) = 0;
pBoard( src ) = 0;
hopbuf( count ) = dst;
if ~pBoard( dst + 2 ) && pBoard( dst + 1 )>0
FindHopTree( pBoard, dst, dst + 2, hop_value + pBoard( dst + 1 ), count + 1 );
end
if ~pBoard( dst - 2 ) && pBoard( dst - 1 )>0
FindHopTree( pBoard, dst, dst - 2, hop_value + pBoard( dst - 1 ), count + 1 );
end
if ~pBoard( dst + 2*rows ) && pBoard( dst + rows )>0
FindHopTree( pBoard, dst, dst + 2*rows, hop_value + pBoard( dst + rows ), count + 1 );
end
if ~pBoard( dst - 2*rows ) && pBoard( dst - rows )>0
FindHopTree( pBoard, dst, dst - 2*rows, hop_value + pBoard( dst - rows ), count + 1 );
end
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 );
if POP>0 && ~pBoard( dst ) && pBoard( src )>0
n = n + 1;
if sum( pBoard( [ dst + 1, dst - 1, dst + rows, dst - rows ] )>0 )==1
valbuf( n ) = POP - pBoard( src ) - dead_weight;
else
valbuf( n ) = POP - pBoard( src );
end
cellbuf( n ) = src;
movebuf( n ) = dst;
end
end
function n = CalculateHole(pBoard,dst,src,n)
pop = (src + dst)*0.5;
if pBoard( pop )>0 && pBoard( src )>0
n = n + 1;
if sum( pBoard( [ dst + 1, dst - 1, dst + rows, dst - rows ] )>0 )==1
valbuf( n ) = pBoard( pop ) - pBoard( src ) - dead_weight;
else
valbuf( n ) = pBoard( pop ) - pBoard( src );
end
cellbuf( n ) = src;
movebuf( n ) = dst;
end
end
function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(pBoard)
zb = find( pBoard>0 );
zz = find( ~pBoard );
n = 0;
if numel( zz )<numel( zb )
for zi = 1:numel( zz )
i = zz( zi );
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 )
i = zb( zi );
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
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 );
dst = lLandings( pos );
pop = (src + dst)*0.5;
pBoard( dst ) = pBoard( src );
pBoard( pop ) = 0;
pBoard( src ) = 0;
u = src - pop;
if (abs( u )==1)
v = rows;
else
v = 1;
end
lLandings( logical( lLandings==dst ) ) = 0;
lLandings( logical( lJumpers==src ) ) = 0;
lLandings( logical( lJumpers==pop ) ) = 0;
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;
[lLandings,rem_dst] = sort( lLandings, 'descend' );
lJumpers = lJumpers( rem_dst );
lValues = lValues( rem_dst );
ncnt = find( ~lLandings, 1, 'first' );
lJumpers = lJumpers( 1:ncnt - 1 );
lValues = lValues( 1:ncnt - 1 );
lLandings = lLandings( 1:ncnt - 1 );
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 (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 );
moves = zeros( pegCount - 1, 4 );
v0 = zeros( pegCount - 1, 1 );
Bzero = ~board;
Bpos = board>0;
Bmax = max( board, 0 );
validMoves = (Bpos( F ) & Bzero( T ) & Bpos( M ));
h = find( validMoves );
C0 = board( M( h ) ) - board( F( h ) );
if d
CV = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [ ], 2 );
else
CV = 0;
end
[v,k] = max( (1 + rrr( 1:length( C0 ) )) .* (C0 + CV*d) );
v0( 1 ) = C0( k );
k = h( k );
moves( 1, : ) = MV( k, : );
T0 = T( k );
F0 = F( k );
M0 = M( k );
t = 2;
Bmax( T0 ) = board( F0 );
Bmax( F0 ) = 0;
Bmax( M0 ) = 0;
board( T0 ) = board( F0 );
Bzero( T0 ) = false;
Bpos( T0 ) = true;
board( F0 ) = 0;
Bzero( F0 ) = true;
Bpos( F0 ) = false;
board( M0 ) = 0;
Bpos( M0 ) = false;
Bzero( M0 ) = true;
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 ];
validMoves( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
h = find( validMoves );
while ~isempty( h )
if (numel( h )>1)
c = find( F( h )==T0 );
if ~isempty( c )
h = h( c );
C0 = board( M( h ) );
else
C0 = board( M( h ) ) - board( F( h ) );
end
if d
CV = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [ ], 2 );
else
CV = 0;
end
[v,k] = max( (1 + rrr( 1:length( C0 ) )) .* (C0 + CV*d) );
v0( t ) = C0( k );
k = h( k );
else
k = h( 1 );
v0( t ) = board( M( k ) ) - board( F( k ) );
end
moves( t, : ) = MV( k, : );
T0 = T( k );
F0 = F( k );
M0 = M( k );
t = t + 1;
Bmax( T0 ) = board( F0 );
Bmax( F0 ) = 0;
Bmax( M0 ) = 0;
board( T0 ) = board( F0 );
Bzero( T0 ) = false;
Bpos( T0 ) = true;
board( F0 ) = 0;
Bzero( F0 ) = true;
Bpos( F0 ) = false;
board( M0 ) = 0;
Bpos( M0 ) = false;
Bzero( M0 ) = true;
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 ];
validMoves( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
h = find( validMoves );
end
v0 = cumsum( v0 );
[v,t] = max( v0 );
moves = moves( 1:t, : );
end
function [moves,v] = subsoltweak(board,F,T,M,pegCount,TT,MM,MV,MVV,moveid1,moveid2,moveid3)
moves = zeros( pegCount - 1, 4 );
v0 = zeros( pegCount - 1, 1 );
Bzero = ~board;
Bpos = board>0;
Bmax = max( board, 0 );
hs = (Bpos( F ) & Bzero( T ) & Bpos( M ));
h = find( hs );
C0 = board( M( h ) ) - board( F( h ) );
[CV,kc] = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [ ], 2 );
[v,k] = max( C0 + CV );
v0( 1 ) = C0( k );
k = h( k );
moves( 1, : ) = MV( k, : );
F0 = F( k );
t = 2;
T0 = T( k );
FF = [ F0, M( k ), T0 ];
M0 = M( k );
Bmax( T0 ) = board( F0 );
Bmax( F0 ) = 0;
Bmax( M0 ) = 0;
board( T0 ) = board( F0 );
Bzero( T0 ) = false;
Bpos( T0 ) = true;
board( F0 ) = 0;
Bzero( F0 ) = true;
Bpos( F0 ) = false;
board( M0 ) = 0;
Bpos( M0 ) = false;
Bzero( M0 ) = true;
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 ];
hs( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
h = find( hs );
while ~isempty( h )
c = find( F( h )==T0 );
if ~isempty( c )
h = h( c );
C0 = board( M( h ) );
else
C0 = board( M( h ) ) - board( F( h ) );
end
[CV,kc] = max( Bmax( MM( h, : ) ) .* Bzero( TT( h, : ) ), [ ], 2 );
[v,k] = max( C0 + CV );
v0( t ) = C0( k );
cv = CV( k );
kc = kc( k );
k = h( k );
moves( t, : ) = MV( k, : );
F0 = F( k );
t = t + 1;
if ~cv
T0 = T( k );
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 );
Bzero( T0 ) = false;
Bpos( T0 ) = true;
board( F0 ) = 0;
Bzero( F0 ) = true;
Bpos( F0 ) = false;
board( M0 ) = 0;
Bpos( M0 ) = false;
Bzero( M0 ) = true;
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 ];
hs( allMoves ) = Bpos( F( allMoves ) ) & Bzero( T( allMoves ) ) & Bpos( M( allMoves ) );
h = find( hs );
end
vv0 = cumsum( v0 );
[v,t] = max( vv0 );
moves = moves( 1:t, : );
end
