blunders_engine/search/
quiescence.rs

1//! Quiescence Search
2//!
3//! When a position is being searched, nodes at the final depth (leaf nodes)
4//! can be either terminal or non-terminal.
5//! Terminal nodes get an absolute score. Non-terminal nodes are scored
6//! according to a static evaluation function that provides a best guess at to
7//! that node's value.
8//!
9//! Statically evaluating non-terminal leaf nodes leads to the horizon effect.
10//! An engine may see a leaf node where Queen x Pawn as a winning position,
11//! while right over the horizon exists Pawn x Queen.
12//!
13//! To reduce this horizon effect, a quiescence search is used in place of
14//! a direct static evaluation of a leaf node.
15//! Quiescence search searches a small sub-tree of the leaf node to evaluate
16//! quiet position, so the evaluation of the original leaf node is more stable.
17
18use crate::coretypes::{Cp, PlyKind};
19use crate::eval::evaluate;
20use crate::movelist::MoveInfoList;
21use crate::moveorder::pick_best_move;
22use crate::Position;
23use std::cmp::max;
24
25/// notes:
26/// Quiescence search returns a score relative to active player.
27/// It can be given any max depth to limit its search.
28/// A depth of 0 is the same as the stand pat evaluation.
29/// Quiescence is guaranteed to have a short runtime because it only evaluates captures,
30/// and there are a limited number of captures to be had for any position.
31///
32/// Quiescence is implemented as a fail-soft negamax.
33///
34/// example: leaf(Queen x Pawn) -> +100
35///          next(Pawn x Queen) -> -800
36///          actual -> -800
37/// A search would normally return a static evaluation.
38/// This can be an over or underestimate.
39///
40/// Quiescence needs pruning. Can aggressive pruning cause inaccurate scores?
41///
42///
43/// Initial Call to Quiescence:
44/// Negamax:
45///     if node is leaf and non-terminal, return quiescence(position, alpha, beta)
46pub fn quiescence(
47    position: &mut Position,
48    mut alpha: Cp,
49    beta: Cp,
50    ply: PlyKind,
51    nodes: &mut u64,
52) -> Cp {
53    let mut best_score = evaluate(position);
54
55    // Depth limited search.
56    if ply == 0 {
57        return best_score;
58    }
59
60    // Standing Beta cutoff.
61    if best_score >= beta {
62        return best_score;
63    }
64    if best_score > alpha {
65        alpha = best_score;
66    }
67
68    let cache = position.cache();
69    let mut legal_captures: MoveInfoList = position
70        .get_legal_moves()
71        .into_iter()
72        .map(|move_| position.move_info(move_))
73        .filter(|move_info| move_info.is_capture())
74        .collect();
75
76    while let Some(capture) = pick_best_move(&mut legal_captures, None) {
77        *nodes += 1;
78        position.do_move_info(capture);
79        let score = -quiescence(position, -beta, -alpha, ply - 1, nodes);
80        position.undo_move(capture, cache);
81
82        best_score = max(best_score, score);
83
84        // Beta cutoff in loop.
85        if best_score >= beta {
86            return best_score;
87        }
88        if best_score > alpha {
89            alpha = best_score;
90        }
91    }
92
93    return best_score;
94}
blunders_engine/search/quiescence.rs

blunders_engine/search/
quiescence.rs
