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;
305 /// Position::set_castling_right() is a helper function used to set castling
306 /// rights given the corresponding color and the rook starting square.
308 void Position::set_castling_right(Color c, Square rfrom) {
310 Square kfrom = square<KING>(c);
311 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
313 st->castlingRights |= cr;
314 castlingRightsMask[kfrom] |= cr;
315 castlingRightsMask[rfrom] |= cr;
316 castlingRookSquare[cr] = rfrom;
318 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
319 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
321 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
326 /// Position::set_check_info() sets king attacks to detect if a move gives check
328 void Position::set_check_info(StateInfo* si) const {
330 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
331 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
333 Square ksq = square<KING>(~sideToMove);
335 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
336 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
337 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
338 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
339 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
340 si->checkSquares[KING] = 0;
344 /// Position::set_state() computes the hash keys of the position, and other
345 /// data that once computed is updated incrementally as moves are made.
346 /// The function is only used when a new position is set up, and to verify
347 /// the correctness of the StateInfo data when running in debug mode.
349 void Position::set_state(StateInfo* si) const {
351 si->key = si->materialKey = 0;
352 si->pawnKey = Zobrist::noPawns;
353 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
354 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
358 for (Bitboard b = pieces(); b; )
360 Square s = pop_lsb(&b);
361 Piece pc = piece_on(s);
362 si->key ^= Zobrist::psq[pc][s];
364 if (type_of(pc) == PAWN)
365 si->pawnKey ^= Zobrist::psq[pc][s];
367 else if (type_of(pc) != KING)
368 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
371 if (si->epSquare != SQ_NONE)
372 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
374 if (sideToMove == BLACK)
375 si->key ^= Zobrist::side;
377 si->key ^= Zobrist::castling[si->castlingRights];
379 for (Piece pc : Pieces)
380 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
381 si->materialKey ^= Zobrist::psq[pc][cnt];
385 /// Position::set() is an overload to initialize the position object with
386 /// the given endgame code string like "KBPKN". It is mainly a helper to
387 /// get the material key out of an endgame code.
389 Position& Position::set(const string& code, Color c, StateInfo* si) {
391 assert(code[0] == 'K');
393 string sides[] = { code.substr(code.find('K', 1)), // Weak
394 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
396 assert(sides[0].length() > 0 && sides[0].length() < 8);
397 assert(sides[1].length() > 0 && sides[1].length() < 8);
399 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
401 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
402 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
404 return set(fenStr, false, si, nullptr);
408 /// Position::fen() returns a FEN representation of the position. In case of
409 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
411 const string Position::fen() const {
414 std::ostringstream ss;
416 for (Rank r = RANK_8; r >= RANK_1; --r)
418 for (File f = FILE_A; f <= FILE_H; ++f)
420 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
427 ss << PieceToChar[piece_on(make_square(f, r))];
434 ss << (sideToMove == WHITE ? " w " : " b ");
436 if (can_castle(WHITE_OO))
437 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
439 if (can_castle(WHITE_OOO))
440 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
442 if (can_castle(BLACK_OO))
443 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
445 if (can_castle(BLACK_OOO))
446 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
448 if (!can_castle(ANY_CASTLING))
451 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
452 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
458 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
459 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
460 /// slider if removing that piece from the board would result in a position where
461 /// square 's' is attacked. For example, a king-attack blocking piece can be either
462 /// a pinned or a discovered check piece, according if its color is the opposite
463 /// or the same of the color of the slider.
465 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
467 Bitboard blockers = 0;
470 // Snipers are sliders that attack 's' when a piece and other snipers are removed
471 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
472 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
473 Bitboard occupancy = pieces() ^ snipers;
477 Square sniperSq = pop_lsb(&snipers);
478 Bitboard b = between_bb(s, sniperSq) & occupancy;
480 if (b && !more_than_one(b))
483 if (b & pieces(color_of(piece_on(s))))
491 /// Position::attackers_to() computes a bitboard of all pieces which attack a
492 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
494 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
496 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
497 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
498 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
499 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
500 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
501 | (attacks_bb<KING>(s) & pieces(KING));
505 /// Position::legal() tests whether a pseudo-legal move is legal
507 bool Position::legal(Move m) const {
511 Color us = sideToMove;
512 Square from = from_sq(m);
513 Square to = to_sq(m);
515 assert(color_of(moved_piece(m)) == us);
516 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
518 // En passant captures are a tricky special case. Because they are rather
519 // uncommon, we do it simply by testing whether the king is attacked after
521 if (type_of(m) == ENPASSANT)
523 Square ksq = square<KING>(us);
524 Square capsq = to - pawn_push(us);
525 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
527 assert(to == ep_square());
528 assert(moved_piece(m) == make_piece(us, PAWN));
529 assert(piece_on(capsq) == make_piece(~us, PAWN));
530 assert(piece_on(to) == NO_PIECE);
532 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
533 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
536 // Castling moves generation does not check if the castling path is clear of
537 // enemy attacks, it is delayed at a later time: now!
538 if (type_of(m) == CASTLING)
540 // After castling, the rook and king final positions are the same in
541 // Chess960 as they would be in standard chess.
542 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
543 Direction step = to > from ? WEST : EAST;
545 for (Square s = to; s != from; s += step)
546 if (attackers_to(s) & pieces(~us))
549 // In case of Chess960, verify that when moving the castling rook we do
550 // not discover some hidden checker.
551 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
553 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
556 // If the moving piece is a king, check whether the destination square is
557 // attacked by the opponent.
558 if (type_of(piece_on(from)) == KING)
559 return !(attackers_to(to) & pieces(~us));
561 // A non-king move is legal if and only if it is not pinned or it
562 // is moving along the ray towards or away from the king.
563 return !(blockers_for_king(us) & from)
564 || aligned(from, to, square<KING>(us));
568 /// Position::pseudo_legal() takes a random move and tests whether the move is
569 /// pseudo legal. It is used to validate moves from TT that can be corrupted
570 /// due to SMP concurrent access or hash position key aliasing.
572 bool Position::pseudo_legal(const Move m) const {
574 Color us = sideToMove;
575 Square from = from_sq(m);
576 Square to = to_sq(m);
577 Piece pc = moved_piece(m);
579 // Use a slower but simpler function for uncommon cases
580 if (type_of(m) != NORMAL)
581 return MoveList<LEGAL>(*this).contains(m);
583 // Is not a promotion, so promotion piece must be empty
584 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
587 // If the 'from' square is not occupied by a piece belonging to the side to
588 // move, the move is obviously not legal.
589 if (pc == NO_PIECE || color_of(pc) != us)
592 // The destination square cannot be occupied by a friendly piece
596 // Handle the special case of a pawn move
597 if (type_of(pc) == PAWN)
599 // We have already handled promotion moves, so destination
600 // cannot be on the 8th/1st rank.
601 if ((Rank8BB | Rank1BB) & to)
604 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
605 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
606 && !( (from + 2 * pawn_push(us) == to) // Not a double push
607 && (relative_rank(us, from) == RANK_2)
609 && empty(to - pawn_push(us))))
612 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
615 // Evasions generator already takes care to avoid some kind of illegal moves
616 // and legal() relies on this. We therefore have to take care that the same
617 // kind of moves are filtered out here.
620 if (type_of(pc) != KING)
622 // Double check? In this case a king move is required
623 if (more_than_one(checkers()))
626 // Our move must be a blocking evasion or a capture of the checking piece
627 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
630 // In case of king moves under check we have to remove king so as to catch
631 // invalid moves like b1a1 when opposite queen is on c1.
632 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
640 /// Position::gives_check() tests whether a pseudo-legal move gives a check
642 bool Position::gives_check(Move m) const {
645 assert(color_of(moved_piece(m)) == sideToMove);
647 Square from = from_sq(m);
648 Square to = to_sq(m);
650 // Is there a direct check?
651 if (check_squares(type_of(piece_on(from))) & to)
654 // Is there a discovered check?
655 if ( (blockers_for_king(~sideToMove) & from)
656 && !aligned(from, to, square<KING>(~sideToMove)))
665 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
667 // En passant capture with check? We have already handled the case
668 // of direct checks and ordinary discovered check, so the only case we
669 // need to handle is the unusual case of a discovered check through
670 // the captured pawn.
673 Square capsq = make_square(file_of(to), rank_of(from));
674 Bitboard b = (pieces() ^ from ^ capsq) | to;
676 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
677 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
682 Square rfrom = to; // Castling is encoded as 'king captures the rook'
683 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
684 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
686 return (attacks_bb<ROOK>(rto) & square<KING>(~sideToMove))
687 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
696 /// Position::do_move() makes a move, and saves all information necessary
697 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
698 /// moves should be filtered out before this function is called.
700 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
703 assert(&newSt != st);
705 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
706 Key k = st->key ^ Zobrist::side;
708 // Copy some fields of the old state to our new StateInfo object except the
709 // ones which are going to be recalculated from scratch anyway and then switch
710 // our state pointer to point to the new (ready to be updated) state.
711 std::memcpy(&newSt, st, offsetof(StateInfo, key));
715 // Increment ply counters. In particular, rule50 will be reset to zero later on
716 // in case of a capture or a pawn move.
722 st->accumulator.computed_accumulation = false;
723 st->accumulator.computed_score = false;
724 PieceId dp0 = PIECE_ID_NONE;
725 PieceId dp1 = PIECE_ID_NONE;
726 auto& dp = st->dirtyPiece;
729 Color us = sideToMove;
731 Square from = from_sq(m);
732 Square to = to_sq(m);
733 Piece pc = piece_on(from);
734 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
736 assert(color_of(pc) == us);
737 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
738 assert(type_of(captured) != KING);
740 if (type_of(m) == CASTLING)
742 assert(pc == make_piece(us, KING));
743 assert(captured == make_piece(us, ROOK));
746 do_castling<true>(us, from, to, rfrom, rto);
748 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
756 // If the captured piece is a pawn, update pawn hash key, otherwise
757 // update non-pawn material.
758 if (type_of(captured) == PAWN)
760 if (type_of(m) == ENPASSANT)
762 capsq -= pawn_push(us);
764 assert(pc == make_piece(us, PAWN));
765 assert(to == st->epSquare);
766 assert(relative_rank(us, to) == RANK_6);
767 assert(piece_on(to) == NO_PIECE);
768 assert(piece_on(capsq) == make_piece(them, PAWN));
771 st->pawnKey ^= Zobrist::psq[captured][capsq];
774 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
778 dp.dirty_num = 2; // 2 pieces moved
779 dp1 = piece_id_on(capsq);
781 dp.old_piece[1] = evalList.piece_with_id(dp1);
782 evalList.put_piece(dp1, capsq, NO_PIECE);
783 dp.new_piece[1] = evalList.piece_with_id(dp1);
786 // Update board and piece lists
789 if (type_of(m) == ENPASSANT)
790 board[capsq] = NO_PIECE;
792 // Update material hash key and prefetch access to materialTable
793 k ^= Zobrist::psq[captured][capsq];
794 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
795 prefetch(thisThread->materialTable[st->materialKey]);
797 // Reset rule 50 counter
802 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
804 // Reset en passant square
805 if (st->epSquare != SQ_NONE)
807 k ^= Zobrist::enpassant[file_of(st->epSquare)];
808 st->epSquare = SQ_NONE;
811 // Update castling rights if needed
812 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
814 k ^= Zobrist::castling[st->castlingRights];
815 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
816 k ^= Zobrist::castling[st->castlingRights];
819 // Move the piece. The tricky Chess960 castling is handled earlier
820 if (type_of(m) != CASTLING)
824 dp0 = piece_id_on(from);
826 dp.old_piece[0] = evalList.piece_with_id(dp0);
827 evalList.put_piece(dp0, to, pc);
828 dp.new_piece[0] = evalList.piece_with_id(dp0);
831 move_piece(from, to);
834 // If the moving piece is a pawn do some special extra work
835 if (type_of(pc) == PAWN)
837 // Set en-passant square if the moved pawn can be captured
838 if ( (int(to) ^ int(from)) == 16
839 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
841 st->epSquare = to - pawn_push(us);
842 k ^= Zobrist::enpassant[file_of(st->epSquare)];
845 else if (type_of(m) == PROMOTION)
847 Piece promotion = make_piece(us, promotion_type(m));
849 assert(relative_rank(us, to) == RANK_8);
850 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
853 put_piece(promotion, to);
857 dp0 = piece_id_on(to);
858 evalList.put_piece(dp0, to, promotion);
859 dp.new_piece[0] = evalList.piece_with_id(dp0);
863 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
864 st->pawnKey ^= Zobrist::psq[pc][to];
865 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
866 ^ Zobrist::psq[pc][pieceCount[pc]];
869 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
872 // Update pawn hash key
873 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
875 // Reset rule 50 draw counter
880 st->capturedPiece = captured;
882 // Update the key with the final value
885 // Calculate checkers bitboard (if move gives check)
886 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
888 sideToMove = ~sideToMove;
890 // Update king attacks used for fast check detection
893 // Calculate the repetition info. It is the ply distance from the previous
894 // occurrence of the same position, negative in the 3-fold case, or zero
895 // if the position was not repeated.
897 int end = std::min(st->rule50, st->pliesFromNull);
900 StateInfo* stp = st->previous->previous;
901 for (int i = 4; i <= end; i += 2)
903 stp = stp->previous->previous;
904 if (stp->key == st->key)
906 st->repetition = stp->repetition ? -i : i;
916 /// Position::undo_move() unmakes a move. When it returns, the position should
917 /// be restored to exactly the same state as before the move was made.
919 void Position::undo_move(Move m) {
923 sideToMove = ~sideToMove;
925 Color us = sideToMove;
926 Square from = from_sq(m);
927 Square to = to_sq(m);
928 Piece pc = piece_on(to);
930 assert(empty(from) || type_of(m) == CASTLING);
931 assert(type_of(st->capturedPiece) != KING);
933 if (type_of(m) == PROMOTION)
935 assert(relative_rank(us, to) == RANK_8);
936 assert(type_of(pc) == promotion_type(m));
937 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
940 pc = make_piece(us, PAWN);
944 if (type_of(m) == CASTLING)
947 do_castling<false>(us, from, to, rfrom, rto);
951 move_piece(to, from); // Put the piece back at the source square
955 PieceId dp0 = st->dirtyPiece.pieceId[0];
956 evalList.put_piece(dp0, from, pc);
959 if (st->capturedPiece)
963 if (type_of(m) == ENPASSANT)
965 capsq -= pawn_push(us);
967 assert(type_of(pc) == PAWN);
968 assert(to == st->previous->epSquare);
969 assert(relative_rank(us, to) == RANK_6);
970 assert(piece_on(capsq) == NO_PIECE);
971 assert(st->capturedPiece == make_piece(~us, PAWN));
974 put_piece(st->capturedPiece, capsq); // Restore the captured piece
978 PieceId dp1 = st->dirtyPiece.pieceId[1];
979 assert(evalList.piece_with_id(dp1).from[WHITE] == PS_NONE);
980 assert(evalList.piece_with_id(dp1).from[BLACK] == PS_NONE);
981 evalList.put_piece(dp1, capsq, st->capturedPiece);
986 // Finally point our state pointer back to the previous state
994 /// Position::do_castling() is a helper used to do/undo a castling move. This
995 /// is a bit tricky in Chess960 where from/to squares can overlap.
997 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
999 bool kingSide = to > from;
1000 rfrom = to; // Castling is encoded as "king captures friendly rook"
1001 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1002 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1007 auto& dp = st->dirtyPiece;
1008 dp.dirty_num = 2; // 2 pieces moved
1012 dp0 = piece_id_on(from);
1013 dp1 = piece_id_on(rfrom);
1014 dp.pieceId[0] = dp0;
1015 dp.old_piece[0] = evalList.piece_with_id(dp0);
1016 evalList.put_piece(dp0, to, make_piece(us, KING));
1017 dp.new_piece[0] = evalList.piece_with_id(dp0);
1018 dp.pieceId[1] = dp1;
1019 dp.old_piece[1] = evalList.piece_with_id(dp1);
1020 evalList.put_piece(dp1, rto, make_piece(us, ROOK));
1021 dp.new_piece[1] = evalList.piece_with_id(dp1);
1025 dp0 = piece_id_on(to);
1026 dp1 = piece_id_on(rto);
1027 evalList.put_piece(dp0, from, make_piece(us, KING));
1028 evalList.put_piece(dp1, rfrom, make_piece(us, ROOK));
1032 // Remove both pieces first since squares could overlap in Chess960
1033 remove_piece(Do ? from : to);
1034 remove_piece(Do ? rfrom : rto);
1035 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
1036 put_piece(make_piece(us, KING), Do ? to : from);
1037 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
1041 /// Position::do(undo)_null_move() is used to do(undo) a "null move": it flips
1042 /// the side to move without executing any move on the board.
1044 void Position::do_null_move(StateInfo& newSt) {
1046 assert(!checkers());
1047 assert(&newSt != st);
1051 std::memcpy(&newSt, st, sizeof(StateInfo));
1052 st->accumulator.computed_score = false;
1055 std::memcpy(&newSt, st, offsetof(StateInfo, accumulator));
1057 newSt.previous = st;
1060 if (st->epSquare != SQ_NONE)
1062 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1063 st->epSquare = SQ_NONE;
1066 st->key ^= Zobrist::side;
1067 prefetch(TT.first_entry(st->key));
1070 st->pliesFromNull = 0;
1072 sideToMove = ~sideToMove;
1078 assert(pos_is_ok());
1081 void Position::undo_null_move() {
1083 assert(!checkers());
1086 sideToMove = ~sideToMove;
1090 /// Position::key_after() computes the new hash key after the given move. Needed
1091 /// for speculative prefetch. It doesn't recognize special moves like castling,
1092 /// en-passant and promotions.
1094 Key Position::key_after(Move m) const {
1096 Square from = from_sq(m);
1097 Square to = to_sq(m);
1098 Piece pc = piece_on(from);
1099 Piece captured = piece_on(to);
1100 Key k = st->key ^ Zobrist::side;
1103 k ^= Zobrist::psq[captured][to];
1105 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1109 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1110 /// SEE value of move is greater or equal to the given threshold. We'll use an
1111 /// algorithm similar to alpha-beta pruning with a null window.
1113 bool Position::see_ge(Move m, Value threshold) const {
1117 // Only deal with normal moves, assume others pass a simple see
1118 if (type_of(m) != NORMAL)
1119 return VALUE_ZERO >= threshold;
1121 Square from = from_sq(m), to = to_sq(m);
1123 int swap = PieceValue[MG][piece_on(to)] - threshold;
1127 swap = PieceValue[MG][piece_on(from)] - swap;
1131 Bitboard occupied = pieces() ^ from ^ to;
1132 Color stm = color_of(piece_on(from));
1133 Bitboard attackers = attackers_to(to, occupied);
1134 Bitboard stmAttackers, bb;
1140 attackers &= occupied;
1142 // If stm has no more attackers then give up: stm loses
1143 if (!(stmAttackers = attackers & pieces(stm)))
1146 // Don't allow pinned pieces to attack (except the king) as long as
1147 // there are pinners on their original square.
1148 if (pinners(~stm) & occupied)
1149 stmAttackers &= ~blockers_for_king(stm);
1156 // Locate and remove the next least valuable attacker, and add to
1157 // the bitboard 'attackers' any X-ray attackers behind it.
1158 if ((bb = stmAttackers & pieces(PAWN)))
1160 if ((swap = PawnValueMg - swap) < res)
1163 occupied ^= lsb(bb);
1164 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1167 else if ((bb = stmAttackers & pieces(KNIGHT)))
1169 if ((swap = KnightValueMg - swap) < res)
1172 occupied ^= lsb(bb);
1175 else if ((bb = stmAttackers & pieces(BISHOP)))
1177 if ((swap = BishopValueMg - swap) < res)
1180 occupied ^= lsb(bb);
1181 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1184 else if ((bb = stmAttackers & pieces(ROOK)))
1186 if ((swap = RookValueMg - swap) < res)
1189 occupied ^= lsb(bb);
1190 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1193 else if ((bb = stmAttackers & pieces(QUEEN)))
1195 if ((swap = QueenValueMg - swap) < res)
1198 occupied ^= lsb(bb);
1199 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1200 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1204 // If we "capture" with the king but opponent still has attackers,
1205 // reverse the result.
1206 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1213 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1214 /// or by repetition. It does not detect stalemates.
1216 bool Position::is_draw(int ply) const {
1218 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1221 // Return a draw score if a position repeats once earlier but strictly
1222 // after the root, or repeats twice before or at the root.
1223 return st->repetition && st->repetition < ply;
1227 // Position::has_repeated() tests whether there has been at least one repetition
1228 // of positions since the last capture or pawn move.
1230 bool Position::has_repeated() const {
1232 StateInfo* stc = st;
1233 int end = std::min(st->rule50, st->pliesFromNull);
1236 if (stc->repetition)
1239 stc = stc->previous;
1245 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1246 /// or an earlier position has a move that directly reaches the current position.
1248 bool Position::has_game_cycle(int ply) const {
1252 int end = std::min(st->rule50, st->pliesFromNull);
1257 Key originalKey = st->key;
1258 StateInfo* stp = st->previous;
1260 for (int i = 3; i <= end; i += 2)
1262 stp = stp->previous->previous;
1264 Key moveKey = originalKey ^ stp->key;
1265 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1266 || (j = H2(moveKey), cuckoo[j] == moveKey))
1268 Move move = cuckooMove[j];
1269 Square s1 = from_sq(move);
1270 Square s2 = to_sq(move);
1272 if (!(between_bb(s1, s2) & pieces()))
1277 // For nodes before or at the root, check that the move is a
1278 // repetition rather than a move to the current position.
1279 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1280 // the same location, so we have to select which square to check.
1281 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1284 // For repetitions before or at the root, require one more
1285 if (stp->repetition)
1294 /// Position::flip() flips position with the white and black sides reversed. This
1295 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1297 void Position::flip() {
1300 std::stringstream ss(fen());
1302 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1304 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1305 f.insert(0, token + (f.empty() ? " " : "/"));
1308 ss >> token; // Active color
1309 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1311 ss >> token; // Castling availability
1314 std::transform(f.begin(), f.end(), f.begin(),
1315 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1317 ss >> token; // En passant square
1318 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1320 std::getline(ss, token); // Half and full moves
1323 set(f, is_chess960(), st, this_thread());
1325 assert(pos_is_ok());
1329 /// Position::pos_is_ok() performs some consistency checks for the
1330 /// position object and raises an asserts if something wrong is detected.
1331 /// This is meant to be helpful when debugging.
1333 bool Position::pos_is_ok() const {
1335 constexpr bool Fast = true; // Quick (default) or full check?
1337 if ( (sideToMove != WHITE && sideToMove != BLACK)
1338 || piece_on(square<KING>(WHITE)) != W_KING
1339 || piece_on(square<KING>(BLACK)) != B_KING
1340 || ( ep_square() != SQ_NONE
1341 && relative_rank(sideToMove, ep_square()) != RANK_6))
1342 assert(0 && "pos_is_ok: Default");
1347 if ( pieceCount[W_KING] != 1
1348 || pieceCount[B_KING] != 1
1349 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1350 assert(0 && "pos_is_ok: Kings");
1352 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1353 || pieceCount[W_PAWN] > 8
1354 || pieceCount[B_PAWN] > 8)
1355 assert(0 && "pos_is_ok: Pawns");
1357 if ( (pieces(WHITE) & pieces(BLACK))
1358 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1359 || popcount(pieces(WHITE)) > 16
1360 || popcount(pieces(BLACK)) > 16)
1361 assert(0 && "pos_is_ok: Bitboards");
1363 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1364 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1365 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1366 assert(0 && "pos_is_ok: Bitboards");
1370 if (std::memcmp(&si, st, sizeof(StateInfo)))
1371 assert(0 && "pos_is_ok: State");
1373 for (Piece pc : Pieces)
1375 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1376 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1377 assert(0 && "pos_is_ok: Pieces");
1379 for (int i = 0; i < pieceCount[pc]; ++i)
1380 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1381 assert(0 && "pos_is_ok: Index");
1384 for (Color c : { WHITE, BLACK })
1385 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1387 if (!can_castle(cr))
1390 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1391 || castlingRightsMask[castlingRookSquare[cr]] != cr
1392 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1393 assert(0 && "pos_is_ok: Castling");