2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2021 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"
41 Key psq[PIECE_NB][SQUARE_NB];
42 Key enpassant[FILE_NB];
43 Key castling[CASTLING_RIGHT_NB];
49 const string PieceToChar(" PNBRQK pnbrqk");
51 constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
52 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
56 /// operator<<(Position) returns an ASCII representation of the position
58 std::ostream& operator<<(std::ostream& os, const Position& pos) {
60 os << "\n +---+---+---+---+---+---+---+---+\n";
62 for (Rank r = RANK_8; r >= RANK_1; --r)
64 for (File f = FILE_A; f <= FILE_H; ++f)
65 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
67 os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n";
70 os << " a b c d e f g h\n"
71 << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
72 << std::setfill('0') << std::setw(16) << pos.key()
73 << std::setfill(' ') << std::dec << "\nCheckers: ";
75 for (Bitboard b = pos.checkers(); b; )
76 os << UCI::square(pop_lsb(b)) << " ";
78 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
79 && !pos.can_castle(ANY_CASTLING))
82 ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize);
85 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
86 Tablebases::ProbeState s1, s2;
87 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
88 int dtz = Tablebases::probe_dtz(p, &s2);
89 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
90 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
97 // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
98 // situations. Description of the algorithm in the following paper:
99 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
101 // First and second hash functions for indexing the cuckoo tables
102 inline int H1(Key h) { return h & 0x1fff; }
103 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
105 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
107 Move cuckooMove[8192];
110 /// Position::init() initializes at startup the various arrays used to compute hash keys
112 void Position::init() {
116 for (Piece pc : Pieces)
117 for (Square s = SQ_A1; s <= SQ_H8; ++s)
118 Zobrist::psq[pc][s] = rng.rand<Key>();
120 for (File f = FILE_A; f <= FILE_H; ++f)
121 Zobrist::enpassant[f] = rng.rand<Key>();
123 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
124 Zobrist::castling[cr] = rng.rand<Key>();
126 Zobrist::side = rng.rand<Key>();
127 Zobrist::noPawns = rng.rand<Key>();
129 // Prepare the cuckoo tables
130 std::memset(cuckoo, 0, sizeof(cuckoo));
131 std::memset(cuckooMove, 0, sizeof(cuckooMove));
133 for (Piece pc : Pieces)
134 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
135 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
136 if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2))
138 Move move = make_move(s1, s2);
139 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
143 std::swap(cuckoo[i], key);
144 std::swap(cuckooMove[i], move);
145 if (move == MOVE_NONE) // Arrived at empty slot?
147 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
151 assert(count == 3668);
155 /// Position::set() initializes the position object with the given FEN string.
156 /// This function is not very robust - make sure that input FENs are correct,
157 /// this is assumed to be the responsibility of the GUI.
159 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
161 A FEN string defines a particular position using only the ASCII character set.
163 A FEN string contains six fields separated by a space. The fields are:
165 1) Piece placement (from white's perspective). Each rank is described, starting
166 with rank 8 and ending with rank 1. Within each rank, the contents of each
167 square are described from file A through file H. Following the Standard
168 Algebraic Notation (SAN), each piece is identified by a single letter taken
169 from the standard English names. White pieces are designated using upper-case
170 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
171 noted using digits 1 through 8 (the number of blank squares), and "/"
174 2) Active color. "w" means white moves next, "b" means black.
176 3) Castling availability. If neither side can castle, this is "-". Otherwise,
177 this has one or more letters: "K" (White can castle kingside), "Q" (White
178 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
179 can castle queenside).
181 4) En passant target square (in algebraic notation). If there's no en passant
182 target square, this is "-". If a pawn has just made a 2-square move, this
183 is the position "behind" the pawn. Following X-FEN standard, this is recorded only
184 if there is a pawn in position to make an en passant capture, and if there really
185 is a pawn that might have advanced two squares.
187 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
188 or capture. This is used to determine if a draw can be claimed under the
191 6) Fullmove number. The number of the full move. It starts at 1, and is
192 incremented after Black's move.
195 unsigned char col, row, token;
198 std::istringstream ss(fenStr);
200 std::memset(this, 0, sizeof(Position));
201 std::memset(si, 0, sizeof(StateInfo));
206 // 1. Piece placement
207 while ((ss >> token) && !isspace(token))
210 sq += (token - '0') * EAST; // Advance the given number of files
212 else if (token == '/')
215 else if ((idx = PieceToChar.find(token)) != string::npos) {
216 put_piece(Piece(idx), sq);
223 sideToMove = (token == 'w' ? WHITE : BLACK);
226 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
227 // Shredder-FEN that uses the letters of the columns on which the rooks began
228 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
229 // if an inner rook is associated with the castling right, the castling tag is
230 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
231 while ((ss >> token) && !isspace(token))
234 Color c = islower(token) ? BLACK : WHITE;
235 Piece rook = make_piece(c, ROOK);
237 token = char(toupper(token));
240 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
242 else if (token == 'Q')
243 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
245 else if (token >= 'A' && token <= 'H')
246 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
251 set_castling_right(c, rsq);
256 // 4. En passant square.
257 // Ignore if square is invalid or not on side to move relative rank 6.
258 bool enpassant = false;
260 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
261 && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3'))))
263 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
265 // En passant square will be considered only if
266 // a) side to move have a pawn threatening epSquare
267 // b) there is an enemy pawn in front of epSquare
268 // c) there is no piece on epSquare or behind epSquare
269 // d) enemy pawn didn't block a check of its own color by moving forward
270 enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN)
271 && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))
272 && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove))))
273 && ( file_of(square<KING>(sideToMove)) == file_of(st->epSquare)
274 || !(blockers_for_king(sideToMove) & (st->epSquare + pawn_push(~sideToMove))));
277 // It's necessary for st->previous to be intialized in this way because legality check relies on its existence
279 st->previous = new StateInfo();
280 remove_piece(st->epSquare - pawn_push(sideToMove));
281 st->previous->checkersBB = attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove);
282 st->previous->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), st->previous->pinners[BLACK]);
283 st->previous->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), st->previous->pinners[WHITE]);
284 put_piece(make_piece(~sideToMove, PAWN), st->epSquare - pawn_push(sideToMove));
287 st->epSquare = SQ_NONE;
289 // 5-6. Halfmove clock and fullmove number
290 ss >> std::skipws >> st->rule50 >> gamePly;
292 // Convert from fullmove starting from 1 to gamePly starting from 0,
293 // handle also common incorrect FEN with fullmove = 0.
294 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
296 chess960 = isChess960;
298 st->accumulator.state[WHITE] = Eval::NNUE::INIT;
299 st->accumulator.state[BLACK] = Eval::NNUE::INIT;
307 /// Position::set_castling_right() is a helper function used to set castling
308 /// rights given the corresponding color and the rook starting square.
310 void Position::set_castling_right(Color c, Square rfrom) {
312 Square kfrom = square<KING>(c);
313 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
315 st->castlingRights |= cr;
316 castlingRightsMask[kfrom] |= cr;
317 castlingRightsMask[rfrom] |= cr;
318 castlingRookSquare[cr] = rfrom;
320 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
321 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
323 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto))
328 /// Position::set_check_info() sets king attacks to detect if a move gives check
330 void Position::set_check_info(StateInfo* si) const {
332 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
333 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
335 Square ksq = square<KING>(~sideToMove);
337 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
338 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
339 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
340 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
341 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
342 si->checkSquares[KING] = 0;
346 /// Position::set_state() computes the hash keys of the position, and other
347 /// data that once computed is updated incrementally as moves are made.
348 /// The function is only used when a new position is set up, and to verify
349 /// the correctness of the StateInfo data when running in debug mode.
351 void Position::set_state(StateInfo* si) const {
353 si->key = si->materialKey = 0;
354 si->pawnKey = Zobrist::noPawns;
355 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
356 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
360 for (Bitboard b = pieces(); b; )
362 Square s = pop_lsb(b);
363 Piece pc = piece_on(s);
364 si->key ^= Zobrist::psq[pc][s];
366 if (type_of(pc) == PAWN)
367 si->pawnKey ^= Zobrist::psq[pc][s];
369 else if (type_of(pc) != KING)
370 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
373 if (si->epSquare != SQ_NONE)
374 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
376 if (sideToMove == BLACK)
377 si->key ^= Zobrist::side;
379 si->key ^= Zobrist::castling[si->castlingRights];
381 for (Piece pc : Pieces)
382 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
383 si->materialKey ^= Zobrist::psq[pc][cnt];
387 /// Position::set() is an overload to initialize the position object with
388 /// the given endgame code string like "KBPKN". It is mainly a helper to
389 /// get the material key out of an endgame code.
391 Position& Position::set(const string& code, Color c, StateInfo* si) {
393 assert(code[0] == 'K');
395 string sides[] = { code.substr(code.find('K', 1)), // Weak
396 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
398 assert(sides[0].length() > 0 && sides[0].length() < 8);
399 assert(sides[1].length() > 0 && sides[1].length() < 8);
401 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
403 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
404 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
406 return set(fenStr, false, si, nullptr);
410 /// Position::fen() returns a FEN representation of the position. In case of
411 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
413 string Position::fen() const {
416 std::ostringstream ss;
418 for (Rank r = RANK_8; r >= RANK_1; --r)
420 for (File f = FILE_A; f <= FILE_H; ++f)
422 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
429 ss << PieceToChar[piece_on(make_square(f, r))];
436 ss << (sideToMove == WHITE ? " w " : " b ");
438 if (can_castle(WHITE_OO))
439 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
441 if (can_castle(WHITE_OOO))
442 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
444 if (can_castle(BLACK_OO))
445 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
447 if (can_castle(BLACK_OOO))
448 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
450 if (!can_castle(ANY_CASTLING))
453 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
454 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
460 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
461 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
462 /// slider if removing that piece from the board would result in a position where
463 /// square 's' is attacked. For example, a king-attack blocking piece can be either
464 /// a pinned or a discovered check piece, according if its color is the opposite
465 /// or the same of the color of the slider.
467 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
469 Bitboard blockers = 0;
472 // Snipers are sliders that attack 's' when a piece and other snipers are removed
473 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
474 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
475 Bitboard occupancy = pieces() ^ snipers;
479 Square sniperSq = pop_lsb(snipers);
480 Bitboard b = between_bb(s, sniperSq) & occupancy;
482 if (b && !more_than_one(b))
485 if (b & pieces(color_of(piece_on(s))))
493 /// Position::attackers_to() computes a bitboard of all pieces which attack a
494 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
496 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
498 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
499 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
500 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
501 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
502 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
503 | (attacks_bb<KING>(s) & pieces(KING));
507 /// Position::legal() tests whether a pseudo-legal move is legal
509 bool Position::legal(Move m) const {
513 Color us = sideToMove;
514 Square from = from_sq(m);
515 Square to = to_sq(m);
517 assert(color_of(moved_piece(m)) == us);
518 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
520 // st->previous->blockersForKing consider capsq as empty.
521 // If pinned, it has to move along the king ray.
522 if (type_of(m) == EN_PASSANT)
523 return !(st->previous->blockersForKing[sideToMove] & from)
524 || aligned(from, to, square<KING>(us));
526 // Castling moves generation does not check if the castling path is clear of
527 // enemy attacks, it is delayed at a later time: now!
528 if (type_of(m) == CASTLING)
530 // After castling, the rook and king final positions are the same in
531 // Chess960 as they would be in standard chess.
532 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
533 Direction step = to > from ? WEST : EAST;
535 for (Square s = to; s != from; s += step)
536 if (attackers_to(s) & pieces(~us))
539 // In case of Chess960, verify if the Rook blocks some checks
540 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
541 return !chess960 || !(blockers_for_king(us) & to_sq(m));
544 // If the moving piece is a king, check whether the destination square is
545 // attacked by the opponent.
546 if (type_of(piece_on(from)) == KING)
547 return !(attackers_to(to, pieces() ^ from) & pieces(~us));
549 // A non-king move is legal if and only if it is not pinned or it
550 // is moving along the ray towards or away from the king.
551 return !(blockers_for_king(us) & from)
552 || aligned(from, to, square<KING>(us));
556 /// Position::pseudo_legal() takes a random move and tests whether the move is
557 /// pseudo legal. It is used to validate moves from TT that can be corrupted
558 /// due to SMP concurrent access or hash position key aliasing.
560 bool Position::pseudo_legal(const Move m) const {
562 Color us = sideToMove;
563 Square from = from_sq(m);
564 Square to = to_sq(m);
565 Piece pc = moved_piece(m);
567 // Use a slower but simpler function for uncommon cases
568 // yet we skip the legality check of MoveList<LEGAL>().
569 if (type_of(m) != NORMAL)
570 return checkers() ? MoveList< EVASIONS>(*this).contains(m)
571 : MoveList<NON_EVASIONS>(*this).contains(m);
573 // Is not a promotion, so promotion piece must be empty
574 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
577 // If the 'from' square is not occupied by a piece belonging to the side to
578 // move, the move is obviously not legal.
579 if (pc == NO_PIECE || color_of(pc) != us)
582 // The destination square cannot be occupied by a friendly piece
586 // Handle the special case of a pawn move
587 if (type_of(pc) == PAWN)
589 // We have already handled promotion moves, so destination
590 // cannot be on the 8th/1st rank.
591 if ((Rank8BB | Rank1BB) & to)
594 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
595 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
596 && !( (from + 2 * pawn_push(us) == to) // Not a double push
597 && (relative_rank(us, from) == RANK_2)
599 && empty(to - pawn_push(us))))
602 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
605 // Evasions generator already takes care to avoid some kind of illegal moves
606 // and legal() relies on this. We therefore have to take care that the same
607 // kind of moves are filtered out here.
610 if (type_of(pc) != KING)
612 // Double check? In this case a king move is required
613 if (more_than_one(checkers()))
616 // Our move must be a blocking interposition or a capture of the checking piece
617 if (!(between_bb(square<KING>(us), lsb(checkers())) & to))
620 // In case of king moves under check we have to remove king so as to catch
621 // invalid moves like b1a1 when opposite queen is on c1.
622 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
630 /// Position::gives_check() tests whether a pseudo-legal move gives a check
632 bool Position::gives_check(Move m) const {
635 assert(color_of(moved_piece(m)) == sideToMove);
637 Square from = from_sq(m);
638 Square to = to_sq(m);
640 // Is there a direct check?
641 if (check_squares(type_of(piece_on(from))) & to)
644 // Is there a discovered check?
645 if ( (blockers_for_king(~sideToMove) & from)
646 && !aligned(from, to, square<KING>(~sideToMove)))
655 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
657 // The double-pushed pawn blocked a check? En Passant will remove the blocker.
658 // The only discovery check that wasn't handle is through capsq and fromsq
659 // So the King must be in the same rank as fromsq to consider this possibility.
660 // st->previous->blockersForKing consider capsq as empty.
662 return st->previous->checkersBB
663 || ( rank_of(square<KING>(~sideToMove)) == rank_of(from)
664 && st->previous->blockersForKing[~sideToMove] & from);
668 // Castling is encoded as 'king captures the rook'
669 Square ksq = square<KING>(~sideToMove);
670 Square rto = relative_square(sideToMove, to > from ? SQ_F1 : SQ_D1);
672 return (attacks_bb<ROOK>(rto) & ksq)
673 && (attacks_bb<ROOK>(rto, pieces() ^ from ^ to) & ksq);
679 /// Position::do_move() makes a move, and saves all information necessary
680 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
681 /// moves should be filtered out before this function is called.
683 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
686 assert(&newSt != st);
688 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
689 Key k = st->key ^ Zobrist::side;
691 // Copy some fields of the old state to our new StateInfo object except the
692 // ones which are going to be recalculated from scratch anyway and then switch
693 // our state pointer to point to the new (ready to be updated) state.
694 std::memcpy(&newSt, st, offsetof(StateInfo, key));
698 // Increment ply counters. In particular, rule50 will be reset to zero later on
699 // in case of a capture or a pawn move.
705 st->accumulator.state[WHITE] = Eval::NNUE::EMPTY;
706 st->accumulator.state[BLACK] = Eval::NNUE::EMPTY;
707 auto& dp = st->dirtyPiece;
710 Color us = sideToMove;
712 Square from = from_sq(m);
713 Square to = to_sq(m);
714 Piece pc = piece_on(from);
715 Piece captured = type_of(m) == EN_PASSANT ? make_piece(them, PAWN) : piece_on(to);
717 assert(color_of(pc) == us);
718 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
719 assert(type_of(captured) != KING);
721 if (type_of(m) == CASTLING)
723 assert(pc == make_piece(us, KING));
724 assert(captured == make_piece(us, ROOK));
727 do_castling<true>(us, from, to, rfrom, rto);
729 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
737 // If the captured piece is a pawn, update pawn hash key, otherwise
738 // update non-pawn material.
739 if (type_of(captured) == PAWN)
741 if (type_of(m) == EN_PASSANT)
743 capsq -= pawn_push(us);
745 assert(pc == make_piece(us, PAWN));
746 assert(to == st->epSquare);
747 assert(relative_rank(us, to) == RANK_6);
748 assert(piece_on(to) == NO_PIECE);
749 assert(piece_on(capsq) == make_piece(them, PAWN));
752 st->pawnKey ^= Zobrist::psq[captured][capsq];
755 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
759 dp.dirty_num = 2; // 1 piece moved, 1 piece captured
760 dp.piece[1] = captured;
765 // Update board and piece lists
768 if (type_of(m) == EN_PASSANT)
769 board[capsq] = NO_PIECE;
771 // Update material hash key and prefetch access to materialTable
772 k ^= Zobrist::psq[captured][capsq];
773 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
774 prefetch(thisThread->materialTable[st->materialKey]);
776 // Reset rule 50 counter
781 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
783 // Reset en passant square
784 if (st->epSquare != SQ_NONE)
786 k ^= Zobrist::enpassant[file_of(st->epSquare)];
787 st->epSquare = SQ_NONE;
790 // Update castling rights if needed
791 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
793 k ^= Zobrist::castling[st->castlingRights];
794 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
795 k ^= Zobrist::castling[st->castlingRights];
798 // Move the piece. The tricky Chess960 castling is handled earlier
799 if (type_of(m) != CASTLING)
808 move_piece(from, to);
811 // If the moving piece is a pawn do some special extra work
812 if (type_of(pc) == PAWN)
814 // Set en passant square if the moved pawn can be captured
815 if ( (int(to) ^ int(from)) == 16
816 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
818 st->epSquare = to - pawn_push(us);
819 k ^= Zobrist::enpassant[file_of(st->epSquare)];
822 else if (type_of(m) == PROMOTION)
824 Piece promotion = make_piece(us, promotion_type(m));
826 assert(relative_rank(us, to) == RANK_8);
827 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
830 put_piece(promotion, to);
834 // Promoting pawn to SQ_NONE, promoted piece from SQ_NONE
836 dp.piece[dp.dirty_num] = promotion;
837 dp.from[dp.dirty_num] = SQ_NONE;
838 dp.to[dp.dirty_num] = to;
843 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
844 st->pawnKey ^= Zobrist::psq[pc][to];
845 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
846 ^ Zobrist::psq[pc][pieceCount[pc]];
849 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
852 // Update pawn hash key
853 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
855 // Reset rule 50 draw counter
860 st->capturedPiece = captured;
862 // Update the key with the final value
865 // Calculate checkers bitboard (if move gives check)
866 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
868 sideToMove = ~sideToMove;
870 // Update king attacks used for fast check detection
873 // Calculate the repetition info. It is the ply distance from the previous
874 // occurrence of the same position, negative in the 3-fold case, or zero
875 // if the position was not repeated.
877 int end = std::min(st->rule50, st->pliesFromNull);
880 StateInfo* stp = st->previous->previous;
881 for (int i = 4; i <= end; i += 2)
883 stp = stp->previous->previous;
884 if (stp->key == st->key)
886 st->repetition = stp->repetition ? -i : i;
896 /// Position::undo_move() unmakes a move. When it returns, the position should
897 /// be restored to exactly the same state as before the move was made.
899 void Position::undo_move(Move m) {
903 sideToMove = ~sideToMove;
905 Color us = sideToMove;
906 Square from = from_sq(m);
907 Square to = to_sq(m);
908 Piece pc = piece_on(to);
910 assert(empty(from) || type_of(m) == CASTLING);
911 assert(type_of(st->capturedPiece) != KING);
913 if (type_of(m) == PROMOTION)
915 assert(relative_rank(us, to) == RANK_8);
916 assert(type_of(pc) == promotion_type(m));
917 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
920 pc = make_piece(us, PAWN);
924 if (type_of(m) == CASTLING)
927 do_castling<false>(us, from, to, rfrom, rto);
931 move_piece(to, from); // Put the piece back at the source square
933 if (st->capturedPiece)
937 if (type_of(m) == EN_PASSANT)
939 capsq -= pawn_push(us);
941 assert(type_of(pc) == PAWN);
942 assert(to == st->previous->epSquare);
943 assert(relative_rank(us, to) == RANK_6);
944 assert(piece_on(capsq) == NO_PIECE);
945 assert(st->capturedPiece == make_piece(~us, PAWN));
948 put_piece(st->capturedPiece, capsq); // Restore the captured piece
952 // Finally point our state pointer back to the previous state
960 /// Position::do_castling() is a helper used to do/undo a castling move. This
961 /// is a bit tricky in Chess960 where from/to squares can overlap.
963 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
965 bool kingSide = to > from;
966 rfrom = to; // Castling is encoded as "king captures friendly rook"
967 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
968 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
970 if (Do && Eval::useNNUE)
972 auto& dp = st->dirtyPiece;
973 dp.piece[0] = make_piece(us, KING);
976 dp.piece[1] = make_piece(us, ROOK);
982 // Remove both pieces first since squares could overlap in Chess960
983 remove_piece(Do ? from : to);
984 remove_piece(Do ? rfrom : rto);
985 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
986 put_piece(make_piece(us, KING), Do ? to : from);
987 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
991 /// Position::do_null_move() is used to do a "null move": it flips
992 /// the side to move without executing any move on the board.
994 void Position::do_null_move(StateInfo& newSt) {
997 assert(&newSt != st);
999 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
1001 newSt.previous = st;
1004 st->dirtyPiece.dirty_num = 0;
1005 st->dirtyPiece.piece[0] = NO_PIECE; // Avoid checks in UpdateAccumulator()
1006 st->accumulator.state[WHITE] = Eval::NNUE::EMPTY;
1007 st->accumulator.state[BLACK] = Eval::NNUE::EMPTY;
1009 if (st->epSquare != SQ_NONE)
1011 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1012 st->epSquare = SQ_NONE;
1015 st->key ^= Zobrist::side;
1016 prefetch(TT.first_entry(key()));
1019 st->pliesFromNull = 0;
1021 sideToMove = ~sideToMove;
1027 assert(pos_is_ok());
1031 /// Position::undo_null_move() must be used to undo a "null move"
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 as long as there are
1099 // 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 ^= least_significant_square_bb(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 ^= least_significant_square_bb(bb);
1127 else if ((bb = stmAttackers & pieces(BISHOP)))
1129 if ((swap = BishopValueMg - swap) < res)
1132 occupied ^= least_significant_square_bb(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 ^= least_significant_square_bb(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 ^= least_significant_square_bb(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) ^ 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");
1321 ASSERT_ALIGNED(&si, Eval::NNUE::CacheLineSize);
1324 if (std::memcmp(&si, st, sizeof(StateInfo)))
1325 assert(0 && "pos_is_ok: State");
1327 for (Piece pc : Pieces)
1328 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1329 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1330 assert(0 && "pos_is_ok: Pieces");
1332 for (Color c : { WHITE, BLACK })
1333 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1335 if (!can_castle(cr))
1338 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1339 || castlingRightsMask[castlingRookSquare[cr]] != cr
1340 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1341 assert(0 && "pos_is_ok: Castling");
1347 } // namespace Stockfish