3 files changed, 42 insertions, 55 deletions

diff --git a/src/grossmeister/mod.rs b/src/grossmeister/mod.rs
index 875f4f8..d45302f 100644
--- a/src/grossmeister/mod.rs
+++ b/src/grossmeister/mod.rs
@@ -3,7 +3,7 @@ use std::sync::{atomic::AtomicBool, Arc};
 use smallvec::{SmallVec, smallvec};
 
 use crate::board::Board;
-use self::{ttable::{TranspositionTable, TTABLE_SIZE}, move_selector::MoveSelector};
+use self::{ttable::TranspositionTable, move_selector::MoveSelector};
 
 mod ttable;
 mod evaluation;
@@ -41,7 +41,7 @@ impl Grossmeister {
     pub fn new(board: Board) -> Self {
         Self {
             board,
-            transposition_table: vec![None; TTABLE_SIZE as usize],
+            transposition_table: TranspositionTable::default(),
             move_selectors: smallvec![MoveSelector::default(); 512],
             should_halt: Arc::new(AtomicBool::new(false)),
             debug: false,
diff --git a/src/grossmeister/search.rs b/src/grossmeister/search.rs
index d9dbdf1..a4b6707 100644
--- a/src/grossmeister/search.rs
+++ b/src/grossmeister/search.rs
@@ -267,7 +267,7 @@ impl Grossmeister {
         let mut pv = Vec::with_capacity(depth as usize);
 
         if depth > 0 {
-            if let Some(transposition) = self.transposition() {
+            if let Some(transposition) = self.transposition().cloned() {
                 if let Some(mov) = transposition.mov {
                     debug_assert!(transposition.depth >= depth, "TTable node should be at least as deep as we expect");
                     if transposition.depth > depth {
@@ -362,7 +362,7 @@ impl Grossmeister {
             }
         }
 
-        println!("info hashfull {}", 1000 * self.transposition_table.iter().filter(|item| item.is_some()).count() / self.transposition_table.len());
+        println!("info hashfull {}", self.table_full());
         if !pv.is_empty() {
             print!("bestmove {}", pv[0]);
             if pv.len() > 1 {
diff --git a/src/grossmeister/ttable.rs b/src/grossmeister/ttable.rs
index 0c6724f..2f673c9 100644
--- a/src/grossmeister/ttable.rs
+++ b/src/grossmeister/ttable.rs
@@ -1,7 +1,5 @@
-use std::cmp::Ordering;
-
+use std::collections::HashMap;
 use crate::moves::Move;
-
 use super::Grossmeister;
 
 /// https://www.chessprogramming.org/Node_Types
@@ -15,21 +13,6 @@ 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
@@ -40,52 +23,56 @@ pub struct TranspositionTableItem {
     pub node_type: NodeType,
 }
 
-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);
-        if depth_ordering != Some(Ordering::Equal) {
-            return depth_ordering
-        }
+pub const TTABLE_SIZE: u64 = 2u64.pow(23);
 
-        self.node_type.partial_cmp(&other.node_type)
-    }
+#[derive(Debug, Clone)]
+pub struct TranspositionTable {
+    pub always_replace: HashMap<u64, TranspositionTableItem>,
+    pub depth_preferred: HashMap<u64, TranspositionTableItem>,
 }
 
-
-pub const TTABLE_SIZE: u64 = 2u64.pow(24);
-pub type TranspositionTable = Vec<Option<TranspositionTableItem>>;
-
-impl Grossmeister {
-    fn transposition_ref(&mut self) -> &mut Option<TranspositionTableItem> {
-        &mut self.transposition_table[(self.board.hash % TTABLE_SIZE) as usize]
+impl Default for TranspositionTable {
+    fn default() -> Self {
+        TranspositionTable {
+            always_replace: HashMap::with_capacity(TTABLE_SIZE as usize),
+            depth_preferred: HashMap::with_capacity(TTABLE_SIZE as usize),
+        }
     }
+}
 
+impl Grossmeister {
     /// 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 == hash {
-                    return Some(*item)
-                }
+    pub fn transposition(&self) -> Option<&TranspositionTableItem> {
+        self.transposition_table.depth_preferred.get(&self.board.hash).and_then(|item| {
+            if item.hash == self.board.hash {
+                Some(item)
+            } else {
                 None
             }
-            None => None
-        }
+        }).or(self.transposition_table.always_replace.get(&self.board.hash).and_then(|item| {
+            if item.hash == self.board.hash {
+                Some(item)
+            } else {
+                None
+            }
+        }))
     }
 
     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)
+        self.transposition_table.always_replace.insert(self.board.hash, transposition);
+        if match self.transposition_table.depth_preferred.get(&self.board.hash) {
+            Some(existing_transposition) => transposition.depth >= existing_transposition.depth,
+            None => true,
+        } {
+            self.transposition_table.depth_preferred.insert(self.board.hash, transposition);
         }
     }
 
+    pub fn table_full(&self) -> u64 {
+        let total_entries = self.transposition_table.always_replace.len() + self.transposition_table.depth_preferred.len();
+        let total_size = TTABLE_SIZE * 2;
+        (1000.0 * (total_entries as f64 / total_size as f64)) as u64
+    }
+
 }