blunders_engine/search/
minimax.rs

1//! Minimax implementation.
2
3use std::cmp;
4use std::time::Instant;
5
6use crate::coretypes::Color::*;
7use crate::coretypes::{Cp, Move, PlyKind, Square};
8use crate::eval::{evaluate_abs, terminal_abs};
9use crate::movelist::Line;
10use crate::search::SearchResult;
11use crate::Position;
12
13const WHITE: u8 = White as u8;
14const BLACK: u8 = Black as u8;
15
16/// Base minimax call. This function assumes that the current player in the passed position
17/// is the engine.
18/// It returns the best move and score for the position in the search tree.
19pub fn minimax(position: Position, ply: PlyKind) -> SearchResult {
20    assert_ne!(ply, 0);
21
22    let instant = Instant::now();
23    let mut pv = Line::new();
24    let mut nodes = 0;
25
26    let (score, best_move) = minimax_root(position, ply, &mut nodes);
27
28    pv.push(best_move);
29
30    SearchResult {
31        player: position.player,
32        depth: ply,
33        best_move,
34        score,
35        pv,
36        nodes,
37        elapsed: instant.elapsed(),
38        stopped: false,
39        ..Default::default()
40    }
41}
42
43/// Minimax root is almost the same as minimax impl, except it links a Cp score to its node.
44/// It can only operate on positions that are not terminal positions.
45///
46/// Minimax cannot prune any of its children directly because:
47/// 1. Alpha and Beta are inherited as -Inf and +Inf.
48/// 2. Only one of Alpha and Beta can be updated from a nodes children.
49/// Thus, for the root position either Alpha or Beta will stay infinitely bounded,
50/// so no pruning can occur.
51fn minimax_root(mut position: Position, ply: PlyKind, nodes: &mut u64) -> (Cp, Move) {
52    *nodes += 1;
53    let cache = position.cache();
54    let legal_moves = position.get_legal_moves();
55    assert_ne!(ply, 0);
56    assert!(legal_moves.len() > 0);
57
58    let mut best_move = Move::new(Square::D2, Square::D4, None);
59    let mut best_cp;
60
61    if position.player == White {
62        best_cp = Cp::MIN;
63
64        for legal_move in legal_moves {
65            let move_info = position.do_move(legal_move);
66            let move_cp = minimax_impl::<BLACK>(&mut position, ply - 1, nodes);
67            position.undo_move(move_info, cache);
68
69            if move_cp > best_cp {
70                best_cp = move_cp;
71                best_move = legal_move;
72            }
73        }
74    } else {
75        best_cp = Cp::MAX;
76
77        for legal_move in legal_moves {
78            let move_info = position.do_move(legal_move);
79            let move_cp = minimax_impl::<WHITE>(&mut position, ply - 1, nodes);
80            position.undo_move(move_info, cache);
81
82            if move_cp < best_cp {
83                best_cp = move_cp;
84                best_move = legal_move;
85            }
86        }
87    }
88
89    (best_cp, best_move)
90}
91
92fn minimax_impl<const COLOR: u8>(position: &mut Position, ply: PlyKind, nodes: &mut u64) -> Cp {
93    *nodes += 1;
94    let cache = position.cache();
95    let legal_moves = position.get_legal_moves();
96    let num_moves = legal_moves.len();
97
98    // Stop at terminal node: Checkmate/Stalemate/last depth.
99    if num_moves == 0 {
100        return terminal_abs(position);
101    } else if ply == 0 {
102        return evaluate_abs(position);
103    }
104
105    let mut best_cp;
106
107    if COLOR == White as u8 {
108        best_cp = Cp::MIN;
109
110        for legal_move in legal_moves {
111            let move_info = position.do_move(legal_move);
112            let move_cp = minimax_impl::<BLACK>(position, ply - 1, nodes);
113            position.undo_move(move_info, cache);
114            best_cp = cmp::max(best_cp, move_cp);
115        }
116    } else {
117        best_cp = Cp::MAX;
118
119        for legal_move in legal_moves {
120            let move_info = position.do_move(legal_move);
121            let move_cp = minimax_impl::<WHITE>(position, ply - 1, nodes);
122            position.undo_move(move_info, cache);
123            best_cp = cmp::min(best_cp, move_cp);
124        }
125    }
126
127    best_cp
128}
blunders_engine/search/minimax.rs

blunders_engine/search/
minimax.rs
