search.rb
# Performs a depth first variation search beyond the root of the move tree
Performs a depth first variation search beyond the root of the move tree
Performs a depth first variation search beyond the root of the move tree
def search(alpha, beta, depth)
    quiesce = false
    if depth <= 0
      score = evaluate
      return beta if score >= beta
      alpha = score if score > alpha
      return alpha if @ply >= MAXPLY - 1 || score < alpha - 900 || depth < -3
      @npp_qs[@ply] += 1
      quiesce = true
    end
    moved, i = false, @mv_n
    generate_moves(quiesce)
    c, n = @check, @mv_n - 1
    return -INF if n < i && c
    assert_pv(i, n) if @on_pv
    sort_moves(i, n)
    @mv_ply = @ply
    i.upto(n) do |j|
      idx = @mv_idx[j]
      @on_mv[@ply] = idx
      next unless make_move
      moved = true
      if j == i
        @npp_pv[@ply] += 1
        score = -search(-beta, -alpha, depth - 1)
      else
        @npp_nw[@ply] += 1
        score = -search(-alpha-1, -alpha, depth - 1)
        if score > alpha && score < beta && depth > 1
          @npp_pv[@ply] += 1
          score = -search(-beta, -alpha, depth - 1)
        end
      end
      unmake_move
      if score > alpha
        if @mv[idx].target == EMPTY
          @rpt[@root][@mv[idx].piece][@mv[idx].to] += depth
          @ppt[@ply][@mv[idx].piece][@mv[idx].to] += depth
          @pt[@mv[idx].piece][@mv[idx].to] += 1
        end
        if score >= beta
          if @mv[idx].target == EMPTY
            @k2[@ply] = @k1[@ply]
            @k1[@ply] = idx
          end
          return beta
        end
        alpha = score
        @pv[@root][@ply] = @mv[idx].dup
        (@ply + 1).upto(@mv_ply) { |k| @pv[@root][k] = @mv[@on_mv[k]].dup }
        @pv_ply[@root] = @mv_ply
      elsif @mv[idx].target == EMPTY
        @rtn[@root][@mv[idx].to] += depth
        @ptn[@mv[idx].piece][@mv[idx].to] += 1
      end
    end
    moved ? alpha : -INF
  end
def search ( alpha , beta , depth ) quiesce = false if depth <= 0 score = evaluate return beta if score >= beta alpha = score if score > alpha return alpha if @ply >= MAXPLY - 1 || score < alpha - 900 || depth < - 3 @npp_qs [ @ply ] += 1 quiesce = true end moved , i = false , @mv_n generate_moves ( quiesce ) c , n = @check , @mv_n - 1 return - INF if n < i && c assert_pv ( i , n ) if @on_pv sort_moves ( i , n ) @mv_ply = @ply i . upto ( n ) do | j | idx = @mv_idx [ j ] @on_mv [ @ply ] = idx next unless make_move moved = true if j == i @npp_pv [ @ply ] += 1 score = - search ( - beta , - alpha , depth - 1 ) else @npp_nw [ @ply ] += 1 score = - search ( - alpha - 1 , - alpha , depth - 1 ) if score > alpha && score < beta && depth > 1 @npp_pv [ @ply ] += 1 score = - search ( - beta , - alpha , depth - 1 ) end end unmake_move if score > alpha if @mv [ idx ] . target == EMPTY @rpt [ @root ] [ @mv [ idx ] . piece ] [ @mv [ idx ] . to ] += depth @ppt [ @ply ] [ @mv [ idx ] . piece ] [ @mv [ idx ] . to ] += depth @pt [ @mv [ idx ] . piece ] [ @mv [ idx ] . to ] += 1 end if score >= beta if @mv [ idx ] . target == EMPTY @k2 [ @ply ] = @k1 [ @ply ] @k1 [ @ply ] = idx end return beta end alpha = score @pv [ @root ] [ @ply ] = @mv [ idx ] . dup ( @ply + 1 ) . upto ( @mv_ply ) { | k | @pv [ @root ] [ k ] = @mv [ @on_mv [ k ] ] . dup } @pv_ply [ @root ] = @mv_ply elsif @mv [ idx ] . target == EMPTY @rtn [ @root ] [ @mv [ idx ] . to ] += depth @ptn [ @mv [ idx ] . piece ] [ @mv [ idx ] . to ] += 1 end end moved ? alpha : - INF end
Performs a depth first variation search beyond the root of the move tree
Performs a depth first variation search beyond the root of the move tree
alpha
<not_specific>
beta
<not_specific>
depth
<not_specific>