diff options
| -rw-r--r-- | benches/negamax.rs | 7 | ||||
| -rw-r--r-- | src/board/engine.rs | 52 | ||||
| -rw-r--r-- | src/board/mod.rs | 12 | ||||
| -rw-r--r-- | src/board/ttable.rs | 25 | ||||
| -rw-r--r-- | src/moves.rs | 2 |
5 files changed, 85 insertions, 13 deletions
diff --git a/benches/negamax.rs b/benches/negamax.rs index 33c90ea..0c952d6 100644 --- a/benches/negamax.rs +++ b/benches/negamax.rs @@ -8,13 +8,14 @@ fn main() { let depth = 4; let start = Instant::now(); - let (eval, pv) = board.negamax_search(-INFINITY, INFINITY, depth); - println!("Negamax search (depth = {}) finished in {:?}: {:?}", depth, start.elapsed(), eval); + let (score, pv) = board.negamax_search(-INFINITY, INFINITY, depth); + println!("Negamax search (depth = {}) finished in {:?}: {:?}", depth, start.elapsed(), score); board.print(); for mov in pv { println!("{:?}", mov); - println!("Eval for {:?}: {}", board.color(), board.evaluate(None)); + println!("Score for {:?}: {}", board.color(), board.evaluate(None)); board.make_move(mov); board.print(); } + println!("Score for {:?}: {}", board.color(), board.evaluate(None)); } diff --git a/src/board/engine.rs b/src/board/engine.rs index 73c57af..fb06fa4 100644 --- a/src/board/engine.rs +++ b/src/board/engine.rs @@ -1,5 +1,7 @@ use crate::{bitboard::pop_count, board::*}; +use super::ttable::{NodeType, TranspositionTableItem}; + #[derive(Debug, Default, PartialEq)] pub struct PerftResult { leaf_nodes: u64, @@ -115,10 +117,23 @@ impl Board { } pub fn negamax_search(&mut self, mut alpha: f32, beta: f32, depth_left: u8) -> (f32, Vec<Move>) { + let transposition = self.transposition_table[(self.hash % TTABLE_SIZE) as usize]; + let mut principal_variation = Vec::new(); let color = self.color(); - let moves = self.generate_pseudolegal_moves(color); + let moves = match transposition { + Some(item) => { + // println!("Cache hit! {:?}", item); + + if item.node_type == NodeType::PV && item.depth >= depth_left { + vec![item.best_move] + } else { + self.generate_pseudolegal_moves(color) + } + } + None => self.generate_pseudolegal_moves(color), + }; if depth_left == 0 { return (self.evaluate(Some(moves.len() as f32)), principal_variation); @@ -131,18 +146,41 @@ impl Board { let captured_piece = self.make_move(mov); if !self.is_king_in_check(color) { - let (mut evaluation, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1); - evaluation *= -1.; + let (mut score, mut subtree_pv) = self.negamax_search(-beta, -alpha, depth_left - 1); + score *= -1.; self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); - if evaluation >= beta { - return (beta, principal_variation); // Fail-hard beta-cutoff + if score >= beta { + self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.hash, + best_move: mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::Cut, + score, + }); + return (beta, principal_variation); } - if evaluation > alpha { - alpha = evaluation; + if score > alpha { + alpha = score; principal_variation = Vec::with_capacity(depth_left as usize); principal_variation.push(mov); principal_variation.append(&mut subtree_pv); + + self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.hash, + best_move: mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::PV, + score, + }); + } else { + self.transposition_table[(self.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem { + hash: self.hash, + best_move: mov, + depth: depth_left, // TODO: should be actual depth searched + node_type: NodeType::All, + score, + }); } } else { self.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before); diff --git a/src/board/mod.rs b/src/board/mod.rs index a8166a1..2ff7f9c 100644 --- a/src/board/mod.rs +++ b/src/board/mod.rs @@ -1,13 +1,16 @@ use rand::Rng; use crate::{bitboard::{Bitboard, serialize_bitboard, bitscan, pop_count}, moves::{Move, MoveKind}, attacks::Attacks, square::Square}; + +use self::ttable::{TranspositionTable, TTABLE_SIZE}; mod engine; +mod ttable; pub enum CastlingSide { King, Queen, } -#[derive(Debug, Clone, PartialEq, Eq)] +#[derive(Debug, Clone, PartialEq)] pub struct Board { pub pieces: [Bitboard; 12], @@ -26,6 +29,7 @@ pub struct Board { /// Zobrist hash of the current position pub hash: u64, + transposition_table: TranspositionTable, zobrist_seed: [u64; 781], attacks: Attacks, } @@ -121,6 +125,7 @@ impl Board { castling_rights: [[true; 2]; 2], // TODO: actualy parse from FEN ep_target: None, // TODO: parse from FEN hash: 0, + transposition_table: vec![None; TTABLE_SIZE as usize], zobrist_seed, }; board.update_occupancy(); @@ -524,7 +529,10 @@ impl Board { self.hash ^= self.zobrist_seed[source_piece * 12 + mov.target as usize]; PieceType::from(source_piece) }, - None => panic!("Move is malformed: source piece not found"), + None => { + self.print(); + panic!("{:?} is malformed: source piece not found", mov); + } }; // When castling, also move a rook diff --git a/src/board/ttable.rs b/src/board/ttable.rs new file mode 100644 index 0000000..3a103da --- /dev/null +++ b/src/board/ttable.rs @@ -0,0 +1,25 @@ +use crate::moves::Move; + +/// https://www.chessprogramming.org/Node_Types +#[derive(Debug, PartialEq, Clone, Copy)] +pub enum NodeType { + /// Principal variation node - exact score + PV, + /// Fail-high + Cut, + /// Fail-low + All, +} + +#[derive(Debug, PartialEq, Clone, Copy)] +pub struct TranspositionTableItem { + /// Zobrist hash of this position + pub hash: u64, + pub best_move: Move, + pub depth: u8, + pub score: f32, + pub node_type: NodeType, +} + +pub const TTABLE_SIZE: u64 = 2u64.pow(24); +pub type TranspositionTable = Vec<Option<TranspositionTableItem>>; diff --git a/src/moves.rs b/src/moves.rs index f31d864..66a3be1 100644 --- a/src/moves.rs +++ b/src/moves.rs @@ -9,7 +9,7 @@ pub enum MoveKind { DoublePush, } -#[derive(Debug, Clone, Copy)] +#[derive(Debug, Clone, Copy, PartialEq, Eq)] pub struct Move { pub source: Square, pub target: Square, |