Material, negamax and alpha-beta
Stage 5 · tag stage-05-alphabeta · code in crates/engine
This is where cb2026 starts to play chess. It looks a few moves ahead, counts material at the end of each line, and picks the move whose worst case is best. That’s enough to win material, avoid losing it, and find mates. Against the stage 4 random mover it won 285 of 286 games.
Evaluation: counting material
The search can’t see to the end of the game, so at the edge of its tree it needs a number that says how good a position looks. The simplest useful one counts material in centipawns (hundredths of a pawn), from the point of view of the side to move:
/// The evaluation's tunable numbers, and switches for its term groups.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct EvalParams {
/// Middlegame value of each piece type in centipawns, indexed by [`PieceType::index`]
/// (the king's value is never used: both sides always have one).
pub mg_values: [i32; 6],
/// Endgame value of each piece type.
pub eg_values: [i32; 6],
/// Middlegame piece-square tables, indexed by [`PieceType::index`].
pub mg_pst: [Pst; 6],
/// Endgame piece-square tables.
pub eg_pst: [Pst; 6],
/// How much each piece type counts toward the game phase.
pub phase_weights: [i32; 6],
/// Use the piece-square tables (off: material only).
pub use_pst: bool,
/// Blend middlegame and endgame values by phase (off: middlegame values only).
pub tapered: bool,
/// The positional terms of the full evaluation (stage 15).
pub terms: TermParams,
}/// Reports every term of the evaluation, for both sides, to `sink`.
pub fn collect<S: TermSink>(pos: &Position, params: &EvalParams, sink: &mut S) {
for color in Color::ALL {
for piece_type in PieceType::ALL {
for square in pos.pieces(color, piece_type) {
sink.term(color, Param::Material(piece_type), 1);
if params.use_pst {
sink.term(color, Param::Pst(piece_type, pst_index(color, square)), 1);
}
}
}
}
hce::collect(pos, ¶ms.terms, sink);
}
/// The game phase: from 0 (bare kings and pawns) to [`MAX_PHASE`] (all the pieces).
pub fn phase(pos: &Position, params: &EvalParams) -> i32 {
let phase: i32 = PieceType::ALL
.iter()
.map(|&pt| params.phase_weights[pt.index()] * pos.pieces_of_type(pt).count() as i32)
.sum();
phase.min(MAX_PHASE)
}
/// Adds up the terms' values into an [`EvalTrace`].
struct TraceSink<'a> {
params: &'a EvalParams,
trace: EvalTrace,
}
impl TermSink for TraceSink<'_> {
fn term(&mut self, side: Color, param: Param, count: i32) {
let t = &mut self.trace;
let slot = match param {
Param::Material(_) => &mut t.material,
Param::Pst(..) => &mut t.pst,
Param::Mobility(_) => &mut t.mobility,
Param::Doubled | Param::Isolated => &mut t.pawns,
Param::Passed(_) => &mut t.passed,
Param::BishopPair | Param::RookOpenFile | Param::RookSemiOpenFile => &mut t.pieces,
Param::PawnShield => &mut t.king_safety,
Param::Tempo => &mut t.tempo,
};
let (mg, eg) = self.params.value(param);
slot[side.index()].0 += mg * count;
slot[side.index()].1 += eg * count;
}
fn king_danger(&mut self, side: Color, penalty: i32) {
self.trace.king_safety[side.index()].0 -= penalty;
}
}
/// Works out the evaluation's parts; the total is from White's point of view.
pub fn trace(pos: &Position, params: &EvalParams) -> EvalTrace {
let mut sink = TraceSink {
params,
trace: EvalTrace::default(),
};
collect(pos, params, &mut sink);
let mut t = sink.trace;
t.phase = phase(pos, params);
let (mg, eg) = t.net();
t.total = if params.tapered {
(mg * t.phase + eg * (MAX_PHASE - t.phase)) / MAX_PHASE
} else {
mg
};
t
}
/// The position's value in centipawns, from the side to move's point of view.
pub fn evaluate(pos: &Position, params: &EvalParams) -> i32 {
let total = trace(pos, params).total;
match pos.side_to_move() {
Color::White => total,
Color::Black => -total,
}
}The values are named parameters, not constants buried in code. Stage 16 tunes all the evaluation’s numbers automatically, and that only works if they live in one place.
Minimax and negamax
To pick a move, imagine every move, every reply, every reply to that, down to some depth. Evaluate the positions at the bottom, then work back up assuming each side picks what’s best for it: the side to move takes the maximum, its opponent the minimum. That’s minimax.
Because chess scores are symmetric (+3 for White is −3 for Black), the two cases fold into one: a position’s score is the best, over all moves, of minus the score after the move. That’s negamax, and it’s what the code below implements.
Alpha-beta
Most of the minimax tree can’t change the answer. Suppose White’s first move turns out to be worth +1. For the second move, the moment Black finds one reply that makes it worse than +1, White’s second move is refuted: White would never play it, so Black’s other replies needn’t be examined.
Alpha-beta formalises this with a window [alpha, beta]:
alphais what the side to move can already guarantee elsewhere;betais the most its opponent will allow.
As soon as a move scores ≥ beta, the opponent won’t let this position happen. The remaining
moves are skipped: a beta cutoff.
/// The negamax score of `pos` searched `depth` plies deep, `ply` plies from the root,
/// within the window `[alpha, beta]`. The best line found is written to `pv`. `cut_node`
/// says whether the node is expected to fail high (an expected cut node; see
/// [`Searcher::search_move`]); a node with a full window never is.
// The search's state is in `self`; these are the node's own.
#[allow(clippy::too_many_arguments)]
fn negamax(
&mut self,
pos: &Position,
depth: u32,
ply: u32,
mut alpha: i32,
beta: i32,
cut_node: bool,
pv: &mut Vec<Move>,
) -> i32 {
self.nodes += 1;
self.note(Note::Enter { depth, alpha, beta });
self.seldepth = self.seldepth.max(ply);
pv.clear();
if self.should_stop() {
return 0;
}
// Set while a singular extension's search leaves this node's hash move out.
let excluded = self.excluded[ply as usize];
let moves = pos.legal_moves();
if moves.is_empty() {
// Checkmate (worse the sooner it happens) or stalemate.
return if pos.in_check() {
-MATE + ply as i32
} else {
0
};
}
if self.is_draw(pos) {
return 0;
}
if ply >= MAX_PLY {
return self.evaluate(pos, ply);
}
if depth == 0 {
return if self.techniques.quiescence {
self.quiescence(pos, ply, alpha, beta, pv)
} else {
self.evaluate(pos, ply)
};
}
// The fail highs two plies down are counted afresh under each node: the next ply's
// count then covers this node's children and its siblings'.
self.cutoffs[ply as usize + 2] = 0;
// Transposition table: a deep enough result may settle this position at once, and in
// any case its best move is searched first.
// (Not in a singular extension's search: the entry is about the node with every move.)
let mut tt_move = None;
let mut tt_entry = None;
if self.techniques.tt
&& excluded.is_none()
&& let Some(entry) = self.tt.probe(pos.hash())
{
self.note(Note::TtHit);
tt_entry = Some(entry);
tt_move = entry.best_move.filter(|mv| moves.contains(mv));
if u32::from(entry.depth) >= depth {
let score = score_from_tt(entry.score, ply);
let usable = match entry.bound {
Bound::Exact => true,
Bound::Lower => score >= beta,
Bound::Upper => score <= alpha,
};
if usable {
self.note(Note::TtCutoff);
pv.extend(tt_move);
return score;
}
}
}
let pv_node = beta - alpha > 1;
// Is or has been on the principal variation: a PV node now, or one the table remembers
// as one. A singular extension's search, of the same node, keeps the node's flag.
if excluded.is_none() {
self.tt_pv[ply as usize] = pv_node || tt_entry.is_some_and(|entry| entry.pv);
}
let tt_pv = self.tt_pv[ply as usize];
// Internal iterative reduction: with no hash move to try first, move ordering is poor
// and the node probably isn't important; search it a ply shallower.
let depth = if self.techniques.iir
&& tt_move.is_none()
&& excluded.is_none()
&& depth >= self.search_params.iir_min_depth
{
depth - 1
} else {
depth
};
// Endgame tablebases: right after a capture or pawn move, a covered position's result
// is known exactly.
if let Some((tb, tb_params)) = self.tablebase
&& ply > 0
&& depth >= tb_params.probe_depth
&& pos.halfmove_clock() == 0
&& tablebase::covers(tb, &tb_params, pos)
&& let Some(wdl) = tb.probe_wdl(pos)
{
self.tb_hits += 1;
self.note(Note::Tablebase);
let score = tablebase::score(wdl, ply);
if self.techniques.tt {
let stored = score_to_tt(score, ply);
self.tt
.store(pos.hash(), None, stored, MAX_PLY, Bound::Exact, tt_pv);
}
return score;
}
let p = self.search_params;
let in_check = pos.in_check();
// The static evaluation, for the pruning decisions (meaningless in check), corrected by
// what the search has learnt about positions with these pawns.
let raw_eval = if in_check {
-INFINITY
} else {
self.evaluate(pos, ply)
};
let static_eval = if in_check {
-INFINITY
} else {
self.corrected_eval(pos, raw_eval)
};
// Improving: better than two plies ago, when this side last moved. Its evaluation will
// probably keep rising, which changes the bets the pruning techniques make.
self.evals[ply as usize] = static_eval;
let improving = self.techniques.improving
&& !in_check
&& ply >= 2
&& static_eval > self.evals[ply as usize - 2];
// Selective pruning happens only off the principal variation and out of check.
let selective = self.techniques.alpha_beta && !pv_node && !in_check;
// Reverse futility pruning: far enough above beta, assume a search would stay there.
// An improving side gets a smaller margin, but never none at all.
let rfp_margin = p.rfp_margin * depth as i32 - if improving { p.rfp_improving } else { 0 };
if self.techniques.reverse_futility
&& selective
&& depth <= p.rfp_max_depth
&& static_eval - rfp_margin >= beta
{
self.note(Note::ReverseFutility);
return static_eval;
}
// Razoring: far below alpha near the leaves, only captures could save the node.
if self.techniques.razoring
&& self.techniques.quiescence
&& selective
&& depth <= p.razor_max_depth
&& static_eval + p.razor_margin * (depth as i32) < alpha
{
let score = self.quiescence(pos, ply, alpha, alpha + 1, pv);
if score <= alpha {
self.note(Note::Razoring);
return score;
}
pv.clear();
}
// Null-move pruning: if passing still keeps us at or above beta, a real move would too.
if self.techniques.null_move
&& selective
&& excluded.is_none()
&& depth >= p.null_min_depth
&& self.path.last() != Some(&None)
&& has_pieces(pos)
&& static_eval >= beta
{
self.note(Note::NullMove);
let reduction = p.null_reduction + depth / p.null_depth_divisor;
let mut child = pos.clone();
child.make_null_move();
self.push_move(pos, None);
self.update_accumulator(pos, None, ply);
self.keys.push(pos.hash());
let mut null_pv = Vec::new();
let score = -self.negamax(
&child,
depth.saturating_sub(1 + reduction),
ply + 1,
-beta,
-beta + 1,
!cut_node,
&mut null_pv,
);
self.note(Note::Exit { score: -score });
self.keys.pop();
self.pop_move();
if self.aborted {
return 0;
}
if score >= beta {
self.note(Note::NullMoveCutoff);
// A mate found after passing isn't a real mate: claim no more than beta.
return if score >= MATE - MAX_PLY as i32 {
beta
} else {
score
};
}
}
// ProbCut: if a good capture beats beta by a margin even in a shallower search, the
// full-depth search would almost surely beat beta too, so the node is cut off. Not if
// the hash table already says that a search about as deep fell short of the margin.
let probcut_beta = beta + p.probcut_margin;
if self.techniques.probcut
&& self.techniques.quiescence
&& selective
&& excluded.is_none()
&& depth >= p.probcut_min_depth
&& beta.abs() + p.probcut_margin < MATE - MAX_PLY as i32
&& !tt_entry.is_some_and(|entry| {
entry.bound != Bound::Lower
&& u32::from(entry.depth) + p.probcut_reduction > depth
&& score_from_tt(entry.score, ply) < probcut_beta
})
{
self.note(Note::ProbCut);
let probcut_depth = depth.saturating_sub(p.probcut_reduction);
let captures: Vec<Move> = moves.iter().copied().filter(|&mv| is_noisy(mv)).collect();
let previous = self.previous();
let picker = MovePicker::new(
pos,
&captures,
tt_move,
ply,
&previous,
self.ordering,
&self.techniques,
);
let mut cutoff = None;
let mut probcut_pv = Vec::new();
self.keys.push(pos.hash());
for mv in picker {
// Only captures that win, by static exchange, at least what the static
// evaluation is short of the margin.
if see(pos, mv) < probcut_beta - static_eval {
continue;
}
let mut child = pos.clone();
child.make_move(mv);
self.push_move(pos, Some(mv));
self.update_accumulator(pos, Some(mv), ply);
// The quiescence search first: it is cheap, and if even it can't reach the
// margin, the shallower search seldom does.
let mut score = -self.quiescence(
&child,
ply + 1,
-probcut_beta,
-probcut_beta + 1,
&mut probcut_pv,
);
if score >= probcut_beta && probcut_depth > 0 && !self.aborted {
score = self.search_child(
&child,
probcut_depth,
probcut_beta - 1,
probcut_beta,
!cut_node,
&mut probcut_pv,
);
}
self.pop_move();
if self.aborted {
break;
}
if score >= probcut_beta {
cutoff = Some((mv, score));
break;
}
}
self.keys.pop();
if self.aborted {
return 0;
}
if let Some((mv, score)) = cutoff {
self.note(Note::ProbCutCutoff(mv));
// What ProbCut found is a lower bound from its shallower search.
if self.techniques.tt {
let stored = score_to_tt(score, ply);
self.tt.store(
pos.hash(),
Some(mv),
stored,
probcut_depth + 1,
Bound::Lower,
tt_pv,
);
}
return score;
}
}
// Singular extension: is the hash move much better than every other move? Search the
// node again, at half the depth and without the hash move, against a window a little
// below the hash move's score. If no other move reaches it, the hash move is probably
// forced, and it is searched a ply deeper.
let mut singular_move = None;
let mut double_move = None;
let mut shallower_move = None;
if self.techniques.singular_extension
&& depth >= p.singular_min_depth
&& ply < 2 * self.root_depth
&& let Some(entry) = tt_entry
&& let Some(hash_move) = tt_move
&& entry.bound != Bound::Upper
&& u32::from(entry.depth) + p.singular_tt_depth_margin >= depth
{
let tt_score = score_from_tt(entry.score, ply);
if tt_score.abs() < MATE - MAX_PLY as i32 {
let singular_beta = tt_score - p.singular_margin * depth as i32;
self.note(Note::SingularSearch(hash_move));
self.excluded[ply as usize] = Some(hash_move);
let mut singular_pv = Vec::new();
let score = self.negamax(
pos,
(depth - 1) / 2,
ply,
singular_beta - 1,
singular_beta,
cut_node,
&mut singular_pv,
);
self.excluded[ply as usize] = None;
self.note(Note::Exit { score });
if self.aborted {
return 0;
}
if score < singular_beta {
self.note(Note::SingularExtension(hash_move));
singular_move = Some(hash_move);
// Double extension: nothing else comes close even well below
// `singular_beta`, so the hash move is searched a second ply deeper. Only
// off the principal variation, and only a few times along a line, so that
// the search can't explode.
if self.techniques.double_extension
&& !pv_node
&& score < singular_beta - p.double_extension_margin
&& self.double_extensions < p.double_extension_limit
{
self.note(Note::DoubleExtension(hash_move));
double_move = Some(hash_move);
}
} else if self.techniques.multi_cut && singular_beta >= beta {
// Multi-cut: the hash move beat beta, and another move beats it too even
// at half the depth. With two moves that good, the node is a cutoff.
self.note(Note::MultiCut);
return singular_beta;
} else if self.techniques.negative_extension && tt_score >= beta {
// Negative extension: not singular, but its hash score beats beta. The
// node will probably cut off either way, so its line needs less care.
self.note(Note::NegativeExtension(hash_move));
shallower_move = Some(hash_move);
}
}
}
// In a singular extension's search, the hash move is left out. If it was the only
// move, nothing else comes close: fail low.
let without_excluded: Vec<Move>;
let moves: &[Move] = match excluded {
Some(left_out) => {
without_excluded = moves.iter().copied().filter(|&mv| mv != left_out).collect();
&without_excluded
}
None => &moves,
};
if moves.is_empty() {
return alpha;
}
let previous = self.previous();
let picker = MovePicker::new(
pos,
moves,
tt_move,
ply,
&previous,
self.ordering,
&self.techniques,
);
let original_alpha = alpha;
let mut best = -INFINITY;
let mut best_move = None;
let mut child_pv = Vec::new();
// Quiet moves searched so far that didn't cause a cutoff (for the history penalty),
// and the same for captures and queen promotions (for capture history's).
let mut quiets_tried = Vec::new();
let mut noisy_tried = Vec::new();
// Moves actually searched (not pruned) so far.
let mut searched = 0;
self.keys.push(pos.hash());
for (index, mv) in picker.enumerate() {
let quiet = !is_noisy(mv);
let mut child = pos.clone();
child.make_move(mv);
let gives_check = child.in_check();
let ordinary = quiet && !in_check && !gives_check;
// Late move pruning: near the leaves, after enough quiet moves, skip the rest
// (once a move has shown we aren't simply getting mated).
if self.techniques.late_move_pruning
&& ordinary
&& !pv_node
&& depth <= p.lmp_max_depth
&& best > -MATE + MAX_PLY as i32
&& quiets_tried.len() as u32
>= (p.lmp_base + depth * depth) * if improving { p.lmp_improving } else { 1 }
{
self.note(Note::LateMovePruning(mv));
continue;
}
// History pruning: near the leaves, skip a quiet move whose history says it keeps
// failing where other moves cut off, by more the deeper the node. As in Stockfish
// (GPL-3.0), which scores the move by continuation history alone.
if self.techniques.history_pruning
&& ordinary
&& !pv_node
&& depth <= p.history_pruning_max_depth
&& best > -MATE + MAX_PLY as i32
&& self
.ordering
.quiet_score(pos, mv, &previous, &self.techniques)
< -p.history_pruning_margin * depth as i32
{
self.note(Note::HistoryPruning(mv));
continue;
}
// Futility pruning: a quiet move can't lift a hopeless static evaluation to alpha.
if self.techniques.futility
&& ordinary
&& !pv_node
&& depth <= p.futility_max_depth
&& best > -MATE + MAX_PLY as i32
&& static_eval + p.futility_base + p.futility_per_depth * depth as i32 <= alpha
{
self.note(Note::Futility(mv));
continue;
}
// SEE pruning: near the leaves, skip moves that lose material outright.
if self.techniques.see_pruning
&& selective
&& index > 0
&& !gives_check
&& depth <= p.see_max_depth
&& best > -MATE + MAX_PLY as i32
{
let margin = if quiet {
p.see_quiet_margin
} else {
p.see_capture_margin
};
if see(pos, mv) < -margin * (depth as i32) {
self.note(Note::SeePruning(mv));
continue;
}
}
let how = if index == 0 {
MoveSearch::First
} else if self.techniques.lmr
&& ordinary
&& depth >= p.lmr_min_depth
&& index as u32 >= p.lmr_min_moves
{
let row = &self.lmr[(depth as usize).min(LMR_TABLE_SIZE - 1)];
let mut reduction = i32::from(row[index.min(LMR_TABLE_SIZE - 1)]);
// Reduce the principal variation less: its exact score matters.
if pv_node {
reduction -= 1;
}
// Reduce more at an expected cut node: one move should refute it, and the late
// ones seldom matter.
if self.techniques.cut_node_reductions && cut_node {
reduction += p.lmr_cut_node;
}
// Reduce more when many moves at this ply have been refuted: this node is
// probably failing low, and its late moves along with it.
if self.techniques.cutoff_reductions
&& self.cutoffs[ply as usize + 1] > p.lmr_cutoff_count
{
reduction += p.lmr_cutoff_plies;
// More at an expected all-node, as in Stockfish 17.
if !pv_node && !cut_node {
reduction += p.lmr_cutoff_all_node_plies;
}
}
// Reduce more when the hash move is a capture: it is probably the best move,
// and a quiet move this late seldom beats it. Less (by default not at all) on
// the principal variation, whose exact score matters.
if self.techniques.tt_capture_reductions && tt_move.is_some_and(is_noisy) {
reduction += if pv_node {
p.lmr_tt_capture_pv
} else {
p.lmr_tt_capture
};
}
// Reduce less at an expected all-node: every move has to fail low for its
// score to hold, so a late move that is wrongly reduced into failing low
// makes the parent's move a refutation it isn't.
if self.techniques.all_node_reductions && !pv_node && !cut_node {
reduction -= p.lmr_all_node;
}
// Reduce less at a node that has been on the principal variation: it may be
// again.
if self.techniques.tt_pv && tt_pv && !pv_node {
reduction -= p.lmr_tt_pv;
}
// Reduce a move with a good history less: it has caused cutoffs elsewhere. And
// one with a bad history more.
if self.techniques.history_lmr {
let score = self
.ordering
.quiet_score(pos, mv, &previous, &self.techniques);
reduction -= p.lmr_history_adjustment(score);
}
MoveSearch::Later {
// Never reduce into the quiescence search.
reduction: reduction.clamp(0, depth as i32 - 2) as u32,
}
} else {
MoveSearch::Later { reduction: 0 }
};
// Check extension: a move that gives check is searched one ply deeper. So is a
// singular hash move (above), and one singular by a wide margin a ply more.
let doubled = Some(mv) == double_move;
let extension = u32::from(
(self.techniques.check_extension && gives_check && ply < MAX_PLY / 2)
|| Some(mv) == singular_move,
) + u32::from(doubled);
// A hash move that isn't singular but beats beta is searched shallower (above).
let shallower = if Some(mv) == shallower_move {
p.negative_extension_plies
} else {
0
};
searched += 1;
self.push_move(pos, Some(mv));
self.update_accumulator(pos, Some(mv), ply);
let child_depth = (depth - 1 + extension).saturating_sub(shallower);
self.double_extensions += u32::from(doubled);
let score = self.search_move(
&child,
child_depth,
alpha,
beta,
how,
cut_node,
&mut child_pv,
);
self.double_extensions -= u32::from(doubled);
self.pop_move();
if self.aborted {
break;
}
if score > best {
best = score;
best_move = Some(mv);
if score > alpha {
alpha = score;
pv.clear();
pv.push(mv);
pv.extend_from_slice(&child_pv);
}
}
// Beta cutoff: the opponent won't allow this position, so stop looking.
if self.techniques.alpha_beta && alpha >= beta {
self.note(Note::BetaCutoff(mv, searched));
// Counted for the node above: once more without a hash move, and less for a
// doubly extended move, as in Stockfish 17.
let counts = if doubled {
p.cutoff_count_double_extended
} else {
1
};
self.cutoffs[ply as usize] += counts + u32::from(tt_move.is_none());
if quiet {
self.ordering
.record_cutoff(pos, mv, &quiets_tried, ply, depth, &previous);
}
// The captures tried before it failed, whichever kind of move cut off.
let noisy_best = (!quiet).then_some(mv);
self.ordering
.record_captures(pos, noisy_best, &noisy_tried, depth);
break;
}
if quiet {
quiets_tried.push(mv);
} else {
noisy_tried.push(mv);
}
}
self.keys.pop();
let bound = if best >= beta {
Bound::Lower
} else if best > original_alpha {
Bound::Exact
} else {
Bound::Upper
};
// After a fail low under a node that is or has been on the principal variation, the
// opponent's last move was probably good, so this position may be on the next one.
if bound == Bound::Upper && ply > 0 && excluded.is_none() && depth > p.tt_pv_fail_low_depth
{
self.tt_pv[ply as usize] |= self.tt_pv[ply as usize - 1];
}
let tt_pv = self.tt_pv[ply as usize];
// (Not in a singular extension's search: its result leaves the best move out.)
if self.techniques.tt && !self.aborted && excluded.is_none() {
// After a fail low every move was refuted, so none of them is known to be best.
let move_to_store = if bound == Bound::Upper {
None
} else {
best_move
};
let score = score_to_tt(best, ply);
self.tt
.store(pos.hash(), move_to_store, score, depth, bound, tt_pv);
}
// Correction history learns how far the static evaluation was off: not in check (there
// is none), not in a singular extension's search (its score leaves the best move out),
// and not when the best move is a capture or promotion (its gain is material the static
// evaluation isn't meant to see).
let settings = self.correction_settings();
if self.techniques.correction_history
&& !self.aborted
&& !in_check
&& excluded.is_none()
&& !best_move.is_some_and(is_noisy)
&& let Some(correction) = self.correction.as_deref_mut()
{
correction.update(pos, depth, raw_eval, best, bound, &settings);
}
best
}Alpha-beta returns exactly the minimax result. It only skips work that can’t change the
answer. With perfect move ordering it searches about b^(d/2) positions instead of b^d,
which means twice the depth for the same effort.
Try it in the shell on Kiwipete:
> fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
> set alphabeta off
> go depth 4
cb2026 plays Bxa6 (depth 4, +0.10, 4185552 nodes, 868 ms; line: Bxa6 hxg2 Qxg2 bxc3)
> undo
> set alphabeta on
> go depth 4
cb2026 plays Bxa6 (depth 4, +0.10, 131847 nodes, 39 ms; line: Bxa6 hxg2 Qxg2 bxc3)
It plays the same move with the same score, from 32 times fewer positions, and that’s with moves in whatever order the generator produced them. Stage 10 orders moves well and gets much closer to the ideal.
Mate and draws
- Checkmate scores
−MATE + plyfor the side that is mated. Being mated sooner is worse, so the winner prefers the quickest mate and the loser the slowest. The score translates back to “mate in N” for GUIs. - Stalemate, the fifty-move rule, insufficient material and repetition score 0. Inside the search a single repetition counts as a draw: if a position can come back once, it can come back again, so there’s no point searching it twice.
Stopping
Stage 5 searches to a fixed depth: four plies unless told otherwise. It also stops early when any of these says so:
- the GUI’s
stop; - a node limit;
- a time limit, about 1/30th of the remaining clock plus most of the increment.
When stopped early it plays the best move found so far. Stage 6 replaces this with iterative deepening and proper time management.
Bench
cb2026 bench searches 14 fixed positions to a fixed depth (4 at this stage, 10 from stage
14 on) and prints the node count:
$ cb2026 bench
Total time (ms) : 108
Nodes searched : 556884
Nodes/second : 5113843
Because the search is deterministic, that number is a fingerprint of the search. Every commit
message ends with Bench: <nodes>, and a change meant to leave the search alone must leave it
unchanged.
What it’s worth
| Test | Result |
|---|---|
| Stage 5 vs stage 4 (random mover), 8+0.08, SPRT [0, 5] | +285 −0 =1 over 286 games: passed |
The Elo figure from such a lopsided match is meaningless (about +1100 ± 740), but the point stands: lookahead plus material counting beats random play every time. From now on each stage is measured against the one before.
Further reading
- Chess Programming Wiki: Minimax, Negamax, Alpha-Beta, Checkmate, Point Value.
- Donald Knuth and Ronald Moore, “An Analysis of Alpha-Beta Pruning”, Artificial Intelligence 6 (1975): the classic proof of how much alpha-beta saves.