blunders_engine/
perft.rs

1//! Performance Test
2//!
3//! [Perft](https://www.chessprogramming.org/Perft)
4//!
5//! A simple debugging and testing function used to count
6//! the number of nodes at a specific depth.
7
8use std::ops::{Add, AddAssign};
9use std::sync::{Arc, Mutex};
10use std::thread;
11
12use crate::coretypes::PlyKind;
13use crate::movelist::MoveList;
14use crate::position::Position;
15
16/// Debugging information about results of perft test.
17/// nodes: Number of nodes at lowest depth of perft.
18#[derive(Copy, Clone, Debug, Eq, PartialEq)]
19pub struct PerftInfo {
20    pub nodes: u64,
21}
22
23impl PerftInfo {
24    fn new(nodes: u64) -> Self {
25        PerftInfo { nodes }
26    }
27}
28
29impl Add for PerftInfo {
30    type Output = Self;
31    fn add(self, rhs: Self) -> Self::Output {
32        PerftInfo {
33            nodes: self.nodes + rhs.nodes,
34        }
35    }
36}
37
38impl AddAssign for PerftInfo {
39    fn add_assign(&mut self, rhs: Self) {
40        self.nodes += rhs.nodes;
41    }
42}
43
44// Count the number of nodes at a certain depth.
45// This ignores higher terminal nodes.
46// In other words, it counts the number of paths to the given depth.
47pub fn perft(mut position: Position, ply: PlyKind, threads: usize) -> PerftInfo {
48    // Guard easy to calculate inputs.
49    if ply == 0 {
50        // Ever only 1 position at 0 ply.
51        return PerftInfo::new(1);
52    } else if ply <= 2 || threads <= 1 {
53        // Simple enough to not require threads, or single threaded.
54        return perft_recurse(&mut position, ply);
55    }
56    debug_assert!(ply > 2);
57    debug_assert!(threads > 1);
58
59    let legal_moves = position.get_legal_moves();
60    // Guard no moves to search.
61    if legal_moves.len() == 0 {
62        return PerftInfo::new(0);
63    }
64
65    let legal_moves = Arc::new(Mutex::new(legal_moves));
66    let total_perft_info = Arc::new(Mutex::new(PerftInfo::new(0)));
67    let mut handles = Vec::new();
68
69    // Create threads to process partitioned moves.
70    for _ in 0..threads {
71        // Arcs
72        let position = position.clone();
73        let legal_moves = legal_moves.clone();
74        let total_perft_info = total_perft_info.clone();
75
76        let handle = thread::spawn(move || {
77            perft_executor(position, ply, legal_moves, total_perft_info);
78        });
79
80        handles.push(handle);
81    }
82
83    // Wait for all handles to finish.
84    for handle in handles {
85        handle.join().unwrap();
86    }
87
88    // Move out of Mutex, moved out of arc.
89    Arc::try_unwrap(total_perft_info)
90        .unwrap()
91        .into_inner()
92        .unwrap()
93}
94
95/// perft_executor works by stealing one move at a time from given moves list and running perft on that move.
96/// When there are no moves left to steal, this function stores the data it has collected so far and returns.
97/// params:
98/// position - position to evaluate moves on.
99/// ply - ply of provided position. Must be greater than 1.
100/// moves - synchronous access to list of moves to steal from. Moves must be valid for given position.
101/// perft_info - place to store information post execution.
102#[inline(always)]
103fn perft_executor(
104    mut position: Position,
105    ply: PlyKind,
106    moves: Arc<Mutex<MoveList>>,
107    total_perft_info: Arc<Mutex<PerftInfo>>,
108) {
109    debug_assert!(ply > 1);
110    let mut perft_info = PerftInfo::new(0);
111    let mut maybe_move = { moves.lock().unwrap().pop() };
112    let cache = position.cache();
113
114    while let Some(move_) = maybe_move {
115        let move_info = position.do_move(move_);
116        perft_info += perft_recurse(&mut position, ply - 1);
117        position.undo_move(move_info, cache);
118        maybe_move = moves.lock().unwrap().pop();
119    }
120
121    *total_perft_info.lock().unwrap() += perft_info;
122}
123
124/// Ply must be non-zero.
125fn perft_recurse(position: &mut Position, ply: PlyKind) -> PerftInfo {
126    debug_assert_ne!(ply, 0);
127    let cache = position.cache();
128    if ply == 1 {
129        // If we reach the depth before the end,
130        // return the count of legal moves.
131        PerftInfo::new(position.get_legal_moves().len() as u64)
132    } else {
133        let legal_moves = position.get_legal_moves();
134        let mut perft_info = PerftInfo::new(0);
135        for legal_move in legal_moves {
136            let move_info = position.do_move(legal_move);
137            perft_info += perft_recurse(position, ply - 1);
138            position.undo_move(move_info, cache);
139        }
140        perft_info
141    }
142}
blunders_engine/perft.rs

blunders_engine/
perft.rs
