Winner the cyclist (typ2)

Finish 2006-04-12 09:00:00 UTC

Cluster-based solver 6e.

by Markus Buehren

Status: Passed
Results: 85349
CPU Time: 63.5477
Score: 856.307
Submitted at: 2006-04-12 16:53:49 UTC
Scored at: 2006-04-12 23:51:02 UTC

Current Rank: 697th
Based on: take a chance #5 - I do! 2 (diff)
Basis for: poptastic 4 (diff)
Basis for: poptastic 5 (diff)
Basis for: poptastic 6 (diff)
...and 15 others.

Comments
Markus Buehren
12 Apr 2006
Let me try some tweaks that I saved for the last minutes...
Please login or create a profile.
Code
function moves=solver(board,nMoves)
[rows, cols] = size(board);
rows_orig = rows;
row_diff = 1;
moves = ones(nMoves,3);
count=0;
r=rand(4,1);

nOfPoints = rows*cols;
% set move calculation parameters
if nOfPoints > 10.5*nMoves
  next_move_count = 40;
  choke_factor = .847;
  depth_factor = 2.93;
  rotinv       = 0.638;
  rotinv2      = 1.283;
elseif nOfPoints > 8.5*nMoves
  next_move_count = 29;
  choke_factor = .847;
  depth_factor = 2.93;
  rotinv       = 0.638;
  rotinv2      = 1.283;
elseif nOfPoints >= 256
  next_move_count = 26;
  choke_factor = .951;
  depth_factor = 2.8;
  rotinv       = 0.714;
  rotinv2      = 1.2;
else
  next_move_count = 26;
  choke_factor = 0.945;
  depth_factor = 2.97;
  rotinv       = 0.685;
  rotinv2      = 1.23;
end

% adjust block weights
board = board .^ rotinv;

depth = ceil(depth_factor*nMoves/10);
flip = floor((0.66+(rand-0.5)*0.1)*nMoves);
while 1
  % restore original colour values half-way through game
  if count==flip
    board = board .^ rotinv2;
  end

  % find highest value moves
  [cell_list,value_list,mask] = CalculateMoves(rows,cols,board);
  if isempty(cell_list),
    [swapmv,board]=CheckForSwap(rows,cols,board, row_diff);
    if swapmv(1)
      count = count+1;
      moves(count,:) = swapmv;
      if (count==nMoves)
        break
      end
      continue
    end
    break
  end

  % check future move values and re-weight current moves
  if count<nMoves-1
    [value_list,pos]=sort(value_list,2,'descend');
    cell_list=cell_list(pos);
    for k=1:min(numel(cell_list),next_move_count)
      new_board = ProcessMove(board,mask,cell_list(k),rows);
      [new_cell_list,new_value_list] = CalculateMoves(rows,cols,new_board);

      if (~isempty(new_cell_list))
        depth_ = max(min(depth,nMoves-count-3),1);
        if numel(new_value_list)<=depth_
          value_list(k) = value_list(k) + sum(new_value_list);
        else
          new_value_list=sort(new_value_list,2,'descend');
          value_list(k) = value_list(k) + sum(new_value_list(1:depth_));
        end
      end
      if (value_list(k) < choke_factor * value_list(1))
        break;
      end
    end
  end

  % take new most-valuable move
  [max_val,pos] = max(value_list); %#ok
  max_cell = cell_list(pos);
  count = count+1;
  moves(count,:) = [mod(max_cell-1,rows)+row_diff,ceil(max_cell/rows),0];
  board = ProcessMove(board,mask,max_cell,rows);

  % new: shrink board
  minRow = find(any(board, 2), 1);
  if minRow > 1
    board(1:minRow-1, :) = [];
    rows = rows - minRow + 1;
    row_diff = rows_orig-rows + 1;
  end

  if (count==nMoves)
    break;
  end
end
moves = moves(1:count,:);

function [cell_list,value_list,mask] = CalculateMoves(rows,cols,board)

mask = zeros(rows,cols);

% find first row from top that has non-zeros
first_row = 1;

if (first_row == 1)
  % first row is non-zero so build column weighted match value
  bk=board(1);
  if bk
    mask(1)=1;
  end
  k=1;
  for j=2:cols
    m = k;
    k = k + rows;
    bm=bk;
    bk=board(k);
    if bk
      mask(k) = k;
      if (bm == bk)
        % block to left matches current
        mask(m) = k;
      end
    end
  end
