//! Defines the `MoveGenerator` trait. use std::mem::uninitialized; use std::cmp::max; use uci::SetOption; use board::*; use moves::*; use value::*; use evaluator::Evaluator; use bitsets::*; use utils::BoardGeometry; /// A trait for move generators. /// /// A `MoveGenerator` holds a chess position and can: /// /// * Calculate Zobrist hashes. /// /// * Find which pieces and pawns attack a given square. /// /// * Find if the side to move is in check. /// /// * Generate all legal moves, or a subset of all legal moves in the /// current position. /// /// * Generate a null move. /// /// * Verify if a random move digest represents a proper move. /// /// * Play a selected move and take it back. /// /// * Provide a static evaluator bound to the current position. /// /// * Perform static exchange evaluation for the generated moves. /// /// **Important note:** `MoveGenerator` is unaware of repeating /// positions and rule-50. pub trait MoveGenerator: Clone + SetOption + Send + 'static { /// The type of static evaluator that the implementation works /// with. type Evaluator: Evaluator; /// Creates a new instance, consuming the supplied `Board` /// instance. /// /// Returns `Err(IllegalBoard)` if the position is illegal. fn from_board(board: Board) -> Result; /// Returns a reference to the underlying `Board` instance. fn board(&self) -> &Board; /// Returns the Zobrist hash value for the underlying `Board` /// instance. /// /// Zobrist hashing is a technique to transform a board position /// into a number of a fixed length, with an equal distribution /// over all possible numbers, invented by Albert Zobrist. The key /// property of this method is that two similar positions generate /// entirely different hash numbers. /// /// **Important note:** This method will be relatively slow if the /// implementation calculates the hash value "from /// scratch". Inspect the implementation before using `hash` in /// time-critical paths. (See `do_move`.) fn hash(&self) -> u64; /// Returns a bitboard with all pieces and pawns that attack a /// given square. fn attacks_to(&self, square: Square) -> Bitboard; /// Returns if the side to move is in check. fn is_check(&self) -> bool; /// Generates all legal moves, possibly including some /// pseudo-legal moves too. /// /// The moves are added to `moves`. All generated moves with /// pieces other than the king will be legal. Some of the /// generated king's moves may be illegal because the destination /// square is under attack. This arrangement has two important /// advantages: /// /// * `do_move` can do its work without knowing the set of /// checkers and pinned pieces, so there is no need to keep /// those around. /// /// * A beta cut-off may make the verification that king's /// destination square is not under attack unnecessary, thus /// saving time. /// /// The initial move score for the generated moves is /// *unspecified*. /// /// **Note:** A pseudo-legal move is a move that is otherwise /// legal, except it might leave the king in check. fn generate_all(&self, moves: &mut T); /// Generates moves for the quiescence search. /// /// The moves are added to `moves`. This method always generates a /// **subset** of the moves generated by `generate_all`: /// /// * If the king is in check, all legal moves are included. /// /// * Captures and pawn promotions to queen are always included. /// /// * If `generate_checks` is `true`, moves that give check are /// included too. Discovered checks and checks given by castling /// can be omitted for speed. fn generate_forcing(&self, generate_checks: bool, moves: &mut T); /// 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 null_move(&self) -> Move; /// Verifies if the supplied move digest represents a proper move. /// /// If a move `m` exists that would be generated by `generate_all` /// if called for the current position on the board, 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_all`. fn try_move_digest(&self, move_digest: MoveDigest) -> Option; /// Plays a move on the board. /// /// It the move leaves the king in check, `None` is returned /// without updating the board. Otherwise, the board is updated /// and an `u64` value is returned, which should be XOR-ed with /// board's old Zobrist hash value to obtain board's new Zobrist /// hash value. The move passed to this method **must** have been /// generated by `generate_all`, `generate_forcing`, /// `try_move_digest`, or `null_move` methods for the current /// position on the board. fn do_move(&mut self, m: Move) -> Option; /// Takes back last played move. /// /// The move passed to this method **must** be the last move passed /// to `do_move`. fn undo_move(&mut self, m: Move); /// Returns a reference to a static evaluator bound to the current /// position. fn evaluator(&self) -> &Self::Evaluator; /// 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_all`, `generate_forcing`, `try_move_digest`, or /// `null_move` methods for the current position on the board. fn evaluate_move(&self, m: Move) -> Value { debug_assert!(m.played_piece() < PIECE_NONE); debug_assert!(m.captured_piece() <= PIECE_NONE); const PIECE_VALUES: [Value; 8] = [10000, 975, 500, 325, 325, 100, 0, 0]; unsafe { let mut piece = m.played_piece(); let captured_piece = m.captured_piece(); // Try not to waste CPU cycles when the played piece is // less valuable than the captured piece. if piece > captured_piece { return *PIECE_VALUES.get_unchecked(captured_piece); } // This is the square on which all the action takes place. let exchange_square = m.dest_square(); let color: &[Bitboard; 2] = &self.board().pieces.color; let piece_type: &[Bitboard; 6] = &self.board().pieces.piece_type; let file_sliders = piece_type[QUEEN] | piece_type[ROOK]; let diag_sliders = piece_type[QUEEN] | piece_type[BISHOP]; let geometry = BoardGeometry::get(); let behind_blocker: &[Bitboard; 64] = geometry .squares_behind_blocker .get_unchecked(exchange_square); // These variables (along with `piece`) will be updated on each capture: let mut us = self.board().to_move; let mut depth = 0; let mut orig_square_bb = 1 << m.orig_square(); let mut attackers_and_defenders = self.attacks_to(exchange_square); // The `gain` array will hold the total material gained at // each `depth`, from the viewpoint of the side that made the // last capture (`us`). let mut gain: [Value; 34] = uninitialized(); gain[0] = if m.move_type() == MOVE_PROMOTION { piece = Move::piece_from_aux_data(m.aux_data()); PIECE_VALUES[captured_piece] + PIECE_VALUES[piece] - PIECE_VALUES[PAWN] } else { *PIECE_VALUES.get_unchecked(captured_piece) }; // Examine the possible exchanges, fill the `gain` array. 'exchange: while orig_square_bb != 0 { let current_gain = *gain.get_unchecked(depth); // Store a speculative value that will be used if the // captured piece happens to be defended. let speculative_gain: &mut Value = gain.get_unchecked_mut(depth + 1); *speculative_gain = *PIECE_VALUES.get_unchecked(piece) - current_gain; if max(-current_gain, *speculative_gain) < 0 { // The side that made the last capture wins even if // the captured piece happens to be defended. So, we // stop here to save precious CPU cycles. Note that // here we may happen to return an incorrect SEE // value, but the sign will be correct, which is by // far the most important information. break; } // Register that capturing piece's origin square is now vacant. attackers_and_defenders &= !orig_square_bb; // Consider adding new attackers/defenders, now that // capturing piece's origin square is vacant. let behind = self.board().occupied & *behind_blocker.get_unchecked(bsf(orig_square_bb)); if behind & (file_sliders | diag_sliders) != 0 && piece != KING { attackers_and_defenders |= match behind & file_sliders & geometry.attacks_from_unsafe(ROOK, exchange_square, behind) { 0 => { // Not a file slider, possibly a diagonal slider. behind & diag_sliders & geometry.attacks_from_unsafe(BISHOP, exchange_square, behind) } bb => { // A file slider. bb } }; } // Change the side to move. us ^= 1; // Find the next piece to enter the exchange. (The least // valuable piece belonging to the side to move.) let candidates = attackers_and_defenders & *color.get_unchecked(us); if candidates != 0 { for p in (KING..PIECE_NONE).rev() { let bb = candidates & piece_type[p]; if bb != 0 { depth += 1; piece = p; orig_square_bb = lsb(bb); continue 'exchange; } } } break 'exchange; } // Negamax the `gain` array for the final static exchange // evaluation. (The `gain` array actually represents an unary // tree, at each node of which the player can either continue // the exchange or back off.) while depth > 0 { *gain.get_unchecked_mut(depth - 1) = -max(-*gain.get_unchecked(depth - 1), *gain.get_unchecked(depth)); depth -= 1; } gain[0] } } }