blunders_engine/search/
history.rs

1//! History structure used within search.
2
3use crate::arrayvec::ArrayVec;
4use crate::coretypes::MAX_HISTORY;
5use crate::position::Game;
6use crate::zobrist::{HashKind, ZobristTable};
7
8type HashHistory = ArrayVec<HashKind, MAX_HISTORY>;
9type Unrepeatables = ArrayVec<usize, MAX_HISTORY>;
10
11/// History primary use is for tracking repeated moves to prevent threefold repetition.
12/// It is stateful, in that functions assume the next interaction comes from the next
13/// possible move in a played game.
14///
15/// It contains the hashes of all previously visited positions,
16/// and the indices of positions which cannot be repeated in future positions.
17#[derive(Debug, Clone, Eq, PartialEq)]
18pub struct History {
19    hash_history: HashHistory,    // All visited position hashes in order.
20    unrepeatables: Unrepeatables, // Stack of unrepeatable position indices.
21    head: usize,                  // Most recent unrepeatable position.
22}
23
24impl History {
25    /// Create a new empty History.
26    pub fn empty() -> Self {
27        Self {
28            hash_history: HashHistory::new(),
29            unrepeatables: Unrepeatables::new(),
30            head: 0,
31        }
32    }
33    /// Create a new History from a game and a Zobrist Table.
34    pub fn new(game: &Game, ztable: &ZobristTable) -> Self {
35        let mut history = Self::empty();
36        let mut position = game.base_position;
37
38        // Only push a move when it is in the past (original hash after a move is applied).
39        // The final (current) move is not added to history because it is active.
40        for move_ in &game.moves {
41            let hash = ztable.generate_hash((&position).into());
42            let move_info = position.do_legal_move(*move_).expect("move not legal");
43
44            history.push(hash, move_info.is_unrepeatable());
45        }
46
47        debug_assert_eq!(position, game.position);
48        history
49    }
50
51    /// Pushes a new position into the hash history, and updates the most recent unrepeatable
52    /// index if applicable.
53    pub fn push(&mut self, hash: HashKind, is_unrepeatable: bool) {
54        self.hash_history.push(hash);
55
56        if is_unrepeatable {
57            self.unrepeatables.push(self.head);
58            self.head = self.hash_history.len().checked_sub(1).unwrap_or(0);
59        }
60    }
61
62    /// Pops a position from history stack. If the popped item was the most recent unrepeatable,
63    /// then replace it with the previous unrepeatable index.
64    pub fn pop(&mut self) {
65        self.hash_history.pop();
66
67        // If the current head exceeds the limit, replace it with the previous unrepeatable index.
68        if self.head >= self.hash_history.len() {
69            self.head = self.unrepeatables.pop().unwrap_or(0);
70        }
71    }
72
73    /// Returns true if the position occurs at least once in history.
74    /// This is done by only checking the history from the last unrepeatable index to the most recent entry.
75    /// All positions before the index cannot reoccur in the next sequence.
76    pub fn contains(&self, hash: HashKind) -> bool {
77        self.contains_n(hash, 1)
78    }
79
80    /// Returns true if the position occurs in history at least `n` times,
81    /// assuming the position to check may be the next move in this game's history.
82    pub fn contains_n(&self, hash: HashKind, count: usize) -> bool {
83        let mut counter = 0;
84        self.hash_history[self.head..].iter().rev().any(|old_hash| {
85            if *old_hash == hash {
86                counter += 1;
87                if counter >= count {
88                    return true;
89                }
90            }
91            false
92        })
93    }
94
95    /// Returns true if the position occurs twice in history, indicating that the given
96    /// position is the second repetition (position occurs total of three times).
97    pub fn is_threefold_repetition(&self, hash: HashKind) -> bool {
98        self.contains_n(hash, 2)
99    }
100
101    /// Returns true if the position occurs once in history, indicating that
102    /// the given position is the first repetition (position occurs total of two times).
103    pub fn is_twofold_repetition(&self, hash: HashKind) -> bool {
104        self.contains(hash)
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    use crate::Position;
112
113    #[test]
114    fn position_with_no_history() {
115        let ztable = ZobristTable::new();
116        let game = Game::from(Position::start_position());
117
118        let history = History::new(&game, &ztable);
119
120        assert_eq!(history.head, 0);
121        assert_eq!(history.hash_history.len(), 0);
122        assert_eq!(history.unrepeatables.len(), 0);
123    }
124}
blunders_engine/search/history.rs

blunders_engine/search/
history.rs
