From 2f7a449038fb5dbc620e9f156c24bb6fa318d8fb Mon Sep 17 00:00:00 2001
From: eug-vs <eugene@eug-vs.xyz>
Date: Mon, 4 Sep 2023 10:23:56 +0300
Subject: feat: define strict ordering between ttable items

---
 src/grossmeister/search.rs | 16 ++++++-------
 src/grossmeister/ttable.rs | 59 ++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 60 insertions(+), 15 deletions(-)

(limited to 'src/grossmeister')

diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs
index d0fddbb..23bcdfa 100644
--- a/src/grossmeister/search.rs
+++ b/src/grossmeister/search.rs
@@ -96,7 +96,6 @@ impl Grossmeister {
                 } else {
                     // After we have PV-node (that raised alpha) all other nodes will be searched
                     // with zero-window first to confirm this assumption
-                    // TODO: changing 0.001 -> 0.0001 leads to a weird bug
                     let score = self.negamax_search(-(alpha + 0.001), -alpha, depth_left - 1, root_distance + 1);
                     // In case some of the other nodes raises alpha, then it's true PV node now,
                     // let's research with full window to find its exact value
@@ -110,10 +109,10 @@ impl Grossmeister {
                 self.board.unmake_move(mov, captured_piece, ep_target_before, castling_rights_before, hash_before);
 
                 if score >= beta {
-                    self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                    self.store_transposition(TranspositionTableItem {
                         hash: self.board.hash,
                         mov,
-                        depth: depth_left, // TODO: should be actual depth searched
+                        depth: depth_left,
                         node_type: NodeType::Cut,
                         score,
                     });
@@ -128,18 +127,18 @@ impl Grossmeister {
                     alpha = score;
                     should_pv_search = false; // Once we have PV-node we can start zero-window searching
 
-                    self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                    self.store_transposition(TranspositionTableItem {
                         hash: self.board.hash,
                         mov,
-                        depth: depth_left, // TODO: should be actual depth searched
+                        depth: depth_left,
                         node_type: NodeType::PV,
                         score,
                     });
-                } else if self.transposition().is_none() {
-                    self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] = Some(TranspositionTableItem {
+                } else {
+                    self.store_transposition(TranspositionTableItem {
                         hash: self.board.hash,
                         mov,
-                        depth: depth_left, // TODO: should be actual depth searched
+                        depth: depth_left,
                         node_type: NodeType::All,
                         score,
                     });
@@ -230,6 +229,7 @@ impl Grossmeister {
         let mut pv = Vec::with_capacity(depth as usize);
 
         if let Some(transposition) = self.transposition() {
+            debug_assert!(transposition.node_type == NodeType::PV);
             let mov = transposition.mov;
             let ep_target_before = self.board.ep_target;
             let castling_rights_before = self.board.castling_rights;
diff --git a/src/grossmeister/ttable.rs b/src/grossmeister/ttable.rs
index 87099c2..0420e22 100644
--- a/src/grossmeister/ttable.rs
+++ b/src/grossmeister/ttable.rs
@@ -1,3 +1,5 @@
+use std::cmp::Ordering;
+
 use crate::moves::Move;
 
 use super::Grossmeister;
@@ -13,6 +15,21 @@ pub enum NodeType {
     All,
 }
 
+impl NodeType {
+    fn cmp_order(&self) -> u8 {
+        match self {
+            NodeType::PV => 2,
+            NodeType::Cut => 1,
+            NodeType::All => 0,
+        }
+    }
+}
+impl PartialOrd for NodeType {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp_order().cmp(&other.cmp_order()))
+    }
+}
+
 #[derive(Debug, PartialEq, Clone, Copy)]
 pub struct TranspositionTableItem {
     /// Zobrist hash of this position
@@ -23,18 +40,34 @@ pub struct TranspositionTableItem {
     pub node_type: NodeType,
 }
 
-pub const TTABLE_SIZE: u64 = 2u64.pow(24);
+impl PartialOrd for TranspositionTableItem {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        // Order by depth first, then node type
+        let depth_ordering = self.depth.partial_cmp(&other.depth);
+        match depth_ordering {
+            Some(Ordering::Equal) => self.node_type.partial_cmp(&other.node_type),
+            _ => depth_ordering,
+        }
+    }
+}
 
-pub type TranspositionTable = Vec<Option<TranspositionTableItem>>;
 
+pub const TTABLE_SIZE: u64 = 2u64.pow(24);
+pub type TranspositionTable = Vec<Option<TranspositionTableItem>>;
 
 impl Grossmeister {
-    /// Find current transposition in Transposition Table
-    pub fn transposition(&self) -> Option<TranspositionTableItem> {
-        match self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize] {
+    fn transposition_ref(&mut self) -> &mut Option<TranspositionTableItem> {
+        &mut self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize]
+    }
+
+    /// Find current position in Transposition Table
+    /// This operation is safe from collisions since it compares the *full* hash
+    pub fn transposition(&mut self) -> Option<TranspositionTableItem> {
+        let hash = self.board.hash;
+        match self.transposition_ref() {
             Some(item) => {
-                if item.hash == self.board.hash {
-                    return Some(item)
+                if item.hash == hash {
+                    return Some(*item)
                 }
                 None
             }
@@ -42,4 +75,16 @@ impl Grossmeister {
         }
     }
 
+    pub fn store_transposition(&mut self, transposition: TranspositionTableItem) {
+        let transposition_ref = self.transposition_ref();
+        match transposition_ref {
+            Some(existing_transposition) => {
+                if transposition >= *existing_transposition {
+                    *transposition_ref = Some(transposition)
+                }
+            }
+            None => *transposition_ref = Some(transposition)
+        }
+    }
+
 }
-- 
cgit v1.2.3