diff options
| -rw-r--r-- | src/grossmeister/search.rs | 16 | ||||
| -rw-r--r-- | src/grossmeister/ttable.rs | 59 |
2 files changed, 60 insertions, 15 deletions
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) + } + } + } |