2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 Copyright (C) 2015-2020 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
7 Stockfish is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 #include <cstddef> // For offsetof()
24 #include <cstring> // For std::memset, std::memcmp
35 #include "syzygy/tbprobe.h"
41 Key psq[PIECE_NB][SQUARE_NB];
42 Key enpassant[FILE_NB];
43 Key castling[CASTLING_RIGHT_NB];
49 const string PieceToChar(" PNBRQK pnbrqk");
51 constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
52 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
56 /// operator<<(Position) returns an ASCII representation of the position
58 std::ostream& operator<<(std::ostream& os, const Position& pos) {
60 os << "\n +---+---+---+---+---+---+---+---+\n";
62 for (Rank r = RANK_8; r >= RANK_1; --r)
64 for (File f = FILE_A; f <= FILE_H; ++f)
65 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
67 os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n";
70 os << " a b c d e f g h\n"
71 << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
72 << std::setfill('0') << std::setw(16) << pos.key()
73 << std::setfill(' ') << std::dec << "\nCheckers: ";
75 for (Bitboard b = pos.checkers(); b; )
76 os << UCI::square(pop_lsb(&b)) << " ";
78 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
79 && !pos.can_castle(ANY_CASTLING))
83 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
84 Tablebases::ProbeState s1, s2;
85 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
86 int dtz = Tablebases::probe_dtz(p, &s2);
87 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
88 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
95 // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
96 // situations. Description of the algorithm in the following paper:
97 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
99 // First and second hash functions for indexing the cuckoo tables
100 inline int H1(Key h) { return h & 0x1fff; }
101 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
103 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
105 Move cuckooMove[8192];
108 /// Position::init() initializes at startup the various arrays used to compute hash keys
110 void Position::init() {
114 for (Piece pc : Pieces)
115 for (Square s = SQ_A1; s <= SQ_H8; ++s)
116 Zobrist::psq[pc][s] = rng.rand<Key>();
118 for (File f = FILE_A; f <= FILE_H; ++f)
119 Zobrist::enpassant[f] = rng.rand<Key>();
121 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
122 Zobrist::castling[cr] = rng.rand<Key>();
124 Zobrist::side = rng.rand<Key>();
125 Zobrist::noPawns = rng.rand<Key>();
127 // Prepare the cuckoo tables
128 std::memset(cuckoo, 0, sizeof(cuckoo));
129 std::memset(cuckooMove, 0, sizeof(cuckooMove));
131 for (Piece pc : Pieces)
132 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
133 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
134 if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2))
136 Move move = make_move(s1, s2);
137 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
141 std::swap(cuckoo[i], key);
142 std::swap(cuckooMove[i], move);
143 if (move == MOVE_NONE) // Arrived at empty slot?
145 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
149 assert(count == 3668);
153 /// Position::set() initializes the position object with the given FEN string.
154 /// This function is not very robust - make sure that input FENs are correct,
155 /// this is assumed to be the responsibility of the GUI.
157 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
159 A FEN string defines a particular position using only the ASCII character set.
161 A FEN string contains six fields separated by a space. The fields are:
163 1) Piece placement (from white's perspective). Each rank is described, starting
164 with rank 8 and ending with rank 1. Within each rank, the contents of each
165 square are described from file A through file H. Following the Standard
166 Algebraic Notation (SAN), each piece is identified by a single letter taken
167 from the standard English names. White pieces are designated using upper-case
168 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
169 noted using digits 1 through 8 (the number of blank squares), and "/"
172 2) Active color. "w" means white moves next, "b" means black.
174 3) Castling availability. If neither side can castle, this is "-". Otherwise,
175 this has one or more letters: "K" (White can castle kingside), "Q" (White
176 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
177 can castle queenside).
179 4) En passant target square (in algebraic notation). If there's no en passant
180 target square, this is "-". If a pawn has just made a 2-square move, this
181 is the position "behind" the pawn. This is recorded only if there is a pawn
182 in position to make an en passant capture, and if there really is a pawn
183 that might have advanced two squares.
185 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
186 or capture. This is used to determine if a draw can be claimed under the
189 6) Fullmove number. The number of the full move. It starts at 1, and is
190 incremented after Black's move.
193 unsigned char col, row, token;
196 std::istringstream ss(fenStr);
198 std::memset(this, 0, sizeof(Position));
199 std::memset(si, 0, sizeof(StateInfo));
200 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
205 // 1. Piece placement
206 while ((ss >> token) && !isspace(token))
209 sq += (token - '0') * EAST; // Advance the given number of files
211 else if (token == '/')
214 else if ((idx = PieceToChar.find(token)) != string::npos)
216 put_piece(Piece(idx), sq);
223 sideToMove = (token == 'w' ? WHITE : BLACK);
226 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
227 // Shredder-FEN that uses the letters of the columns on which the rooks began
228 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
229 // if an inner rook is associated with the castling right, the castling tag is
230 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
231 while ((ss >> token) && !isspace(token))
234 Color c = islower(token) ? BLACK : WHITE;
235 Piece rook = make_piece(c, ROOK);
237 token = char(toupper(token));
240 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
242 else if (token == 'Q')
243 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
245 else if (token >= 'A' && token <= 'H')
246 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
251 set_castling_right(c, rsq);
254 // 4. En passant square. Ignore if no pawn capture is possible
255 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
256 && ((ss >> row) && (row == '3' || row == '6')))
258 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
260 if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
261 || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
262 st->epSquare = SQ_NONE;
265 st->epSquare = SQ_NONE;
267 // 5-6. Halfmove clock and fullmove number
268 ss >> std::skipws >> st->rule50 >> gamePly;
270 // Convert from fullmove starting from 1 to gamePly starting from 0,
271 // handle also common incorrect FEN with fullmove = 0.
272 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
274 chess960 = isChess960;
284 /// Position::set_castling_right() is a helper function used to set castling
285 /// rights given the corresponding color and the rook starting square.
287 void Position::set_castling_right(Color c, Square rfrom) {
289 Square kfrom = square<KING>(c);
290 CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE: QUEEN_SIDE);
292 st->castlingRights |= cr;
293 castlingRightsMask[kfrom] |= cr;
294 castlingRightsMask[rfrom] |= cr;
295 castlingRookSquare[cr] = rfrom;
297 Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1);
298 Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1);
300 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
305 /// Position::set_check_info() sets king attacks to detect if a move gives check
307 void Position::set_check_info(StateInfo* si) const {
309 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
310 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
312 Square ksq = square<KING>(~sideToMove);
314 si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq);
315 si->checkSquares[KNIGHT] = attacks_bb<KNIGHT>(ksq);
316 si->checkSquares[BISHOP] = attacks_bb<BISHOP>(ksq, pieces());
317 si->checkSquares[ROOK] = attacks_bb<ROOK>(ksq, pieces());
318 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
319 si->checkSquares[KING] = 0;
323 /// Position::set_state() computes the hash keys of the position, and other
324 /// data that once computed is updated incrementally as moves are made.
325 /// The function is only used when a new position is set up, and to verify
326 /// the correctness of the StateInfo data when running in debug mode.
328 void Position::set_state(StateInfo* si) const {
330 si->key = si->materialKey = 0;
331 si->pawnKey = Zobrist::noPawns;
332 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
333 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
337 for (Bitboard b = pieces(); b; )
339 Square s = pop_lsb(&b);
340 Piece pc = piece_on(s);
341 si->key ^= Zobrist::psq[pc][s];
343 if (type_of(pc) == PAWN)
344 si->pawnKey ^= Zobrist::psq[pc][s];
346 else if (type_of(pc) != KING)
347 si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc];
350 if (si->epSquare != SQ_NONE)
351 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
353 if (sideToMove == BLACK)
354 si->key ^= Zobrist::side;
356 si->key ^= Zobrist::castling[si->castlingRights];
358 for (Piece pc : Pieces)
359 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
360 si->materialKey ^= Zobrist::psq[pc][cnt];
364 /// Position::set() is an overload to initialize the position object with
365 /// the given endgame code string like "KBPKN". It is mainly a helper to
366 /// get the material key out of an endgame code.
368 Position& Position::set(const string& code, Color c, StateInfo* si) {
370 assert(code[0] == 'K');
372 string sides[] = { code.substr(code.find('K', 1)), // Weak
373 code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong
375 assert(sides[0].length() > 0 && sides[0].length() < 8);
376 assert(sides[1].length() > 0 && sides[1].length() < 8);
378 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
380 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
381 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
383 return set(fenStr, false, si, nullptr);
387 /// Position::fen() returns a FEN representation of the position. In case of
388 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
390 const string Position::fen() const {
393 std::ostringstream ss;
395 for (Rank r = RANK_8; r >= RANK_1; --r)
397 for (File f = FILE_A; f <= FILE_H; ++f)
399 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
406 ss << PieceToChar[piece_on(make_square(f, r))];
413 ss << (sideToMove == WHITE ? " w " : " b ");
415 if (can_castle(WHITE_OO))
416 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
418 if (can_castle(WHITE_OOO))
419 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
421 if (can_castle(BLACK_OO))
422 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
424 if (can_castle(BLACK_OOO))
425 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
427 if (!can_castle(ANY_CASTLING))
430 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
431 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
437 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
438 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
439 /// slider if removing that piece from the board would result in a position where
440 /// square 's' is attacked. For example, a king-attack blocking piece can be either
441 /// a pinned or a discovered check piece, according if its color is the opposite
442 /// or the same of the color of the slider.
444 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
446 Bitboard blockers = 0;
449 // Snipers are sliders that attack 's' when a piece and other snipers are removed
450 Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK))
451 | (attacks_bb<BISHOP>(s) & pieces(QUEEN, BISHOP))) & sliders;
452 Bitboard occupancy = pieces() ^ snipers;
456 Square sniperSq = pop_lsb(&snipers);
457 Bitboard b = between_bb(s, sniperSq) & occupancy;
459 if (b && !more_than_one(b))
462 if (b & pieces(color_of(piece_on(s))))
470 /// Position::attackers_to() computes a bitboard of all pieces which attack a
471 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
473 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
475 return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN))
476 | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN))
477 | (attacks_bb<KNIGHT>(s) & pieces(KNIGHT))
478 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
479 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
480 | (attacks_bb<KING>(s) & pieces(KING));
484 /// Position::legal() tests whether a pseudo-legal move is legal
486 bool Position::legal(Move m) const {
490 Color us = sideToMove;
491 Square from = from_sq(m);
492 Square to = to_sq(m);
494 assert(color_of(moved_piece(m)) == us);
495 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
497 // En passant captures are a tricky special case. Because they are rather
498 // uncommon, we do it simply by testing whether the king is attacked after
500 if (type_of(m) == ENPASSANT)
502 Square ksq = square<KING>(us);
503 Square capsq = to - pawn_push(us);
504 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
506 assert(to == ep_square());
507 assert(moved_piece(m) == make_piece(us, PAWN));
508 assert(piece_on(capsq) == make_piece(~us, PAWN));
509 assert(piece_on(to) == NO_PIECE);
511 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
512 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
515 // Castling moves generation does not check if the castling path is clear of
516 // enemy attacks, it is delayed at a later time: now!
517 if (type_of(m) == CASTLING)
519 // After castling, the rook and king final positions are the same in
520 // Chess960 as they would be in standard chess.
521 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
522 Direction step = to > from ? WEST : EAST;
524 for (Square s = to; s != from; s += step)
525 if (attackers_to(s) & pieces(~us))
528 // In case of Chess960, verify that when moving the castling rook we do
529 // not discover some hidden checker.
530 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
532 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
535 // If the moving piece is a king, check whether the destination square is
536 // attacked by the opponent.
537 if (type_of(piece_on(from)) == KING)
538 return !(attackers_to(to) & pieces(~us));
540 // A non-king move is legal if and only if it is not pinned or it
541 // is moving along the ray towards or away from the king.
542 return !(blockers_for_king(us) & from)
543 || aligned(from, to, square<KING>(us));
547 /// Position::pseudo_legal() takes a random move and tests whether the move is
548 /// pseudo legal. It is used to validate moves from TT that can be corrupted
549 /// due to SMP concurrent access or hash position key aliasing.
551 bool Position::pseudo_legal(const Move m) const {
553 Color us = sideToMove;
554 Square from = from_sq(m);
555 Square to = to_sq(m);
556 Piece pc = moved_piece(m);
558 // Use a slower but simpler function for uncommon cases
559 if (type_of(m) != NORMAL)
560 return MoveList<LEGAL>(*this).contains(m);
562 // Is not a promotion, so promotion piece must be empty
563 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
566 // If the 'from' square is not occupied by a piece belonging to the side to
567 // move, the move is obviously not legal.
568 if (pc == NO_PIECE || color_of(pc) != us)
571 // The destination square cannot be occupied by a friendly piece
575 // Handle the special case of a pawn move
576 if (type_of(pc) == PAWN)
578 // We have already handled promotion moves, so destination
579 // cannot be on the 8th/1st rank.
580 if ((Rank8BB | Rank1BB) & to)
583 if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture
584 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
585 && !( (from + 2 * pawn_push(us) == to) // Not a double push
586 && (relative_rank(us, from) == RANK_2)
588 && empty(to - pawn_push(us))))
591 else if (!(attacks_bb(type_of(pc), from, pieces()) & to))
594 // Evasions generator already takes care to avoid some kind of illegal moves
595 // and legal() relies on this. We therefore have to take care that the same
596 // kind of moves are filtered out here.
599 if (type_of(pc) != KING)
601 // Double check? In this case a king move is required
602 if (more_than_one(checkers()))
605 // Our move must be a blocking evasion or a capture of the checking piece
606 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
609 // In case of king moves under check we have to remove king so as to catch
610 // invalid moves like b1a1 when opposite queen is on c1.
611 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
619 /// Position::gives_check() tests whether a pseudo-legal move gives a check
621 bool Position::gives_check(Move m) const {
624 assert(color_of(moved_piece(m)) == sideToMove);
626 Square from = from_sq(m);
627 Square to = to_sq(m);
629 // Is there a direct check?
630 if (check_squares(type_of(piece_on(from))) & to)
633 // Is there a discovered check?
634 if ( (blockers_for_king(~sideToMove) & from)
635 && !aligned(from, to, square<KING>(~sideToMove)))
644 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
646 // En passant capture with check? We have already handled the case
647 // of direct checks and ordinary discovered check, so the only case we
648 // need to handle is the unusual case of a discovered check through
649 // the captured pawn.
652 Square capsq = make_square(file_of(to), rank_of(from));
653 Bitboard b = (pieces() ^ from ^ capsq) | to;
655 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
656 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
661 Square rfrom = to; // Castling is encoded as 'king captures the rook'
662 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
663 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
665 return (attacks_bb<ROOK>(rto) & square<KING>(~sideToMove))
666 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
675 /// Position::do_move() makes a move, and saves all information necessary
676 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
677 /// moves should be filtered out before this function is called.
679 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
682 assert(&newSt != st);
684 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
685 Key k = st->key ^ Zobrist::side;
687 // Copy some fields of the old state to our new StateInfo object except the
688 // ones which are going to be recalculated from scratch anyway and then switch
689 // our state pointer to point to the new (ready to be updated) state.
690 std::memcpy(&newSt, st, offsetof(StateInfo, key));
694 // Increment ply counters. In particular, rule50 will be reset to zero later on
695 // in case of a capture or a pawn move.
700 Color us = sideToMove;
702 Square from = from_sq(m);
703 Square to = to_sq(m);
704 Piece pc = piece_on(from);
705 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
707 assert(color_of(pc) == us);
708 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
709 assert(type_of(captured) != KING);
711 if (type_of(m) == CASTLING)
713 assert(pc == make_piece(us, KING));
714 assert(captured == make_piece(us, ROOK));
717 do_castling<true>(us, from, to, rfrom, rto);
719 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
727 // If the captured piece is a pawn, update pawn hash key, otherwise
728 // update non-pawn material.
729 if (type_of(captured) == PAWN)
731 if (type_of(m) == ENPASSANT)
733 capsq -= pawn_push(us);
735 assert(pc == make_piece(us, PAWN));
736 assert(to == st->epSquare);
737 assert(relative_rank(us, to) == RANK_6);
738 assert(piece_on(to) == NO_PIECE);
739 assert(piece_on(capsq) == make_piece(them, PAWN));
742 st->pawnKey ^= Zobrist::psq[captured][capsq];
745 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
747 // Update board and piece lists
750 if (type_of(m) == ENPASSANT)
751 board[capsq] = NO_PIECE;
753 // Update material hash key and prefetch access to materialTable
754 k ^= Zobrist::psq[captured][capsq];
755 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
756 prefetch(thisThread->materialTable[st->materialKey]);
758 // Reset rule 50 counter
763 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
765 // Reset en passant square
766 if (st->epSquare != SQ_NONE)
768 k ^= Zobrist::enpassant[file_of(st->epSquare)];
769 st->epSquare = SQ_NONE;
772 // Update castling rights if needed
773 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
775 k ^= Zobrist::castling[st->castlingRights];
776 st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]);
777 k ^= Zobrist::castling[st->castlingRights];
780 // Move the piece. The tricky Chess960 castling is handled earlier
781 if (type_of(m) != CASTLING)
782 move_piece(from, to);
784 // If the moving piece is a pawn do some special extra work
785 if (type_of(pc) == PAWN)
787 // Set en-passant square if the moved pawn can be captured
788 if ( (int(to) ^ int(from)) == 16
789 && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN)))
791 st->epSquare = to - pawn_push(us);
792 k ^= Zobrist::enpassant[file_of(st->epSquare)];
795 else if (type_of(m) == PROMOTION)
797 Piece promotion = make_piece(us, promotion_type(m));
799 assert(relative_rank(us, to) == RANK_8);
800 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
803 put_piece(promotion, to);
806 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
807 st->pawnKey ^= Zobrist::psq[pc][to];
808 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
809 ^ Zobrist::psq[pc][pieceCount[pc]];
812 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
815 // Update pawn hash key
816 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
818 // Reset rule 50 draw counter
823 st->capturedPiece = captured;
825 // Update the key with the final value
828 // Calculate checkers bitboard (if move gives check)
829 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
831 sideToMove = ~sideToMove;
833 // Update king attacks used for fast check detection
836 // Calculate the repetition info. It is the ply distance from the previous
837 // occurrence of the same position, negative in the 3-fold case, or zero
838 // if the position was not repeated.
840 int end = std::min(st->rule50, st->pliesFromNull);
843 StateInfo* stp = st->previous->previous;
844 for (int i = 4; i <= end; i += 2)
846 stp = stp->previous->previous;
847 if (stp->key == st->key)
849 st->repetition = stp->repetition ? -i : i;
859 /// Position::undo_move() unmakes a move. When it returns, the position should
860 /// be restored to exactly the same state as before the move was made.
862 void Position::undo_move(Move m) {
866 sideToMove = ~sideToMove;
868 Color us = sideToMove;
869 Square from = from_sq(m);
870 Square to = to_sq(m);
871 Piece pc = piece_on(to);
873 assert(empty(from) || type_of(m) == CASTLING);
874 assert(type_of(st->capturedPiece) != KING);
876 if (type_of(m) == PROMOTION)
878 assert(relative_rank(us, to) == RANK_8);
879 assert(type_of(pc) == promotion_type(m));
880 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
883 pc = make_piece(us, PAWN);
887 if (type_of(m) == CASTLING)
890 do_castling<false>(us, from, to, rfrom, rto);
894 move_piece(to, from); // Put the piece back at the source square
896 if (st->capturedPiece)
900 if (type_of(m) == ENPASSANT)
902 capsq -= pawn_push(us);
904 assert(type_of(pc) == PAWN);
905 assert(to == st->previous->epSquare);
906 assert(relative_rank(us, to) == RANK_6);
907 assert(piece_on(capsq) == NO_PIECE);
908 assert(st->capturedPiece == make_piece(~us, PAWN));
911 put_piece(st->capturedPiece, capsq); // Restore the captured piece
915 // Finally point our state pointer back to the previous state
923 /// Position::do_castling() is a helper used to do/undo a castling move. This
924 /// is a bit tricky in Chess960 where from/to squares can overlap.
926 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
928 bool kingSide = to > from;
929 rfrom = to; // Castling is encoded as "king captures friendly rook"
930 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
931 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
933 // Remove both pieces first since squares could overlap in Chess960
934 remove_piece(Do ? from : to);
935 remove_piece(Do ? rfrom : rto);
936 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us
937 put_piece(make_piece(us, KING), Do ? to : from);
938 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
942 /// Position::do(undo)_null_move() is used to do(undo) a "null move": it flips
943 /// the side to move without executing any move on the board.
945 void Position::do_null_move(StateInfo& newSt) {
948 assert(&newSt != st);
950 std::memcpy(&newSt, st, sizeof(StateInfo));
954 if (st->epSquare != SQ_NONE)
956 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
957 st->epSquare = SQ_NONE;
960 st->key ^= Zobrist::side;
961 prefetch(TT.first_entry(st->key));
964 st->pliesFromNull = 0;
966 sideToMove = ~sideToMove;
975 void Position::undo_null_move() {
980 sideToMove = ~sideToMove;
984 /// Position::key_after() computes the new hash key after the given move. Needed
985 /// for speculative prefetch. It doesn't recognize special moves like castling,
986 /// en-passant and promotions.
988 Key Position::key_after(Move m) const {
990 Square from = from_sq(m);
991 Square to = to_sq(m);
992 Piece pc = piece_on(from);
993 Piece captured = piece_on(to);
994 Key k = st->key ^ Zobrist::side;
997 k ^= Zobrist::psq[captured][to];
999 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1003 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1004 /// SEE value of move is greater or equal to the given threshold. We'll use an
1005 /// algorithm similar to alpha-beta pruning with a null window.
1007 bool Position::see_ge(Move m, Value threshold) const {
1011 // Only deal with normal moves, assume others pass a simple see
1012 if (type_of(m) != NORMAL)
1013 return VALUE_ZERO >= threshold;
1015 Square from = from_sq(m), to = to_sq(m);
1017 int swap = PieceValue[MG][piece_on(to)] - threshold;
1021 swap = PieceValue[MG][piece_on(from)] - swap;
1025 Bitboard occupied = pieces() ^ from ^ to;
1026 Color stm = color_of(piece_on(from));
1027 Bitboard attackers = attackers_to(to, occupied);
1028 Bitboard stmAttackers, bb;
1034 attackers &= occupied;
1036 // If stm has no more attackers then give up: stm loses
1037 if (!(stmAttackers = attackers & pieces(stm)))
1040 // Don't allow pinned pieces to attack (except the king) as long as
1041 // there are pinners on their original square.
1042 if (st->pinners[~stm] & occupied)
1043 stmAttackers &= ~st->blockersForKing[stm];
1050 // Locate and remove the next least valuable attacker, and add to
1051 // the bitboard 'attackers' any X-ray attackers behind it.
1052 if ((bb = stmAttackers & pieces(PAWN)))
1054 if ((swap = PawnValueMg - swap) < res)
1057 occupied ^= lsb(bb);
1058 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1061 else if ((bb = stmAttackers & pieces(KNIGHT)))
1063 if ((swap = KnightValueMg - swap) < res)
1066 occupied ^= lsb(bb);
1069 else if ((bb = stmAttackers & pieces(BISHOP)))
1071 if ((swap = BishopValueMg - swap) < res)
1074 occupied ^= lsb(bb);
1075 attackers |= attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN);
1078 else if ((bb = stmAttackers & pieces(ROOK)))
1080 if ((swap = RookValueMg - swap) < res)
1083 occupied ^= lsb(bb);
1084 attackers |= attacks_bb<ROOK>(to, occupied) & pieces(ROOK, QUEEN);
1087 else if ((bb = stmAttackers & pieces(QUEEN)))
1089 if ((swap = QueenValueMg - swap) < res)
1092 occupied ^= lsb(bb);
1093 attackers |= (attacks_bb<BISHOP>(to, occupied) & pieces(BISHOP, QUEEN))
1094 | (attacks_bb<ROOK >(to, occupied) & pieces(ROOK , QUEEN));
1098 // If we "capture" with the king but opponent still has attackers,
1099 // reverse the result.
1100 return (attackers & ~pieces(stm)) ? res ^ 1 : res;
1107 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1108 /// or by repetition. It does not detect stalemates.
1110 bool Position::is_draw(int ply) const {
1112 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1115 // Return a draw score if a position repeats once earlier but strictly
1116 // after the root, or repeats twice before or at the root.
1117 return st->repetition && st->repetition < ply;
1121 // Position::has_repeated() tests whether there has been at least one repetition
1122 // of positions since the last capture or pawn move.
1124 bool Position::has_repeated() const {
1126 StateInfo* stc = st;
1127 int end = std::min(st->rule50, st->pliesFromNull);
1130 if (stc->repetition)
1133 stc = stc->previous;
1139 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1140 /// or an earlier position has a move that directly reaches the current position.
1142 bool Position::has_game_cycle(int ply) const {
1146 int end = std::min(st->rule50, st->pliesFromNull);
1151 Key originalKey = st->key;
1152 StateInfo* stp = st->previous;
1154 for (int i = 3; i <= end; i += 2)
1156 stp = stp->previous->previous;
1158 Key moveKey = originalKey ^ stp->key;
1159 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1160 || (j = H2(moveKey), cuckoo[j] == moveKey))
1162 Move move = cuckooMove[j];
1163 Square s1 = from_sq(move);
1164 Square s2 = to_sq(move);
1166 if (!(between_bb(s1, s2) & pieces()))
1171 // For nodes before or at the root, check that the move is a
1172 // repetition rather than a move to the current position.
1173 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in
1174 // the same location, so we have to select which square to check.
1175 if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move())
1178 // For repetitions before or at the root, require one more
1179 if (stp->repetition)
1188 /// Position::flip() flips position with the white and black sides reversed. This
1189 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1191 void Position::flip() {
1194 std::stringstream ss(fen());
1196 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1198 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1199 f.insert(0, token + (f.empty() ? " " : "/"));
1202 ss >> token; // Active color
1203 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1205 ss >> token; // Castling availability
1208 std::transform(f.begin(), f.end(), f.begin(),
1209 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1211 ss >> token; // En passant square
1212 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1214 std::getline(ss, token); // Half and full moves
1217 set(f, is_chess960(), st, this_thread());
1219 assert(pos_is_ok());
1223 /// Position::pos_is_ok() performs some consistency checks for the
1224 /// position object and raises an asserts if something wrong is detected.
1225 /// This is meant to be helpful when debugging.
1227 bool Position::pos_is_ok() const {
1229 constexpr bool Fast = true; // Quick (default) or full check?
1231 if ( (sideToMove != WHITE && sideToMove != BLACK)
1232 || piece_on(square<KING>(WHITE)) != W_KING
1233 || piece_on(square<KING>(BLACK)) != B_KING
1234 || ( ep_square() != SQ_NONE
1235 && relative_rank(sideToMove, ep_square()) != RANK_6))
1236 assert(0 && "pos_is_ok: Default");
1241 if ( pieceCount[W_KING] != 1
1242 || pieceCount[B_KING] != 1
1243 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1244 assert(0 && "pos_is_ok: Kings");
1246 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1247 || pieceCount[W_PAWN] > 8
1248 || pieceCount[B_PAWN] > 8)
1249 assert(0 && "pos_is_ok: Pawns");
1251 if ( (pieces(WHITE) & pieces(BLACK))
1252 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1253 || popcount(pieces(WHITE)) > 16
1254 || popcount(pieces(BLACK)) > 16)
1255 assert(0 && "pos_is_ok: Bitboards");
1257 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1258 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1259 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1260 assert(0 && "pos_is_ok: Bitboards");
1264 if (std::memcmp(&si, st, sizeof(StateInfo)))
1265 assert(0 && "pos_is_ok: State");
1267 for (Piece pc : Pieces)
1269 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1270 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1271 assert(0 && "pos_is_ok: Pieces");
1273 for (int i = 0; i < pieceCount[pc]; ++i)
1274 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1275 assert(0 && "pos_is_ok: Index");
1278 for (Color c : { WHITE, BLACK })
1279 for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE})
1281 if (!can_castle(cr))
1284 if ( piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK)
1285 || castlingRightsMask[castlingRookSquare[cr]] != cr
1286 || (castlingRightsMask[square<KING>(c)] & cr) != cr)
1287 assert(0 && "pos_is_ok: Castling");