search.rb
# Progressive deepening from the root of the move tree, stores the best variations from
#   each root move to accelerate deepening on the next progression
Progressive deepening from the root of the move tree, stores the best variations from
each root move to accelerate deepening on the next progression
Progressive deepening from the root of the move tree stores the best variations from each root move to accelerate deepening on the next progression
def start(duration = 4)
    make_tables
    make_gamestate
    make_board
    make_root
    @duration = duration
    clock_start = Time.now
    clock_stop = clock_start + @duration
    alpha_idx = 0
    MAXPLY.times do |depth|
      @best_idx = alpha_idx
      alpha, alpha_idx = -INF, 0
      sort_moves(1, @root_n - 1)
      1.upto(@root_n - 1) do |i|
        next unless @mv_legal[@mv_idx[i]]
        @root = @mv_idx[i]
        @on_mv[1] = @root
        next unless make_move
        @pv[@root][1] = @mv[@root].dup if depth == 0
        @pv_ply[@root], @mv_ply, @on_pv, @mv_n = 1, 1, true, @root_n
        @k1.fill(0)
        @k2.fill(0)
        if depth == 0 || i == 1
          @npp_pv[@ply] += 1
          score = -search(-INF, -alpha, depth)
        else
          @npp_nw[@ply] += 1
          score = -search(-alpha-1, -alpha, depth)
          if score > alpha
            @npp_pv[@ply] += 1
            score = -search(-INF, -alpha, depth)
          end
        end
        unmake_move
        @mv_score[@root] = score
        if score > alpha
          alpha, alpha_idx = score, @root
        end
        break if Time.now > clock_stop
      end
      break if Time.now > clock_stop
      next if alpha_idx == 0 || depth == 0
      pvl = []
      1.upto([@pv_ply[alpha_idx], 5].min) do |j|
        if @pv[alpha_idx][j] && @pv[alpha_idx][j].from
          m = @pv[alpha_idx][j]
          @pv_chart[SQ64[m.to]] = { piece: UTF8[m.mx + 1 & 1][m.piece], depth: depth, ply: j}
          pvl << make_san(m)
        else
          break
        end
      end
      @pv_list << { depth: depth, moves: pvl.join(", ") } unless pvl.empty?
    end
    @clock = Time.now - clock_start
    @root, @fen = @best_idx, @mv_fen[@best_idx]
    @san, type = @mv_san[@root], @mv_type[@root]
    piece, from = UTF8[@mx][@mv[@root].piece], SQ_ID[@mv[@root].from]
    to, target = SQ_ID[@mv[@root].to], ""
    target = " #{UTF8[@mn][P]}" if @san.include?('e.p.')
    target = " #{UTF8[@mn][@mv[@root].target]}" unless @mv[@root].target == EMPTY
    @best_move = { notation: @san, type: type, move: "#{piece}#{from} → #{to}#{target}",
                   score: @mv_score[@root], fen: @fen }
    @ply, @on_mv[0], @mv[0] = 0, 0, @mv[@root].dup
    make_move
    make_root
    evaluate
    nil
  end
def start ( duration = 4 ) make_tables make_gamestate make_board make_root @duration = duration clock_start = Time . now clock_stop = clock_start + @duration alpha_idx = 0 MAXPLY . times do | depth | @best_idx = alpha_idx alpha , alpha_idx = - INF , 0 sort_moves ( 1 , @root_n - 1 ) 1 . upto ( @root_n - 1 ) do | i | next unless @mv_legal [ @mv_idx [ i ] ] @root = @mv_idx [ i ] @on_mv [ 1 ] = @root next unless make_move @pv [ @root ] [ 1 ] = @mv [ @root ] . dup if depth == 0 @pv_ply [ @root ] , @mv_ply , @on_pv , @mv_n = 1 , 1 , true , @root_n @k1 . fill ( 0 ) @k2 . fill ( 0 ) if depth == 0 || i == 1 @npp_pv [ @ply ] += 1 score = - search ( - INF , - alpha , depth ) else @npp_nw [ @ply ] += 1 score = - search ( - alpha - 1 , - alpha , depth ) if score > alpha @npp_pv [ @ply ] += 1 score = - search ( - INF , - alpha , depth ) end end unmake_move @mv_score [ @root ] = score if score > alpha alpha , alpha_idx = score , @root end break if Time . now > clock_stop end break if Time . now > clock_stop next if alpha_idx == 0 || depth == 0 pvl = [ ] 1 . upto ( [ @pv_ply [ alpha_idx ] , 5 ] . min ) do | j | if @pv [ alpha_idx ] [ j ] && @pv [ alpha_idx ] [ j ] . from m = @pv [ alpha_idx ] [ j ] @pv_chart [ SQ64 [ m . to ] ] = { piece : UTF8 [ m . mx + 1 & 1 ] [ m . piece ] , depth : depth , ply : j } pvl << make_san ( m ) else break end end @pv_list << { depth : depth , moves : pvl . join ( ", " ) } unless pvl . empty? end @clock = Time . now - clock_start @root , @fen = @best_idx , @mv_fen [ @best_idx ] @san , type = @mv_san [ @root ] , @mv_type [ @root ] piece , from = UTF8 [ @mx ] [ @mv [ @root ] . piece ] , SQ_ID [ @mv [ @root ] . from ] to , target = SQ_ID [ @mv [ @root ] . to ] , "" target = " #{UTF8[@mn][P]}" if @san . include? ( 'e.p.' ) target = " #{UTF8[@mn][@mv[@root].target]}" unless @mv [ @root ] . target == EMPTY @best_move = { notation : @san , type : type , move : "#{piece}#{from} → #{to}#{target}", score : @mv_score [ @root ] , fen : @fen } @ply , @on_mv [ 0 ] , @mv [ 0 ] = 0 , 0 , @mv [ @root ] . dup make_move make_root evaluate nil end
Progressive deepening from the root of the move tree, stores the best variations from
each root move to accelerate deepening on the next progression
Progressive deepening from the root of the move tree stores the best variations from each root move to accelerate deepening on the next progression
duration
<not_specific>