end

% Start at first row (or second if first is top and loop to bottom)
for i = max(2,first_row):rows
  k=i;
  bk=board(k);
  if (bk)
    % first block in row is non-zero
    mask(k) = k;
    m = k-1;
    if (board(m) == bk)
      % block above matches current
      n = -1;
      while (n ~= m)
        n = m;
        m = mask(n);
        mask(n) = k;
      end
    end
  end

  % loop through columns and build column+row weighted match value
  for j=2:cols
    k = k + rows;   % move over one column
    bm=bk;
    bk=board(k);
    if (bk)
      mask(k) = k;
      if (bm==bk)
        % block to left matches current
        mask(k-rows) = k;
      end
      if (board(k-1)==bk)
        % block above matches current
        n = -1;
        m = k - 1;
        while (n ~= m)
          n = m;
          m = mask(n);
          mask(n) = k;
        end
      end
    end
  end
end

cell_list = zeros(1,256);
group_count = 0;
group_count_matrix = zeros(rows, cols);

for i=rows:-1:first_row
  k = i + rows*(cols-1);
  for j=cols:-1:1
    if board(k)
      m = mask(k);
      if (m == k)
        group_count_matrix(k) = 1;
      else
        while group_count_matrix(m) == 0
          m = mask(m);
        end
        mask(k) = mask(m);
        group_block_count = group_count_matrix(m) + 1;
        group_count_matrix(m) = group_block_count;
        if (group_block_count == 2)
          group_count = group_count + 1;
          cell_list(1,group_count) = m;
        end
        mask(m)= k;
      end
    end
    k = k - rows;
  end
end

cell_list = cell_list(1:group_count);
value_list = zeros(1,group_count);

for k = 1:group_count
  m = cell_list(k);
  cell_list(k) = mask(m);
  value_list(k) = group_count_matrix(m) * board(m);
  mask(m) = m;
end

function B=ProcessMove(B,dj,cell,R)
y=cell;
B(y)=0;
col=ceil(y/R);
minCol=col;maxCol=col;
while dj(y)~=y
  y=dj(y);
  B(y)=0;
  col=ceil(y/R);
  minCol=min(minCol, col);
  maxCol=max(maxCol, col);
end;
for i=minCol:maxCol,
  k=B(B(:,i)>0,i);
  B(:,i)=0;B(R-numel(k)+1:R,i)=k;
end

function [swapmv,outboard]=CheckForSwap(rows,cols,board, row_diff)
swapper=[-1 rows 1 -rows];
lentmp=rows*cols;
swapmv=zeros(1,3);
outboard=board;
maxswap=0;
list=find(board~=0)';
nList=numel(list);
for k=1:nList
  jj=list(k);
  for swapdir=1:4
    np=jj+swapper(swapdir);
    if np>0 && np<=lentmp && board(np)>0 && board(np)~=board(jj)
      tboard=board;
      tboard([jj,np]) = tboard([np,jj]);
      [s_ceil,s_value]=CalculateMoves(rows,cols,tboard); %#ok
      if (~isempty(s_value))
        if (max(s_value)> maxswap)
          maxswap=max(s_value);
          idxq=jj;
          idxr=swapdir;
          idxs=np;
        end
      else
        for k2=max(1,k-10):min(nList,k+10)
          jj2=list(k2);
          for swapdir2=1:4
            np2=jj2+swapper(swapdir2);
            if np2>0 && np2<=lentmp && tboard(np2)>0 && tboard(np2)~=tboard(jj2)
              tboard2=tboard;
              tboard2([jj2,np2]) = tboard2([np2,jj2]);
              [s_ceil2,s_value2,s_mask2]=CalculateMoves(rows,cols,tboard2);
              if (~isempty(s_value2) && max(s_value2)>maxswap)
                [s_max,s_idx]=max(s_value2); %#ok
                Y=s_ceil2(s_idx);
                while (s_mask2(Y)~=Y)
                  Y = s_mask2(Y);
                end
                if (Y==np || Y==jj)
                  maxswap=max(s_value2);
                  idxq=jj;
                  idxr=swapdir;
                  idxs=np;
                end
              end
            end
          end
        end
      end
    end
  end
end
if (maxswap>0)
  swapmv = [mod(idxq-1,rows)+row_diff,ceil(idxq/rows),idxr];
  outboard=board;
  outboard([idxq,idxs]) = tboard([idxs,idxq]);
end