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];
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]);
84 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
87 template<> FORCE_INLINE
88 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
89 return KING; // No need to update bitboards, it is the last cycle
97 CheckInfo::CheckInfo(const Position& pos) {
99 Color them = ~pos.side_to_move();
100 ksq = pos.king_square(them);
102 pinned = pos.pinned_pieces();
103 dcCandidates = pos.discovered_check_candidates();
105 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
106 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
107 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
108 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
109 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
114 /// Position::init() initializes at startup the various arrays used to compute
115 /// hash keys and the piece square tables. The latter is a two-step operation:
116 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
117 /// the black halves of the tables are initialized by flipping and changing the
118 /// sign of the white scores.
120 void Position::init() {
124 for (Color c = WHITE; c <= BLACK; c++)
125 for (PieceType pt = PAWN; pt <= KING; pt++)
126 for (Square s = SQ_A1; s <= SQ_H8; s++)
127 Zobrist::psq[c][pt][s] = rk.rand<Key>();
129 for (File f = FILE_A; f <= FILE_H; f++)
130 Zobrist::enpassant[f] = rk.rand<Key>();
132 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
137 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
138 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
142 Zobrist::side = rk.rand<Key>();
143 Zobrist::exclusion = rk.rand<Key>();
145 for (PieceType pt = PAWN; pt <= KING; pt++)
147 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
148 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
150 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
152 for (Square s = SQ_A1; s <= SQ_H8; s++)
154 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
155 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
161 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
162 /// object do not depend on any external data so we detach state pointer from
165 Position& Position::operator=(const Position& pos) {
167 std::memcpy(this, &pos, sizeof(Position));
178 /// Position::set() initializes the position object with the given FEN string.
179 /// This function is not very robust - make sure that input FENs are correct,
180 /// this is assumed to be the responsibility of the GUI.
182 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
184 A FEN string defines a particular position using only the ASCII character set.
186 A FEN string contains six fields separated by a space. The fields are:
188 1) Piece placement (from white's perspective). Each rank is described, starting
189 with rank 8 and ending with rank 1; within each rank, the contents of each
190 square are described from file A through file H. Following the Standard
191 Algebraic Notation (SAN), each piece is identified by a single letter taken
192 from the standard English names. White pieces are designated using upper-case
193 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
194 noted using digits 1 through 8 (the number of blank squares), and "/"
197 2) Active color. "w" means white moves next, "b" means black.
199 3) Castling availability. If neither side can castle, this is "-". Otherwise,
200 this has one or more letters: "K" (White can castle kingside), "Q" (White
201 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
202 can castle queenside).
204 4) En passant target square (in algebraic notation). If there's no en passant
205 target square, this is "-". If a pawn has just made a 2-square move, this
206 is the position "behind" the pawn. This is recorded regardless of whether
207 there is a pawn in position to make an en passant capture.
209 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
210 or capture. This is used to determine if a draw can be claimed under the
213 6) Fullmove number. The number of the full move. It starts at 1, and is
214 incremented after Black's move.
217 char col, row, token;
220 std::istringstream ss(fenStr);
225 // 1. Piece placement
226 while ((ss >> token) && !isspace(token))
229 sq += Square(token - '0'); // Advance the given number of files
231 else if (token == '/')
234 else if ((p = PieceToChar.find(token)) != string::npos)
236 put_piece(Piece(p), sq);
243 sideToMove = (token == 'w' ? WHITE : BLACK);
246 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
247 // Shredder-FEN that uses the letters of the columns on which the rooks began
248 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
249 // if an inner rook is associated with the castling right, the castling tag is
250 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
251 while ((ss >> token) && !isspace(token))
254 Color c = islower(token) ? BLACK : WHITE;
256 token = char(toupper(token));
259 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
261 else if (token == 'Q')
262 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
264 else if (token >= 'A' && token <= 'H')
265 rsq = File(token - 'A') | relative_rank(c, RANK_1);
270 set_castle_right(c, rsq);
273 // 4. En passant square. Ignore if no pawn capture is possible
274 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
275 && ((ss >> row) && (row == '3' || row == '6')))
277 st->epSquare = File(col - 'a') | Rank(row - '1');
279 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
280 st->epSquare = SQ_NONE;
283 // 5-6. Halfmove clock and fullmove number
284 ss >> std::skipws >> st->rule50 >> gamePly;
286 // Convert from fullmove starting from 1 to ply starting from 0,
287 // handle also common incorrect FEN with fullmove = 0.
288 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
290 st->key = compute_key();
291 st->pawnKey = compute_pawn_key();
292 st->materialKey = compute_material_key();
293 st->psq = compute_psq_score();
294 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
295 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
296 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
297 chess960 = isChess960;
304 /// Position::set_castle_right() is an helper function used to set castling
305 /// rights given the corresponding color and the rook starting square.
307 void Position::set_castle_right(Color c, Square rfrom) {
309 Square kfrom = king_square(c);
310 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
311 CastleRight cr = make_castle_right(c, cs);
313 st->castleRights |= cr;
314 castleRightsMask[kfrom] |= cr;
315 castleRightsMask[rfrom] |= cr;
316 castleRookSquare[c][cs] = rfrom;
318 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
319 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
321 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
322 if (s != kfrom && s != rfrom)
323 castlePath[c][cs] |= s;
325 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
326 if (s != kfrom && s != rfrom)
327 castlePath[c][cs] |= s;
331 /// Position::fen() returns a FEN representation of the position. In case
332 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
334 const string Position::fen() const {
336 std::ostringstream ss;
338 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
340 for (File file = FILE_A; file <= FILE_H; file++)
342 Square sq = file | rank;
348 for ( ; file < FILE_H && is_empty(sq++); file++)
354 ss << PieceToChar[piece_on(sq)];
361 ss << (sideToMove == WHITE ? " w " : " b ");
363 if (can_castle(WHITE_OO))
364 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
366 if (can_castle(WHITE_OOO))
367 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
369 if (can_castle(BLACK_OO))
370 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
372 if (can_castle(BLACK_OOO))
373 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
375 if (st->castleRights == CASTLES_NONE)
378 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
379 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
385 /// Position::pretty() returns an ASCII representation of the position to be
386 /// printed to the standard output together with the move's san notation.
388 const string Position::pretty(Move move) const {
390 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
391 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
392 + dottedLine + "\n| . | | . | | . | | . | |";
394 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
396 std::ostringstream ss;
399 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
400 << move_to_san(*const_cast<Position*>(this), move);
402 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
403 if (piece_on(sq) != NO_PIECE)
404 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
406 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
407 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
409 for (Bitboard b = checkers(); b; )
410 ss << square_to_string(pop_lsb(&b)) << " ";
412 ss << "\nLegal moves: ";
413 for (MoveList<LEGAL> it(*this); *it; ++it)
414 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
420 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
421 /// pieces, according to the call parameters. Pinned pieces protect our king,
422 /// discovery check pieces attack the enemy king.
424 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
426 Bitboard b, pinners, result = 0;
428 // Pinners are sliders that give check when pinned piece is removed
429 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
430 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
434 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
436 if (!more_than_one(b))
437 result |= b & pieces(sideToMove);
443 /// Position::attackers_to() computes a bitboard of all pieces which attack a
444 /// given square. Slider attacks use occ bitboard as occupancy.
446 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
448 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
449 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
450 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
451 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
452 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
453 | (attacks_from<KING>(s) & pieces(KING));
457 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
458 /// put in a given square. Slider attacks use occ bitboard as occupancy.
460 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
466 case BISHOP: return attacks_bb<BISHOP>(s, occ);
467 case ROOK : return attacks_bb<ROOK>(s, occ);
468 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
469 default : return StepAttacksBB[p][s];
474 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
476 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
479 assert(pinned == pinned_pieces());
481 Color us = sideToMove;
482 Square from = from_sq(m);
484 assert(color_of(piece_moved(m)) == us);
485 assert(piece_on(king_square(us)) == make_piece(us, KING));
487 // En passant captures are a tricky special case. Because they are rather
488 // uncommon, we do it simply by testing whether the king is attacked after
490 if (type_of(m) == ENPASSANT)
493 Square to = to_sq(m);
494 Square capsq = to + pawn_push(them);
495 Square ksq = king_square(us);
496 Bitboard b = (pieces() ^ from ^ capsq) | to;
498 assert(to == ep_square());
499 assert(piece_moved(m) == make_piece(us, PAWN));
500 assert(piece_on(capsq) == make_piece(them, PAWN));
501 assert(piece_on(to) == NO_PIECE);
503 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
504 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
507 // If the moving piece is a king, check whether the destination
508 // square is attacked by the opponent. Castling moves are checked
509 // for legality during move generation.
510 if (type_of(piece_on(from)) == KING)
511 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
513 // A non-king move is legal if and only if it is not pinned or it
514 // is moving along the ray towards or away from the king.
517 || squares_aligned(from, to_sq(m), king_square(us));
521 /// Position::is_pseudo_legal() takes a random move and tests whether the move
522 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
523 /// due to SMP concurrent access or hash position key aliasing.
525 bool Position::is_pseudo_legal(const Move m) const {
527 Color us = sideToMove;
528 Square from = from_sq(m);
529 Square to = to_sq(m);
530 Piece pc = piece_moved(m);
532 // Use a slower but simpler function for uncommon cases
533 if (type_of(m) != NORMAL)
534 return MoveList<LEGAL>(*this).contains(m);
536 // Is not a promotion, so promotion piece must be empty
537 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
540 // If the from square is not occupied by a piece belonging to the side to
541 // move, the move is obviously not legal.
542 if (pc == NO_PIECE || color_of(pc) != us)
545 // The destination square cannot be occupied by a friendly piece
546 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
549 // Handle the special case of a pawn move
550 if (type_of(pc) == PAWN)
552 // Move direction must be compatible with pawn color
553 int direction = to - from;
554 if ((us == WHITE) != (direction > 0))
557 // We have already handled promotion moves, so destination
558 // cannot be on the 8/1th rank.
559 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
562 // Proceed according to the square delta between the origin and
563 // destination squares.
570 // Capture. The destination square must be occupied by an enemy
571 // piece (en passant captures was handled earlier).
572 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
575 // From and to files must be one file apart, avoids a7h5
576 if (abs(file_of(from) - file_of(to)) != 1)
582 // Pawn push. The destination square must be empty.
588 // Double white pawn push. The destination square must be on the fourth
589 // rank, and both the destination square and the square between the
590 // source and destination squares must be empty.
591 if ( rank_of(to) != RANK_4
593 || !is_empty(from + DELTA_N))
598 // Double black pawn push. The destination square must be on the fifth
599 // rank, and both the destination square and the square between the
600 // source and destination squares must be empty.
601 if ( rank_of(to) != RANK_5
603 || !is_empty(from + DELTA_S))
611 else if (!(attacks_from(pc, from) & to))
614 // Evasions generator already takes care to avoid some kind of illegal moves
615 // and pl_move_is_legal() relies on this. So we have to take care that the
616 // same kind of moves are filtered out here.
619 if (type_of(pc) != KING)
621 // Double check? In this case a king move is required
622 if (more_than_one(checkers()))
625 // Our move must be a blocking evasion or a capture of the checking piece
626 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
629 // In case of king moves under check we have to remove king so to catch
630 // as invalid moves like b1a1 when opposite queen is on c1.
631 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
639 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
641 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
644 assert(ci.dcCandidates == discovered_check_candidates());
645 assert(color_of(piece_moved(m)) == sideToMove);
647 Square from = from_sq(m);
648 Square to = to_sq(m);
649 PieceType pt = type_of(piece_on(from));
652 if (ci.checkSq[pt] & to)
656 if (ci.dcCandidates && (ci.dcCandidates & from))
658 // For pawn and king moves we need to verify also direction
659 if ( (pt != PAWN && pt != KING)
660 || !squares_aligned(from, to, king_square(~sideToMove)))
664 // Can we skip the ugly special cases ?
665 if (type_of(m) == NORMAL)
668 Color us = sideToMove;
669 Square ksq = king_square(~us);
674 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
676 // En passant capture with check ? We have already handled the case
677 // of direct checks and ordinary discovered check, the only case we
678 // need to handle is the unusual case of a discovered check through
679 // the captured pawn.
682 Square capsq = file_of(to) | rank_of(from);
683 Bitboard b = (pieces() ^ from ^ capsq) | to;
685 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
686 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
691 Square rfrom = to; // 'King captures the rook' notation
692 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
693 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
695 return (PseudoAttacks[ROOK][rto] & ksq)
696 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
705 /// Position::do_move() makes a move, and saves all information necessary
706 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
707 /// moves should be filtered out before this function is called.
709 void Position::do_move(Move m, StateInfo& newSt) {
712 do_move(m, newSt, ci, move_gives_check(m, ci));
715 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
718 assert(&newSt != st);
723 // Copy some fields of old state to our new StateInfo object except the ones
724 // which are going to be recalculated from scratch anyway, then switch our state
725 // pointer to point to the new, ready to be updated, state.
726 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
731 // Update side to move
734 // Increment ply counters.In particular rule50 will be later reset it to zero
735 // in case of a capture or a pawn move.
740 Color us = sideToMove;
742 Square from = from_sq(m);
743 Square to = to_sq(m);
744 Piece pc = piece_on(from);
745 PieceType pt = type_of(pc);
746 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
748 assert(color_of(pc) == us);
749 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
750 assert(capture != KING);
752 if (type_of(m) == CASTLE)
754 assert(pc == make_piece(us, KING));
756 bool kingSide = to > from;
757 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
758 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
759 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
760 capture = NO_PIECE_TYPE;
762 do_castle(from, to, rfrom, rto);
764 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
765 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
772 // If the captured piece is a pawn, update pawn hash key, otherwise
773 // update non-pawn material.
776 if (type_of(m) == ENPASSANT)
778 capsq += pawn_push(them);
781 assert(to == st->epSquare);
782 assert(relative_rank(us, to) == RANK_6);
783 assert(piece_on(to) == NO_PIECE);
784 assert(piece_on(capsq) == make_piece(them, PAWN));
786 board[capsq] = NO_PIECE;
789 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
792 st->npMaterial[them] -= PieceValue[MG][capture];
794 // Remove the captured piece
795 byTypeBB[ALL_PIECES] ^= capsq;
796 byTypeBB[capture] ^= capsq;
797 byColorBB[them] ^= capsq;
799 // Update piece list, move the last piece at index[capsq] position and
802 // WARNING: This is a not reversible operation. When we will reinsert the
803 // captured piece in undo_move() we will put it at the end of the list and
804 // not in its original place, it means index[] and pieceList[] are not
805 // guaranteed to be invariant to a do_move() + undo_move() sequence.
806 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
807 index[lastSquare] = index[capsq];
808 pieceList[them][capture][index[lastSquare]] = lastSquare;
809 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
811 // Update material hash key and prefetch access to materialTable
812 k ^= Zobrist::psq[them][capture][capsq];
813 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
814 prefetch((char*)thisThread->materialTable[st->materialKey]);
816 // Update incremental scores
817 st->psq -= psq[them][capture][capsq];
819 // Reset rule 50 counter
824 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
826 // Reset en passant square
827 if (st->epSquare != SQ_NONE)
829 k ^= Zobrist::enpassant[file_of(st->epSquare)];
830 st->epSquare = SQ_NONE;
833 // Update castle rights if needed
834 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
836 int cr = castleRightsMask[from] | castleRightsMask[to];
837 k ^= Zobrist::castle[st->castleRights & cr];
838 st->castleRights &= ~cr;
841 // Prefetch TT access as soon as we know the new hash key
842 prefetch((char*)TT.first_entry(k));
844 // Move the piece. The tricky Chess960 castle is handled earlier
845 if (type_of(m) != CASTLE)
847 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
848 byTypeBB[ALL_PIECES] ^= from_to_bb;
849 byTypeBB[pt] ^= from_to_bb;
850 byColorBB[us] ^= from_to_bb;
852 board[from] = NO_PIECE;
855 // Update piece lists, index[from] is not updated and becomes stale. This
856 // works as long as index[] is accessed just by known occupied squares.
857 index[to] = index[from];
858 pieceList[us][pt][index[to]] = to;
861 // If the moving piece is a pawn do some special extra work
864 // Set en-passant square, only if moved pawn can be captured
865 if ( (int(to) ^ int(from)) == 16
866 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
868 st->epSquare = Square((from + to) / 2);
869 k ^= Zobrist::enpassant[file_of(st->epSquare)];
872 if (type_of(m) == PROMOTION)
874 PieceType promotion = promotion_type(m);
876 assert(relative_rank(us, to) == RANK_8);
877 assert(promotion >= KNIGHT && promotion <= QUEEN);
879 // Replace the pawn with the promoted piece
880 byTypeBB[PAWN] ^= to;
881 byTypeBB[promotion] |= to;
882 board[to] = make_piece(us, promotion);
884 // Update piece lists, move the last pawn at index[to] position
885 // and shrink the list. Add a new promotion piece to the list.
886 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
887 index[lastSquare] = index[to];
888 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
889 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
890 index[to] = pieceCount[us][promotion];
891 pieceList[us][promotion][index[to]] = to;
894 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
895 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
896 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
897 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
899 // Update incremental score
900 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
903 st->npMaterial[us] += PieceValue[MG][promotion];
906 // Update pawn hash key and prefetch access to pawnsTable
907 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
908 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
910 // Reset rule 50 draw counter
914 // Update incremental scores
915 st->psq += psq[us][pt][to] - psq[us][pt][from];
918 st->capturedType = capture;
920 // Update the key with the final value
923 // Update checkers bitboard, piece must be already moved
928 if (type_of(m) != NORMAL)
929 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
933 if (ci.checkSq[pt] & to)
934 st->checkersBB |= to;
937 if (ci.dcCandidates && (ci.dcCandidates & from))
940 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
943 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
948 sideToMove = ~sideToMove;
954 /// Position::undo_move() unmakes a move. When it returns, the position should
955 /// be restored to exactly the same state as before the move was made.
957 void Position::undo_move(Move m) {
961 sideToMove = ~sideToMove;
963 Color us = sideToMove;
965 Square from = from_sq(m);
966 Square to = to_sq(m);
967 PieceType pt = type_of(piece_on(to));
968 PieceType capture = st->capturedType;
970 assert(is_empty(from) || type_of(m) == CASTLE);
971 assert(capture != KING);
973 if (type_of(m) == PROMOTION)
975 PieceType promotion = promotion_type(m);
977 assert(promotion == pt);
978 assert(relative_rank(us, to) == RANK_8);
979 assert(promotion >= KNIGHT && promotion <= QUEEN);
981 // Replace the promoted piece with the pawn
982 byTypeBB[promotion] ^= to;
983 byTypeBB[PAWN] |= to;
984 board[to] = make_piece(us, PAWN);
986 // Update piece lists, move the last promoted piece at index[to] position
987 // and shrink the list. Add a new pawn to the list.
988 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
989 index[lastSquare] = index[to];
990 pieceList[us][promotion][index[lastSquare]] = lastSquare;
991 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
992 index[to] = pieceCount[us][PAWN]++;
993 pieceList[us][PAWN][index[to]] = to;
998 if (type_of(m) == CASTLE)
1000 bool kingSide = to > from;
1001 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1002 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1003 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1004 capture = NO_PIECE_TYPE;
1006 do_castle(to, from, rto, rfrom);
1010 // Put the piece back at the source square
1011 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1012 byTypeBB[ALL_PIECES] ^= from_to_bb;
1013 byTypeBB[pt] ^= from_to_bb;
1014 byColorBB[us] ^= from_to_bb;
1016 board[to] = NO_PIECE;
1017 board[from] = make_piece(us, pt);
1019 // Update piece lists, index[to] is not updated and becomes stale. This
1020 // works as long as index[] is accessed just by known occupied squares.
1021 index[from] = index[to];
1022 pieceList[us][pt][index[from]] = from;
1029 if (type_of(m) == ENPASSANT)
1031 capsq -= pawn_push(us);
1034 assert(to == st->previous->epSquare);
1035 assert(relative_rank(us, to) == RANK_6);
1036 assert(piece_on(capsq) == NO_PIECE);
1039 // Restore the captured piece
1040 byTypeBB[ALL_PIECES] |= capsq;
1041 byTypeBB[capture] |= capsq;
1042 byColorBB[them] |= capsq;
1044 board[capsq] = make_piece(them, capture);
1046 // Update piece list, add a new captured piece in capsq square
1047 index[capsq] = pieceCount[them][capture]++;
1048 pieceList[them][capture][index[capsq]] = capsq;
1051 // Finally point our state pointer back to the previous state
1055 assert(pos_is_ok());
1059 /// Position::do_castle() is a helper used to do/undo a castling move. This
1060 /// is a bit tricky, especially in Chess960.
1062 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1064 Color us = sideToMove;
1065 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1066 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1067 byTypeBB[KING] ^= k_from_to_bb;
1068 byTypeBB[ROOK] ^= r_from_to_bb;
1069 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1070 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1072 // Could be from == to, so first set NO_PIECE then KING and ROOK
1073 board[kfrom] = board[rfrom] = NO_PIECE;
1074 board[kto] = make_piece(us, KING);
1075 board[rto] = make_piece(us, ROOK);
1077 // Could be kfrom == rto, so use a 'tmp' variable
1078 int tmp = index[kfrom];
1079 index[rto] = index[rfrom];
1081 pieceList[us][KING][index[kto]] = kto;
1082 pieceList[us][ROOK][index[rto]] = rto;
1086 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1087 /// the side to move without executing any move on the board.
1089 void Position::do_null_move(StateInfo& newSt) {
1091 assert(!checkers());
1093 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1095 newSt.previous = st;
1098 if (st->epSquare != SQ_NONE)
1100 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1101 st->epSquare = SQ_NONE;
1104 st->key ^= Zobrist::side;
1105 prefetch((char*)TT.first_entry(st->key));
1108 st->pliesFromNull = 0;
1110 sideToMove = ~sideToMove;
1112 assert(pos_is_ok());
1115 void Position::undo_null_move() {
1117 assert(!checkers());
1120 sideToMove = ~sideToMove;
1124 /// Position::see() is a static exchange evaluator: It tries to estimate the
1125 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1126 /// tempi into account. If the side who initiated the capturing sequence does the
1127 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1128 /// the capturing sequence is considered bad.
1130 int Position::see_sign(Move m) const {
1134 // Early return if SEE cannot be negative because captured piece value
1135 // is not less then capturing one. Note that king moves always return
1136 // here because king midgame value is set to 0.
1137 if (PieceValue[MG][piece_moved(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1143 int Position::see(Move m, int asymmThreshold) const {
1146 Bitboard occupied, attackers, stmAttackers;
1147 int swapList[32], slIndex = 1;
1155 captured = type_of(piece_on(to));
1156 occupied = pieces() ^ from;
1158 // Handle en passant moves
1159 if (type_of(m) == ENPASSANT)
1161 Square capQq = to - pawn_push(sideToMove);
1164 assert(type_of(piece_on(capQq)) == PAWN);
1166 // Remove the captured pawn
1170 else if (type_of(m) == CASTLE)
1171 // Castle moves are implemented as king capturing the rook so cannot be
1172 // handled correctly. Simply return 0 that is always the correct value
1173 // unless the rook is ends up under attack.
1176 // Find all attackers to the destination square, with the moving piece
1177 // removed, but possibly an X-ray attacker added behind it.
1178 attackers = attackers_to(to, occupied);
1180 // If the opponent has no attackers we are finished
1181 stm = ~color_of(piece_on(from));
1182 stmAttackers = attackers & pieces(stm);
1184 return PieceValue[MG][captured];
1186 // The destination square is defended, which makes things rather more
1187 // difficult to compute. We proceed by building up a "swap list" containing
1188 // the material gain or loss at each stop in a sequence of captures to the
1189 // destination square, where the sides alternately capture, and always
1190 // capture with the least valuable piece. After each capture, we look for
1191 // new X-ray attacks from behind the capturing piece.
1192 swapList[0] = PieceValue[MG][captured];
1193 captured = type_of(piece_on(from));
1196 assert(slIndex < 32);
1198 // Add the new entry to the swap list
1199 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1202 // Locate and remove the next least valuable attacker
1203 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1204 attackers &= occupied; // Remove the just found attacker
1206 stmAttackers = attackers & pieces(stm);
1208 if (captured == KING)
1210 // Stop before processing a king capture
1212 swapList[slIndex++] = QueenValueMg * 16;
1217 } while (stmAttackers);
1219 // If we are doing asymmetric SEE evaluation and the same side does the first
1220 // and the last capture, he loses a tempo and gain must be at least worth
1221 // 'asymmThreshold', otherwise we replace the score with a very low value,
1222 // before negamaxing.
1224 for (int i = 0; i < slIndex; i += 2)
1225 if (swapList[i] < asymmThreshold)
1226 swapList[i] = - QueenValueMg * 16;
1228 // Having built the swap list, we negamax through it to find the best
1229 // achievable score from the point of view of the side to move.
1231 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1237 /// Position::clear() erases the position object to a pristine state, with an
1238 /// empty board, white to move, and no castling rights.
1240 void Position::clear() {
1242 std::memset(this, 0, sizeof(Position));
1243 startState.epSquare = SQ_NONE;
1246 for (int i = 0; i < 8; i++)
1247 for (int j = 0; j < 16; j++)
1248 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1252 /// Position::put_piece() puts a piece on the given square of the board,
1253 /// updating the board array, pieces list, bitboards, and piece counts.
1255 void Position::put_piece(Piece p, Square s) {
1257 Color c = color_of(p);
1258 PieceType pt = type_of(p);
1261 index[s] = pieceCount[c][pt]++;
1262 pieceList[c][pt][index[s]] = s;
1264 byTypeBB[ALL_PIECES] |= s;
1270 /// Position::compute_key() computes the hash key of the position. The hash
1271 /// key is usually updated incrementally as moves are made and unmade, the
1272 /// compute_key() function is only used when a new position is set up, and
1273 /// to verify the correctness of the hash key when running in debug mode.
1275 Key Position::compute_key() const {
1277 Key k = Zobrist::castle[st->castleRights];
1279 for (Bitboard b = pieces(); b; )
1281 Square s = pop_lsb(&b);
1282 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1285 if (ep_square() != SQ_NONE)
1286 k ^= Zobrist::enpassant[file_of(ep_square())];
1288 if (sideToMove == BLACK)
1295 /// Position::compute_pawn_key() computes the hash key of the position. The
1296 /// hash key is usually updated incrementally as moves are made and unmade,
1297 /// the compute_pawn_key() function is only used when a new position is set
1298 /// up, and to verify the correctness of the pawn hash key when running in
1301 Key Position::compute_pawn_key() const {
1305 for (Bitboard b = pieces(PAWN); b; )
1307 Square s = pop_lsb(&b);
1308 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1315 /// Position::compute_material_key() computes the hash key of the position.
1316 /// The hash key is usually updated incrementally as moves are made and unmade,
1317 /// the compute_material_key() function is only used when a new position is set
1318 /// up, and to verify the correctness of the material hash key when running in
1321 Key Position::compute_material_key() const {
1325 for (Color c = WHITE; c <= BLACK; c++)
1326 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1327 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1328 k ^= Zobrist::psq[c][pt][cnt];
1334 /// Position::compute_psq_score() computes the incremental scores for the middle
1335 /// game and the endgame. These functions are used to initialize the incremental
1336 /// scores when a new position is set up, and to verify that the scores are correctly
1337 /// updated by do_move and undo_move when the program is running in debug mode.
1338 Score Position::compute_psq_score() const {
1340 Score score = SCORE_ZERO;
1342 for (Bitboard b = pieces(); b; )
1344 Square s = pop_lsb(&b);
1345 Piece pc = piece_on(s);
1346 score += psq[color_of(pc)][type_of(pc)][s];
1353 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1354 /// game material value for the given side. Material values are updated
1355 /// incrementally during the search, this function is only used while
1356 /// initializing a new Position object.
1358 Value Position::compute_non_pawn_material(Color c) const {
1360 Value value = VALUE_ZERO;
1362 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1363 value += pieceCount[c][pt] * PieceValue[MG][pt];
1369 /// Position::is_draw() tests whether the position is drawn by material,
1370 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1371 /// must be done by the search.
1372 bool Position::is_draw() const {
1374 // Draw by material?
1376 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1379 // Draw by the 50 moves rule?
1380 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1383 // Draw by repetition?
1384 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1388 StateInfo* stp = st->previous->previous;
1391 stp = stp->previous->previous;
1393 if (stp->key == st->key)
1405 /// Position::flip() flips position with the white and black sides reversed. This
1406 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1408 void Position::flip() {
1410 const Position pos(*this);
1414 sideToMove = ~pos.side_to_move();
1415 thisThread = pos.this_thread();
1416 nodes = pos.nodes_searched();
1417 chess960 = pos.is_chess960();
1418 gamePly = pos.game_ply();
1420 for (Square s = SQ_A1; s <= SQ_H8; s++)
1421 if (!pos.is_empty(s))
1422 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1424 if (pos.can_castle(WHITE_OO))
1425 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1426 if (pos.can_castle(WHITE_OOO))
1427 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1428 if (pos.can_castle(BLACK_OO))
1429 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1430 if (pos.can_castle(BLACK_OOO))
1431 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1433 if (pos.st->epSquare != SQ_NONE)
1434 st->epSquare = ~pos.st->epSquare;
1436 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1438 st->key = compute_key();
1439 st->pawnKey = compute_pawn_key();
1440 st->materialKey = compute_material_key();
1441 st->psq = compute_psq_score();
1442 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1443 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1445 assert(pos_is_ok());
1449 /// Position::pos_is_ok() performs some consitency checks for the position object.
1450 /// This is meant to be helpful when debugging.
1452 bool Position::pos_is_ok(int* failedStep) const {
1454 int dummy, *step = failedStep ? failedStep : &dummy;
1456 // What features of the position should be verified?
1457 const bool all = false;
1459 const bool debugBitboards = all || false;
1460 const bool debugKingCount = all || false;
1461 const bool debugKingCapture = all || false;
1462 const bool debugCheckerCount = all || false;
1463 const bool debugKey = all || false;
1464 const bool debugMaterialKey = all || false;
1465 const bool debugPawnKey = all || false;
1466 const bool debugIncrementalEval = all || false;
1467 const bool debugNonPawnMaterial = all || false;
1468 const bool debugPieceCounts = all || false;
1469 const bool debugPieceList = all || false;
1470 const bool debugCastleSquares = all || false;
1474 if (sideToMove != WHITE && sideToMove != BLACK)
1477 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1480 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1483 if ((*step)++, debugKingCount)
1485 int kingCount[COLOR_NB] = {};
1487 for (Square s = SQ_A1; s <= SQ_H8; s++)
1488 if (type_of(piece_on(s)) == KING)
1489 kingCount[color_of(piece_on(s))]++;
1491 if (kingCount[0] != 1 || kingCount[1] != 1)
1495 if ((*step)++, debugKingCapture)
1496 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1499 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1502 if ((*step)++, debugBitboards)
1504 // The intersection of the white and black pieces must be empty
1505 if (pieces(WHITE) & pieces(BLACK))
1508 // The union of the white and black pieces must be equal to all
1510 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1513 // Separate piece type bitboards must have empty intersections
1514 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1515 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1516 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1520 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1523 if ((*step)++, debugKey && st->key != compute_key())
1526 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1529 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1532 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1535 if ((*step)++, debugNonPawnMaterial)
1536 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1537 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1540 if ((*step)++, debugPieceCounts)
1541 for (Color c = WHITE; c <= BLACK; c++)
1542 for (PieceType pt = PAWN; pt <= KING; pt++)
1543 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1546 if ((*step)++, debugPieceList)
1547 for (Color c = WHITE; c <= BLACK; c++)
1548 for (PieceType pt = PAWN; pt <= KING; pt++)
1549 for (int i = 0; i < pieceCount[c][pt]; i++)
1550 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1551 || index[pieceList[c][pt][i]] != i)
1554 if ((*step)++, debugCastleSquares)
1555 for (Color c = WHITE; c <= BLACK; c++)
1556 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1558 CastleRight cr = make_castle_right(c, s);
1560 if (!can_castle(cr))
1563 if ( (castleRightsMask[king_square(c)] & cr) != cr
1564 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1565 || castleRightsMask[castleRookSquare[c][s]] != cr)