feat: define strict ordering between ttable items

1 files changed, 52 insertions, 7 deletions

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)
+        }
+    }
+
 }