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;
289 /// Position::set_castling_right() is a helper function used to set castling
290 /// rights given the corresponding color and the rook starting square.
292 void Position::set_castling_right(Color c, Square rfrom) {
294 Square kfrom = square<KING>(c);
295 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
297 st->castlingRights |= cr;
298 castlingRightsMask[kfrom] |= cr;
299 castlingRightsMask[rfrom] |= cr;
300 castlingRookSquare[cr] = rfrom;
302 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
303 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
305 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
310 /// Position::set_check_info() sets king attacks to detect if a move gives check
312 void Position::set_check_info(StateInfo* si) const {
314 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
315 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
317 Square ksq = square<KING>(~sideToMove);
319 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
320 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
321 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
322 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
323 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
324 si->checkSquares[KING] = 0;
328 /// Position::set_state() computes the hash keys of the position, and other
329 /// data that once computed is updated incrementally as moves are made.
330 /// The function is only used when a new position is set up, and to verify
331 /// the correctness of the StateInfo data when running in debug mode.
333 void Position::set_state(StateInfo* si) const {
335 si->key = si->materialKey = 0;
336 si->pawnKey = Zobrist::noPawns;
337 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
338 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
342 for (Bitboard b = pieces(); b; )
344 Square s = pop_lsb(&b);
345 Piece pc = piece_on(s);
346 si->key ^= Zobrist::psq[pc][s];
348 if (type_of(pc) == PAWN)
349 si->pawnKey ^= Zobrist::psq[pc][s];
351 else if (type_of(pc) != KING)
352 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
355 if (si->epSquare != SQ_NONE)
356 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
358 if (sideToMove == BLACK)
359 si->key ^= Zobrist::side;
361 si->key ^= Zobrist::castling[si->castlingRights];
363 for (Piece pc : Pieces)
364 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
365 si->materialKey ^= Zobrist::psq[pc][cnt];
369 /// Position::set() is an overload to initialize the position object with
370 /// the given endgame code string like "KBPKN". It is mainly a helper to
371 /// get the material key out of an endgame code.
373 Position& Position::set(const string& code, Color c, StateInfo* si) {
375 assert(code[0] == 'K');
377 string sides[] = { code.substr(code.find('K', 1)), // Weak
378 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
380 assert(sides[0].length() > 0 && sides[0].length() < 8);
381 assert(sides[1].length() > 0 && sides[1].length() < 8);
383 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
385 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
386 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
388 return set(fenStr, false, si, nullptr);
392 /// Position::fen() returns a FEN representation of the position. In case of
393 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
395 const string Position::fen() const {
398 std::ostringstream ss;
400 for (Rank r = RANK_8; r >= RANK_1; --r)
402 for (File f = FILE_A; f <= FILE_H; ++f)
404 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
411 ss << PieceToChar[piece_on(make_square(f, r))];
418 ss << (sideToMove == WHITE ? " w " : " b ");
420 if (can_castle(WHITE_OO))
421 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
423 if (can_castle(WHITE_OOO))
424 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
426 if (can_castle(BLACK_OO))
427 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
429 if (can_castle(BLACK_OOO))
430 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
432 if (!can_castle(ANY_CASTLING))
435 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
436 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
442 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
443 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
444 /// slider if removing that piece from the board would result in a position where
445 /// square 's' is attacked. For example, a king-attack blocking piece can be either
446 /// a pinned or a discovered check piece, according if its color is the opposite
447 /// or the same of the color of the slider.
449 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
451 Bitboard blockers = 0;
454 // Snipers are sliders that attack 's' when a piece and other snipers are removed
455 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
456 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
457 Bitboard occupancy = pieces() ^ snipers;
461 Square sniperSq = pop_lsb(&snipers);
462 Bitboard b = between_bb(s, sniperSq) & occupancy;
464 if (b && !more_than_one(b))
467 if (b & pieces(color_of(piece_on(s))))
475 /// Position::attackers_to() computes a bitboard of all pieces which attack a
476 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
478 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
480 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
481 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
482 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
483 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
484 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
485 | (attacks_bb<KING>(s) & pieces(KING));
489 /// Position::legal() tests whether a pseudo-legal move is legal
491 bool Position::legal(Move m) const {
495 Color us = sideToMove;
496 Square from = from_sq(m);
497 Square to = to_sq(m);
499 assert(color_of(moved_piece(m)) == us);
500 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
502 // En passant captures are a tricky special case. Because they are rather
503 // uncommon, we do it simply by testing whether the king is attacked after
505 if (type_of(m) == ENPASSANT)
507 Square ksq = square<KING>(us);
508 Square capsq = to - pawn_push(us);
509 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
511 assert(to == ep_square());
512 assert(moved_piece(m) == make_piece(us, PAWN));
513 assert(piece_on(capsq) == make_piece(~us, PAWN));
514 assert(piece_on(to) == NO_PIECE);
516 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
517 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
520 // Castling moves generation does not check if the castling path is clear of
521 // enemy attacks, it is delayed at a later time: now!
522 if (type_of(m) == CASTLING)
524 // After castling, the rook and king final positions are the same in
525 // Chess960 as they would be in standard chess.
526 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
527 Direction step = to > from ? WEST : EAST;
529 for (Square s = to; s != from; s += step)
530 if (attackers_to(s) & pieces(~us))
533 // In case of Chess960, verify that when moving the castling rook we do
534 // not discover some hidden checker.
535 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
537 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
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(~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 if (type_of(m) != NORMAL)
565 return MoveList<LEGAL>(*this).contains(m);
567 // Is not a promotion, so promotion piece must be empty
568 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
571 // If the 'from' square is not occupied by a piece belonging to the side to
572 // move, the move is obviously not legal.
573 if (pc == NO_PIECE || color_of(pc) != us)
576 // The destination square cannot be occupied by a friendly piece
580 // Handle the special case of a pawn move
581 if (type_of(pc) == PAWN)
583 // We have already handled promotion moves, so destination
584 // cannot be on the 8th/1st rank.
585 if ((Rank8BB | Rank1BB) & to)
588 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
589 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
590 && !( (from + 2 * pawn_push(us) == to) // Not a double push
591 && (relative_rank(us, from) == RANK_2)
593 && empty(to - pawn_push(us))))
596 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
599 // Evasions generator already takes care to avoid some kind of illegal moves
600 // and legal() relies on this. We therefore have to take care that the same
601 // kind of moves are filtered out here.
604 if (type_of(pc) != KING)
606 // Double check? In this case a king move is required
607 if (more_than_one(checkers()))
610 // Our move must be a blocking evasion or a capture of the checking piece
611 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
614 // In case of king moves under check we have to remove king so as to catch
615 // invalid moves like b1a1 when opposite queen is on c1.
616 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
624 /// Position::gives_check() tests whether a pseudo-legal move gives a check
626 bool Position::gives_check(Move m) const {
629 assert(color_of(moved_piece(m)) == sideToMove);
631 Square from = from_sq(m);
632 Square to = to_sq(m);
634 // Is there a direct check?
635 if (check_squares(type_of(piece_on(from))) & to)
638 // Is there a discovered check?
639 if ( (blockers_for_king(~sideToMove) & from)
640 && !aligned(from, to, square<KING>(~sideToMove)))
649 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
651 // En passant capture with check? We have already handled the case
652 // of direct checks and ordinary discovered check, so the only case we
653 // need to handle is the unusual case of a discovered check through
654 // the captured pawn.
657 Square capsq = make_square(file_of(to), rank_of(from));
658 Bitboard b = (pieces() ^ from ^ capsq) | to;
660 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
661 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
666 Square rfrom = to; // Castling is encoded as 'king captures the rook'
667 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
668 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
670 return (attacks_bb<ROOK>(rto) & square<KING>(~sideToMove))
671 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
680 /// Position::do_move() makes a move, and saves all information necessary
681 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
682 /// moves should be filtered out before this function is called.
684 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
687 assert(&newSt != st);
689 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
690 Key k = st->key ^ Zobrist::side;
692 // Copy some fields of the old state to our new StateInfo object except the
693 // ones which are going to be recalculated from scratch anyway and then switch
694 // our state pointer to point to the new (ready to be updated) state.
695 std::memcpy(&newSt, st, offsetof(StateInfo, key));
699 // Increment ply counters. In particular, rule50 will be reset to zero later on
700 // in case of a capture or a pawn move.
706 st->accumulator.computed_accumulation = false;
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) == ENPASSANT ? 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) == ENPASSANT)
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) == ENPASSANT)
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) == ENPASSANT)
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(undo)_null_move() is used to do(undo) 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);
1001 std::memcpy(&newSt, st, sizeof(StateInfo));
1004 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
1006 newSt.previous = st;
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(st->key));
1019 st->pliesFromNull = 0;
1021 sideToMove = ~sideToMove;
1027 assert(pos_is_ok());
1030 void Position::undo_null_move() {
1032 assert(!checkers());
1035 sideToMove = ~sideToMove;
1039 /// Position::key_after() computes the new hash key after the given move. Needed
1040 /// for speculative prefetch. It doesn't recognize special moves like castling,
1041 /// en-passant and promotions.
1043 Key Position::key_after(Move m) const {
1045 Square from = from_sq(m);
1046 Square to = to_sq(m);
1047 Piece pc = piece_on(from);
1048 Piece captured = piece_on(to);
1049 Key k = st->key ^ Zobrist::side;
1052 k ^= Zobrist::psq[captured][to];
1054 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1058 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1059 /// SEE value of move is greater or equal to the given threshold. We'll use an
1060 /// algorithm similar to alpha-beta pruning with a null window.
1062 bool Position::see_ge(Move m, Value threshold) const {
1066 // Only deal with normal moves, assume others pass a simple see
1067 if (type_of(m) != NORMAL)
1068 return VALUE_ZERO >= threshold;
1070 Square from = from_sq(m), to = to_sq(m);
1072 int swap = PieceValue[MG][piece_on(to)] - threshold;
1076 swap = PieceValue[MG][piece_on(from)] - swap;
1080 Bitboard occupied = pieces() ^ from ^ to;
1081 Color stm = color_of(piece_on(from));
1082 Bitboard attackers = attackers_to(to, occupied);
1083 Bitboard stmAttackers, bb;
1089 attackers &= occupied;
1091 // If stm has no more attackers then give up: stm loses
1092 if (!(stmAttackers = attackers & pieces(stm)))
1095 // Don't allow pinned pieces to attack (except the king) as long as
1096 // there are pinners on their original square.
1097 if (pinners(~stm) & occupied)
1098 stmAttackers &= ~blockers_for_king(stm);
1105 // Locate and remove the next least valuable attacker, and add to
1106 // the bitboard 'attackers' any X-ray attackers behind it.
1107 if ((bb = stmAttackers & pieces(PAWN)))
1109 if ((swap = PawnValueMg - swap) < res)
1112 occupied ^= lsb(bb);
1113 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1116 else if ((bb = stmAttackers & pieces(KNIGHT)))
1118 if ((swap = KnightValueMg - swap) < res)
1121 occupied ^= lsb(bb);
1124 else if ((bb = stmAttackers & pieces(BISHOP)))
1126 if ((swap = BishopValueMg - swap) < res)
1129 occupied ^= lsb(bb);
1130 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1133 else if ((bb = stmAttackers & pieces(ROOK)))
1135 if ((swap = RookValueMg - swap) < res)
1138 occupied ^= lsb(bb);
1139 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1142 else if ((bb = stmAttackers & pieces(QUEEN)))
1144 if ((swap = QueenValueMg - swap) < res)
1147 occupied ^= lsb(bb);
1148 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1149 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1153 // If we "capture" with the king but opponent still has attackers,
1154 // reverse the result.
1155 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1162 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1163 /// or by repetition. It does not detect stalemates.
1165 bool Position::is_draw(int ply) const {
1167 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1170 // Return a draw score if a position repeats once earlier but strictly
1171 // after the root, or repeats twice before or at the root.
1172 return st->repetition && st->repetition < ply;
1176 // Position::has_repeated() tests whether there has been at least one repetition
1177 // of positions since the last capture or pawn move.
1179 bool Position::has_repeated() const {
1181 StateInfo* stc = st;
1182 int end = std::min(st->rule50, st->pliesFromNull);
1185 if (stc->repetition)
1188 stc = stc->previous;
1194 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1195 /// or an earlier position has a move that directly reaches the current position.
1197 bool Position::has_game_cycle(int ply) const {
1201 int end = std::min(st->rule50, st->pliesFromNull);
1206 Key originalKey = st->key;
1207 StateInfo* stp = st->previous;
1209 for (int i = 3; i <= end; i += 2)
1211 stp = stp->previous->previous;
1213 Key moveKey = originalKey ^ stp->key;
1214 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1215 || (j = H2(moveKey), cuckoo[j] == moveKey))
1217 Move move = cuckooMove[j];
1218 Square s1 = from_sq(move);
1219 Square s2 = to_sq(move);
1221 if (!(between_bb(s1, s2) & pieces()))
1226 // For nodes before or at the root, check that the move is a
1227 // repetition rather than a move to the current position.
1228 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1229 // the same location, so we have to select which square to check.
1230 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1233 // For repetitions before or at the root, require one more
1234 if (stp->repetition)
1243 /// Position::flip() flips position with the white and black sides reversed. This
1244 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1246 void Position::flip() {
1249 std::stringstream ss(fen());
1251 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1253 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1254 f.insert(0, token + (f.empty() ? " " : "/"));
1257 ss >> token; // Active color
1258 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1260 ss >> token; // Castling availability
1263 std::transform(f.begin(), f.end(), f.begin(),
1264 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1266 ss >> token; // En passant square
1267 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1269 std::getline(ss, token); // Half and full moves
1272 set(f, is_chess960(), st, this_thread());
1274 assert(pos_is_ok());
1278 /// Position::pos_is_ok() performs some consistency checks for the
1279 /// position object and raises an asserts if something wrong is detected.
1280 /// This is meant to be helpful when debugging.
1282 bool Position::pos_is_ok() const {
1284 constexpr bool Fast = true; // Quick (default) or full check?
1286 if ( (sideToMove != WHITE && sideToMove != BLACK)
1287 || piece_on(square<KING>(WHITE)) != W_KING
1288 || piece_on(square<KING>(BLACK)) != B_KING
1289 || ( ep_square() != SQ_NONE
1290 && relative_rank(sideToMove, ep_square()) != RANK_6))
1291 assert(0 && "pos_is_ok: Default");
1296 if ( pieceCount[W_KING] != 1
1297 || pieceCount[B_KING] != 1
1298 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1299 assert(0 && "pos_is_ok: Kings");
1301 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1302 || pieceCount[W_PAWN] > 8
1303 || pieceCount[B_PAWN] > 8)
1304 assert(0 && "pos_is_ok: Pawns");
1306 if ( (pieces(WHITE) & pieces(BLACK))
1307 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1308 || popcount(pieces(WHITE)) > 16
1309 || popcount(pieces(BLACK)) > 16)
1310 assert(0 && "pos_is_ok: Bitboards");
1312 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1313 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1314 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1315 assert(0 && "pos_is_ok: Bitboards");
1319 if (std::memcmp(&si, st, sizeof(StateInfo)))
1320 assert(0 && "pos_is_ok: State");
1322 for (Piece pc : Pieces)
1324 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1325 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1326 assert(0 && "pos_is_ok: Pieces");
1328 for (int i = 0; i < pieceCount[pc]; ++i)
1329 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1330 assert(0 && "pos_is_ok: Index");
1333 for (Color c : { WHITE, BLACK })
1334 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1336 if (!can_castle(cr))
1339 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1340 || castlingRightsMask[castlingRookSquare[cr]] != cr
1341 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1342 assert(0 && "pos_is_ok: Castling");