2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // min_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the bitboards and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 Bitboard b = stmAttackers & bb[Pt];
72 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
74 occupied ^= b & ~(b - 1);
76 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
77 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
79 if (Pt == ROOK || Pt == QUEEN)
80 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
82 attackers &= occupied; // After X-ray that may add already processed pieces
86 template<> FORCE_INLINE
87 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
88 return KING; // No need to update bitboards, it is the last cycle
96 CheckInfo::CheckInfo(const Position& pos) {
98 Color them = ~pos.side_to_move();
99 ksq = pos.king_square(them);
101 pinned = pos.pinned_pieces();
102 dcCandidates = pos.discovered_check_candidates();
104 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
105 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
106 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
107 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
108 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
113 /// Position::init() initializes at startup the various arrays used to compute
114 /// hash keys and the piece square tables. The latter is a two-step operation:
115 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
116 /// the black halves of the tables are initialized by flipping and changing the
117 /// sign of the white scores.
119 void Position::init() {
123 for (Color c = WHITE; c <= BLACK; c++)
124 for (PieceType pt = PAWN; pt <= KING; pt++)
125 for (Square s = SQ_A1; s <= SQ_H8; s++)
126 Zobrist::psq[c][pt][s] = rk.rand<Key>();
128 for (File f = FILE_A; f <= FILE_H; f++)
129 Zobrist::enpassant[f] = rk.rand<Key>();
131 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
136 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
137 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
141 Zobrist::side = rk.rand<Key>();
142 Zobrist::exclusion = rk.rand<Key>();
144 for (PieceType pt = PAWN; pt <= KING; pt++)
146 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
147 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
149 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
151 for (Square s = SQ_A1; s <= SQ_H8; s++)
153 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
154 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
160 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
161 /// object do not depend on any external data so we detach state pointer from
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
177 /// Position::set() initializes the position object with the given FEN string.
178 /// This function is not very robust - make sure that input FENs are correct,
179 /// this is assumed to be the responsibility of the GUI.
181 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
183 A FEN string defines a particular position using only the ASCII character set.
185 A FEN string contains six fields separated by a space. The fields are:
187 1) Piece placement (from white's perspective). Each rank is described, starting
188 with rank 8 and ending with rank 1; within each rank, the contents of each
189 square are described from file A through file H. Following the Standard
190 Algebraic Notation (SAN), each piece is identified by a single letter taken
191 from the standard English names. White pieces are designated using upper-case
192 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
193 noted using digits 1 through 8 (the number of blank squares), and "/"
196 2) Active color. "w" means white moves next, "b" means black.
198 3) Castling availability. If neither side can castle, this is "-". Otherwise,
199 this has one or more letters: "K" (White can castle kingside), "Q" (White
200 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
201 can castle queenside).
203 4) En passant target square (in algebraic notation). If there's no en passant
204 target square, this is "-". If a pawn has just made a 2-square move, this
205 is the position "behind" the pawn. This is recorded regardless of whether
206 there is a pawn in position to make an en passant capture.
208 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
209 or capture. This is used to determine if a draw can be claimed under the
212 6) Fullmove number. The number of the full move. It starts at 1, and is
213 incremented after Black's move.
216 char col, row, token;
219 std::istringstream ss(fenStr);
224 // 1. Piece placement
225 while ((ss >> token) && !isspace(token))
228 sq += Square(token - '0'); // Advance the given number of files
230 else if (token == '/')
233 else if ((p = PieceToChar.find(token)) != string::npos)
235 put_piece(Piece(p), sq);
242 sideToMove = (token == 'w' ? WHITE : BLACK);
245 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
246 // Shredder-FEN that uses the letters of the columns on which the rooks began
247 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
248 // if an inner rook is associated with the castling right, the castling tag is
249 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
250 while ((ss >> token) && !isspace(token))
253 Color c = islower(token) ? BLACK : WHITE;
255 token = char(toupper(token));
258 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
260 else if (token == 'Q')
261 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
263 else if (token >= 'A' && token <= 'H')
264 rsq = File(token - 'A') | relative_rank(c, RANK_1);
269 set_castle_right(c, rsq);
272 // 4. En passant square. Ignore if no pawn capture is possible
273 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
274 && ((ss >> row) && (row == '3' || row == '6')))
276 st->epSquare = File(col - 'a') | Rank(row - '1');
278 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
279 st->epSquare = SQ_NONE;
282 // 5-6. Halfmove clock and fullmove number
283 ss >> std::skipws >> st->rule50 >> gamePly;
285 // Convert from fullmove starting from 1 to ply starting from 0,
286 // handle also common incorrect FEN with fullmove = 0.
287 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
289 st->key = compute_key();
290 st->pawnKey = compute_pawn_key();
291 st->materialKey = compute_material_key();
292 st->psq = compute_psq_score();
293 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
294 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
295 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
296 chess960 = isChess960;
303 /// Position::set_castle_right() is an helper function used to set castling
304 /// rights given the corresponding color and the rook starting square.
306 void Position::set_castle_right(Color c, Square rfrom) {
308 Square kfrom = king_square(c);
309 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
310 CastleRight cr = make_castle_right(c, cs);
312 st->castleRights |= cr;
313 castleRightsMask[kfrom] |= cr;
314 castleRightsMask[rfrom] |= cr;
315 castleRookSquare[c][cs] = rfrom;
317 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
318 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
320 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
321 if (s != kfrom && s != rfrom)
322 castlePath[c][cs] |= s;
324 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
325 if (s != kfrom && s != rfrom)
326 castlePath[c][cs] |= s;
330 /// Position::fen() returns a FEN representation of the position. In case
331 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
333 const string Position::fen() const {
335 std::ostringstream ss;
337 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
339 for (File file = FILE_A; file <= FILE_H; file++)
341 Square sq = file | rank;
347 for ( ; file < FILE_H && is_empty(sq++); file++)
353 ss << PieceToChar[piece_on(sq)];
360 ss << (sideToMove == WHITE ? " w " : " b ");
362 if (can_castle(WHITE_OO))
363 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
365 if (can_castle(WHITE_OOO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
368 if (can_castle(BLACK_OO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
371 if (can_castle(BLACK_OOO))
372 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
374 if (st->castleRights == CASTLES_NONE)
377 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
378 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
384 /// Position::pretty() returns an ASCII representation of the position to be
385 /// printed to the standard output together with the move's san notation.
387 const string Position::pretty(Move move) const {
389 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
390 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
391 + dottedLine + "\n| . | | . | | . | | . | |";
393 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
395 for (Bitboard b = pieces(); b; )
397 Square s = pop_lsb(&b);
398 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
401 std::ostringstream ss;
404 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
405 << move_to_san(*const_cast<Position*>(this), move);
407 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
408 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
410 for (Bitboard b = checkers(); b; )
411 ss << square_to_string(pop_lsb(&b)) << " ";
413 ss << "\nLegal moves: ";
414 for (MoveList<LEGAL> it(*this); *it; ++it)
415 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
421 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
422 /// pieces, according to the call parameters. Pinned pieces protect our king,
423 /// discovery check pieces attack the enemy king.
425 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
427 Bitboard b, pinners, result = 0;
429 // Pinners are sliders that give check when pinned piece is removed
430 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
431 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
435 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
437 if (!more_than_one(b))
438 result |= b & pieces(sideToMove);
444 /// Position::attackers_to() computes a bitboard of all pieces which attack a
445 /// given square. Slider attacks use occ bitboard as occupancy.
447 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
449 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
450 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
451 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
452 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
453 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
454 | (attacks_from<KING>(s) & pieces(KING));
458 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
459 /// put in a given square. Slider attacks use occ bitboard as occupancy.
461 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
467 case BISHOP: return attacks_bb<BISHOP>(s, occ);
468 case ROOK : return attacks_bb<ROOK>(s, occ);
469 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
470 default : return StepAttacksBB[p][s];
475 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
477 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
480 assert(pinned == pinned_pieces());
482 Color us = sideToMove;
483 Square from = from_sq(m);
485 assert(color_of(piece_moved(m)) == us);
486 assert(piece_on(king_square(us)) == make_piece(us, KING));
488 // En passant captures are a tricky special case. Because they are rather
489 // uncommon, we do it simply by testing whether the king is attacked after
491 if (type_of(m) == ENPASSANT)
494 Square to = to_sq(m);
495 Square capsq = to + pawn_push(them);
496 Square ksq = king_square(us);
497 Bitboard b = (pieces() ^ from ^ capsq) | to;
499 assert(to == ep_square());
500 assert(piece_moved(m) == make_piece(us, PAWN));
501 assert(piece_on(capsq) == make_piece(them, PAWN));
502 assert(piece_on(to) == NO_PIECE);
504 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
505 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
508 // If the moving piece is a king, check whether the destination
509 // square is attacked by the opponent. Castling moves are checked
510 // for legality during move generation.
511 if (type_of(piece_on(from)) == KING)
512 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
514 // A non-king move is legal if and only if it is not pinned or it
515 // is moving along the ray towards or away from the king.
518 || squares_aligned(from, to_sq(m), king_square(us));
522 /// Position::is_pseudo_legal() takes a random move and tests whether the move
523 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
524 /// due to SMP concurrent access or hash position key aliasing.
526 bool Position::is_pseudo_legal(const Move m) const {
528 Color us = sideToMove;
529 Square from = from_sq(m);
530 Square to = to_sq(m);
531 Piece pc = piece_moved(m);
533 // Use a slower but simpler function for uncommon cases
534 if (type_of(m) != NORMAL)
535 return MoveList<LEGAL>(*this).contains(m);
537 // Is not a promotion, so promotion piece must be empty
538 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
541 // If the from square is not occupied by a piece belonging to the side to
542 // move, the move is obviously not legal.
543 if (pc == NO_PIECE || color_of(pc) != us)
546 // The destination square cannot be occupied by a friendly piece
550 // Handle the special case of a pawn move
551 if (type_of(pc) == PAWN)
553 // Move direction must be compatible with pawn color
554 int direction = to - from;
555 if ((us == WHITE) != (direction > 0))
558 // We have already handled promotion moves, so destination
559 // cannot be on the 8/1th rank.
560 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
563 // Proceed according to the square delta between the origin and
564 // destination squares.
571 // Capture. The destination square must be occupied by an enemy
572 // piece (en passant captures was handled earlier).
573 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
576 // From and to files must be one file apart, avoids a7h5
577 if (abs(file_of(from) - file_of(to)) != 1)
583 // Pawn push. The destination square must be empty.
589 // Double white pawn push. The destination square must be on the fourth
590 // rank, and both the destination square and the square between the
591 // source and destination squares must be empty.
592 if ( rank_of(to) != RANK_4
594 || !is_empty(from + DELTA_N))
599 // Double black pawn push. The destination square must be on the fifth
600 // rank, and both the destination square and the square between the
601 // source and destination squares must be empty.
602 if ( rank_of(to) != RANK_5
604 || !is_empty(from + DELTA_S))
612 else if (!(attacks_from(pc, from) & to))
615 // Evasions generator already takes care to avoid some kind of illegal moves
616 // and pl_move_is_legal() relies on this. So we have to take care that the
617 // same kind of moves are filtered out here.
620 if (type_of(pc) != KING)
622 // Double check? In this case a king move is required
623 if (more_than_one(checkers()))
626 // Our move must be a blocking evasion or a capture of the checking piece
627 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
630 // In case of king moves under check we have to remove king so to catch
631 // as invalid moves like b1a1 when opposite queen is on c1.
632 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
640 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
642 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
645 assert(ci.dcCandidates == discovered_check_candidates());
646 assert(color_of(piece_moved(m)) == sideToMove);
648 Square from = from_sq(m);
649 Square to = to_sq(m);
650 PieceType pt = type_of(piece_on(from));
653 if (ci.checkSq[pt] & to)
657 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
659 // For pawn and king moves we need to verify also direction
660 if ( (pt != PAWN && pt != KING)
661 || !squares_aligned(from, to, king_square(~sideToMove)))
665 // Can we skip the ugly special cases ?
666 if (type_of(m) == NORMAL)
669 Color us = sideToMove;
670 Square ksq = king_square(~us);
675 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
677 // En passant capture with check ? We have already handled the case
678 // of direct checks and ordinary discovered check, the only case we
679 // need to handle is the unusual case of a discovered check through
680 // the captured pawn.
683 Square capsq = file_of(to) | rank_of(from);
684 Bitboard b = (pieces() ^ from ^ capsq) | to;
686 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
687 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
692 Square rfrom = to; // 'King captures the rook' notation
693 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
694 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
696 return (PseudoAttacks[ROOK][rto] & ksq)
697 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
706 /// Position::do_move() makes a move, and saves all information necessary
707 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
708 /// moves should be filtered out before this function is called.
710 void Position::do_move(Move m, StateInfo& newSt) {
713 do_move(m, newSt, ci, move_gives_check(m, ci));
716 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
719 assert(&newSt != st);
724 // Copy some fields of old state to our new StateInfo object except the ones
725 // which are going to be recalculated from scratch anyway, then switch our state
726 // pointer to point to the new, ready to be updated, state.
727 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
732 // Update side to move
735 // Increment ply counters.In particular rule50 will be later reset it to zero
736 // in case of a capture or a pawn move.
741 Color us = sideToMove;
743 Square from = from_sq(m);
744 Square to = to_sq(m);
745 Piece pc = piece_on(from);
746 PieceType pt = type_of(pc);
747 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
749 assert(color_of(pc) == us);
750 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
751 assert(capture != KING);
753 if (type_of(m) == CASTLE)
755 assert(pc == make_piece(us, KING));
757 bool kingSide = to > from;
758 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
759 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
760 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
761 capture = NO_PIECE_TYPE;
763 do_castle(from, to, rfrom, rto);
765 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
766 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
773 // If the captured piece is a pawn, update pawn hash key, otherwise
774 // update non-pawn material.
777 if (type_of(m) == ENPASSANT)
779 capsq += pawn_push(them);
782 assert(to == st->epSquare);
783 assert(relative_rank(us, to) == RANK_6);
784 assert(piece_on(to) == NO_PIECE);
785 assert(piece_on(capsq) == make_piece(them, PAWN));
787 board[capsq] = NO_PIECE;
790 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
793 st->npMaterial[them] -= PieceValue[MG][capture];
795 // Remove the captured piece
796 byTypeBB[ALL_PIECES] ^= capsq;
797 byTypeBB[capture] ^= capsq;
798 byColorBB[them] ^= capsq;
800 // Update piece lists
801 remove_piece(capsq, them, capture);
803 // Update material hash key and prefetch access to materialTable
804 k ^= Zobrist::psq[them][capture][capsq];
805 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
806 prefetch((char*)thisThread->materialTable[st->materialKey]);
808 // Update incremental scores
809 st->psq -= psq[them][capture][capsq];
811 // Reset rule 50 counter
816 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
818 // Reset en passant square
819 if (st->epSquare != SQ_NONE)
821 k ^= Zobrist::enpassant[file_of(st->epSquare)];
822 st->epSquare = SQ_NONE;
825 // Update castle rights if needed
826 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
828 int cr = castleRightsMask[from] | castleRightsMask[to];
829 k ^= Zobrist::castle[st->castleRights & cr];
830 st->castleRights &= ~cr;
833 // Prefetch TT access as soon as we know the new hash key
834 prefetch((char*)TT.first_entry(k));
836 // Move the piece. The tricky Chess960 castle is handled earlier
837 if (type_of(m) != CASTLE)
839 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
840 byTypeBB[ALL_PIECES] ^= from_to_bb;
841 byTypeBB[pt] ^= from_to_bb;
842 byColorBB[us] ^= from_to_bb;
844 board[from] = NO_PIECE;
847 move_piece(from, to, us, pt);
850 // If the moving piece is a pawn do some special extra work
853 // Set en-passant square, only if moved pawn can be captured
854 if ( (int(to) ^ int(from)) == 16
855 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
857 st->epSquare = Square((from + to) / 2);
858 k ^= Zobrist::enpassant[file_of(st->epSquare)];
861 if (type_of(m) == PROMOTION)
863 PieceType promotion = promotion_type(m);
865 assert(relative_rank(us, to) == RANK_8);
866 assert(promotion >= KNIGHT && promotion <= QUEEN);
868 // Replace the pawn with the promoted piece
869 byTypeBB[PAWN] ^= to;
870 byTypeBB[promotion] |= to;
871 board[to] = make_piece(us, promotion);
873 // Update piece lists and add a new promotion piece to the list
874 remove_piece(to, us, PAWN);
875 add_piece(to, us, promotion);
878 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
879 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
880 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
881 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
883 // Update incremental score
884 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
887 st->npMaterial[us] += PieceValue[MG][promotion];
890 // Update pawn hash key and prefetch access to pawnsTable
891 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
892 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
894 // Reset rule 50 draw counter
898 // Update incremental scores
899 st->psq += psq[us][pt][to] - psq[us][pt][from];
902 st->capturedType = capture;
904 // Update the key with the final value
907 // Update checkers bitboard, piece must be already moved
912 if (type_of(m) != NORMAL)
913 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
917 if (ci.checkSq[pt] & to)
918 st->checkersBB |= to;
921 if (ci.dcCandidates && (ci.dcCandidates & from))
924 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
927 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
932 sideToMove = ~sideToMove;
938 /// Position::undo_move() unmakes a move. When it returns, the position should
939 /// be restored to exactly the same state as before the move was made.
941 void Position::undo_move(Move m) {
945 sideToMove = ~sideToMove;
947 Color us = sideToMove;
949 Square from = from_sq(m);
950 Square to = to_sq(m);
951 PieceType pt = type_of(piece_on(to));
952 PieceType capture = st->capturedType;
954 assert(is_empty(from) || type_of(m) == CASTLE);
955 assert(capture != KING);
957 if (type_of(m) == PROMOTION)
959 PieceType promotion = promotion_type(m);
961 assert(promotion == pt);
962 assert(relative_rank(us, to) == RANK_8);
963 assert(promotion >= KNIGHT && promotion <= QUEEN);
965 // Replace the promoted piece with the pawn
966 byTypeBB[promotion] ^= to;
967 byTypeBB[PAWN] |= to;
968 board[to] = make_piece(us, PAWN);
970 // Update piece lists and add new pawn to the list
971 remove_piece(to, us, promotion);
972 add_piece(to, us, PAWN);
977 if (type_of(m) == CASTLE)
979 bool kingSide = to > from;
980 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
981 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
982 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
983 capture = NO_PIECE_TYPE;
985 do_castle(to, from, rto, rfrom);
989 // Put the piece back at the source square
990 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
991 byTypeBB[ALL_PIECES] ^= from_to_bb;
992 byTypeBB[pt] ^= from_to_bb;
993 byColorBB[us] ^= from_to_bb;
995 board[to] = NO_PIECE;
996 board[from] = make_piece(us, pt);
998 move_piece(to, from, us, pt);
1005 if (type_of(m) == ENPASSANT)
1007 capsq -= pawn_push(us);
1010 assert(to == st->previous->epSquare);
1011 assert(relative_rank(us, to) == RANK_6);
1012 assert(piece_on(capsq) == NO_PIECE);
1015 // Restore the captured piece
1016 byTypeBB[ALL_PIECES] |= capsq;
1017 byTypeBB[capture] |= capsq;
1018 byColorBB[them] |= capsq;
1020 board[capsq] = make_piece(them, capture);
1022 // Update piece list, add a new captured piece in capsq square
1023 add_piece(capsq, them, capture);
1026 // Finally point our state pointer back to the previous state
1030 assert(pos_is_ok());
1034 /// Position::do_castle() is a helper used to do/undo a castling move. This
1035 /// is a bit tricky, especially in Chess960.
1037 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1039 Color us = sideToMove;
1040 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1041 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1042 byTypeBB[KING] ^= k_from_to_bb;
1043 byTypeBB[ROOK] ^= r_from_to_bb;
1044 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1045 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1047 // Could be from == to, so first set NO_PIECE then KING and ROOK
1048 board[kfrom] = board[rfrom] = NO_PIECE;
1049 board[kto] = make_piece(us, KING);
1050 board[rto] = make_piece(us, ROOK);
1052 // Could be kfrom == rto, so use a 'tmp' variable
1053 int tmp = index[kfrom];
1054 index[rto] = index[rfrom];
1056 pieceList[us][KING][index[kto]] = kto;
1057 pieceList[us][ROOK][index[rto]] = rto;
1061 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1062 /// the side to move without executing any move on the board.
1064 void Position::do_null_move(StateInfo& newSt) {
1066 assert(!checkers());
1068 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1070 newSt.previous = st;
1073 if (st->epSquare != SQ_NONE)
1075 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1076 st->epSquare = SQ_NONE;
1079 st->key ^= Zobrist::side;
1080 prefetch((char*)TT.first_entry(st->key));
1083 st->pliesFromNull = 0;
1085 sideToMove = ~sideToMove;
1087 assert(pos_is_ok());
1090 void Position::undo_null_move() {
1092 assert(!checkers());
1095 sideToMove = ~sideToMove;
1099 /// Position::see() is a static exchange evaluator: It tries to estimate the
1100 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1101 /// tempi into account. If the side who initiated the capturing sequence does the
1102 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1103 /// the capturing sequence is considered bad.
1105 int Position::see_sign(Move m) const {
1109 // Early return if SEE cannot be negative because captured piece value
1110 // is not less then capturing one. Note that king moves always return
1111 // here because king midgame value is set to 0.
1112 if (PieceValue[MG][piece_moved(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1118 int Position::see(Move m, int asymmThreshold) const {
1121 Bitboard occupied, attackers, stmAttackers;
1122 int swapList[32], slIndex = 1;
1130 swapList[0] = PieceValue[MG][type_of(piece_on(to))];
1131 stm = color_of(piece_on(from));
1132 occupied = pieces() ^ from;
1134 // Castle moves are implemented as king capturing the rook so cannot be
1135 // handled correctly. Simply return 0 that is always the correct value
1136 // unless in the rare case the rook ends up under attack.
1137 if (type_of(m) == CASTLE)
1140 if (type_of(m) == ENPASSANT)
1142 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1143 swapList[0] = PieceValue[MG][PAWN];
1146 // Find all attackers to the destination square, with the moving piece
1147 // removed, but possibly an X-ray attacker added behind it.
1148 attackers = attackers_to(to, occupied) & occupied;
1150 // If the opponent has no attackers we are finished
1152 stmAttackers = attackers & pieces(stm);
1156 // The destination square is defended, which makes things rather more
1157 // difficult to compute. We proceed by building up a "swap list" containing
1158 // the material gain or loss at each stop in a sequence of captures to the
1159 // destination square, where the sides alternately capture, and always
1160 // capture with the least valuable piece. After each capture, we look for
1161 // new X-ray attacks from behind the capturing piece.
1162 captured = type_of(piece_on(from));
1165 assert(slIndex < 32);
1167 // Add the new entry to the swap list
1168 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1171 // Locate and remove the next least valuable attacker
1172 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1174 stmAttackers = attackers & pieces(stm);
1176 // Stop before processing a king capture
1177 if (captured == KING && stmAttackers)
1179 swapList[slIndex++] = QueenValueMg * 16;
1183 } while (stmAttackers);
1185 // If we are doing asymmetric SEE evaluation and the same side does the first
1186 // and the last capture, he loses a tempo and gain must be at least worth
1187 // 'asymmThreshold', otherwise we replace the score with a very low value,
1188 // before negamaxing.
1190 for (int i = 0; i < slIndex; i += 2)
1191 if (swapList[i] < asymmThreshold)
1192 swapList[i] = - QueenValueMg * 16;
1194 // Having built the swap list, we negamax through it to find the best
1195 // achievable score from the point of view of the side to move.
1197 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1203 /// Position::clear() erases the position object to a pristine state, with an
1204 /// empty board, white to move, and no castling rights.
1206 void Position::clear() {
1208 std::memset(this, 0, sizeof(Position));
1209 startState.epSquare = SQ_NONE;
1212 for (int i = 0; i < 8; i++)
1213 for (int j = 0; j < 16; j++)
1214 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1218 /// Position::put_piece() puts a piece on the given square of the board,
1219 /// updating the board array, pieces list, bitboards, and piece counts.
1221 void Position::put_piece(Piece p, Square s) {
1223 Color c = color_of(p);
1224 PieceType pt = type_of(p);
1227 add_piece(s, c, pt);
1229 byTypeBB[ALL_PIECES] |= s;
1235 /// Position::compute_key() computes the hash key of the position. The hash
1236 /// key is usually updated incrementally as moves are made and unmade, the
1237 /// compute_key() function is only used when a new position is set up, and
1238 /// to verify the correctness of the hash key when running in debug mode.
1240 Key Position::compute_key() const {
1242 Key k = Zobrist::castle[st->castleRights];
1244 for (Bitboard b = pieces(); b; )
1246 Square s = pop_lsb(&b);
1247 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1250 if (ep_square() != SQ_NONE)
1251 k ^= Zobrist::enpassant[file_of(ep_square())];
1253 if (sideToMove == BLACK)
1260 /// Position::compute_pawn_key() computes the hash key of the position. The
1261 /// hash key is usually updated incrementally as moves are made and unmade,
1262 /// the compute_pawn_key() function is only used when a new position is set
1263 /// up, and to verify the correctness of the pawn hash key when running in
1266 Key Position::compute_pawn_key() const {
1270 for (Bitboard b = pieces(PAWN); b; )
1272 Square s = pop_lsb(&b);
1273 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1280 /// Position::compute_material_key() computes the hash key of the position.
1281 /// The hash key is usually updated incrementally as moves are made and unmade,
1282 /// the compute_material_key() function is only used when a new position is set
1283 /// up, and to verify the correctness of the material hash key when running in
1286 Key Position::compute_material_key() const {
1290 for (Color c = WHITE; c <= BLACK; c++)
1291 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1292 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1293 k ^= Zobrist::psq[c][pt][cnt];
1299 /// Position::compute_psq_score() computes the incremental scores for the middle
1300 /// game and the endgame. These functions are used to initialize the incremental
1301 /// scores when a new position is set up, and to verify that the scores are correctly
1302 /// updated by do_move and undo_move when the program is running in debug mode.
1303 Score Position::compute_psq_score() const {
1305 Score score = SCORE_ZERO;
1307 for (Bitboard b = pieces(); b; )
1309 Square s = pop_lsb(&b);
1310 Piece pc = piece_on(s);
1311 score += psq[color_of(pc)][type_of(pc)][s];
1318 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1319 /// game material value for the given side. Material values are updated
1320 /// incrementally during the search, this function is only used while
1321 /// initializing a new Position object.
1323 Value Position::compute_non_pawn_material(Color c) const {
1325 Value value = VALUE_ZERO;
1327 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1328 value += pieceCount[c][pt] * PieceValue[MG][pt];
1334 /// Position::is_draw() tests whether the position is drawn by material,
1335 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1336 /// must be done by the search.
1337 bool Position::is_draw() const {
1339 // Draw by material?
1341 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1344 // Draw by the 50 moves rule?
1345 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1348 // Draw by repetition?
1349 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1353 StateInfo* stp = st->previous->previous;
1356 stp = stp->previous->previous;
1358 if (stp->key == st->key)
1370 /// Position::flip() flips position with the white and black sides reversed. This
1371 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1373 void Position::flip() {
1375 const Position pos(*this);
1379 sideToMove = ~pos.side_to_move();
1380 thisThread = pos.this_thread();
1381 nodes = pos.nodes_searched();
1382 chess960 = pos.is_chess960();
1383 gamePly = pos.game_ply();
1385 for (Square s = SQ_A1; s <= SQ_H8; s++)
1386 if (!pos.is_empty(s))
1387 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1389 if (pos.can_castle(WHITE_OO))
1390 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1391 if (pos.can_castle(WHITE_OOO))
1392 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1393 if (pos.can_castle(BLACK_OO))
1394 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1395 if (pos.can_castle(BLACK_OOO))
1396 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1398 if (pos.st->epSquare != SQ_NONE)
1399 st->epSquare = ~pos.st->epSquare;
1401 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1403 st->key = compute_key();
1404 st->pawnKey = compute_pawn_key();
1405 st->materialKey = compute_material_key();
1406 st->psq = compute_psq_score();
1407 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1408 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1410 assert(pos_is_ok());
1414 /// Position::pos_is_ok() performs some consitency checks for the position object.
1415 /// This is meant to be helpful when debugging.
1417 bool Position::pos_is_ok(int* failedStep) const {
1419 int dummy, *step = failedStep ? failedStep : &dummy;
1421 // What features of the position should be verified?
1422 const bool all = false;
1424 const bool debugBitboards = all || false;
1425 const bool debugKingCount = all || false;
1426 const bool debugKingCapture = all || false;
1427 const bool debugCheckerCount = all || false;
1428 const bool debugKey = all || false;
1429 const bool debugMaterialKey = all || false;
1430 const bool debugPawnKey = all || false;
1431 const bool debugIncrementalEval = all || false;
1432 const bool debugNonPawnMaterial = all || false;
1433 const bool debugPieceCounts = all || false;
1434 const bool debugPieceList = all || false;
1435 const bool debugCastleSquares = all || false;
1439 if (sideToMove != WHITE && sideToMove != BLACK)
1442 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1445 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1448 if ((*step)++, debugKingCount)
1450 int kingCount[COLOR_NB] = {};
1452 for (Square s = SQ_A1; s <= SQ_H8; s++)
1453 if (type_of(piece_on(s)) == KING)
1454 kingCount[color_of(piece_on(s))]++;
1456 if (kingCount[0] != 1 || kingCount[1] != 1)
1460 if ((*step)++, debugKingCapture)
1461 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1464 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1467 if ((*step)++, debugBitboards)
1469 // The intersection of the white and black pieces must be empty
1470 if (pieces(WHITE) & pieces(BLACK))
1473 // The union of the white and black pieces must be equal to all
1475 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1478 // Separate piece type bitboards must have empty intersections
1479 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1480 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1481 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1485 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1488 if ((*step)++, debugKey && st->key != compute_key())
1491 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1494 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1497 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1500 if ((*step)++, debugNonPawnMaterial)
1501 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1502 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1505 if ((*step)++, debugPieceCounts)
1506 for (Color c = WHITE; c <= BLACK; c++)
1507 for (PieceType pt = PAWN; pt <= KING; pt++)
1508 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1511 if ((*step)++, debugPieceList)
1512 for (Color c = WHITE; c <= BLACK; c++)
1513 for (PieceType pt = PAWN; pt <= KING; pt++)
1514 for (int i = 0; i < pieceCount[c][pt]; i++)
1515 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1516 || index[pieceList[c][pt][i]] != i)
1519 if ((*step)++, debugCastleSquares)
1520 for (Color c = WHITE; c <= BLACK; c++)
1521 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1523 CastleRight cr = make_castle_right(c, s);
1525 if (!can_castle(cr))
1528 if ( (castleRightsMask[king_square(c)] & cr) != cr
1529 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1530 || castleRightsMask[castleRookSquare[c][s]] != cr)