feat: use transposition table in negamax

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,