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:
- Smart position hashing.
- Exact evaluation of final positions.
- Quiescence search.
- 50 move rule awareness.
- 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
type Evaluator: Evaluator
The type of static evaluator that the implementation works with.
type QsearchResult: QsearchResult
The type of result object that qsearch
returns.
Required Methods
fn from_history(
fen: &str,
moves: &mut Iterator<Item = &str>
) -> Result<Self, IllegalBoard>
fen: &str,
moves: &mut Iterator<Item = &str>
) -> Result<Self, IllegalBoard>
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).
fn hash(&self) -> u64
Returns an almost unique hash value for the position.
The returned value is good for use as transposition table key.
fn board(&self) -> &Board
Returns a reference to the underlying Board
instance.
fn halfmove_clock(&self) -> u8
Returns the number of half-moves since the last piece capture or pawn advance.
fn fullmove_number(&self) -> u16
Returns the number of the current full move.
Starts at 1 and is incremented after black's move.
fn is_check(&self) -> bool
Returns if the side to move is in check.
fn evaluator(&self) -> &Self::Evaluator
Returns a reference to a static evaluator bound to the current position.
fn evaluate_final(&self) -> Value
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.)
fn evaluate_move(&self, m: Move) -> Value
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.
fn qsearch(
&self,
depth: Depth,
lower_bound: Value,
upper_bound: Value,
static_eval: Value
) -> Self::QsearchResult
&self,
depth: Depth,
lower_bound: Value,
upper_bound: Value,
static_eval: Value
) -> Self::QsearchResult
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 betweenDEPTH_MIN
and0
. The quiescence search implementation may decide to perform less thorough analysis whendepth
is smaller than zero.lower_bound
andupper_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 thanVALUE_MIN
.upper_bound
should be greater thanlower_bound
, but no greater thanVALUE_MAX
.
static_eval
should be position's static evaluation, orVALUE_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
.
fn generate_moves<T: AddMove>(&self, moves: &mut T)
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.
fn try_move_digest(&self, move_digest: MoveDigest) -> Option<Move>
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
.
fn null_move(&self) -> Move
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.
fn last_move(&self) -> Move
Returns the last played move.
If the last played move is unknown Move::invalid()
is
returned.
fn do_move(&mut self, m: Move) -> bool
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
.
fn undo_last_move(&mut self)
Takes back the last played move.
Provided Methods
fn legal_moves(&self) -> Vec<Move>
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
impl<T: Qsearch> SearchNode for StdSearchNode<T>