2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2020 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/>.
21 #include <cstddef> // For offsetof()
22 #include <cstring> // For std::memset, std::memcmp
33 #include "syzygy/tbprobe.h"
39 Key psq[PIECE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
47 const string PieceToChar(" PNBRQK pnbrqk");
49 constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
50 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
54 /// operator<<(Position) returns an ASCII representation of the position
56 std::ostream& operator<<(std::ostream& os, const Position& pos) {
58 os << "\n +---+---+---+---+---+---+---+---+\n";
60 for (Rank r = RANK_8; r >= RANK_1; --r)
62 for (File f = FILE_A; f <= FILE_H; ++f)
63 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
65 os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n";
68 os << " a b c d e f g h\n"
69 << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
70 << std::setfill('0') << std::setw(16) << pos.key()
71 << std::setfill(' ') << std::dec << "\nCheckers: ";
73 for (Bitboard b = pos.checkers(); b; )
74 os << UCI::square(pop_lsb(&b)) << " ";
76 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
77 && !pos.can_castle(ANY_CASTLING))
81 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
82 Tablebases::ProbeState s1, s2;
83 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
84 int dtz = Tablebases::probe_dtz(p, &s2);
85 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
86 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
93 // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
94 // situations. Description of the algorithm in the following paper:
95 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
97 // First and second hash functions for indexing the cuckoo tables
98 inline int H1(Key h) { return h & 0x1fff; }
99 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
101 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
103 Move cuckooMove[8192];
106 /// Position::init() initializes at startup the various arrays used to compute hash keys
108 void Position::init() {
112 for (Piece pc : Pieces)
113 for (Square s = SQ_A1; s <= SQ_H8; ++s)
114 Zobrist::psq[pc][s] = rng.rand<Key>();
116 for (File f = FILE_A; f <= FILE_H; ++f)
117 Zobrist::enpassant[f] = rng.rand<Key>();
119 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
120 Zobrist::castling[cr] = rng.rand<Key>();
122 Zobrist::side = rng.rand<Key>();
123 Zobrist::noPawns = rng.rand<Key>();
125 // Prepare the cuckoo tables
126 std::memset(cuckoo, 0, sizeof(cuckoo));
127 std::memset(cuckooMove, 0, sizeof(cuckooMove));
129 for (Piece pc : Pieces)
130 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
131 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
132 if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2))
134 Move move = make_move(s1, s2);
135 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
139 std::swap(cuckoo[i], key);
140 std::swap(cuckooMove[i], move);
141 if (move == MOVE_NONE) // Arrived at empty slot?
143 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
147 assert(count == 3668);
151 /// Position::set() initializes the position object with the given FEN string.
152 /// This function is not very robust - make sure that input FENs are correct,
153 /// this is assumed to be the responsibility of the GUI.
155 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
157 A FEN string defines a particular position using only the ASCII character set.
159 A FEN string contains six fields separated by a space. The fields are:
161 1) Piece placement (from white's perspective). Each rank is described, starting
162 with rank 8 and ending with rank 1. Within each rank, the contents of each
163 square are described from file A through file H. Following the Standard
164 Algebraic Notation (SAN), each piece is identified by a single letter taken
165 from the standard English names. White pieces are designated using upper-case
166 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
167 noted using digits 1 through 8 (the number of blank squares), and "/"
170 2) Active color. "w" means white moves next, "b" means black.
172 3) Castling availability. If neither side can castle, this is "-". Otherwise,
173 this has one or more letters: "K" (White can castle kingside), "Q" (White
174 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
175 can castle queenside).
177 4) En passant target square (in algebraic notation). If there's no en passant
178 target square, this is "-". If a pawn has just made a 2-square move, this
179 is the position "behind" the pawn. Following X-FEN standard, this is recorded only
180 if there is a pawn in position to make an en passant capture, and if there really
181 is a pawn that might have advanced two squares.
183 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
184 or capture. This is used to determine if a draw can be claimed under the
187 6) Fullmove number. The number of the full move. It starts at 1, and is
188 incremented after Black's move.
191 unsigned char col, row, token;
194 std::istringstream ss(fenStr);
196 std::memset(this, 0, sizeof(Position));
197 std::memset(si, 0, sizeof(StateInfo));
198 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
203 // 1. Piece placement
204 while ((ss >> token) && !isspace(token))
207 sq += (token - '0') * EAST; // Advance the given number of files
209 else if (token == '/')
212 else if ((idx = PieceToChar.find(token)) != string::npos) {
213 put_piece(Piece(idx), sq);
220 sideToMove = (token == 'w' ? WHITE : BLACK);
223 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
224 // Shredder-FEN that uses the letters of the columns on which the rooks began
225 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
226 // if an inner rook is associated with the castling right, the castling tag is
227 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
228 while ((ss >> token) && !isspace(token))
231 Color c = islower(token) ? BLACK : WHITE;
232 Piece rook = make_piece(c, ROOK);
234 token = char(toupper(token));
237 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
239 else if (token == 'Q')
240 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
242 else if (token >= 'A' && token <= 'H')
243 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
248 set_castling_right(c, rsq);
251 // 4. En passant square.
252 // Ignore if square is invalid or not on side to move relative rank 6.
253 bool enpassant = false;
255 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
256 && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3'))))
258 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
260 // En passant square will be considered only if
261 // a) side to move have a pawn threatening epSquare
262 // b) there is an enemy pawn in front of epSquare
263 // c) there is no piece on epSquare or behind epSquare
264 enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN)
265 && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))
266 && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove))));
270 st->epSquare = SQ_NONE;
272 // 5-6. Halfmove clock and fullmove number
273 ss >> std::skipws >> st->rule50 >> gamePly;
275 // Convert from fullmove starting from 1 to gamePly starting from 0,
276 // handle also common incorrect FEN with fullmove = 0.
277 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
279 chess960 = isChess960;
282 st->accumulator.state[WHITE] = Eval::NNUE::INIT;
283 st->accumulator.state[BLACK] = Eval::NNUE::INIT;
291 /// Position::set_castling_right() is a helper function used to set castling
292 /// rights given the corresponding color and the rook starting square.
294 void Position::set_castling_right(Color c, Square rfrom) {
296 Square kfrom = square<KING>(c);
297 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
299 st->castlingRights |= cr;
300 castlingRightsMask[kfrom] |= cr;
301 castlingRightsMask[rfrom] |= cr;
302 castlingRookSquare[cr] = rfrom;
304 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
305 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
307 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
312 /// Position::set_check_info() sets king attacks to detect if a move gives check
314 void Position::set_check_info(StateInfo* si) const {
316 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
317 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
319 Square ksq = square<KING>(~sideToMove);
321 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
322 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
323 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
324 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
325 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
326 si->checkSquares[KING] = 0;
330 /// Position::set_state() computes the hash keys of the position, and other
331 /// data that once computed is updated incrementally as moves are made.
332 /// The function is only used when a new position is set up, and to verify
333 /// the correctness of the StateInfo data when running in debug mode.
335 void Position::set_state(StateInfo* si) const {
337 si->key = si->materialKey = 0;
338 si->pawnKey = Zobrist::noPawns;
339 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
340 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
344 for (Bitboard b = pieces(); b; )
346 Square s = pop_lsb(&b);
347 Piece pc = piece_on(s);
348 si->key ^= Zobrist::psq[pc][s];
350 if (type_of(pc) == PAWN)
351 si->pawnKey ^= Zobrist::psq[pc][s];
353 else if (type_of(pc) != KING)
354 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
357 if (si->epSquare != SQ_NONE)
358 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
360 if (sideToMove == BLACK)
361 si->key ^= Zobrist::side;
363 si->key ^= Zobrist::castling[si->castlingRights];
365 for (Piece pc : Pieces)
366 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
367 si->materialKey ^= Zobrist::psq[pc][cnt];
371 /// Position::set() is an overload to initialize the position object with
372 /// the given endgame code string like "KBPKN". It is mainly a helper to
373 /// get the material key out of an endgame code.
375 Position& Position::set(const string& code, Color c, StateInfo* si) {
377 assert(code[0] == 'K');
379 string sides[] = { code.substr(code.find('K', 1)), // Weak
380 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
382 assert(sides[0].length() > 0 && sides[0].length() < 8);
383 assert(sides[1].length() > 0 && sides[1].length() < 8);
385 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
387 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
388 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
390 return set(fenStr, false, si, nullptr);
394 /// Position::fen() returns a FEN representation of the position. In case of
395 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
397 const string Position::fen() const {
400 std::ostringstream ss;
402 for (Rank r = RANK_8; r >= RANK_1; --r)
404 for (File f = FILE_A; f <= FILE_H; ++f)
406 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
413 ss << PieceToChar[piece_on(make_square(f, r))];
420 ss << (sideToMove == WHITE ? " w " : " b ");
422 if (can_castle(WHITE_OO))
423 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
425 if (can_castle(WHITE_OOO))
426 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
428 if (can_castle(BLACK_OO))
429 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
431 if (can_castle(BLACK_OOO))
432 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
434 if (!can_castle(ANY_CASTLING))
437 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
438 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
444 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
445 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
446 /// slider if removing that piece from the board would result in a position where
447 /// square 's' is attacked. For example, a king-attack blocking piece can be either
448 /// a pinned or a discovered check piece, according if its color is the opposite
449 /// or the same of the color of the slider.
451 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
453 Bitboard blockers = 0;
456 // Snipers are sliders that attack 's' when a piece and other snipers are removed
457 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
458 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
459 Bitboard occupancy = pieces() ^ snipers;
463 Square sniperSq = pop_lsb(&snipers);
464 Bitboard b = between_bb(s, sniperSq) & occupancy;
466 if (b && !more_than_one(b))
469 if (b & pieces(color_of(piece_on(s))))
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) == ENPASSANT)
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 that when moving the castling rook we do
536 // not discover some hidden checker.
537 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
539 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
542 // If the moving piece is a king, check whether the destination square is
543 // attacked by the opponent.
544 if (type_of(piece_on(from)) == KING)
545 return !(attackers_to(to) & pieces(~us));
547 // A non-king move is legal if and only if it is not pinned or it
548 // is moving along the ray towards or away from the king.
549 return !(blockers_for_king(us) & from)
550 || aligned(from, to, square<KING>(us));
554 /// Position::pseudo_legal() takes a random move and tests whether the move is
555 /// pseudo legal. It is used to validate moves from TT that can be corrupted
556 /// due to SMP concurrent access or hash position key aliasing.
558 bool Position::pseudo_legal(const Move m) const {
560 Color us = sideToMove;
561 Square from = from_sq(m);
562 Square to = to_sq(m);
563 Piece pc = moved_piece(m);
565 // Use a slower but simpler function for uncommon cases
566 if (type_of(m) != NORMAL)
567 return MoveList<LEGAL>(*this).contains(m);
569 // Is not a promotion, so promotion piece must be empty
570 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
573 // If the 'from' square is not occupied by a piece belonging to the side to
574 // move, the move is obviously not legal.
575 if (pc == NO_PIECE || color_of(pc) != us)
578 // The destination square cannot be occupied by a friendly piece
582 // Handle the special case of a pawn move
583 if (type_of(pc) == PAWN)
585 // We have already handled promotion moves, so destination
586 // cannot be on the 8th/1st rank.
587 if ((Rank8BB | Rank1BB) & to)
590 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
591 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
592 && !( (from + 2 * pawn_push(us) == to) // Not a double push
593 && (relative_rank(us, from) == RANK_2)
595 && empty(to - pawn_push(us))))
598 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
601 // Evasions generator already takes care to avoid some kind of illegal moves
602 // and legal() relies on this. We therefore have to take care that the same
603 // kind of moves are filtered out here.
606 if (type_of(pc) != KING)
608 // Double check? In this case a king move is required
609 if (more_than_one(checkers()))
612 // Our move must be a blocking evasion or a capture of the checking piece
613 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
616 // In case of king moves under check we have to remove king so as to catch
617 // invalid moves like b1a1 when opposite queen is on c1.
618 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
626 /// Position::gives_check() tests whether a pseudo-legal move gives a check
628 bool Position::gives_check(Move m) const {
631 assert(color_of(moved_piece(m)) == sideToMove);
633 Square from = from_sq(m);
634 Square to = to_sq(m);
636 // Is there a direct check?
637 if (check_squares(type_of(piece_on(from))) & to)
640 // Is there a discovered check?
641 if ( (blockers_for_king(~sideToMove) & from)
642 && !aligned(from, to, square<KING>(~sideToMove)))
651 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
653 // En passant capture with check? We have already handled the case
654 // of direct checks and ordinary discovered check, so the only case we
655 // need to handle is the unusual case of a discovered check through
656 // the captured pawn.
659 Square capsq = make_square(file_of(to), rank_of(from));
660 Bitboard b = (pieces() ^ from ^ capsq) | to;
662 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
663 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
668 Square rfrom = to; // Castling is encoded as 'king captures the rook'
669 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
670 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
672 return (attacks_bb<ROOK>(rto) & square<KING>(~sideToMove))
673 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
682 /// Position::do_move() makes a move, and saves all information necessary
683 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
684 /// moves should be filtered out before this function is called.
686 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
689 assert(&newSt != st);
691 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
692 Key k = st->key ^ Zobrist::side;
694 // Copy some fields of the old state to our new StateInfo object except the
695 // ones which are going to be recalculated from scratch anyway and then switch
696 // our state pointer to point to the new (ready to be updated) state.
697 std::memcpy(&newSt, st, offsetof(StateInfo, key));
701 // Increment ply counters. In particular, rule50 will be reset to zero later on
702 // in case of a capture or a pawn move.
708 st->accumulator.state[WHITE] = Eval::NNUE::EMPTY;
709 st->accumulator.state[BLACK] = Eval::NNUE::EMPTY;
710 auto& dp = st->dirtyPiece;
713 Color us = sideToMove;
715 Square from = from_sq(m);
716 Square to = to_sq(m);
717 Piece pc = piece_on(from);
718 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
720 assert(color_of(pc) == us);
721 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
722 assert(type_of(captured) != KING);
724 if (type_of(m) == CASTLING)
726 assert(pc == make_piece(us, KING));
727 assert(captured == make_piece(us, ROOK));
730 do_castling<true>(us, from, to, rfrom, rto);
732 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
740 // If the captured piece is a pawn, update pawn hash key, otherwise
741 // update non-pawn material.
742 if (type_of(captured) == PAWN)
744 if (type_of(m) == ENPASSANT)
746 capsq -= pawn_push(us);
748 assert(pc == make_piece(us, PAWN));
749 assert(to == st->epSquare);
750 assert(relative_rank(us, to) == RANK_6);
751 assert(piece_on(to) == NO_PIECE);
752 assert(piece_on(capsq) == make_piece(them, PAWN));
755 st->pawnKey ^= Zobrist::psq[captured][capsq];
758 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
762 dp.dirty_num = 2; // 1 piece moved, 1 piece captured
763 dp.piece[1] = captured;
768 // Update board and piece lists
771 if (type_of(m) == ENPASSANT)
772 board[capsq] = NO_PIECE;
774 // Update material hash key and prefetch access to materialTable
775 k ^= Zobrist::psq[captured][capsq];
776 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
777 prefetch(thisThread->materialTable[st->materialKey]);
779 // Reset rule 50 counter
784 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
786 // Reset en passant square
787 if (st->epSquare != SQ_NONE)
789 k ^= Zobrist::enpassant[file_of(st->epSquare)];
790 st->epSquare = SQ_NONE;
793 // Update castling rights if needed
794 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
796 k ^= Zobrist::castling[st->castlingRights];
797 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
798 k ^= Zobrist::castling[st->castlingRights];
801 // Move the piece. The tricky Chess960 castling is handled earlier
802 if (type_of(m) != CASTLING)
811 move_piece(from, to);
814 // If the moving piece is a pawn do some special extra work
815 if (type_of(pc) == PAWN)
817 // Set en-passant square if the moved pawn can be captured
818 if ( (int(to) ^ int(from)) == 16
819 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
821 st->epSquare = to - pawn_push(us);
822 k ^= Zobrist::enpassant[file_of(st->epSquare)];
825 else if (type_of(m) == PROMOTION)
827 Piece promotion = make_piece(us, promotion_type(m));
829 assert(relative_rank(us, to) == RANK_8);
830 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
833 put_piece(promotion, to);
837 // Promoting pawn to SQ_NONE, promoted piece from SQ_NONE
839 dp.piece[dp.dirty_num] = promotion;
840 dp.from[dp.dirty_num] = SQ_NONE;
841 dp.to[dp.dirty_num] = to;
846 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
847 st->pawnKey ^= Zobrist::psq[pc][to];
848 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
849 ^ Zobrist::psq[pc][pieceCount[pc]];
852 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
855 // Update pawn hash key
856 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
858 // Reset rule 50 draw counter
863 st->capturedPiece = captured;
865 // Update the key with the final value
868 // Calculate checkers bitboard (if move gives check)
869 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
871 sideToMove = ~sideToMove;
873 // Update king attacks used for fast check detection
876 // Calculate the repetition info. It is the ply distance from the previous
877 // occurrence of the same position, negative in the 3-fold case, or zero
878 // if the position was not repeated.
880 int end = std::min(st->rule50, st->pliesFromNull);
883 StateInfo* stp = st->previous->previous;
884 for (int i = 4; i <= end; i += 2)
886 stp = stp->previous->previous;
887 if (stp->key == st->key)
889 st->repetition = stp->repetition ? -i : i;
899 /// Position::undo_move() unmakes a move. When it returns, the position should
900 /// be restored to exactly the same state as before the move was made.
902 void Position::undo_move(Move m) {
906 sideToMove = ~sideToMove;
908 Color us = sideToMove;
909 Square from = from_sq(m);
910 Square to = to_sq(m);
911 Piece pc = piece_on(to);
913 assert(empty(from) || type_of(m) == CASTLING);
914 assert(type_of(st->capturedPiece) != KING);
916 if (type_of(m) == PROMOTION)
918 assert(relative_rank(us, to) == RANK_8);
919 assert(type_of(pc) == promotion_type(m));
920 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
923 pc = make_piece(us, PAWN);
927 if (type_of(m) == CASTLING)
930 do_castling<false>(us, from, to, rfrom, rto);
934 move_piece(to, from); // Put the piece back at the source square
936 if (st->capturedPiece)
940 if (type_of(m) == ENPASSANT)
942 capsq -= pawn_push(us);
944 assert(type_of(pc) == PAWN);
945 assert(to == st->previous->epSquare);
946 assert(relative_rank(us, to) == RANK_6);
947 assert(piece_on(capsq) == NO_PIECE);
948 assert(st->capturedPiece == make_piece(~us, PAWN));
951 put_piece(st->capturedPiece, capsq); // Restore the captured piece
955 // Finally point our state pointer back to the previous state
963 /// Position::do_castling() is a helper used to do/undo a castling move. This
964 /// is a bit tricky in Chess960 where from/to squares can overlap.
966 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
968 bool kingSide = to > from;
969 rfrom = to; // Castling is encoded as "king captures friendly rook"
970 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
971 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
973 if (Do && Eval::useNNUE)
975 auto& dp = st->dirtyPiece;
976 dp.piece[0] = make_piece(us, KING);
979 dp.piece[1] = make_piece(us, ROOK);
985 // Remove both pieces first since squares could overlap in Chess960
986 remove_piece(Do ? from : to);
987 remove_piece(Do ? rfrom : rto);
988 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
989 put_piece(make_piece(us, KING), Do ? to : from);
990 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
994 /// Position::do(undo)_null_move() is used to do(undo) a "null move": it flips
995 /// the side to move without executing any move on the board.
997 void Position::do_null_move(StateInfo& newSt) {
1000 assert(&newSt != st);
1002 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
1004 newSt.previous = st;
1007 st->dirtyPiece.dirty_num = 0;
1008 st->dirtyPiece.piece[0] = NO_PIECE; // Avoid checks in UpdateAccumulator()
1009 st->accumulator.state[WHITE] = Eval::NNUE::EMPTY;
1010 st->accumulator.state[BLACK] = Eval::NNUE::EMPTY;
1012 if (st->epSquare != SQ_NONE)
1014 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1015 st->epSquare = SQ_NONE;
1018 st->key ^= Zobrist::side;
1019 prefetch(TT.first_entry(st->key));
1022 st->pliesFromNull = 0;
1024 sideToMove = ~sideToMove;
1030 assert(pos_is_ok());
1033 void Position::undo_null_move() {
1035 assert(!checkers());
1038 sideToMove = ~sideToMove;
1042 /// Position::key_after() computes the new hash key after the given move. Needed
1043 /// for speculative prefetch. It doesn't recognize special moves like castling,
1044 /// en-passant and promotions.
1046 Key Position::key_after(Move m) const {
1048 Square from = from_sq(m);
1049 Square to = to_sq(m);
1050 Piece pc = piece_on(from);
1051 Piece captured = piece_on(to);
1052 Key k = st->key ^ Zobrist::side;
1055 k ^= Zobrist::psq[captured][to];
1057 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1061 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1062 /// SEE value of move is greater or equal to the given threshold. We'll use an
1063 /// algorithm similar to alpha-beta pruning with a null window.
1065 bool Position::see_ge(Move m, Value threshold) const {
1069 // Only deal with normal moves, assume others pass a simple see
1070 if (type_of(m) != NORMAL)
1071 return VALUE_ZERO >= threshold;
1073 Square from = from_sq(m), to = to_sq(m);
1075 int swap = PieceValue[MG][piece_on(to)] - threshold;
1079 swap = PieceValue[MG][piece_on(from)] - swap;
1083 Bitboard occupied = pieces() ^ from ^ to;
1084 Color stm = color_of(piece_on(from));
1085 Bitboard attackers = attackers_to(to, occupied);
1086 Bitboard stmAttackers, bb;
1092 attackers &= occupied;
1094 // If stm has no more attackers then give up: stm loses
1095 if (!(stmAttackers = attackers & pieces(stm)))
1098 // Don't allow pinned pieces to attack (except the king) as long as
1099 // there are pinners on their original square.
1100 if (pinners(~stm) & occupied)
1101 stmAttackers &= ~blockers_for_king(stm);
1108 // Locate and remove the next least valuable attacker, and add to
1109 // the bitboard 'attackers' any X-ray attackers behind it.
1110 if ((bb = stmAttackers & pieces(PAWN)))
1112 if ((swap = PawnValueMg - swap) < res)
1115 occupied ^= lsb(bb);
1116 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1119 else if ((bb = stmAttackers & pieces(KNIGHT)))
1121 if ((swap = KnightValueMg - swap) < res)
1124 occupied ^= lsb(bb);
1127 else if ((bb = stmAttackers & pieces(BISHOP)))
1129 if ((swap = BishopValueMg - swap) < res)
1132 occupied ^= lsb(bb);
1133 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1136 else if ((bb = stmAttackers & pieces(ROOK)))
1138 if ((swap = RookValueMg - swap) < res)
1141 occupied ^= lsb(bb);
1142 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1145 else if ((bb = stmAttackers & pieces(QUEEN)))
1147 if ((swap = QueenValueMg - swap) < res)
1150 occupied ^= lsb(bb);
1151 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1152 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1156 // If we "capture" with the king but opponent still has attackers,
1157 // reverse the result.
1158 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1165 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1166 /// or by repetition. It does not detect stalemates.
1168 bool Position::is_draw(int ply) const {
1170 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1173 // Return a draw score if a position repeats once earlier but strictly
1174 // after the root, or repeats twice before or at the root.
1175 return st->repetition && st->repetition < ply;
1179 // Position::has_repeated() tests whether there has been at least one repetition
1180 // of positions since the last capture or pawn move.
1182 bool Position::has_repeated() const {
1184 StateInfo* stc = st;
1185 int end = std::min(st->rule50, st->pliesFromNull);
1188 if (stc->repetition)
1191 stc = stc->previous;
1197 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1198 /// or an earlier position has a move that directly reaches the current position.
1200 bool Position::has_game_cycle(int ply) const {
1204 int end = std::min(st->rule50, st->pliesFromNull);
1209 Key originalKey = st->key;
1210 StateInfo* stp = st->previous;
1212 for (int i = 3; i <= end; i += 2)
1214 stp = stp->previous->previous;
1216 Key moveKey = originalKey ^ stp->key;
1217 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1218 || (j = H2(moveKey), cuckoo[j] == moveKey))
1220 Move move = cuckooMove[j];
1221 Square s1 = from_sq(move);
1222 Square s2 = to_sq(move);
1224 if (!(between_bb(s1, s2) & pieces()))
1229 // For nodes before or at the root, check that the move is a
1230 // repetition rather than a move to the current position.
1231 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1232 // the same location, so we have to select which square to check.
1233 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1236 // For repetitions before or at the root, require one more
1237 if (stp->repetition)
1246 /// Position::flip() flips position with the white and black sides reversed. This
1247 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1249 void Position::flip() {
1252 std::stringstream ss(fen());
1254 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1256 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1257 f.insert(0, token + (f.empty() ? " " : "/"));
1260 ss >> token; // Active color
1261 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1263 ss >> token; // Castling availability
1266 std::transform(f.begin(), f.end(), f.begin(),
1267 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1269 ss >> token; // En passant square
1270 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1272 std::getline(ss, token); // Half and full moves
1275 set(f, is_chess960(), st, this_thread());
1277 assert(pos_is_ok());
1281 /// Position::pos_is_ok() performs some consistency checks for the
1282 /// position object and raises an asserts if something wrong is detected.
1283 /// This is meant to be helpful when debugging.
1285 bool Position::pos_is_ok() const {
1287 constexpr bool Fast = true; // Quick (default) or full check?
1289 if ( (sideToMove != WHITE && sideToMove != BLACK)
1290 || piece_on(square<KING>(WHITE)) != W_KING
1291 || piece_on(square<KING>(BLACK)) != B_KING
1292 || ( ep_square() != SQ_NONE
1293 && relative_rank(sideToMove, ep_square()) != RANK_6))
1294 assert(0 && "pos_is_ok: Default");
1299 if ( pieceCount[W_KING] != 1
1300 || pieceCount[B_KING] != 1
1301 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1302 assert(0 && "pos_is_ok: Kings");
1304 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1305 || pieceCount[W_PAWN] > 8
1306 || pieceCount[B_PAWN] > 8)
1307 assert(0 && "pos_is_ok: Pawns");
1309 if ( (pieces(WHITE) & pieces(BLACK))
1310 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1311 || popcount(pieces(WHITE)) > 16
1312 || popcount(pieces(BLACK)) > 16)
1313 assert(0 && "pos_is_ok: Bitboards");
1315 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1316 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1317 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1318 assert(0 && "pos_is_ok: Bitboards");
1322 if (std::memcmp(&si, st, sizeof(StateInfo)))
1323 assert(0 && "pos_is_ok: State");
1325 for (Piece pc : Pieces)
1327 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1328 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1329 assert(0 && "pos_is_ok: Pieces");
1331 for (int i = 0; i < pieceCount[pc]; ++i)
1332 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1333 assert(0 && "pos_is_ok: Index");
1336 for (Color c : { WHITE, BLACK })
1337 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1339 if (!can_castle(cr))
1342 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1343 || castlingRightsMask[castlingRookSquare[cr]] != cr
1344 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1345 assert(0 && "pos_is_ok: Castling");