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 /// operator<<(Position) returns an ASCII representation of the position
66 std::ostream& operator<<(std::ostream& os, const Position& pos) {
68 os << "\n +---+---+---+---+---+---+---+---+\n";
70 for (Rank r = RANK_8; r >= RANK_1; --r)
72 for (File f = FILE_A; f <= FILE_H; ++f)
73 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
75 os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n";
78 os << " a b c d e f g h\n"
79 << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
80 << std::setfill('0') << std::setw(16) << pos.key()
81 << std::setfill(' ') << std::dec << "\nCheckers: ";
83 for (Bitboard b = pos.checkers(); b; )
84 os << UCI::square(pop_lsb(b)) << " ";
86 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
87 && !pos.can_castle(ANY_CASTLING))
90 ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
93 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
94 Tablebases::ProbeState s1, s2;
95 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
96 int dtz = Tablebases::probe_dtz(p, &s2);
97 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
98 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
105 // Implements Marcel van Kervinck's cuckoo algorithm to detect repetition of positions
106 // for 3-fold repetition draws. The algorithm uses two hash tables with Zobrist hashes to
107 // allow fast detection of recurring positions. For details see:
108 // http://web.archive.org/web/20201107002606/https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
110 // First and second hash functions for indexing the cuckoo tables
111 inline int H1(Key h) { return h & 0x1fff; }
112 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
114 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
116 Move cuckooMove[8192];
119 /// Position::init() initializes at startup the various arrays used to compute hash keys
121 void Position::init() {
125 for (Piece pc : Pieces)
126 for (Square s = SQ_A1; s <= SQ_H8; ++s)
127 Zobrist::psq[pc][s] = rng.rand<Key>();
129 for (File f = FILE_A; f <= FILE_H; ++f)
130 Zobrist::enpassant[f] = rng.rand<Key>();
132 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
133 Zobrist::castling[cr] = rng.rand<Key>();
135 Zobrist::side = rng.rand<Key>();
137 // Prepare the cuckoo tables
138 std::memset(cuckoo, 0, sizeof(cuckoo));
139 std::memset(cuckooMove, 0, sizeof(cuckooMove));
140 [[maybe_unused]] int count = 0;
141 for (Piece pc : Pieces)
142 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
143 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
144 if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2))
146 Move move = make_move(s1, s2);
147 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
151 std::swap(cuckoo[i], key);
152 std::swap(cuckooMove[i], move);
153 if (move == MOVE_NONE) // Arrived at empty slot?
155 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
159 assert(count == 3668);
163 /// Position::set() initializes the position object with the given FEN string.
164 /// This function is not very robust - make sure that input FENs are correct,
165 /// this is assumed to be the responsibility of the GUI.
167 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
169 A FEN string defines a particular position using only the ASCII character set.
171 A FEN string contains six fields separated by a space. The fields are:
173 1) Piece placement (from white's perspective). Each rank is described, starting
174 with rank 8 and ending with rank 1. Within each rank, the contents of each
175 square are described from file A through file H. Following the Standard
176 Algebraic Notation (SAN), each piece is identified by a single letter taken
177 from the standard English names. White pieces are designated using upper-case
178 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
179 noted using digits 1 through 8 (the number of blank squares), and "/"
182 2) Active color. "w" means white moves next, "b" means black.
184 3) Castling availability. If neither side can castle, this is "-". Otherwise,
185 this has one or more letters: "K" (White can castle kingside), "Q" (White
186 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
187 can castle queenside).
189 4) En passant target square (in algebraic notation). If there's no en passant
190 target square, this is "-". If a pawn has just made a 2-square move, this
191 is the position "behind" the pawn. Following X-FEN standard, this is recorded only
192 if there is a pawn in position to make an en passant capture, and if there really
193 is a pawn that might have advanced two squares.
195 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
196 or capture. This is used to determine if a draw can be claimed under the
199 6) Fullmove number. The number of the full move. It starts at 1, and is
200 incremented after Black's move.
203 unsigned char col, row, token;
206 std::istringstream ss(fenStr);
208 std::memset(this, 0, sizeof(Position));
209 std::memset(si, 0, sizeof(StateInfo));
214 // 1. Piece placement
215 while ((ss >> token) && !isspace(token))
218 sq += (token - '0') * EAST; // Advance the given number of files
220 else if (token == '/')
223 else if ((idx = PieceToChar.find(token)) != string::npos) {
224 put_piece(Piece(idx), sq);
231 sideToMove = (token == 'w' ? WHITE : BLACK);
234 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
235 // Shredder-FEN that uses the letters of the columns on which the rooks began
236 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
237 // if an inner rook is associated with the castling right, the castling tag is
238 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
239 while ((ss >> token) && !isspace(token))
242 Color c = islower(token) ? BLACK : WHITE;
243 Piece rook = make_piece(c, ROOK);
245 token = char(toupper(token));
248 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
250 else if (token == 'Q')
251 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
253 else if (token >= 'A' && token <= 'H')
254 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
259 set_castling_right(c, rsq);
262 // 4. En passant square.
263 // Ignore if square is invalid or not on side to move relative rank 6.
264 bool enpassant = false;
266 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
267 && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3'))))
269 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
271 // En passant square will be considered only if
272 // a) side to move have a pawn threatening epSquare
273 // b) there is an enemy pawn in front of epSquare
274 // c) there is no piece on epSquare or behind epSquare
275 enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN)
276 && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))
277 && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove))));
281 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 gamePly starting from 0,
287 // handle also common incorrect FEN with fullmove = 0.
288 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
290 chess960 = isChess960;
300 /// Position::set_castling_right() is a helper function used to set castling
301 /// rights given the corresponding color and the rook starting square.
303 void Position::set_castling_right(Color c, Square rfrom) {
305 Square kfrom = square<KING>(c);
306 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
308 st->castlingRights |= cr;
309 castlingRightsMask[kfrom] |= cr;
310 castlingRightsMask[rfrom] |= cr;
311 castlingRookSquare[cr] = rfrom;
313 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
314 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
316 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto))
321 /// Position::set_check_info() sets king attacks to detect if a move gives check
323 void Position::set_check_info() const {
325 update_slider_blockers(WHITE);
326 update_slider_blockers(BLACK);
328 Square ksq = square<KING>(~sideToMove);
330 st->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
331 st->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
332 st->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
333 st->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
334 st->checkSquares[QUEEN] = st->checkSquares[BISHOP] | st->checkSquares[ROOK];
335 st->checkSquares[KING] = 0;
339 /// Position::set_state() computes the hash keys of the position, and other
340 /// data that once computed is updated incrementally as moves are made.
341 /// The function is only used when a new position is set up
343 void Position::set_state() const {
345 st->key = st->materialKey = 0;
346 st->nonPawnMaterial[WHITE] = st->nonPawnMaterial[BLACK] = VALUE_ZERO;
347 st->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
351 for (Bitboard b = pieces(); b; )
353 Square s = pop_lsb(b);
354 Piece pc = piece_on(s);
355 st->key ^= Zobrist::psq[pc][s];
357 if (type_of(pc) != KING && type_of(pc) != PAWN)
358 st->nonPawnMaterial[color_of(pc)] += PieceValue[pc];
361 if (st->epSquare != SQ_NONE)
362 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
364 if (sideToMove == BLACK)
365 st->key ^= Zobrist::side;
367 st->key ^= Zobrist::castling[st->castlingRights];
369 for (Piece pc : Pieces)
370 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
371 st->materialKey ^= Zobrist::psq[pc][cnt];
375 /// Position::set() is an overload to initialize the position object with
376 /// the given endgame code string like "KBPKN". It is mainly a helper to
377 /// get the material key out of an endgame code.
379 Position& Position::set(const string& code, Color c, StateInfo* si) {
381 assert(code[0] == 'K');
383 string sides[] = { code.substr(code.find('K', 1)), // Weak
384 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
386 assert(sides[0].length() > 0 && sides[0].length() < 8);
387 assert(sides[1].length() > 0 && sides[1].length() < 8);
389 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
391 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
392 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
394 return set(fenStr, false, si, nullptr);
398 /// Position::fen() returns a FEN representation of the position. In case of
399 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
401 string Position::fen() const {
404 std::ostringstream ss;
406 for (Rank r = RANK_8; r >= RANK_1; --r)
408 for (File f = FILE_A; f <= FILE_H; ++f)
410 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
417 ss << PieceToChar[piece_on(make_square(f, r))];
424 ss << (sideToMove == WHITE ? " w " : " b ");
426 if (can_castle(WHITE_OO))
427 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
429 if (can_castle(WHITE_OOO))
430 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
432 if (can_castle(BLACK_OO))
433 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
435 if (can_castle(BLACK_OOO))
436 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
438 if (!can_castle(ANY_CASTLING))
441 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
442 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
447 /// update_slider_blockers() calculates st->blockersForKing[c] and st->pinners[~c],
448 /// which store respectively the pieces preventing king of color c from being in check
449 /// and the slider pieces of color ~c pinning pieces of color c to the king.
450 void Position::update_slider_blockers(Color c) const {
452 Square ksq = square<KING>(c);
454 st->blockersForKing[c] = 0;
457 // Snipers are sliders that attack 's' when a piece and other snipers are removed
458 Bitboard snipers = ( (attacks_bb< ROOK>(ksq) & pieces(QUEEN, ROOK))
459 | (attacks_bb<BISHOP>(ksq) & pieces(QUEEN, BISHOP))) & pieces(~c);
460 Bitboard occupancy = pieces() ^ snipers;
464 Square sniperSq = pop_lsb(snipers);
465 Bitboard b = between_bb(ksq, sniperSq) & occupancy;
467 if (b && !more_than_one(b))
469 st->blockersForKing[c] |= b;
471 st->pinners[~c] |= sniperSq;
477 /// Position::attackers_to() computes a bitboard of all pieces which attack a
478 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
480 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
482 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
483 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
484 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
485 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
486 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
487 | (attacks_bb<KING>(s) & pieces(KING));
491 /// Position::legal() tests whether a pseudo-legal move is legal
493 bool Position::legal(Move m) const {
497 Color us = sideToMove;
498 Square from = from_sq(m);
499 Square to = to_sq(m);
501 assert(color_of(moved_piece(m)) == us);
502 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
504 // En passant captures are a tricky special case. Because they are rather
505 // uncommon, we do it simply by testing whether the king is attacked after
507 if (type_of(m) == EN_PASSANT)
509 Square ksq = square<KING>(us);
510 Square capsq = to - pawn_push(us);
511 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
513 assert(to == ep_square());
514 assert(moved_piece(m) == make_piece(us, PAWN));
515 assert(piece_on(capsq) == make_piece(~us, PAWN));
516 assert(piece_on(to) == NO_PIECE);
518 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
519 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
522 // Castling moves generation does not check if the castling path is clear of
523 // enemy attacks, it is delayed at a later time: now!
524 if (type_of(m) == CASTLING)
526 // After castling, the rook and king final positions are the same in
527 // Chess960 as they would be in standard chess.
528 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
529 Direction step = to > from ? WEST : EAST;
531 for (Square s = to; s != from; s += step)
532 if (attackers_to(s) & pieces(~us))
535 // In case of Chess960, verify if the Rook blocks some checks
536 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
537 return !chess960 || !(blockers_for_king(us) & to_sq(m));
540 // If the moving piece is a king, check whether the destination square is
541 // attacked by the opponent.
542 if (type_of(piece_on(from)) == KING)
543 return !(attackers_to(to, pieces() ^ from) & pieces(~us));
545 // A non-king move is legal if and only if it is not pinned or it
546 // is moving along the ray towards or away from the king.
547 return !(blockers_for_king(us) & from)
548 || aligned(from, to, square<KING>(us));
552 /// Position::pseudo_legal() takes a random move and tests whether the move is
553 /// pseudo-legal. It is used to validate moves from TT that can be corrupted
554 /// due to SMP concurrent access or hash position key aliasing.
556 bool Position::pseudo_legal(const Move m) const {
558 Color us = sideToMove;
559 Square from = from_sq(m);
560 Square to = to_sq(m);
561 Piece pc = moved_piece(m);
563 // Use a slower but simpler function for uncommon cases
564 // yet we skip the legality check of MoveList<LEGAL>().
565 if (type_of(m) != NORMAL)
566 return checkers() ? MoveList< EVASIONS>(*this).contains(m)
567 : MoveList<NON_EVASIONS>(*this).contains(m);
569 // Is not a promotion, so the promotion piece must be empty
570 assert(promotion_type(m) - KNIGHT == NO_PIECE_TYPE);
572 // If the 'from' square is not occupied by a piece belonging to the side to
573 // move, the move is obviously not legal.
574 if (pc == NO_PIECE || color_of(pc) != us)
577 // The destination square cannot be occupied by a friendly piece
581 // Handle the special case of a pawn move
582 if (type_of(pc) == PAWN)
584 // We have already handled promotion moves, so destination
585 // cannot be on the 8th/1st rank.
586 if ((Rank8BB | Rank1BB) & to)
589 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
590 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
591 && !( (from + 2 * pawn_push(us) == to) // Not a double push
592 && (relative_rank(us, from) == RANK_2)
594 && empty(to - pawn_push(us))))
597 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
600 // Evasions generator already takes care to avoid some kind of illegal moves
601 // and legal() relies on this. We therefore have to take care that the same
602 // kind of moves are filtered out here.
605 if (type_of(pc) != KING)
607 // Double check? In this case, a king move is required
608 if (more_than_one(checkers()))
611 // Our move must be a blocking interposition or a capture of the checking piece
612 if (!(between_bb(square<KING>(us), lsb(checkers())) & to))
615 // In case of king moves under check we have to remove the king so as to catch
616 // invalid moves like b1a1 when opposite queen is on c1.
617 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
625 /// Position::gives_check() tests whether a pseudo-legal move gives a check
627 bool Position::gives_check(Move m) const {
630 assert(color_of(moved_piece(m)) == sideToMove);
632 Square from = from_sq(m);
633 Square to = to_sq(m);
635 // Is there a direct check?
636 if (check_squares(type_of(piece_on(from))) & to)
639 // Is there a discovered check?
640 if (blockers_for_king(~sideToMove) & from)
641 return !aligned(from, to, square<KING>(~sideToMove))
642 || type_of(m) == CASTLING;
650 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
652 // En passant capture with check? We have already handled the case
653 // of direct checks and ordinary discovered check, so the only case we
654 // need to handle is the unusual case of a discovered check through
655 // the captured pawn.
658 Square capsq = make_square(file_of(to), rank_of(from));
659 Bitboard b = (pieces() ^ from ^ capsq) | to;
661 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
662 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
666 // Castling is encoded as 'king captures the rook'
667 Square rto = relative_square(sideToMove, to > from ? SQ_F1 : SQ_D1);
669 return check_squares(ROOK) & rto;
675 /// Position::do_move() makes a move, and saves all information necessary
676 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
677 /// moves should be filtered out before this function is called.
679 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
682 assert(&newSt != st);
684 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
685 Key k = st->key ^ Zobrist::side;
687 // Copy some fields of the old state to our new StateInfo object except the
688 // ones which are going to be recalculated from scratch anyway and then switch
689 // our state pointer to point to the new (ready to be updated) state.
690 std::memcpy(&newSt, st, offsetof(StateInfo, key));
694 // Increment ply counters. In particular, rule50 will be reset to zero later on
695 // in case of a capture or a pawn move.
701 st->accumulator.computed[WHITE] = false;
702 st->accumulator.computed[BLACK] = false;
703 auto& dp = st->dirtyPiece;
706 Color us = sideToMove;
708 Square from = from_sq(m);
709 Square to = to_sq(m);
710 Piece pc = piece_on(from);
711 Piece captured = type_of(m) == EN_PASSANT ? make_piece(them, PAWN) : piece_on(to);
713 assert(color_of(pc) == us);
714 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
715 assert(type_of(captured) != KING);
717 if (type_of(m) == CASTLING)
719 assert(pc == make_piece(us, KING));
720 assert(captured == make_piece(us, ROOK));
723 do_castling<true>(us, from, to, rfrom, rto);
725 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
733 // If the captured piece is a pawn, update pawn hash key, otherwise
734 // update non-pawn material.
735 if (type_of(captured) == PAWN)
737 if (type_of(m) == EN_PASSANT)
739 capsq -= pawn_push(us);
741 assert(pc == make_piece(us, PAWN));
742 assert(to == st->epSquare);
743 assert(relative_rank(us, to) == RANK_6);
744 assert(piece_on(to) == NO_PIECE);
745 assert(piece_on(capsq) == make_piece(them, PAWN));
749 st->nonPawnMaterial[them] -= PieceValue[captured];
751 dp.dirty_num = 2; // 1 piece moved, 1 piece captured
752 dp.piece[1] = captured;
756 // Update board and piece lists
759 // Update material hash key and prefetch access to materialTable
760 k ^= Zobrist::psq[captured][capsq];
761 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
763 // Reset rule 50 counter
768 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
770 // Reset en passant square
771 if (st->epSquare != SQ_NONE)
773 k ^= Zobrist::enpassant[file_of(st->epSquare)];
774 st->epSquare = SQ_NONE;
777 // Update castling rights if needed
778 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
780 k ^= Zobrist::castling[st->castlingRights];
781 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
782 k ^= Zobrist::castling[st->castlingRights];
785 // Move the piece. The tricky Chess960 castling is handled earlier
786 if (type_of(m) != CASTLING)
792 move_piece(from, to);
795 // If the moving piece is a pawn do some special extra work
796 if (type_of(pc) == PAWN)
798 // Set en passant square if the moved pawn can be captured
799 if ( (int(to) ^ int(from)) == 16
800 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
802 st->epSquare = to - pawn_push(us);
803 k ^= Zobrist::enpassant[file_of(st->epSquare)];
806 else if (type_of(m) == PROMOTION)
808 Piece promotion = make_piece(us, promotion_type(m));
810 assert(relative_rank(us, to) == RANK_8);
811 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
814 put_piece(promotion, to);
816 // Promoting pawn to SQ_NONE, promoted piece from SQ_NONE
818 dp.piece[dp.dirty_num] = promotion;
819 dp.from[dp.dirty_num] = SQ_NONE;
820 dp.to[dp.dirty_num] = to;
824 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
825 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
826 ^ Zobrist::psq[pc][pieceCount[pc]];
829 st->nonPawnMaterial[us] += PieceValue[promotion];
832 // Reset rule 50 draw counter
837 st->capturedPiece = captured;
839 // Update the key with the final value
842 // Calculate checkers bitboard (if move gives check)
843 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
845 sideToMove = ~sideToMove;
847 // Update king attacks used for fast check detection
850 // Calculate the repetition info. It is the ply distance from the previous
851 // occurrence of the same position, negative in the 3-fold case, or zero
852 // if the position was not repeated.
854 int end = std::min(st->rule50, st->pliesFromNull);
857 StateInfo* stp = st->previous->previous;
858 for (int i = 4; i <= end; i += 2)
860 stp = stp->previous->previous;
861 if (stp->key == st->key)
863 st->repetition = stp->repetition ? -i : i;
873 /// Position::undo_move() unmakes a move. When it returns, the position should
874 /// be restored to exactly the same state as before the move was made.
876 void Position::undo_move(Move m) {
880 sideToMove = ~sideToMove;
882 Color us = sideToMove;
883 Square from = from_sq(m);
884 Square to = to_sq(m);
885 Piece pc = piece_on(to);
887 assert(empty(from) || type_of(m) == CASTLING);
888 assert(type_of(st->capturedPiece) != KING);
890 if (type_of(m) == PROMOTION)
892 assert(relative_rank(us, to) == RANK_8);
893 assert(type_of(pc) == promotion_type(m));
894 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
897 pc = make_piece(us, PAWN);
901 if (type_of(m) == CASTLING)
904 do_castling<false>(us, from, to, rfrom, rto);
908 move_piece(to, from); // Put the piece back at the source square
910 if (st->capturedPiece)
914 if (type_of(m) == EN_PASSANT)
916 capsq -= pawn_push(us);
918 assert(type_of(pc) == PAWN);
919 assert(to == st->previous->epSquare);
920 assert(relative_rank(us, to) == RANK_6);
921 assert(piece_on(capsq) == NO_PIECE);
922 assert(st->capturedPiece == make_piece(~us, PAWN));
925 put_piece(st->capturedPiece, capsq); // Restore the captured piece
929 // Finally point our state pointer back to the previous state
937 /// Position::do_castling() is a helper used to do/undo a castling move. This
938 /// is a bit tricky in Chess960 where from/to squares can overlap.
940 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
942 bool kingSide = to > from;
943 rfrom = to; // Castling is encoded as "king captures friendly rook"
944 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
945 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
949 auto& dp = st->dirtyPiece;
950 dp.piece[0] = make_piece(us, KING);
953 dp.piece[1] = make_piece(us, ROOK);
959 // Remove both pieces first since squares could overlap in Chess960
960 remove_piece(Do ? from : to);
961 remove_piece(Do ? rfrom : rto);
962 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
963 put_piece(make_piece(us, KING), Do ? to : from);
964 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
968 /// Position::do_null_move() is used to do a "null move": it flips
969 /// the side to move without executing any move on the board.
971 void Position::do_null_move(StateInfo& newSt) {
974 assert(&newSt != st);
976 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
981 st->dirtyPiece.dirty_num = 0;
982 st->dirtyPiece.piece[0] = NO_PIECE; // Avoid checks in UpdateAccumulator()
983 st->accumulator.computed[WHITE] = false;
984 st->accumulator.computed[BLACK] = false;
986 if (st->epSquare != SQ_NONE)
988 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
989 st->epSquare = SQ_NONE;
992 st->key ^= Zobrist::side;
994 prefetch(TT.first_entry(key()));
996 st->pliesFromNull = 0;
998 sideToMove = ~sideToMove;
1004 assert(pos_is_ok());
1008 /// Position::undo_null_move() must be used to undo a "null move"
1010 void Position::undo_null_move() {
1012 assert(!checkers());
1015 sideToMove = ~sideToMove;
1019 /// Position::key_after() computes the new hash key after the given move. Needed
1020 /// for speculative prefetch. It doesn't recognize special moves like castling,
1021 /// en passant and promotions.
1023 Key Position::key_after(Move m) const {
1025 Square from = from_sq(m);
1026 Square to = to_sq(m);
1027 Piece pc = piece_on(from);
1028 Piece captured = piece_on(to);
1029 Key k = st->key ^ Zobrist::side;
1032 k ^= Zobrist::psq[captured][to];
1034 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1036 return (captured || type_of(pc) == PAWN)
1037 ? k : adjust_key50<true>(k);
1041 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1042 /// SEE value of move is greater or equal to the given threshold. We'll use an
1043 /// algorithm similar to alpha-beta pruning with a null window.
1045 bool Position::see_ge(Move m, Value threshold) const {
1049 // Only deal with normal moves, assume others pass a simple SEE
1050 if (type_of(m) != NORMAL)
1051 return VALUE_ZERO >= threshold;
1053 Square from = from_sq(m), to = to_sq(m);
1055 int swap = PieceValue[piece_on(to)] - threshold;
1059 swap = PieceValue[piece_on(from)] - swap;
1063 assert(color_of(piece_on(from)) == sideToMove);
1064 Bitboard occupied = pieces() ^ from ^ to; // xoring to is important for pinned piece logic
1065 Color stm = sideToMove;
1066 Bitboard attackers = attackers_to(to, occupied);
1067 Bitboard stmAttackers, bb;
1073 attackers &= occupied;
1075 // If stm has no more attackers then give up: stm loses
1076 if (!(stmAttackers = attackers & pieces(stm)))
1079 // Don't allow pinned pieces to attack as long as there are
1080 // pinners on their original square.
1081 if (pinners(~stm) & occupied)
1083 stmAttackers &= ~blockers_for_king(stm);
1091 // Locate and remove the next least valuable attacker, and add to
1092 // the bitboard 'attackers' any X-ray attackers behind it.
1093 if ((bb = stmAttackers & pieces(PAWN)))
1095 if ((swap = PawnValue - swap) < res)
1097 occupied ^= least_significant_square_bb(bb);
1099 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1102 else if ((bb = stmAttackers & pieces(KNIGHT)))
1104 if ((swap = KnightValue - swap) < res)
1106 occupied ^= least_significant_square_bb(bb);
1109 else if ((bb = stmAttackers & pieces(BISHOP)))
1111 if ((swap = BishopValue - swap) < res)
1113 occupied ^= least_significant_square_bb(bb);
1115 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1118 else if ((bb = stmAttackers & pieces(ROOK)))
1120 if ((swap = RookValue - swap) < res)
1122 occupied ^= least_significant_square_bb(bb);
1124 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1127 else if ((bb = stmAttackers & pieces(QUEEN)))
1129 if ((swap = QueenValue - swap) < res)
1131 occupied ^= least_significant_square_bb(bb);
1133 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1134 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1138 // If we "capture" with the king but the opponent still has attackers,
1139 // reverse the result.
1140 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1146 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1147 /// or by repetition. It does not detect stalemates.
1149 bool Position::is_draw(int ply) const {
1151 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1154 // Return a draw score if a position repeats once earlier but strictly
1155 // after the root, or repeats twice before or at the root.
1156 return st->repetition && st->repetition < ply;
1160 // Position::has_repeated() tests whether there has been at least one repetition
1161 // of positions since the last capture or pawn move.
1163 bool Position::has_repeated() const {
1165 StateInfo* stc = st;
1166 int end = std::min(st->rule50, st->pliesFromNull);
1169 if (stc->repetition)
1172 stc = stc->previous;
1178 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1179 /// or an earlier position has a move that directly reaches the current position.
1181 bool Position::has_game_cycle(int ply) const {
1185 int end = std::min(st->rule50, st->pliesFromNull);
1190 Key originalKey = st->key;
1191 StateInfo* stp = st->previous;
1193 for (int i = 3; i <= end; i += 2)
1195 stp = stp->previous->previous;
1197 Key moveKey = originalKey ^ stp->key;
1198 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1199 || (j = H2(moveKey), cuckoo[j] == moveKey))
1201 Move move = cuckooMove[j];
1202 Square s1 = from_sq(move);
1203 Square s2 = to_sq(move);
1205 if (!((between_bb(s1, s2) ^ s2) & pieces()))
1210 // For nodes before or at the root, check that the move is a
1211 // repetition rather than a move to the current position.
1212 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1213 // the same location, so we have to select which square to check.
1214 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1217 // For repetitions before or at the root, require one more
1218 if (stp->repetition)
1227 /// Position::flip() flips position with the white and black sides reversed. This
1228 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1230 void Position::flip() {
1233 std::stringstream ss(fen());
1235 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1237 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1238 f.insert(0, token + (f.empty() ? " " : "/"));
1241 ss >> token; // Active color
1242 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1244 ss >> token; // Castling availability
1247 std::transform(f.begin(), f.end(), f.begin(),
1248 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1250 ss >> token; // En passant square
1251 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1253 std::getline(ss, token); // Half and full moves
1256 set(f, is_chess960(), st, this_thread());
1258 assert(pos_is_ok());
1262 /// Position::pos_is_ok() performs some consistency checks for the
1263 /// position object and raise an assert if something wrong is detected.
1264 /// This is meant to be helpful when debugging.
1266 bool Position::pos_is_ok() const {
1268 constexpr bool Fast = true; // Quick (default) or full check?
1270 if ( (sideToMove != WHITE && sideToMove != BLACK)
1271 || piece_on(square<KING>(WHITE)) != W_KING
1272 || piece_on(square<KING>(BLACK)) != B_KING
1273 || ( ep_square() != SQ_NONE
1274 && relative_rank(sideToMove, ep_square()) != RANK_6))
1275 assert(0 && "pos_is_ok: Default");
1280 if ( pieceCount[W_KING] != 1
1281 || pieceCount[B_KING] != 1
1282 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1283 assert(0 && "pos_is_ok: Kings");
1285 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1286 || pieceCount[W_PAWN] > 8
1287 || pieceCount[B_PAWN] > 8)
1288 assert(0 && "pos_is_ok: Pawns");
1290 if ( (pieces(WHITE) & pieces(BLACK))
1291 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1292 || popcount(pieces(WHITE)) > 16
1293 || popcount(pieces(BLACK)) > 16)
1294 assert(0 && "pos_is_ok: Bitboards");
1296 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1297 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1298 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1299 assert(0 && "pos_is_ok: Bitboards");
1302 for (Piece pc : Pieces)
1303 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1304 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1305 assert(0 && "pos_is_ok: Pieces");
1307 for (Color c : { WHITE, BLACK })
1308 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1310 if (!can_castle(cr))
1313 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1314 || castlingRightsMask[castlingRookSquare[cr]] != cr
1315 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1316 assert(0 && "pos_is_ok: Castling");
1322 } // namespace Stockfish