alcibiades 0.3.0

//! 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<usize>) -> 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<Self::Entry>;

    /// 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<T: SearchNode>(&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<Move>,

    /// 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,
}