From 3522398f7a456b400dc48de4c202a013490cd4fc Mon Sep 17 00:00:00 2001
From: eug-vs <eugene@eug-vs.xyz>
Date: Wed, 25 Jan 2023 05:18:38 +0300
Subject: feat: use transposition table in negamax

---
 src/board/engine.rs | 52 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 45 insertions(+), 7 deletions(-)

(limited to 'src/board/engine.rs')

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);
-- 
cgit v1.2.3