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);
201 // Each piece on board gets a unique ID used to track the piece later
202 PieceId piece_id, next_piece_id = PIECE_ID_ZERO;
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)
217 auto pc = Piece(idx);
222 // Kings get a fixed ID, other pieces get ID in order of placement
224 (idx == W_KING) ? PIECE_ID_WKING :
225 (idx == B_KING) ? PIECE_ID_BKING :
227 evalList.put_piece(piece_id, sq, pc);
236 sideToMove = (token == 'w' ? WHITE : BLACK);
239 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
240 // Shredder-FEN that uses the letters of the columns on which the rooks began
241 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
242 // if an inner rook is associated with the castling right, the castling tag is
243 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
244 while ((ss >> token) && !isspace(token))
247 Color c = islower(token) ? BLACK : WHITE;
248 Piece rook = make_piece(c, ROOK);
250 token = char(toupper(token));
253 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
255 else if (token == 'Q')
256 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
258 else if (token >= 'A' && token <= 'H')
259 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
264 set_castling_right(c, rsq);
267 // 4. En passant square.
268 // Ignore if square is invalid or not on side to move relative rank 6.
269 bool enpassant = false;
271 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
272 && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3'))))
274 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
276 // En passant square will be considered only if
277 // a) side to move have a pawn threatening epSquare
278 // b) there is an enemy pawn in front of epSquare
279 // c) there is no piece on epSquare or behind epSquare
280 enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN)
281 && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))
282 && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove))));
286 st->epSquare = SQ_NONE;
288 // 5-6. Halfmove clock and fullmove number
289 ss >> std::skipws >> st->rule50 >> gamePly;
291 // Convert from fullmove starting from 1 to gamePly starting from 0,
292 // handle also common incorrect FEN with fullmove = 0.
293 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
295 chess960 = isChess960;
303 /// Position::set_castling_right() is a helper function used to set castling
304 /// rights given the corresponding color and the rook starting square.
306 void Position::set_castling_right(Color c, Square rfrom) {
308 Square kfrom = square<KING>(c);
309 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
311 st->castlingRights |= cr;
312 castlingRightsMask[kfrom] |= cr;
313 castlingRightsMask[rfrom] |= cr;
314 castlingRookSquare[cr] = rfrom;
316 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
317 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
319 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
324 /// Position::set_check_info() sets king attacks to detect if a move gives check
326 void Position::set_check_info(StateInfo* si) const {
328 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
329 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
331 Square ksq = square<KING>(~sideToMove);
333 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
334 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
335 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
336 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
337 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
338 si->checkSquares[KING] = 0;
342 /// Position::set_state() computes the hash keys of the position, and other
343 /// data that once computed is updated incrementally as moves are made.
344 /// The function is only used when a new position is set up, and to verify
345 /// the correctness of the StateInfo data when running in debug mode.
347 void Position::set_state(StateInfo* si) const {
349 si->key = si->materialKey = 0;
350 si->pawnKey = Zobrist::noPawns;
351 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
352 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
356 for (Bitboard b = pieces(); b; )
358 Square s = pop_lsb(&b);
359 Piece pc = piece_on(s);
360 si->key ^= Zobrist::psq[pc][s];
362 if (type_of(pc) == PAWN)
363 si->pawnKey ^= Zobrist::psq[pc][s];
365 else if (type_of(pc) != KING)
366 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
369 if (si->epSquare != SQ_NONE)
370 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
372 if (sideToMove == BLACK)
373 si->key ^= Zobrist::side;
375 si->key ^= Zobrist::castling[si->castlingRights];
377 for (Piece pc : Pieces)
378 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
379 si->materialKey ^= Zobrist::psq[pc][cnt];
383 /// Position::set() is an overload to initialize the position object with
384 /// the given endgame code string like "KBPKN". It is mainly a helper to
385 /// get the material key out of an endgame code.
387 Position& Position::set(const string& code, Color c, StateInfo* si) {
389 assert(code[0] == 'K');
391 string sides[] = { code.substr(code.find('K', 1)), // Weak
392 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
394 assert(sides[0].length() > 0 && sides[0].length() < 8);
395 assert(sides[1].length() > 0 && sides[1].length() < 8);
397 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
399 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
400 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
402 return set(fenStr, false, si, nullptr);
406 /// Position::fen() returns a FEN representation of the position. In case of
407 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
409 const string Position::fen() const {
412 std::ostringstream ss;
414 for (Rank r = RANK_8; r >= RANK_1; --r)
416 for (File f = FILE_A; f <= FILE_H; ++f)
418 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
425 ss << PieceToChar[piece_on(make_square(f, r))];
432 ss << (sideToMove == WHITE ? " w " : " b ");
434 if (can_castle(WHITE_OO))
435 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
437 if (can_castle(WHITE_OOO))
438 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
440 if (can_castle(BLACK_OO))
441 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
443 if (can_castle(BLACK_OOO))
444 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
446 if (!can_castle(ANY_CASTLING))
449 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
450 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
456 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
457 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
458 /// slider if removing that piece from the board would result in a position where
459 /// square 's' is attacked. For example, a king-attack blocking piece can be either
460 /// a pinned or a discovered check piece, according if its color is the opposite
461 /// or the same of the color of the slider.
463 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
465 Bitboard blockers = 0;
468 // Snipers are sliders that attack 's' when a piece and other snipers are removed
469 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
470 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
471 Bitboard occupancy = pieces() ^ snipers;
475 Square sniperSq = pop_lsb(&snipers);
476 Bitboard b = between_bb(s, sniperSq) & occupancy;
478 if (b && !more_than_one(b))
481 if (b & pieces(color_of(piece_on(s))))
489 /// Position::attackers_to() computes a bitboard of all pieces which attack a
490 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
492 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
494 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
495 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
496 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
497 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
498 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
499 | (attacks_bb<KING>(s) & pieces(KING));
503 /// Position::legal() tests whether a pseudo-legal move is legal
505 bool Position::legal(Move m) const {
509 Color us = sideToMove;
510 Square from = from_sq(m);
511 Square to = to_sq(m);
513 assert(color_of(moved_piece(m)) == us);
514 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
516 // En passant captures are a tricky special case. Because they are rather
517 // uncommon, we do it simply by testing whether the king is attacked after
519 if (type_of(m) == ENPASSANT)
521 Square ksq = square<KING>(us);
522 Square capsq = to - pawn_push(us);
523 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
525 assert(to == ep_square());
526 assert(moved_piece(m) == make_piece(us, PAWN));
527 assert(piece_on(capsq) == make_piece(~us, PAWN));
528 assert(piece_on(to) == NO_PIECE);
530 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
531 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
534 // Castling moves generation does not check if the castling path is clear of
535 // enemy attacks, it is delayed at a later time: now!
536 if (type_of(m) == CASTLING)
538 // After castling, the rook and king final positions are the same in
539 // Chess960 as they would be in standard chess.
540 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
541 Direction step = to > from ? WEST : EAST;
543 for (Square s = to; s != from; s += step)
544 if (attackers_to(s) & pieces(~us))
547 // In case of Chess960, verify that when moving the castling rook we do
548 // not discover some hidden checker.
549 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
551 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
554 // If the moving piece is a king, check whether the destination square is
555 // attacked by the opponent.
556 if (type_of(piece_on(from)) == KING)
557 return !(attackers_to(to) & pieces(~us));
559 // A non-king move is legal if and only if it is not pinned or it
560 // is moving along the ray towards or away from the king.
561 return !(blockers_for_king(us) & from)
562 || aligned(from, to, square<KING>(us));
566 /// Position::pseudo_legal() takes a random move and tests whether the move is
567 /// pseudo legal. It is used to validate moves from TT that can be corrupted
568 /// due to SMP concurrent access or hash position key aliasing.
570 bool Position::pseudo_legal(const Move m) const {
572 Color us = sideToMove;
573 Square from = from_sq(m);
574 Square to = to_sq(m);
575 Piece pc = moved_piece(m);
577 // Use a slower but simpler function for uncommon cases
578 if (type_of(m) != NORMAL)
579 return MoveList<LEGAL>(*this).contains(m);
581 // Is not a promotion, so promotion piece must be empty
582 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
585 // If the 'from' square is not occupied by a piece belonging to the side to
586 // move, the move is obviously not legal.
587 if (pc == NO_PIECE || color_of(pc) != us)
590 // The destination square cannot be occupied by a friendly piece
594 // Handle the special case of a pawn move
595 if (type_of(pc) == PAWN)
597 // We have already handled promotion moves, so destination
598 // cannot be on the 8th/1st rank.
599 if ((Rank8BB | Rank1BB) & to)
602 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
603 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
604 && !( (from + 2 * pawn_push(us) == to) // Not a double push
605 && (relative_rank(us, from) == RANK_2)
607 && empty(to - pawn_push(us))))
610 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
613 // Evasions generator already takes care to avoid some kind of illegal moves
614 // and legal() relies on this. We therefore have to take care that the same
615 // kind of moves are filtered out here.
618 if (type_of(pc) != KING)
620 // Double check? In this case a king move is required
621 if (more_than_one(checkers()))
624 // Our move must be a blocking evasion or a capture of the checking piece
625 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
628 // In case of king moves under check we have to remove king so as to catch
629 // invalid moves like b1a1 when opposite queen is on c1.
630 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
638 /// Position::gives_check() tests whether a pseudo-legal move gives a check
640 bool Position::gives_check(Move m) const {
643 assert(color_of(moved_piece(m)) == sideToMove);
645 Square from = from_sq(m);
646 Square to = to_sq(m);
648 // Is there a direct check?
649 if (check_squares(type_of(piece_on(from))) & to)
652 // Is there a discovered check?
653 if ( (blockers_for_king(~sideToMove) & from)
654 && !aligned(from, to, square<KING>(~sideToMove)))
663 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
665 // En passant capture with check? We have already handled the case
666 // of direct checks and ordinary discovered check, so the only case we
667 // need to handle is the unusual case of a discovered check through
668 // the captured pawn.
671 Square capsq = make_square(file_of(to), rank_of(from));
672 Bitboard b = (pieces() ^ from ^ capsq) | to;
674 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
675 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
680 Square rfrom = to; // Castling is encoded as 'king captures the rook'
681 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
682 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
684 return (attacks_bb<ROOK>(rto) & square<KING>(~sideToMove))
685 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
694 /// Position::do_move() makes a move, and saves all information necessary
695 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
696 /// moves should be filtered out before this function is called.
698 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
701 assert(&newSt != st);
703 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
704 Key k = st->key ^ Zobrist::side;
706 // Copy some fields of the old state to our new StateInfo object except the
707 // ones which are going to be recalculated from scratch anyway and then switch
708 // our state pointer to point to the new (ready to be updated) state.
709 std::memcpy(&newSt, st, offsetof(StateInfo, key));
713 // Increment ply counters. In particular, rule50 will be reset to zero later on
714 // in case of a capture or a pawn move.
720 st->accumulator.computed_accumulation = false;
721 st->accumulator.computed_score = false;
722 PieceId dp0 = PIECE_ID_NONE;
723 PieceId dp1 = PIECE_ID_NONE;
724 auto& dp = st->dirtyPiece;
727 Color us = sideToMove;
729 Square from = from_sq(m);
730 Square to = to_sq(m);
731 Piece pc = piece_on(from);
732 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
734 assert(color_of(pc) == us);
735 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
736 assert(type_of(captured) != KING);
738 if (type_of(m) == CASTLING)
740 assert(pc == make_piece(us, KING));
741 assert(captured == make_piece(us, ROOK));
744 do_castling<true>(us, from, to, rfrom, rto);
746 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
754 // If the captured piece is a pawn, update pawn hash key, otherwise
755 // update non-pawn material.
756 if (type_of(captured) == PAWN)
758 if (type_of(m) == ENPASSANT)
760 capsq -= pawn_push(us);
762 assert(pc == make_piece(us, PAWN));
763 assert(to == st->epSquare);
764 assert(relative_rank(us, to) == RANK_6);
765 assert(piece_on(to) == NO_PIECE);
766 assert(piece_on(capsq) == make_piece(them, PAWN));
769 st->pawnKey ^= Zobrist::psq[captured][capsq];
772 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
776 dp.dirty_num = 2; // 2 pieces moved
777 dp1 = piece_id_on(capsq);
779 dp.old_piece[1] = evalList.piece_with_id(dp1);
780 evalList.put_piece(dp1, capsq, NO_PIECE);
781 dp.new_piece[1] = evalList.piece_with_id(dp1);
784 // Update board and piece lists
787 if (type_of(m) == ENPASSANT)
788 board[capsq] = NO_PIECE;
790 // Update material hash key and prefetch access to materialTable
791 k ^= Zobrist::psq[captured][capsq];
792 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
793 prefetch(thisThread->materialTable[st->materialKey]);
795 // Reset rule 50 counter
800 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
802 // Reset en passant square
803 if (st->epSquare != SQ_NONE)
805 k ^= Zobrist::enpassant[file_of(st->epSquare)];
806 st->epSquare = SQ_NONE;
809 // Update castling rights if needed
810 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
812 k ^= Zobrist::castling[st->castlingRights];
813 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
814 k ^= Zobrist::castling[st->castlingRights];
817 // Move the piece. The tricky Chess960 castling is handled earlier
818 if (type_of(m) != CASTLING)
822 dp0 = piece_id_on(from);
824 dp.old_piece[0] = evalList.piece_with_id(dp0);
825 evalList.put_piece(dp0, to, pc);
826 dp.new_piece[0] = evalList.piece_with_id(dp0);
829 move_piece(from, to);
832 // If the moving piece is a pawn do some special extra work
833 if (type_of(pc) == PAWN)
835 // Set en-passant square if the moved pawn can be captured
836 if ( (int(to) ^ int(from)) == 16
837 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
839 st->epSquare = to - pawn_push(us);
840 k ^= Zobrist::enpassant[file_of(st->epSquare)];
843 else if (type_of(m) == PROMOTION)
845 Piece promotion = make_piece(us, promotion_type(m));
847 assert(relative_rank(us, to) == RANK_8);
848 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
851 put_piece(promotion, to);
855 dp0 = piece_id_on(to);
856 evalList.put_piece(dp0, to, promotion);
857 dp.new_piece[0] = evalList.piece_with_id(dp0);
861 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
862 st->pawnKey ^= Zobrist::psq[pc][to];
863 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
864 ^ Zobrist::psq[pc][pieceCount[pc]];
867 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
870 // Update pawn hash key
871 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
873 // Reset rule 50 draw counter
878 st->capturedPiece = captured;
880 // Update the key with the final value
883 // Calculate checkers bitboard (if move gives check)
884 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
886 sideToMove = ~sideToMove;
888 // Update king attacks used for fast check detection
891 // Calculate the repetition info. It is the ply distance from the previous
892 // occurrence of the same position, negative in the 3-fold case, or zero
893 // if the position was not repeated.
895 int end = std::min(st->rule50, st->pliesFromNull);
898 StateInfo* stp = st->previous->previous;
899 for (int i = 4; i <= end; i += 2)
901 stp = stp->previous->previous;
902 if (stp->key == st->key)
904 st->repetition = stp->repetition ? -i : i;
914 /// Position::undo_move() unmakes a move. When it returns, the position should
915 /// be restored to exactly the same state as before the move was made.
917 void Position::undo_move(Move m) {
921 sideToMove = ~sideToMove;
923 Color us = sideToMove;
924 Square from = from_sq(m);
925 Square to = to_sq(m);
926 Piece pc = piece_on(to);
928 assert(empty(from) || type_of(m) == CASTLING);
929 assert(type_of(st->capturedPiece) != KING);
931 if (type_of(m) == PROMOTION)
933 assert(relative_rank(us, to) == RANK_8);
934 assert(type_of(pc) == promotion_type(m));
935 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
938 pc = make_piece(us, PAWN);
942 if (type_of(m) == CASTLING)
945 do_castling<false>(us, from, to, rfrom, rto);
949 move_piece(to, from); // Put the piece back at the source square
953 PieceId dp0 = st->dirtyPiece.pieceId[0];
954 evalList.put_piece(dp0, from, pc);
957 if (st->capturedPiece)
961 if (type_of(m) == ENPASSANT)
963 capsq -= pawn_push(us);
965 assert(type_of(pc) == PAWN);
966 assert(to == st->previous->epSquare);
967 assert(relative_rank(us, to) == RANK_6);
968 assert(piece_on(capsq) == NO_PIECE);
969 assert(st->capturedPiece == make_piece(~us, PAWN));
972 put_piece(st->capturedPiece, capsq); // Restore the captured piece
976 PieceId dp1 = st->dirtyPiece.pieceId[1];
977 assert(evalList.piece_with_id(dp1).from[WHITE] == PS_NONE);
978 assert(evalList.piece_with_id(dp1).from[BLACK] == PS_NONE);
979 evalList.put_piece(dp1, capsq, st->capturedPiece);
984 // Finally point our state pointer back to the previous state
992 /// Position::do_castling() is a helper used to do/undo a castling move. This
993 /// is a bit tricky in Chess960 where from/to squares can overlap.
995 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
997 bool kingSide = to > from;
998 rfrom = to; // Castling is encoded as "king captures friendly rook"
999 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1000 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1005 auto& dp = st->dirtyPiece;
1006 dp.dirty_num = 2; // 2 pieces moved
1010 dp0 = piece_id_on(from);
1011 dp1 = piece_id_on(rfrom);
1012 dp.pieceId[0] = dp0;
1013 dp.old_piece[0] = evalList.piece_with_id(dp0);
1014 evalList.put_piece(dp0, to, make_piece(us, KING));
1015 dp.new_piece[0] = evalList.piece_with_id(dp0);
1016 dp.pieceId[1] = dp1;
1017 dp.old_piece[1] = evalList.piece_with_id(dp1);
1018 evalList.put_piece(dp1, rto, make_piece(us, ROOK));
1019 dp.new_piece[1] = evalList.piece_with_id(dp1);
1023 dp0 = piece_id_on(to);
1024 dp1 = piece_id_on(rto);
1025 evalList.put_piece(dp0, from, make_piece(us, KING));
1026 evalList.put_piece(dp1, rfrom, make_piece(us, ROOK));
1030 // Remove both pieces first since squares could overlap in Chess960
1031 remove_piece(Do ? from : to);
1032 remove_piece(Do ? rfrom : rto);
1033 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
1034 put_piece(make_piece(us, KING), Do ? to : from);
1035 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
1039 /// Position::do(undo)_null_move() is used to do(undo) a "null move": it flips
1040 /// the side to move without executing any move on the board.
1042 void Position::do_null_move(StateInfo& newSt) {
1044 assert(!checkers());
1045 assert(&newSt != st);
1049 std::memcpy(&newSt, st, sizeof(StateInfo));
1050 st->accumulator.computed_score = false;
1053 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
1055 newSt.previous = st;
1058 if (st->epSquare != SQ_NONE)
1060 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1061 st->epSquare = SQ_NONE;
1064 st->key ^= Zobrist::side;
1065 prefetch(TT.first_entry(st->key));
1068 st->pliesFromNull = 0;
1070 sideToMove = ~sideToMove;
1076 assert(pos_is_ok());
1079 void Position::undo_null_move() {
1081 assert(!checkers());
1084 sideToMove = ~sideToMove;
1088 /// Position::key_after() computes the new hash key after the given move. Needed
1089 /// for speculative prefetch. It doesn't recognize special moves like castling,
1090 /// en-passant and promotions.
1092 Key Position::key_after(Move m) const {
1094 Square from = from_sq(m);
1095 Square to = to_sq(m);
1096 Piece pc = piece_on(from);
1097 Piece captured = piece_on(to);
1098 Key k = st->key ^ Zobrist::side;
1101 k ^= Zobrist::psq[captured][to];
1103 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1107 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1108 /// SEE value of move is greater or equal to the given threshold. We'll use an
1109 /// algorithm similar to alpha-beta pruning with a null window.
1111 bool Position::see_ge(Move m, Value threshold) const {
1115 // Only deal with normal moves, assume others pass a simple see
1116 if (type_of(m) != NORMAL)
1117 return VALUE_ZERO >= threshold;
1119 Square from = from_sq(m), to = to_sq(m);
1121 int swap = PieceValue[MG][piece_on(to)] - threshold;
1125 swap = PieceValue[MG][piece_on(from)] - swap;
1129 Bitboard occupied = pieces() ^ from ^ to;
1130 Color stm = color_of(piece_on(from));
1131 Bitboard attackers = attackers_to(to, occupied);
1132 Bitboard stmAttackers, bb;
1138 attackers &= occupied;
1140 // If stm has no more attackers then give up: stm loses
1141 if (!(stmAttackers = attackers & pieces(stm)))
1144 // Don't allow pinned pieces to attack (except the king) as long as
1145 // there are pinners on their original square.
1146 if (st->pinners[~stm] & occupied)
1147 stmAttackers &= ~st->blockersForKing[stm];
1154 // Locate and remove the next least valuable attacker, and add to
1155 // the bitboard 'attackers' any X-ray attackers behind it.
1156 if ((bb = stmAttackers & pieces(PAWN)))
1158 if ((swap = PawnValueMg - swap) < res)
1161 occupied ^= lsb(bb);
1162 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1165 else if ((bb = stmAttackers & pieces(KNIGHT)))
1167 if ((swap = KnightValueMg - swap) < res)
1170 occupied ^= lsb(bb);
1173 else if ((bb = stmAttackers & pieces(BISHOP)))
1175 if ((swap = BishopValueMg - swap) < res)
1178 occupied ^= lsb(bb);
1179 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1182 else if ((bb = stmAttackers & pieces(ROOK)))
1184 if ((swap = RookValueMg - swap) < res)
1187 occupied ^= lsb(bb);
1188 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1191 else if ((bb = stmAttackers & pieces(QUEEN)))
1193 if ((swap = QueenValueMg - swap) < res)
1196 occupied ^= lsb(bb);
1197 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1198 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1202 // If we "capture" with the king but opponent still has attackers,
1203 // reverse the result.
1204 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1211 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1212 /// or by repetition. It does not detect stalemates.
1214 bool Position::is_draw(int ply) const {
1216 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1219 // Return a draw score if a position repeats once earlier but strictly
1220 // after the root, or repeats twice before or at the root.
1221 return st->repetition && st->repetition < ply;
1225 // Position::has_repeated() tests whether there has been at least one repetition
1226 // of positions since the last capture or pawn move.
1228 bool Position::has_repeated() const {
1230 StateInfo* stc = st;
1231 int end = std::min(st->rule50, st->pliesFromNull);
1234 if (stc->repetition)
1237 stc = stc->previous;
1243 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1244 /// or an earlier position has a move that directly reaches the current position.
1246 bool Position::has_game_cycle(int ply) const {
1250 int end = std::min(st->rule50, st->pliesFromNull);
1255 Key originalKey = st->key;
1256 StateInfo* stp = st->previous;
1258 for (int i = 3; i <= end; i += 2)
1260 stp = stp->previous->previous;
1262 Key moveKey = originalKey ^ stp->key;
1263 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1264 || (j = H2(moveKey), cuckoo[j] == moveKey))
1266 Move move = cuckooMove[j];
1267 Square s1 = from_sq(move);
1268 Square s2 = to_sq(move);
1270 if (!(between_bb(s1, s2) & pieces()))
1275 // For nodes before or at the root, check that the move is a
1276 // repetition rather than a move to the current position.
1277 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1278 // the same location, so we have to select which square to check.
1279 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1282 // For repetitions before or at the root, require one more
1283 if (stp->repetition)
1292 /// Position::flip() flips position with the white and black sides reversed. This
1293 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1295 void Position::flip() {
1298 std::stringstream ss(fen());
1300 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1302 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1303 f.insert(0, token + (f.empty() ? " " : "/"));
1306 ss >> token; // Active color
1307 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1309 ss >> token; // Castling availability
1312 std::transform(f.begin(), f.end(), f.begin(),
1313 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1315 ss >> token; // En passant square
1316 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1318 std::getline(ss, token); // Half and full moves
1321 set(f, is_chess960(), st, this_thread());
1323 assert(pos_is_ok());
1327 /// Position::pos_is_ok() performs some consistency checks for the
1328 /// position object and raises an asserts if something wrong is detected.
1329 /// This is meant to be helpful when debugging.
1331 bool Position::pos_is_ok() const {
1333 constexpr bool Fast = true; // Quick (default) or full check?
1335 if ( (sideToMove != WHITE && sideToMove != BLACK)
1336 || piece_on(square<KING>(WHITE)) != W_KING
1337 || piece_on(square<KING>(BLACK)) != B_KING
1338 || ( ep_square() != SQ_NONE
1339 && relative_rank(sideToMove, ep_square()) != RANK_6))
1340 assert(0 && "pos_is_ok: Default");
1345 if ( pieceCount[W_KING] != 1
1346 || pieceCount[B_KING] != 1
1347 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1348 assert(0 && "pos_is_ok: Kings");
1350 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1351 || pieceCount[W_PAWN] > 8
1352 || pieceCount[B_PAWN] > 8)
1353 assert(0 && "pos_is_ok: Pawns");
1355 if ( (pieces(WHITE) & pieces(BLACK))
1356 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1357 || popcount(pieces(WHITE)) > 16
1358 || popcount(pieces(BLACK)) > 16)
1359 assert(0 && "pos_is_ok: Bitboards");
1361 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1362 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1363 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1364 assert(0 && "pos_is_ok: Bitboards");
1368 if (std::memcmp(&si, st, sizeof(StateInfo)))
1369 assert(0 && "pos_is_ok: State");
1371 for (Piece pc : Pieces)
1373 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1374 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1375 assert(0 && "pos_is_ok: Pieces");
1377 for (int i = 0; i < pieceCount[pc]; ++i)
1378 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1379 assert(0 && "pos_is_ok: Index");
1382 for (Color c : { WHITE, BLACK })
1383 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1385 if (!can_castle(cr))
1388 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1389 || castlingRightsMask[castlingRookSquare[cr]] != cr
1390 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1391 assert(0 && "pos_is_ok: Castling");