Trait alcibiades::SearchNode [−] [src]

pub trait SearchNode: Clone + SetOption + Send + 'static {
    type Evaluator: Evaluator;
    type QsearchResult: QsearchResult;
    fn from_history(
        fen: &str, 
        moves: &mut Iterator<Item = &str>
    ) -> Result<Self, IllegalBoard>;
    fn hash(&self) -> u64;
    fn board(&self) -> &Board;
    fn halfmove_clock(&self) -> u8;
    fn fullmove_number(&self) -> u16;
    fn is_check(&self) -> bool;
    fn evaluator(&self) -> &Self::Evaluator;
    fn evaluate_final(&self) -> Value;
    fn evaluate_move(&self, m: Move) -> Value;
    fn qsearch(
        &self, 
        depth: Depth, 
        lower_bound: Value, 
        upper_bound: Value, 
        static_eval: Value
    ) -> Self::QsearchResult;
    fn generate_moves<T: AddMove>(&self, moves: &mut T);
    fn try_move_digest(&self, move_digest: MoveDigest) -> Option<Move>;
    fn null_move(&self) -> Move;
    fn last_move(&self) -> Move;
    fn do_move(&mut self, m: Move) -> bool;
    fn undo_last_move(&mut self);

    fn legal_moves(&self) -> Vec<Move> { ... }
}

A trait for chess positions -- a convenient interface for the tree-searching algorithm.

A SearchNode can generate all legal moves in the current position, play a selected move and take it back. It can also quickly (without doing extensive tree-searching) evaluate the chances of the sides, so that the tree-searching algorithm can use this evaluation to assign realistic game outcomes to its leaf nodes. SearchNode improves on MoveGenerator by adding the following functionality:

  1. Smart position hashing.
  2. Exact evaluation of final positions.
  3. Quiescence search.
  4. 50 move rule awareness.
  5. Threefold/twofold repetition detection.

Important note: Repeating positions are considered a draw after the first repetition, not after the second one as the chess rules prescribe. In order to compensate for that, SearchNode::from_history "forgets" all positions that have occurred exactly once. Also, the newly created instance is never deemed a draw due to repetition or rule-50.

Associated Types

The type of static evaluator that the implementation works with.

The type of result object that qsearch returns.

Required Methods

Instantiates a new chess position from playing history.

fen should be the Forsyth–Edwards Notation of a legal starting position. moves should be an iterator over all the moves that were played from that position. The move format is long algebraic notation. Examples: e2e4, e7e5, e1g1 (white short castling), e7e8q (for promotion).

Returns an almost unique hash value for the position.

The returned value is good for use as transposition table key.

Returns a reference to the underlying Board instance.

Returns the number of half-moves since the last piece capture or pawn advance.

Returns the number of the current full move.

Starts at 1 and is incremented after black's move.

Returns if the side to move is in check.

Returns a reference to a static evaluator bound to the current position.

Evaluates a final position.

In final positions this method will return the correct value of the position (0 for a draw, VALUE_MIN for a checkmate). A position is guaranteed to be final if generate_moves method generates no legal moves. (It may generate some pseudo-legal moves, but if none of them is legal, then the position is final.)

Returns the likely evaluation change (material) to be lost or gained as a result of a given move.

This method performs static exchange evaluation (SEE). It examines the consequence of a series of exchanges on the destination square after a given move. A positive returned value indicates a "winning" move. For example, "PxQ" will always be a win, since the pawn side can choose to stop the exchange after its pawn is recaptured, and still be ahead. SEE is just an evaluation calculated without actually trying moves on the board, and therefore the returned value might be incorrect.

The move passed to this method must have been generated by generate_moves, try_move_digest, or null_move methods for the current position on the board.

Performs quiescence search and returns a result.

Quiescence search is a restricted search which considers only a limited set of moves (for example: winning captures, pawn promotions to queen, check evasions). The goal is to statically evaluate only "quiet" positions (positions where there are no winning tactical moves to be made). Although this search can cheaply and correctly resolve many simple tactical issues, it is completely blind to the more complex ones.

  • depth is the depth at which the main search stops and the quiescence search takes on. It should be between DEPTH_MIN and 0. The quiescence search implementation may decide to perform less thorough analysis when depth is smaller than zero.

  • lower_bound and upper_bound together give the interval within which an as precise as possible evaluation is required. If during the calculation is determined that the exact evaluation is outside of this interval, this method may return a value that is closer to the the interval bounds than the exact evaluation, but always staying on the correct side of the interval (i.e. "fail-soft" semantics).

    • lower_bound should be no lesser than VALUE_MIN.

    • upper_bound should be greater than lower_bound, but no greater than VALUE_MAX.

  • static_eval should be position's static evaluation, or VALUE_UNKNOWN.

Important note: This method will return a reliable result even when the side to move is in check. Repeated and rule-50 positions are always evaluated to 0.

Generates all legal moves, possibly including some pseudo-legal moves too.

A pseudo-legal move is a move that is otherwise legal, except it might leave the king in check. Every legal move is a pseudo-legal move, but not every pseudo-legal move is legal. The generated moves will be added to moves. If all of the moves generated by this methods are illegal (this means that do_move(m) returns false for all of them), then the position is final, and evaluate_final() will return its correct value.

Important note: No moves will be generated in repeated and rule-50 positions.

Verifies if the supplied move digest represents a proper move.

If a move m exists that would be generated by generate_moves if called for the current position, and for that move m.digest() equals the supplied move digest, this method will return Some(m). Otherwise it will return None. This is useful when playing moves from the transposition table, without calling generate_moves.

Returns a null move.

"Null move" is a pseudo-move that changes only the side to move. It is sometimes useful to include a speculative null move in the search tree so as to achieve more aggressive pruning. Null moves are represented as king's moves for which the origin and destination squares are the same.

Returns the last played move.

If the last played move is unknown Move::invalid() is returned.

Plays a move on the board.

It the move leaves the king in check, false is returned without updating the board. Otherwise the board is updated and true is returned. The move passed to this method must have been generated by generate_moves, try_move_digest, or null_move methods for the current position on the board.

Important note: For null moves, if the position is a draw due to repetition or rule-50, do_move will return false.

Takes back the last played move.

Provided Methods

Returns all legal moves in the position.

No moves are returned for repeated and rule-50 positions.

Important note: This method is slower than generate_moves because it ensures that all returned moves are legal.

Implementors