blunders_engine/search/
ids.rs

1//! Iterative Deepening Search.
2
3use std::sync::atomic::AtomicBool;
4use std::sync::Arc;
5use std::time::Instant;
6
7use crate::arrayvec::display;
8use crate::coretypes::MAX_DEPTH;
9use crate::search;
10use crate::search::History;
11use crate::search::SearchResult;
12use crate::timeman::Mode;
13use crate::transposition::{Entry, NodeKind, TranspositionTable};
14use crate::Position;
15
16/// Run Iterative Deepening search on a root position to depth "ply" using
17/// a persistent transposition table.
18/// It returns the best move and score for the position in the search tree.
19/// TODO: Bug fix, returns invalid result in case where stopper was set too quickly.
20pub fn ids(
21    position: Position,
22    mode: Mode,
23    history: History,
24    tt: &TranspositionTable,
25    stopper: Arc<AtomicBool>,
26    debug: bool,
27) -> SearchResult {
28    let hash = tt.generate_hash(&position);
29    let instant = Instant::now();
30    let age = position.age();
31
32    // Invalid default values, will be overwritten after each loop.
33    let mut search_result = SearchResult {
34        player: position.player,
35        stopped: true,
36        ..Default::default()
37    };
38
39    // Run a search for each ply from 1 to target ply.
40    // After each search, ensure that the principal variation from the previous
41    // iteration is in the tt.
42    for ply in 1..=MAX_DEPTH {
43        // Check if we need to stop before the current iteration.
44        if mode.stop(position.player, ply) {
45            break;
46        }
47
48        let stopper = Arc::clone(&stopper);
49        let history = history.clone();
50        let maybe_result = search::iterative_negamax(position, ply, mode, history, tt, stopper);
51
52        // Update search_result from deeper iteration, and return early if it's flagged as stop.
53        // Need to update nodes, q_nodes, and q_elapsed to get running total.
54        if let Some(mut result) = maybe_result {
55            result.add_metrics(search_result);
56            search_result = result;
57
58            if search_result.stopped {
59                break;
60            }
61        } else {
62            break;
63        }
64
65        if debug && !search_result.stopped {
66            // Print UCI info for this completed search result.
67            println!(
68                "info depth {} score cp {} time {} nodes {} nps {} pv {}",
69                search_result.depth,
70                search_result.relative_score(),
71                search_result.elapsed.as_millis(),
72                search_result.nodes,
73                search_result.nps(),
74                display(&search_result.pv),
75            );
76        }
77
78        // Check if this completed search result contains a checkmate, to return early.
79        if search_result.score.is_mate() && !search_result.stopped {
80            break;
81        }
82
83        // Each value in the PV has the same score, so a TT Entry is remade for each
84        // position to ensure the PV is searched first in the next search of deeper ply.
85        // PV may theoretically much longer than the ply of the current search, due to TT hits.
86        // Only positions up to the current ply may be used.
87        // TODO:
88        // Check for possible bugs where the pv is incorrect.
89        // This might be fixed by checking if a position exists in the tt already,
90        // but has different values from what is recreated.
91        let mut position = position.clone();
92        let mut hash = hash.clone();
93        let mut move_ply = ply.clone();
94        let mut relative_pv_score = search_result.relative_score();
95
96        for &pv_move in search_result.pv.iter().take(move_ply as usize) {
97            let pv_entry = Entry::new(hash, pv_move, relative_pv_score, move_ply, NodeKind::Pv);
98            tt.replace(pv_entry, age);
99
100            let cache = position.cache();
101            let move_info = position.do_move(pv_move);
102            tt.update_hash(&mut hash, &position, move_info, cache);
103            move_ply -= 1;
104            relative_pv_score = -relative_pv_score;
105        }
106        // TODO: Handle part of PV that is longer than depth searched.
107    }
108
109    // Update values with those tracked in top level.
110    search_result.elapsed = instant.elapsed();
111
112    search_result
113}
blunders_engine/search/ids.rs

blunders_engine/search/
ids.rs
