diff options
| -rw-r--r-- | src/grossmeister/mod.rs | 4 | ||||
| -rw-r--r-- | src/grossmeister/search.rs | 4 | ||||
| -rw-r--r-- | src/grossmeister/ttable.rs | 89 |
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 + } + } |