refactor: use vector-based table implementation

2 files changed, 40 insertions, 29 deletions

diff --git a/src/grossmeister/mod.rs b/src/grossmeister/mod.rs
index d45302f..1f1a141 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, move_selector::MoveSelector};
+use self::{ttable::MasterTable, move_selector::MoveSelector};
 
 mod ttable;
 mod evaluation;
@@ -23,7 +23,7 @@ pub struct Grossmeister {
     /// Transposition table is a cache of all positions that Grossmeister
     /// has seen and evaluated.
     /// It's indexex by Zobrist hash of a position mod size
-    transposition_table: TranspositionTable,
+    transposition_table: MasterTable,
 
     move_selectors: SmallVec<[MoveSelector; 0]>,
 
@@ -41,7 +41,7 @@ impl Grossmeister {
     pub fn new(board: Board) -> Self {
         Self {
             board,
-            transposition_table: TranspositionTable::default(),
+            transposition_table: MasterTable::default(),
             move_selectors: smallvec![MoveSelector::default(); 512],
             should_halt: Arc::new(AtomicBool::new(false)),
             debug: false,
diff --git a/src/grossmeister/ttable.rs b/src/grossmeister/ttable.rs
index b6b1a2c..b1eeec3 100644
--- a/src/grossmeister/ttable.rs
+++ b/src/grossmeister/ttable.rs
@@ -1,5 +1,5 @@
-use std::collections::HashMap;
 use crate::moves::Move;
+
 use super::Grossmeister;
 
 /// https://www.chessprogramming.org/Node_Types
@@ -26,48 +26,60 @@ pub struct TranspositionTableItem {
 pub const TTABLE_SIZE: u64 = 2u64.pow(23);
 
 #[derive(Debug, Clone)]
-pub struct TranspositionTable {
-    pub always_replace: HashMap<u64, TranspositionTableItem>,
-    pub depth_preferred: HashMap<u64, TranspositionTableItem>,
+struct TranspositionTable {
+    table: Vec<Option<TranspositionTableItem>>,
 }
 
 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),
+        Self {
+            table: vec![None; TTABLE_SIZE as usize]
         }
     }
 }
 
-impl Grossmeister {
-    /// Find current position in Transposition Table
+impl TranspositionTable {
+    fn set(&mut self, hash: u64, item: TranspositionTableItem) {
+        self.table[(hash % TTABLE_SIZE) as usize] = Some(item);
+    }
+
     /// This operation is safe from collisions since it compares the *full* hash
-    pub fn transposition(&self) -> Option<&TranspositionTableItem> {
-        let hash = self.board.hash % TTABLE_SIZE;
-        self.transposition_table.depth_preferred.get(&hash).and_then(|item| {
-            if item.hash == self.board.hash {
+    /// TODO: only compare the other half of the hash
+    fn get(&self, hash: u64) -> Option<&TranspositionTableItem> {
+        self.table[(hash % TTABLE_SIZE) as usize].as_ref().and_then(|item| {
+            if item.hash == hash {
                 Some(item)
             } else {
                 None
             }
-        }).or(self.transposition_table.always_replace.get(&hash).and_then(|item| {
-            if item.hash == self.board.hash {
-                Some(item)
-            } else {
-                None
-            }
-        }))
+        })
+    }
+
+    fn len(&self) -> usize {
+        self.table.iter().filter(|item| item.is_some()).count()
+    }
+}
+
+#[derive(Debug, Default, Clone)]
+pub struct MasterTable {
+    always_replace: TranspositionTable,
+    depth_preferred: TranspositionTable,
+}
+
+impl Grossmeister {
+    pub fn transposition(&self) -> Option<&TranspositionTableItem> {
+        self.transposition_table.depth_preferred.get(self.board.hash)
+            .or(self.transposition_table.always_replace.get(self.board.hash))
     }
 
     pub fn store_transposition(&mut self, transposition: TranspositionTableItem) {
-        let hash = transposition.hash % TTABLE_SIZE;
-        self.transposition_table.always_replace.insert(hash, transposition);
-        if match self.transposition_table.depth_preferred.get(&hash) {
+        self.transposition_table.always_replace.set(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,
+            None => true
         } {
-            self.transposition_table.depth_preferred.insert(hash, transposition);
+            self.transposition_table.depth_preferred.set(self.board.hash, transposition)
         }
     }
 
@@ -76,5 +88,4 @@ impl Grossmeister {
         let total_size = TTABLE_SIZE * 2;
         (1000.0 * (total_entries as f64 / total_size as f64)) as u64
     }
-
 }