2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file)
5 Stockfish is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 Stockfish is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
27 #include <initializer_list>
31 #include <string_view>
37 #include "nnue/nnue_common.h"
38 #include "syzygy/tbprobe.h"
49 Key psq[PIECE_NB][SQUARE_NB];
50 Key enpassant[FILE_NB];
51 Key castling[CASTLING_RIGHT_NB];
57 constexpr std::string_view PieceToChar(" PNBRQK pnbrqk");
59 constexpr Piece Pieces[] = {W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
60 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING};
64 // Returns an ASCII representation of the position
65 std::ostream& operator<<(std::ostream& os, const Position& pos) {
67 os << "\n +---+---+---+---+---+---+---+---+\n";
69 for (Rank r = RANK_8; r >= RANK_1; --r)
71 for (File f = FILE_A; f <= FILE_H; ++f)
72 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
74 os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n";
77 os << " a b c d e f g h\n"
78 << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase << std::setfill('0')
79 << std::setw(16) << pos.key() << std::setfill(' ') << std::dec << "\nCheckers: ";
81 for (Bitboard b = pos.checkers(); b;)
82 os << UCI::square(pop_lsb(b)) << " ";
84 if (int(Tablebases::MaxCardinality) >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING))
87 ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
90 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
91 Tablebases::ProbeState s1, s2;
92 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
93 int dtz = Tablebases::probe_dtz(p, &s2);
94 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
95 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
102 // Implements Marcel van Kervinck's cuckoo algorithm to detect repetition of positions
103 // for 3-fold repetition draws. The algorithm uses two hash tables with Zobrist hashes
104 // to allow fast detection of recurring positions. For details see:
105 // http://web.archive.org/web/20201107002606/https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
107 // First and second hash functions for indexing the cuckoo tables
108 inline int H1(Key h) { return h & 0x1fff; }
109 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
111 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
113 Move cuckooMove[8192];
116 // Initializes at startup the various arrays used to compute hash keys
117 void Position::init() {
121 for (Piece pc : Pieces)
122 for (Square s = SQ_A1; s <= SQ_H8; ++s)
123 Zobrist::psq[pc][s] = rng.rand<Key>();
125 for (File f = FILE_A; f <= FILE_H; ++f)
126 Zobrist::enpassant[f] = rng.rand<Key>();
128 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
129 Zobrist::castling[cr] = rng.rand<Key>();
131 Zobrist::side = rng.rand<Key>();
133 // Prepare the cuckoo tables
134 std::memset(cuckoo, 0, sizeof(cuckoo));
135 std::memset(cuckooMove, 0, sizeof(cuckooMove));
136 [[maybe_unused]] int count = 0;
137 for (Piece pc : Pieces)
138 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
139 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
140 if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2))
142 Move move = make_move(s1, s2);
143 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
147 std::swap(cuckoo[i], key);
148 std::swap(cuckooMove[i], move);
149 if (move == MOVE_NONE) // Arrived at empty slot?
151 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
155 assert(count == 3668);
159 // Initializes the position object with the given FEN string.
160 // This function is not very robust - make sure that input FENs are correct,
161 // this is assumed to be the responsibility of the GUI.
162 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
164 A FEN string defines a particular position using only the ASCII character set.
166 A FEN string contains six fields separated by a space. The fields are:
168 1) Piece placement (from white's perspective). Each rank is described, starting
169 with rank 8 and ending with rank 1. Within each rank, the contents of each
170 square are described from file A through file H. Following the Standard
171 Algebraic Notation (SAN), each piece is identified by a single letter taken
172 from the standard English names. White pieces are designated using upper-case
173 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
174 noted using digits 1 through 8 (the number of blank squares), and "/"
177 2) Active color. "w" means white moves next, "b" means black.
179 3) Castling availability. If neither side can castle, this is "-". Otherwise,
180 this has one or more letters: "K" (White can castle kingside), "Q" (White
181 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
182 can castle queenside).
184 4) En passant target square (in algebraic notation). If there's no en passant
185 target square, this is "-". If a pawn has just made a 2-square move, this
186 is the position "behind" the pawn. Following X-FEN standard, this is recorded
187 only if there is a pawn in position to make an en passant capture, and if
188 there really is a pawn that might have advanced two squares.
190 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
191 or capture. This is used to determine if a draw can be claimed under the
194 6) Fullmove number. The number of the full move. It starts at 1, and is
195 incremented after Black's move.
198 unsigned char col, row, token;
201 std::istringstream ss(fenStr);
203 std::memset(this, 0, sizeof(Position));
204 std::memset(si, 0, sizeof(StateInfo));
209 // 1. Piece placement
210 while ((ss >> token) && !isspace(token))
213 sq += (token - '0') * EAST; // Advance the given number of files
215 else if (token == '/')
218 else if ((idx = PieceToChar.find(token)) != string::npos)
220 put_piece(Piece(idx), sq);
227 sideToMove = (token == 'w' ? WHITE : BLACK);
230 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
231 // Shredder-FEN that uses the letters of the columns on which the rooks began
232 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
233 // if an inner rook is associated with the castling right, the castling tag is
234 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
235 while ((ss >> token) && !isspace(token))
238 Color c = islower(token) ? BLACK : WHITE;
239 Piece rook = make_piece(c, ROOK);
241 token = char(toupper(token));
244 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq)
247 else if (token == 'Q')
248 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq)
251 else if (token >= 'A' && token <= 'H')
252 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
257 set_castling_right(c, rsq);
260 // 4. En passant square.
261 // Ignore if square is invalid or not on side to move relative rank 6.
262 bool enpassant = false;
264 if (((ss >> col) && (col >= 'a' && col <= 'h'))
265 && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3'))))
267 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
269 // En passant square will be considered only if
270 // a) side to move have a pawn threatening epSquare
271 // b) there is an enemy pawn in front of epSquare
272 // c) there is no piece on epSquare or behind epSquare
273 enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN)
274 && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))
275 && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove))));
279 st->epSquare = SQ_NONE;
281 // 5-6. Halfmove clock and fullmove number
282 ss >> std::skipws >> st->rule50 >> gamePly;
284 // Convert from fullmove starting from 1 to gamePly starting from 0,
285 // handle also common incorrect FEN with fullmove = 0.
286 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
288 chess960 = isChess960;
298 // Helper function used to set castling
299 // rights given the corresponding color and the rook starting square.
300 void Position::set_castling_right(Color c, Square rfrom) {
302 Square kfrom = square<KING>(c);
303 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE : QUEEN_SIDE);
305 st->castlingRights |= cr;
306 castlingRightsMask[kfrom] |= cr;
307 castlingRightsMask[rfrom] |= cr;
308 castlingRookSquare[cr] = rfrom;
310 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
311 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
313 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto)) & ~(kfrom | rfrom);
317 // Sets king attacks to detect if a move gives check
318 void Position::set_check_info() const {
320 update_slider_blockers(WHITE);
321 update_slider_blockers(BLACK);
323 Square ksq = square<KING>(~sideToMove);
325 st->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
326 st->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
327 st->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
328 st->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
329 st->checkSquares[QUEEN] = st->checkSquares[BISHOP] | st->checkSquares[ROOK];
330 st->checkSquares[KING] = 0;
334 // Computes the hash keys of the position, and other
335 // data that once computed is updated incrementally as moves are made.
336 // The function is only used when a new position is set up
337 void Position::set_state() const {
339 st->key = st->materialKey = 0;
340 st->nonPawnMaterial[WHITE] = st->nonPawnMaterial[BLACK] = VALUE_ZERO;
341 st->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
345 for (Bitboard b = pieces(); b;)
347 Square s = pop_lsb(b);
348 Piece pc = piece_on(s);
349 st->key ^= Zobrist::psq[pc][s];
351 if (type_of(pc) != KING && type_of(pc) != PAWN)
352 st->nonPawnMaterial[color_of(pc)] += PieceValue[pc];
355 if (st->epSquare != SQ_NONE)
356 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
358 if (sideToMove == BLACK)
359 st->key ^= Zobrist::side;
361 st->key ^= Zobrist::castling[st->castlingRights];
363 for (Piece pc : Pieces)
364 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
365 st->materialKey ^= Zobrist::psq[pc][cnt];
369 // Overload to initialize the position object with
370 // the given endgame code string like "KBPKN". It is mainly a helper to
371 // get the material key out of an endgame code.
372 Position& Position::set(const string& code, Color c, StateInfo* si) {
374 assert(code[0] == 'K');
376 string sides[] = {code.substr(code.find('K', 1)), // Weak
377 code.substr(0, std::min(code.find('v'), code.find('K', 1)))}; // Strong
379 assert(sides[0].length() > 0 && sides[0].length() < 8);
380 assert(sides[1].length() > 0 && sides[1].length() < 8);
382 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
384 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/" + sides[1]
385 + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
387 return set(fenStr, false, si, nullptr);
391 // Returns a FEN representation of the position. In case of
392 // Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
393 string Position::fen() const {
396 std::ostringstream ss;
398 for (Rank r = RANK_8; r >= RANK_1; --r)
400 for (File f = FILE_A; f <= FILE_H; ++f)
402 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
409 ss << PieceToChar[piece_on(make_square(f, r))];
416 ss << (sideToMove == WHITE ? " w " : " b ");
418 if (can_castle(WHITE_OO))
419 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO))) : 'K');
421 if (can_castle(WHITE_OOO))
422 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
424 if (can_castle(BLACK_OO))
425 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO))) : 'k');
427 if (can_castle(BLACK_OOO))
428 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
430 if (!can_castle(ANY_CASTLING))
433 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ") << st->rule50
434 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
439 // Calculates st->blockersForKing[c] and st->pinners[~c],
440 // which store respectively the pieces preventing king of color c from being in check
441 // and the slider pieces of color ~c pinning pieces of color c to the king.
442 void Position::update_slider_blockers(Color c) const {
444 Square ksq = square<KING>(c);
446 st->blockersForKing[c] = 0;
449 // Snipers are sliders that attack 's' when a piece and other snipers are removed
450 Bitboard snipers = ((attacks_bb<ROOK>(ksq) & pieces(QUEEN, ROOK))
451 | (attacks_bb<BISHOP>(ksq) & pieces(QUEEN, BISHOP)))
453 Bitboard occupancy = pieces() ^ snipers;
457 Square sniperSq = pop_lsb(snipers);
458 Bitboard b = between_bb(ksq, sniperSq) & occupancy;
460 if (b && !more_than_one(b))
462 st->blockersForKing[c] |= b;
464 st->pinners[~c] |= sniperSq;
470 // Computes a bitboard of all pieces which attack a
471 // given square. Slider attacks use the occupied bitboard to indicate occupancy.
472 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
474 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
475 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
476 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
477 | (attacks_bb<ROOK>(s, occupied) & pieces(ROOK, QUEEN))
478 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
479 | (attacks_bb<KING>(s) & pieces(KING));
483 // Tests whether a pseudo-legal move is legal
484 bool Position::legal(Move m) const {
488 Color us = sideToMove;
489 Square from = from_sq(m);
490 Square to = to_sq(m);
492 assert(color_of(moved_piece(m)) == us);
493 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
495 // En passant captures are a tricky special case. Because they are rather
496 // uncommon, we do it simply by testing whether the king is attacked after
498 if (type_of(m) == EN_PASSANT)
500 Square ksq = square<KING>(us);
501 Square capsq = to - pawn_push(us);
502 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
504 assert(to == ep_square());
505 assert(moved_piece(m) == make_piece(us, PAWN));
506 assert(piece_on(capsq) == make_piece(~us, PAWN));
507 assert(piece_on(to) == NO_PIECE);
509 return !(attacks_bb<ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
510 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
513 // Castling moves generation does not check if the castling path is clear of
514 // enemy attacks, it is delayed at a later time: now!
515 if (type_of(m) == CASTLING)
517 // After castling, the rook and king final positions are the same in
518 // Chess960 as they would be in standard chess.
519 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
520 Direction step = to > from ? WEST : EAST;
522 for (Square s = to; s != from; s += step)
523 if (attackers_to(s) & pieces(~us))
526 // In case of Chess960, verify if the Rook blocks some checks.
527 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
528 return !chess960 || !(blockers_for_king(us) & to_sq(m));
531 // If the moving piece is a king, check whether the destination square is
532 // attacked by the opponent.
533 if (type_of(piece_on(from)) == KING)
534 return !(attackers_to(to, pieces() ^ from) & pieces(~us));
536 // A non-king move is legal if and only if it is not pinned or it
537 // is moving along the ray towards or away from the king.
538 return !(blockers_for_king(us) & from) || aligned(from, to, square<KING>(us));
542 // Takes a random move and tests whether the move is
543 // pseudo-legal. It is used to validate moves from TT that can be corrupted
544 // due to SMP concurrent access or hash position key aliasing.
545 bool Position::pseudo_legal(const Move m) const {
547 Color us = sideToMove;
548 Square from = from_sq(m);
549 Square to = to_sq(m);
550 Piece pc = moved_piece(m);
552 // Use a slower but simpler function for uncommon cases
553 // yet we skip the legality check of MoveList<LEGAL>().
554 if (type_of(m) != NORMAL)
555 return checkers() ? MoveList<EVASIONS>(*this).contains(m)
556 : MoveList<NON_EVASIONS>(*this).contains(m);
558 // Is not a promotion, so the promotion piece must be empty
559 assert(promotion_type(m) - KNIGHT == NO_PIECE_TYPE);
561 // If the 'from' square is not occupied by a piece belonging to the side to
562 // move, the move is obviously not legal.
563 if (pc == NO_PIECE || color_of(pc) != us)
566 // The destination square cannot be occupied by a friendly piece
570 // Handle the special case of a pawn move
571 if (type_of(pc) == PAWN)
573 // We have already handled promotion moves, so destination
574 // cannot be on the 8th/1st rank.
575 if ((Rank8BB | Rank1BB) & to)
578 if (!(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
579 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
580 && !((from + 2 * pawn_push(us) == to) // Not a double push
581 && (relative_rank(us, from) == RANK_2) && empty(to) && empty(to - pawn_push(us))))
584 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
587 // Evasions generator already takes care to avoid some kind of illegal moves
588 // and legal() relies on this. We therefore have to take care that the same
589 // kind of moves are filtered out here.
592 if (type_of(pc) != KING)
594 // Double check? In this case, a king move is required
595 if (more_than_one(checkers()))
598 // Our move must be a blocking interposition or a capture of the checking piece
599 if (!(between_bb(square<KING>(us), lsb(checkers())) & to))
602 // In case of king moves under check we have to remove the king so as to catch
603 // invalid moves like b1a1 when opposite queen is on c1.
604 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
612 // Tests whether a pseudo-legal move gives a check
613 bool Position::gives_check(Move m) const {
616 assert(color_of(moved_piece(m)) == sideToMove);
618 Square from = from_sq(m);
619 Square to = to_sq(m);
621 // Is there a direct check?
622 if (check_squares(type_of(piece_on(from))) & to)
625 // Is there a discovered check?
626 if (blockers_for_king(~sideToMove) & from)
627 return !aligned(from, to, square<KING>(~sideToMove)) || type_of(m) == CASTLING;
635 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
637 // En passant capture with check? We have already handled the case
638 // of direct checks and ordinary discovered check, so the only case we
639 // need to handle is the unusual case of a discovered check through
640 // the captured pawn.
642 Square capsq = make_square(file_of(to), rank_of(from));
643 Bitboard b = (pieces() ^ from ^ capsq) | to;
645 return (attacks_bb<ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
646 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b)
647 & pieces(sideToMove, QUEEN, BISHOP));
651 // Castling is encoded as 'king captures the rook'
652 Square rto = relative_square(sideToMove, to > from ? SQ_F1 : SQ_D1);
654 return check_squares(ROOK) & rto;
660 // Makes a move, and saves all information necessary
661 // to a StateInfo object. The move is assumed to be legal. Pseudo-legal
662 // moves should be filtered out before this function is called.
663 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
666 assert(&newSt != st);
668 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
669 Key k = st->key ^ Zobrist::side;
671 // Copy some fields of the old state to our new StateInfo object except the
672 // ones which are going to be recalculated from scratch anyway and then switch
673 // our state pointer to point to the new (ready to be updated) state.
674 std::memcpy(&newSt, st, offsetof(StateInfo, key));
678 // Increment ply counters. In particular, rule50 will be reset to zero later on
679 // in case of a capture or a pawn move.
685 st->accumulator.computed[WHITE] = false;
686 st->accumulator.computed[BLACK] = false;
687 auto& dp = st->dirtyPiece;
690 Color us = sideToMove;
692 Square from = from_sq(m);
693 Square to = to_sq(m);
694 Piece pc = piece_on(from);
695 Piece captured = type_of(m) == EN_PASSANT ? make_piece(them, PAWN) : piece_on(to);
697 assert(color_of(pc) == us);
698 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
699 assert(type_of(captured) != KING);
701 if (type_of(m) == CASTLING)
703 assert(pc == make_piece(us, KING));
704 assert(captured == make_piece(us, ROOK));
707 do_castling<true>(us, from, to, rfrom, rto);
709 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
717 // If the captured piece is a pawn, update pawn hash key, otherwise
718 // update non-pawn material.
719 if (type_of(captured) == PAWN)
721 if (type_of(m) == EN_PASSANT)
723 capsq -= pawn_push(us);
725 assert(pc == make_piece(us, PAWN));
726 assert(to == st->epSquare);
727 assert(relative_rank(us, to) == RANK_6);
728 assert(piece_on(to) == NO_PIECE);
729 assert(piece_on(capsq) == make_piece(them, PAWN));
733 st->nonPawnMaterial[them] -= PieceValue[captured];
735 dp.dirty_num = 2; // 1 piece moved, 1 piece captured
736 dp.piece[1] = captured;
740 // Update board and piece lists
743 // Update material hash key and prefetch access to materialTable
744 k ^= Zobrist::psq[captured][capsq];
745 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
747 // Reset rule 50 counter
752 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
754 // Reset en passant square
755 if (st->epSquare != SQ_NONE)
757 k ^= Zobrist::enpassant[file_of(st->epSquare)];
758 st->epSquare = SQ_NONE;
761 // Update castling rights if needed
762 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
764 k ^= Zobrist::castling[st->castlingRights];
765 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
766 k ^= Zobrist::castling[st->castlingRights];
769 // Move the piece. The tricky Chess960 castling is handled earlier
770 if (type_of(m) != CASTLING)
776 move_piece(from, to);
779 // If the moving piece is a pawn do some special extra work
780 if (type_of(pc) == PAWN)
782 // Set en passant square if the moved pawn can be captured
783 if ((int(to) ^ int(from)) == 16
784 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
786 st->epSquare = to - pawn_push(us);
787 k ^= Zobrist::enpassant[file_of(st->epSquare)];
790 else if (type_of(m) == PROMOTION)
792 Piece promotion = make_piece(us, promotion_type(m));
794 assert(relative_rank(us, to) == RANK_8);
795 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
798 put_piece(promotion, to);
800 // Promoting pawn to SQ_NONE, promoted piece from SQ_NONE
802 dp.piece[dp.dirty_num] = promotion;
803 dp.from[dp.dirty_num] = SQ_NONE;
804 dp.to[dp.dirty_num] = to;
808 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
810 Zobrist::psq[promotion][pieceCount[promotion] - 1] ^ Zobrist::psq[pc][pieceCount[pc]];
813 st->nonPawnMaterial[us] += PieceValue[promotion];
816 // Reset rule 50 draw counter
821 st->capturedPiece = captured;
823 // Update the key with the final value
826 // Calculate checkers bitboard (if move gives check)
827 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
829 sideToMove = ~sideToMove;
831 // Update king attacks used for fast check detection
834 // Calculate the repetition info. It is the ply distance from the previous
835 // occurrence of the same position, negative in the 3-fold case, or zero
836 // if the position was not repeated.
838 int end = std::min(st->rule50, st->pliesFromNull);
841 StateInfo* stp = st->previous->previous;
842 for (int i = 4; i <= end; i += 2)
844 stp = stp->previous->previous;
845 if (stp->key == st->key)
847 st->repetition = stp->repetition ? -i : i;
857 // Unmakes a move. When it returns, the position should
858 // be restored to exactly the same state as before the move was made.
859 void Position::undo_move(Move m) {
863 sideToMove = ~sideToMove;
865 Color us = sideToMove;
866 Square from = from_sq(m);
867 Square to = to_sq(m);
868 Piece pc = piece_on(to);
870 assert(empty(from) || type_of(m) == CASTLING);
871 assert(type_of(st->capturedPiece) != KING);
873 if (type_of(m) == PROMOTION)
875 assert(relative_rank(us, to) == RANK_8);
876 assert(type_of(pc) == promotion_type(m));
877 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
880 pc = make_piece(us, PAWN);
884 if (type_of(m) == CASTLING)
887 do_castling<false>(us, from, to, rfrom, rto);
891 move_piece(to, from); // Put the piece back at the source square
893 if (st->capturedPiece)
897 if (type_of(m) == EN_PASSANT)
899 capsq -= pawn_push(us);
901 assert(type_of(pc) == PAWN);
902 assert(to == st->previous->epSquare);
903 assert(relative_rank(us, to) == RANK_6);
904 assert(piece_on(capsq) == NO_PIECE);
905 assert(st->capturedPiece == make_piece(~us, PAWN));
908 put_piece(st->capturedPiece, capsq); // Restore the captured piece
912 // Finally point our state pointer back to the previous state
920 // Helper used to do/undo a castling move. This
921 // is a bit tricky in Chess960 where from/to squares can overlap.
923 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
925 bool kingSide = to > from;
926 rfrom = to; // Castling is encoded as "king captures friendly rook"
927 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
928 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
932 auto& dp = st->dirtyPiece;
933 dp.piece[0] = make_piece(us, KING);
936 dp.piece[1] = make_piece(us, ROOK);
942 // Remove both pieces first since squares could overlap in Chess960
943 remove_piece(Do ? from : to);
944 remove_piece(Do ? rfrom : rto);
945 board[Do ? from : to] = board[Do ? rfrom : rto] =
946 NO_PIECE; // remove_piece does not do this for us
947 put_piece(make_piece(us, KING), Do ? to : from);
948 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
952 // Used to do a "null move": it flips
953 // the side to move without executing any move on the board.
954 void Position::do_null_move(StateInfo& newSt) {
957 assert(&newSt != st);
959 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
964 st->dirtyPiece.dirty_num = 0;
965 st->dirtyPiece.piece[0] = NO_PIECE; // Avoid checks in UpdateAccumulator()
966 st->accumulator.computed[WHITE] = false;
967 st->accumulator.computed[BLACK] = false;
969 if (st->epSquare != SQ_NONE)
971 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
972 st->epSquare = SQ_NONE;
975 st->key ^= Zobrist::side;
977 prefetch(TT.first_entry(key()));
979 st->pliesFromNull = 0;
981 sideToMove = ~sideToMove;
991 // Must be used to undo a "null move"
992 void Position::undo_null_move() {
997 sideToMove = ~sideToMove;
1001 // Computes the new hash key after the given move. Needed
1002 // for speculative prefetch. It doesn't recognize special moves like castling,
1003 // en passant and promotions.
1004 Key Position::key_after(Move m) const {
1006 Square from = from_sq(m);
1007 Square to = to_sq(m);
1008 Piece pc = piece_on(from);
1009 Piece captured = piece_on(to);
1010 Key k = st->key ^ Zobrist::side;
1013 k ^= Zobrist::psq[captured][to];
1015 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1017 return (captured || type_of(pc) == PAWN) ? k : adjust_key50<true>(k);
1021 // Tests if the SEE (Static Exchange Evaluation)
1022 // value of move is greater or equal to the given threshold. We'll use an
1023 // algorithm similar to alpha-beta pruning with a null window.
1024 bool Position::see_ge(Move m, Value threshold) const {
1028 // Only deal with normal moves, assume others pass a simple SEE
1029 if (type_of(m) != NORMAL)
1030 return VALUE_ZERO >= threshold;
1032 Square from = from_sq(m), to = to_sq(m);
1034 int swap = PieceValue[piece_on(to)] - threshold;
1038 swap = PieceValue[piece_on(from)] - swap;
1042 assert(color_of(piece_on(from)) == sideToMove);
1043 Bitboard occupied = pieces() ^ from ^ to; // xoring to is important for pinned piece logic
1044 Color stm = sideToMove;
1045 Bitboard attackers = attackers_to(to, occupied);
1046 Bitboard stmAttackers, bb;
1052 attackers &= occupied;
1054 // If stm has no more attackers then give up: stm loses
1055 if (!(stmAttackers = attackers & pieces(stm)))
1058 // Don't allow pinned pieces to attack as long as there are
1059 // pinners on their original square.
1060 if (pinners(~stm) & occupied)
1062 stmAttackers &= ~blockers_for_king(stm);
1070 // Locate and remove the next least valuable attacker, and add to
1071 // the bitboard 'attackers' any X-ray attackers behind it.
1072 if ((bb = stmAttackers & pieces(PAWN)))
1074 if ((swap = PawnValue - swap) < res)
1076 occupied ^= least_significant_square_bb(bb);
1078 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1081 else if ((bb = stmAttackers & pieces(KNIGHT)))
1083 if ((swap = KnightValue - swap) < res)
1085 occupied ^= least_significant_square_bb(bb);
1088 else if ((bb = stmAttackers & pieces(BISHOP)))
1090 if ((swap = BishopValue - swap) < res)
1092 occupied ^= least_significant_square_bb(bb);
1094 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1097 else if ((bb = stmAttackers & pieces(ROOK)))
1099 if ((swap = RookValue - swap) < res)
1101 occupied ^= least_significant_square_bb(bb);
1103 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1106 else if ((bb = stmAttackers & pieces(QUEEN)))
1108 if ((swap = QueenValue - swap) < res)
1110 occupied ^= least_significant_square_bb(bb);
1112 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1113 | (attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN));
1117 // If we "capture" with the king but the opponent still has attackers,
1118 // reverse the result.
1119 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1125 // Tests whether the position is drawn by 50-move rule
1126 // or by repetition. It does not detect stalemates.
1127 bool Position::is_draw(int ply) const {
1129 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1132 // Return a draw score if a position repeats once earlier but strictly
1133 // after the root, or repeats twice before or at the root.
1134 return st->repetition && st->repetition < ply;
1138 // Tests whether there has been at least one repetition
1139 // of positions since the last capture or pawn move.
1140 bool Position::has_repeated() const {
1142 StateInfo* stc = st;
1143 int end = std::min(st->rule50, st->pliesFromNull);
1146 if (stc->repetition)
1149 stc = stc->previous;
1155 // Tests if the position has a move which draws by repetition,
1156 // or an earlier position has a move that directly reaches the current position.
1157 bool Position::has_game_cycle(int ply) const {
1161 int end = std::min(st->rule50, st->pliesFromNull);
1166 Key originalKey = st->key;
1167 StateInfo* stp = st->previous;
1169 for (int i = 3; i <= end; i += 2)
1171 stp = stp->previous->previous;
1173 Key moveKey = originalKey ^ stp->key;
1174 if ((j = H1(moveKey), cuckoo[j] == moveKey) || (j = H2(moveKey), cuckoo[j] == moveKey))
1176 Move move = cuckooMove[j];
1177 Square s1 = from_sq(move);
1178 Square s2 = to_sq(move);
1180 if (!((between_bb(s1, s2) ^ s2) & pieces()))
1185 // For nodes before or at the root, check that the move is a
1186 // repetition rather than a move to the current position.
1187 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1188 // the same location, so we have to select which square to check.
1189 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1192 // For repetitions before or at the root, require one more
1193 if (stp->repetition)
1202 // Flips position with the white and black sides reversed. This
1203 // is only useful for debugging e.g. for finding evaluation symmetry bugs.
1204 void Position::flip() {
1207 std::stringstream ss(fen());
1209 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1211 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1212 f.insert(0, token + (f.empty() ? " " : "/"));
1215 ss >> token; // Active color
1216 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1218 ss >> token; // Castling availability
1221 std::transform(f.begin(), f.end(), f.begin(),
1222 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1224 ss >> token; // En passant square
1225 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1227 std::getline(ss, token); // Half and full moves
1230 set(f, is_chess960(), st, this_thread());
1232 assert(pos_is_ok());
1236 // Performs some consistency checks for the
1237 // position object and raise an assert if something wrong is detected.
1238 // This is meant to be helpful when debugging.
1239 bool Position::pos_is_ok() const {
1241 constexpr bool Fast = true; // Quick (default) or full check?
1243 if ((sideToMove != WHITE && sideToMove != BLACK) || piece_on(square<KING>(WHITE)) != W_KING
1244 || piece_on(square<KING>(BLACK)) != B_KING
1245 || (ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6))
1246 assert(0 && "pos_is_ok: Default");
1251 if (pieceCount[W_KING] != 1 || pieceCount[B_KING] != 1
1252 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1253 assert(0 && "pos_is_ok: Kings");
1255 if ((pieces(PAWN) & (Rank1BB | Rank8BB)) || pieceCount[W_PAWN] > 8 || pieceCount[B_PAWN] > 8)
1256 assert(0 && "pos_is_ok: Pawns");
1258 if ((pieces(WHITE) & pieces(BLACK)) || (pieces(WHITE) | pieces(BLACK)) != pieces()
1259 || popcount(pieces(WHITE)) > 16 || popcount(pieces(BLACK)) > 16)
1260 assert(0 && "pos_is_ok: Bitboards");
1262 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1263 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1264 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1265 assert(0 && "pos_is_ok: Bitboards");
1268 for (Piece pc : Pieces)
1269 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1270 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1271 assert(0 && "pos_is_ok: Pieces");
1273 for (Color c : {WHITE, BLACK})
1274 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1276 if (!can_castle(cr))
1279 if (piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1280 || castlingRightsMask[castlingRookSquare[cr]] != cr
1281 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1282 assert(0 && "pos_is_ok: Castling");
1288 } // namespace Stockfish