//! Defines types and traits related to transposition tables. use std::cmp::min; use moves::{Move, MoveDigest}; use value::*; use depth::*; use search_node::SearchNode; /// `BOUND_EXACT`, `BOUND_LOWER`, `BOUND_UPPER`, or `BOUND_NONE`. /// /// For the majority of chess positions our evaluations will be more /// or less inaccurate, and there is nothing we can do about it. But /// sometimes we know that a given evaluation is probably inaccurate, /// and we know the sign of the error. `BoundType` defines the /// direction of such **known inaccuracies**. /// /// # Constants: /// /// * `BOUND_EXACT` means that the evaluation is exact (as far as we know). /// /// * `BOUND_LOWER` means that the real value is greater or equal to /// the evaluation (as far as we know). /// /// * `BOUND_UPPER` means that the real value is lesser or equal to /// the evaluation (as far as we know). /// /// * `BOUND_NONE` means that the real value can be anything. pub type BoundType = u8; pub const BOUND_NONE: BoundType = 0; pub const BOUND_LOWER: BoundType = 0b01; pub const BOUND_UPPER: BoundType = 0b10; pub const BOUND_EXACT: BoundType = BOUND_UPPER | BOUND_LOWER; /// A trait for transposition tables. /// /// Chess programs, during their brute-force search, encounter the /// same positions again and again, but from different sequences of /// moves, which is called a "transposition". When the search /// encounters a transposition, it is beneficial to "remember" what /// was determined last time the position was examined, rather than /// redoing the entire search again. For this reason, chess programs /// have a transposition table, which is a large hash table storing /// information about positions previously searched, how deeply they /// were searched, and what we concluded about them. To implement your /// own transposition table, you must define a type that implements /// the `Ttable` trait. pub trait Ttable: Sync + Send + 'static { type Entry: TtableEntry; /// Creates a new transposition table. /// /// `size_mb` is the desired size in Mbytes. fn new(size_mb: Option) -> Self; /// Signals that a new search is about to begin. fn new_search(&self); /// Stores data by key. /// /// After being stored, the data can be retrieved by `probe`. This /// is not guaranteed though, because the entry might have been /// overwritten in the meantime. fn store(&self, key: u64, data: Self::Entry); /// Probes for data by key. fn probe(&self, key: u64) -> Option; /// Removes all entries in the table. fn clear(&self); /// Extracts the principal variation for a given position. /// /// The principal variation (PV) is the sequence of moves that the /// engine considers best and therefore expects to be played. fn extract_pv(&self, position: &T) -> Variation { let mut p = position.clone(); let mut our_turn = true; let mut moves = Vec::with_capacity(32); let mut root_value = VALUE_UNKNOWN; let mut value = VALUE_MAX; let mut bound = BOUND_UPPER; let mut depth = DEPTH_MAX + 1; 'move_extraction: while let Some(e) = self.probe(p.hash()) { depth = min(depth - 1, e.depth()); if e.bound() == BOUND_EXACT || root_value == VALUE_UNKNOWN && e.bound() != BOUND_NONE { // In half of the cases the value is from other side's perspective. if our_turn { value = e.value(); bound = e.bound(); } else { value = -e.value(); bound = match e.bound() { BOUND_UPPER => BOUND_LOWER, BOUND_LOWER => BOUND_UPPER, b => b, }; } assert!(value != VALUE_UNKNOWN); // Set the root value on the first iteration. if root_value == VALUE_UNKNOWN { root_value = value; } // Consider adding current entry's hash move to the // PV. There are 2 conditions for this: // // 1) The depth limit has not been reached yet. // 2) The value has not diverged from the root value. if depth > 0 && match root_value { v if v < VALUE_EVAL_MIN => { v as isize == value as isize + moves.len() as isize } v if v > VALUE_EVAL_MAX => { v as isize == value as isize - moves.len() as isize } v => v == value, } { // Verify that the hash move is legal. if let Some(m) = p.try_move_digest(e.move_digest()) { if p.do_move(m) { moves.push(m); // Note: we continue expanding the PV only on best moves. if e.bound() == BOUND_EXACT { our_turn = !our_turn; continue 'move_extraction; } } } } } break 'move_extraction; } Variation { value: if root_value != VALUE_UNKNOWN { root_value } else { value }, bound: bound, moves: moves, } } } /// A trait for transposition table entries. pub trait TtableEntry: Copy + Send + 'static { /// Creates a new instance. /// /// * `value` -- The value assigned to the position. Must be /// between `VALUE_MIN` and `VALUE_MAX`. /// /// * `bound` -- The accuracy of the assigned value. /// /// * `depth` -- The search depth for the assigned value. Must be /// between `DEPTH_MIN` and `DEPTH_MAX`. fn new(value: Value, bound: BoundType, depth: Depth) -> Self; /// Returns the value assigned to the position. fn value(&self) -> Value; /// Returns the accuracy of the assigned value. fn bound(&self) -> BoundType; /// Returns the search depth for the assigned value. fn depth(&self) -> Depth; /// Consumes the instance and returns a new instance with updated /// best/refutation move digest. fn set_move_digest(self, move_digest: MoveDigest) -> Self; /// Returns the best/refutation move digest assigned to the /// position, or `MoveDigest::invalid()` if no move is available. fn move_digest(&self) -> MoveDigest; /// Consumes the instance and returns a new instance with updated /// static evaluation. /// /// **Important note:** This method will do nothing if the /// underlying memory structure has no field allotted for static /// evaluation. #[allow(unused_variables)] fn set_static_eval(self, static_eval: Value) -> Self { self } /// Returns the static evaluation assigned to the position, or /// `VALUE_UNKNOWN`. fn static_eval(&self) -> Value { VALUE_UNKNOWN } /// Returns the relative importance of the entry. /// /// Transposition tables may use this method to improve their /// record replacement strategy. Normally, when possible, entries /// with lower `importance` will be replaced before entries with /// higher `importance`. Therefore this method should try to /// return higher values for entries that are move likely to save /// CPU work in the future. For example, positions analyzed to a /// higher depth are probably more "important" than those analyzed /// to a lower depth. #[inline] fn importance(&self) -> i16 { let depth = self.depth() as i16; match self.bound() { BOUND_EXACT => depth + 1, BOUND_NONE => DEPTH_MIN as i16 - 1, _ => depth, } } } /// A sequence of moves from some starting position, together with the /// value assigned to the final position. #[derive(Clone, Debug)] pub struct Variation { /// A sequence of moves from some starting position. pub moves: Vec, /// The value assigned to the final position. /// /// The value is from the point of view of player that has the /// move in the starting position. pub value: Value, /// The accuracy of the assigned value. pub bound: BoundType, }