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-2019 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/>.
22 #include <cstddef> // For offsetof()
23 #include <cstring> // For std::memset, std::memcmp
34 #include "syzygy/tbprobe.h"
40 Key psq[PIECE_NB][SQUARE_NB];
41 Key enpassant[FILE_NB];
42 Key castling[CASTLING_RIGHT_NB];
48 const string PieceToChar(" PNBRQK pnbrqk");
50 constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
51 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
53 // min_attacker() is a helper function used by see_ge() to locate the least
54 // valuable attacker for the side to move, remove the attacker we just found
55 // from the bitboards and scan for new X-ray attacks behind it.
58 PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,
59 Bitboard& occupied, Bitboard& attackers) {
61 Bitboard b = stmAttackers & byTypeBB[Pt];
63 return min_attacker<Pt + 1>(byTypeBB, to, stmAttackers, occupied, attackers);
65 occupied ^= lsb(b); // Remove the attacker from occupied
67 // Add any X-ray attack behind the just removed piece. For instance with
68 // rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8.
69 // Note that new added attackers can be of any color.
70 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
71 attackers |= attacks_bb<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);
73 if (Pt == ROOK || Pt == QUEEN)
74 attackers |= attacks_bb<ROOK>(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]);
76 // X-ray may add already processed pieces because byTypeBB[] is constant: in
77 // the rook example, now attackers contains _again_ rook in a7, so remove it.
78 attackers &= occupied;
83 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
84 return KING; // No need to update bitboards: it is the last cycle
90 /// operator<<(Position) returns an ASCII representation of the position
92 std::ostream& operator<<(std::ostream& os, const Position& pos) {
94 os << "\n +---+---+---+---+---+---+---+---+\n";
96 for (Rank r = RANK_8; r >= RANK_1; --r)
98 for (File f = FILE_A; f <= FILE_H; ++f)
99 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
101 os << " |\n +---+---+---+---+---+---+---+---+\n";
104 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
105 << std::setfill('0') << std::setw(16) << pos.key()
106 << std::setfill(' ') << std::dec << "\nCheckers: ";
108 for (Bitboard b = pos.checkers(); b; )
109 os << UCI::square(pop_lsb(&b)) << " ";
111 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
112 && !pos.can_castle(ANY_CASTLING))
116 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
117 Tablebases::ProbeState s1, s2;
118 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
119 int dtz = Tablebases::probe_dtz(p, &s2);
120 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
121 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
128 // Marcel van Kervinck's cuckoo algorithm for fast detection of "upcoming repetition"
129 // situations. Description of the algorithm in the following paper:
130 // https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf
132 // First and second hash functions for indexing the cuckoo tables
133 inline int H1(Key h) { return h & 0x1fff; }
134 inline int H2(Key h) { return (h >> 16) & 0x1fff; }
136 // Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves
138 Move cuckooMove[8192];
141 /// Position::init() initializes at startup the various arrays used to compute
144 void Position::init() {
148 for (Piece pc : Pieces)
149 for (Square s = SQ_A1; s <= SQ_H8; ++s)
150 Zobrist::psq[pc][s] = rng.rand<Key>();
152 for (File f = FILE_A; f <= FILE_H; ++f)
153 Zobrist::enpassant[f] = rng.rand<Key>();
155 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
157 Zobrist::castling[cr] = 0;
161 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
162 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
166 Zobrist::side = rng.rand<Key>();
167 Zobrist::noPawns = rng.rand<Key>();
169 // Prepare the cuckoo tables
170 std::memset(cuckoo, 0, sizeof(cuckoo));
171 std::memset(cuckooMove, 0, sizeof(cuckooMove));
173 for (Piece pc : Pieces)
174 for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
175 for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2)
176 if (PseudoAttacks[type_of(pc)][s1] & s2)
178 Move move = make_move(s1, s2);
179 Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side;
183 std::swap(cuckoo[i], key);
184 std::swap(cuckooMove[i], move);
185 if (move == MOVE_NONE) // Arrived at empty slot?
187 i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
191 assert(count == 3668);
195 /// Position::set() initializes the position object with the given FEN string.
196 /// This function is not very robust - make sure that input FENs are correct,
197 /// this is assumed to be the responsibility of the GUI.
199 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
201 A FEN string defines a particular position using only the ASCII character set.
203 A FEN string contains six fields separated by a space. The fields are:
205 1) Piece placement (from white's perspective). Each rank is described, starting
206 with rank 8 and ending with rank 1. Within each rank, the contents of each
207 square are described from file A through file H. Following the Standard
208 Algebraic Notation (SAN), each piece is identified by a single letter taken
209 from the standard English names. White pieces are designated using upper-case
210 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
211 noted using digits 1 through 8 (the number of blank squares), and "/"
214 2) Active color. "w" means white moves next, "b" means black.
216 3) Castling availability. If neither side can castle, this is "-". Otherwise,
217 this has one or more letters: "K" (White can castle kingside), "Q" (White
218 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
219 can castle queenside).
221 4) En passant target square (in algebraic notation). If there's no en passant
222 target square, this is "-". If a pawn has just made a 2-square move, this
223 is the position "behind" the pawn. This is recorded only if there is a pawn
224 in position to make an en passant capture, and if there really is a pawn
225 that might have advanced two squares.
227 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
228 or capture. This is used to determine if a draw can be claimed under the
231 6) Fullmove number. The number of the full move. It starts at 1, and is
232 incremented after Black's move.
235 unsigned char col, row, token;
238 std::istringstream ss(fenStr);
240 std::memset(this, 0, sizeof(Position));
241 std::memset(si, 0, sizeof(StateInfo));
242 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
247 // 1. Piece placement
248 while ((ss >> token) && !isspace(token))
251 sq += (token - '0') * EAST; // Advance the given number of files
253 else if (token == '/')
256 else if ((idx = PieceToChar.find(token)) != string::npos)
258 put_piece(Piece(idx), sq);
265 sideToMove = (token == 'w' ? WHITE : BLACK);
268 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
269 // Shredder-FEN that uses the letters of the columns on which the rooks began
270 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
271 // if an inner rook is associated with the castling right, the castling tag is
272 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
273 while ((ss >> token) && !isspace(token))
276 Color c = islower(token) ? BLACK : WHITE;
277 Piece rook = make_piece(c, ROOK);
279 token = char(toupper(token));
282 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
284 else if (token == 'Q')
285 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
287 else if (token >= 'A' && token <= 'H')
288 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
293 set_castling_right(c, rsq);
296 // 4. En passant square. Ignore if no pawn capture is possible
297 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
298 && ((ss >> row) && (row == '3' || row == '6')))
300 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
302 if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
303 || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
304 st->epSquare = SQ_NONE;
307 st->epSquare = SQ_NONE;
309 // 5-6. Halfmove clock and fullmove number
310 ss >> std::skipws >> st->rule50 >> gamePly;
312 // Convert from fullmove starting from 1 to gamePly starting from 0,
313 // handle also common incorrect FEN with fullmove = 0.
314 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
316 chess960 = isChess960;
324 /// Position::set_castling_right() is a helper function used to set castling
325 /// rights given the corresponding color and the rook starting square.
327 void Position::set_castling_right(Color c, Square rfrom) {
329 Square kfrom = square<KING>(c);
330 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
331 CastlingRight cr = (c | cs);
333 st->castlingRights |= cr;
334 castlingRightsMask[kfrom] |= cr;
335 castlingRightsMask[rfrom] |= cr;
336 castlingRookSquare[cr] = rfrom;
338 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
339 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
341 castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
342 & ~(square_bb(kfrom) | rfrom);
346 /// Position::set_check_info() sets king attacks to detect if a move gives check
348 void Position::set_check_info(StateInfo* si) const {
350 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinners[BLACK]);
351 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinners[WHITE]);
353 Square ksq = square<KING>(~sideToMove);
355 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
356 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
357 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
358 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
359 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
360 si->checkSquares[KING] = 0;
364 /// Position::set_state() computes the hash keys of the position, and other
365 /// data that once computed is updated incrementally as moves are made.
366 /// The function is only used when a new position is set up, and to verify
367 /// the correctness of the StateInfo data when running in debug mode.
369 void Position::set_state(StateInfo* si) const {
371 si->key = si->materialKey = 0;
372 si->pawnKey = Zobrist::noPawns;
373 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
374 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
378 for (Bitboard b = pieces(); b; )
380 Square s = pop_lsb(&b);
381 Piece pc = piece_on(s);
382 si->key ^= Zobrist::psq[pc][s];
385 if (si->epSquare != SQ_NONE)
386 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
388 if (sideToMove == BLACK)
389 si->key ^= Zobrist::side;
391 si->key ^= Zobrist::castling[si->castlingRights];
393 for (Bitboard b = pieces(PAWN); b; )
395 Square s = pop_lsb(&b);
396 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
399 for (Piece pc : Pieces)
401 if (type_of(pc) != PAWN && type_of(pc) != KING)
402 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
404 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
405 si->materialKey ^= Zobrist::psq[pc][cnt];
410 /// Position::set() is an overload to initialize the position object with
411 /// the given endgame code string like "KBPKN". It is mainly a helper to
412 /// get the material key out of an endgame code.
414 Position& Position::set(const string& code, Color c, StateInfo* si) {
416 assert(code.length() > 0 && code.length() < 8);
417 assert(code[0] == 'K');
419 string sides[] = { code.substr(code.find('K', 1)), // Weak
420 code.substr(0, code.find('K', 1)) }; // Strong
422 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
424 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
425 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
427 return set(fenStr, false, si, nullptr);
431 /// Position::fen() returns a FEN representation of the position. In case of
432 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
434 const string Position::fen() const {
437 std::ostringstream ss;
439 for (Rank r = RANK_8; r >= RANK_1; --r)
441 for (File f = FILE_A; f <= FILE_H; ++f)
443 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
450 ss << PieceToChar[piece_on(make_square(f, r))];
457 ss << (sideToMove == WHITE ? " w " : " b ");
459 if (can_castle(WHITE_OO))
460 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
462 if (can_castle(WHITE_OOO))
463 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
465 if (can_castle(BLACK_OO))
466 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
468 if (can_castle(BLACK_OOO))
469 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
471 if (!can_castle(ANY_CASTLING))
474 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
475 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
481 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
482 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
483 /// slider if removing that piece from the board would result in a position where
484 /// square 's' is attacked. For example, a king-attack blocking piece can be either
485 /// a pinned or a discovered check piece, according if its color is the opposite
486 /// or the same of the color of the slider.
488 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
490 Bitboard blockers = 0;
493 // Snipers are sliders that attack 's' when a piece and other snipers are removed
494 Bitboard snipers = ( (PseudoAttacks[ ROOK][s] & pieces(QUEEN, ROOK))
495 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
496 Bitboard occupancy = pieces() & ~snipers;
500 Square sniperSq = pop_lsb(&snipers);
501 Bitboard b = between_bb(s, sniperSq) & occupancy;
503 if (b && !more_than_one(b))
506 if (b & pieces(color_of(piece_on(s))))
514 /// Position::attackers_to() computes a bitboard of all pieces which attack a
515 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
517 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
519 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
520 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
521 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
522 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
523 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
524 | (attacks_from<KING>(s) & pieces(KING));
528 /// Position::legal() tests whether a pseudo-legal move is legal
530 bool Position::legal(Move m) const {
534 Color us = sideToMove;
535 Square from = from_sq(m);
536 Square to = to_sq(m);
538 assert(color_of(moved_piece(m)) == us);
539 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
541 // En passant captures are a tricky special case. Because they are rather
542 // uncommon, we do it simply by testing whether the king is attacked after
544 if (type_of(m) == ENPASSANT)
546 Square ksq = square<KING>(us);
547 Square capsq = to - pawn_push(us);
548 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
550 assert(to == ep_square());
551 assert(moved_piece(m) == make_piece(us, PAWN));
552 assert(piece_on(capsq) == make_piece(~us, PAWN));
553 assert(piece_on(to) == NO_PIECE);
555 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
556 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
559 // Castling moves generation does not check if the castling path is clear of
560 // enemy attacks, it is delayed at a later time: now!
561 if (type_of(m) == CASTLING)
563 // After castling, the rook and king final positions are the same in
564 // Chess960 as they would be in standard chess.
565 to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
566 Direction step = to > from ? WEST : EAST;
568 for (Square s = to; s != from; s += step)
569 if (attackers_to(s) & pieces(~us))
572 // In case of Chess960, verify that when moving the castling rook we do
573 // not discover some hidden checker.
574 // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
576 || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
579 // If the moving piece is a king, check whether the destination square is
580 // attacked by the opponent.
581 if (type_of(piece_on(from)) == KING)
582 return !(attackers_to(to) & pieces(~us));
584 // A non-king move is legal if and only if it is not pinned or it
585 // is moving along the ray towards or away from the king.
586 return !(blockers_for_king(us) & from)
587 || aligned(from, to, square<KING>(us));
591 /// Position::pseudo_legal() takes a random move and tests whether the move is
592 /// pseudo legal. It is used to validate moves from TT that can be corrupted
593 /// due to SMP concurrent access or hash position key aliasing.
595 bool Position::pseudo_legal(const Move m) const {
597 Color us = sideToMove;
598 Square from = from_sq(m);
599 Square to = to_sq(m);
600 Piece pc = moved_piece(m);
602 // Use a slower but simpler function for uncommon cases
603 if (type_of(m) != NORMAL)
604 return MoveList<LEGAL>(*this).contains(m);
606 // Is not a promotion, so promotion piece must be empty
607 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
610 // If the 'from' square is not occupied by a piece belonging to the side to
611 // move, the move is obviously not legal.
612 if (pc == NO_PIECE || color_of(pc) != us)
615 // The destination square cannot be occupied by a friendly piece
619 // Handle the special case of a pawn move
620 if (type_of(pc) == PAWN)
622 // We have already handled promotion moves, so destination
623 // cannot be on the 8th/1st rank.
624 if ((Rank8BB | Rank1BB) & to)
627 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
628 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
629 && !( (from + 2 * pawn_push(us) == to) // Not a double push
630 && (rank_of(from) == relative_rank(us, RANK_2))
632 && empty(to - pawn_push(us))))
635 else if (!(attacks_from(type_of(pc), from) & to))
638 // Evasions generator already takes care to avoid some kind of illegal moves
639 // and legal() relies on this. We therefore have to take care that the same
640 // kind of moves are filtered out here.
643 if (type_of(pc) != KING)
645 // Double check? In this case a king move is required
646 if (more_than_one(checkers()))
649 // Our move must be a blocking evasion or a capture of the checking piece
650 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
653 // In case of king moves under check we have to remove king so as to catch
654 // invalid moves like b1a1 when opposite queen is on c1.
655 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
663 /// Position::gives_check() tests whether a pseudo-legal move gives a check
665 bool Position::gives_check(Move m) const {
668 assert(color_of(moved_piece(m)) == sideToMove);
670 Square from = from_sq(m);
671 Square to = to_sq(m);
673 // Is there a direct check?
674 if (st->checkSquares[type_of(piece_on(from))] & to)
677 // Is there a discovered check?
678 if ( (st->blockersForKing[~sideToMove] & from)
679 && !aligned(from, to, square<KING>(~sideToMove)))
688 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
690 // En passant capture with check? We have already handled the case
691 // of direct checks and ordinary discovered check, so the only case we
692 // need to handle is the unusual case of a discovered check through
693 // the captured pawn.
696 Square capsq = make_square(file_of(to), rank_of(from));
697 Bitboard b = (pieces() ^ from ^ capsq) | to;
699 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
700 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
705 Square rfrom = to; // Castling is encoded as 'King captures the rook'
706 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
707 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
709 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
710 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
719 /// Position::do_move() makes a move, and saves all information necessary
720 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
721 /// moves should be filtered out before this function is called.
723 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
726 assert(&newSt != st);
728 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
729 Key k = st->key ^ Zobrist::side;
731 // Copy some fields of the old state to our new StateInfo object except the
732 // ones which are going to be recalculated from scratch anyway and then switch
733 // our state pointer to point to the new (ready to be updated) state.
734 std::memcpy(&newSt, st, offsetof(StateInfo, key));
738 // Increment ply counters. In particular, rule50 will be reset to zero later on
739 // in case of a capture or a pawn move.
744 Color us = sideToMove;
746 Square from = from_sq(m);
747 Square to = to_sq(m);
748 Piece pc = piece_on(from);
749 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
751 assert(color_of(pc) == us);
752 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
753 assert(type_of(captured) != KING);
755 if (type_of(m) == CASTLING)
757 assert(pc == make_piece(us, KING));
758 assert(captured == make_piece(us, ROOK));
761 do_castling<true>(us, from, to, rfrom, rto);
763 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
771 // If the captured piece is a pawn, update pawn hash key, otherwise
772 // update non-pawn material.
773 if (type_of(captured) == PAWN)
775 if (type_of(m) == ENPASSANT)
777 capsq -= pawn_push(us);
779 assert(pc == make_piece(us, PAWN));
780 assert(to == st->epSquare);
781 assert(relative_rank(us, to) == RANK_6);
782 assert(piece_on(to) == NO_PIECE);
783 assert(piece_on(capsq) == make_piece(them, PAWN));
785 board[capsq] = NO_PIECE; // Not done by remove_piece()
788 st->pawnKey ^= Zobrist::psq[captured][capsq];
791 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
793 // Update board and piece lists
794 remove_piece(captured, capsq);
796 // Update material hash key and prefetch access to materialTable
797 k ^= Zobrist::psq[captured][capsq];
798 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
799 prefetch(thisThread->materialTable[st->materialKey]);
801 // Reset rule 50 counter
806 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
808 // Reset en passant square
809 if (st->epSquare != SQ_NONE)
811 k ^= Zobrist::enpassant[file_of(st->epSquare)];
812 st->epSquare = SQ_NONE;
815 // Update castling rights if needed
816 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
818 int cr = castlingRightsMask[from] | castlingRightsMask[to];
819 k ^= Zobrist::castling[st->castlingRights & cr];
820 st->castlingRights &= ~cr;
823 // Move the piece. The tricky Chess960 castling is handled earlier
824 if (type_of(m) != CASTLING)
825 move_piece(pc, from, to);
827 // If the moving piece is a pawn do some special extra work
828 if (type_of(pc) == PAWN)
830 // Set en-passant square if the moved pawn can be captured
831 if ( (int(to) ^ int(from)) == 16
832 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
834 st->epSquare = to - pawn_push(us);
835 k ^= Zobrist::enpassant[file_of(st->epSquare)];
838 else if (type_of(m) == PROMOTION)
840 Piece promotion = make_piece(us, promotion_type(m));
842 assert(relative_rank(us, to) == RANK_8);
843 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
845 remove_piece(pc, to);
846 put_piece(promotion, to);
849 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
850 st->pawnKey ^= Zobrist::psq[pc][to];
851 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
852 ^ Zobrist::psq[pc][pieceCount[pc]];
855 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
858 // Update pawn hash key and prefetch access to pawnsTable
859 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
860 prefetch2(thisThread->pawnsTable[st->pawnKey]);
862 // Reset rule 50 draw counter
867 st->capturedPiece = captured;
869 // Update the key with the final value
872 // Calculate checkers bitboard (if move gives check)
873 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
875 sideToMove = ~sideToMove;
877 // Update king attacks used for fast check detection
884 /// Position::undo_move() unmakes a move. When it returns, the position should
885 /// be restored to exactly the same state as before the move was made.
887 void Position::undo_move(Move m) {
891 sideToMove = ~sideToMove;
893 Color us = sideToMove;
894 Square from = from_sq(m);
895 Square to = to_sq(m);
896 Piece pc = piece_on(to);
898 assert(empty(from) || type_of(m) == CASTLING);
899 assert(type_of(st->capturedPiece) != KING);
901 if (type_of(m) == PROMOTION)
903 assert(relative_rank(us, to) == RANK_8);
904 assert(type_of(pc) == promotion_type(m));
905 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
907 remove_piece(pc, to);
908 pc = make_piece(us, PAWN);
912 if (type_of(m) == CASTLING)
915 do_castling<false>(us, from, to, rfrom, rto);
919 move_piece(pc, to, from); // Put the piece back at the source square
921 if (st->capturedPiece)
925 if (type_of(m) == ENPASSANT)
927 capsq -= pawn_push(us);
929 assert(type_of(pc) == PAWN);
930 assert(to == st->previous->epSquare);
931 assert(relative_rank(us, to) == RANK_6);
932 assert(piece_on(capsq) == NO_PIECE);
933 assert(st->capturedPiece == make_piece(~us, PAWN));
936 put_piece(st->capturedPiece, capsq); // Restore the captured piece
940 // Finally point our state pointer back to the previous state
948 /// Position::do_castling() is a helper used to do/undo a castling move. This
949 /// is a bit tricky in Chess960 where from/to squares can overlap.
951 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
953 bool kingSide = to > from;
954 rfrom = to; // Castling is encoded as "king captures friendly rook"
955 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
956 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
958 // Remove both pieces first since squares could overlap in Chess960
959 remove_piece(make_piece(us, KING), Do ? from : to);
960 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
961 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
962 put_piece(make_piece(us, KING), Do ? to : from);
963 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
967 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
968 /// the side to move without executing any move on the board.
970 void Position::do_null_move(StateInfo& newSt) {
973 assert(&newSt != st);
975 std::memcpy(&newSt, st, sizeof(StateInfo));
979 if (st->epSquare != SQ_NONE)
981 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
982 st->epSquare = SQ_NONE;
985 st->key ^= Zobrist::side;
986 prefetch(TT.first_entry(st->key));
989 st->pliesFromNull = 0;
991 sideToMove = ~sideToMove;
998 void Position::undo_null_move() {
1000 assert(!checkers());
1003 sideToMove = ~sideToMove;
1007 /// Position::key_after() computes the new hash key after the given move. Needed
1008 /// for speculative prefetch. It doesn't recognize special moves like castling,
1009 /// en-passant and promotions.
1011 Key Position::key_after(Move m) const {
1013 Square from = from_sq(m);
1014 Square to = to_sq(m);
1015 Piece pc = piece_on(from);
1016 Piece captured = piece_on(to);
1017 Key k = st->key ^ Zobrist::side;
1020 k ^= Zobrist::psq[captured][to];
1022 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1026 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1027 /// SEE value of move is greater or equal to the given threshold. We'll use an
1028 /// algorithm similar to alpha-beta pruning with a null window.
1030 bool Position::see_ge(Move m, Value threshold) const {
1034 // Only deal with normal moves, assume others pass a simple see
1035 if (type_of(m) != NORMAL)
1036 return VALUE_ZERO >= threshold;
1038 Bitboard stmAttackers;
1039 Square from = from_sq(m), to = to_sq(m);
1040 PieceType nextVictim = type_of(piece_on(from));
1041 Color us = color_of(piece_on(from));
1042 Color stm = ~us; // First consider opponent's move
1043 Value balance; // Values of the pieces taken by us minus opponent's ones
1045 // The opponent may be able to recapture so this is the best result
1047 balance = PieceValue[MG][piece_on(to)] - threshold;
1049 if (balance < VALUE_ZERO)
1052 // Now assume the worst possible result: that the opponent can
1053 // capture our piece for free.
1054 balance -= PieceValue[MG][nextVictim];
1056 // If it is enough (like in PxQ) then return immediately. Note that
1057 // in case nextVictim == KING we always return here, this is ok
1058 // if the given move is legal.
1059 if (balance >= VALUE_ZERO)
1062 // Find all attackers to the destination square, with the moving piece
1063 // removed, but possibly an X-ray attacker added behind it.
1064 Bitboard occupied = pieces() ^ from ^ to;
1065 Bitboard attackers = attackers_to(to, occupied) & occupied;
1069 stmAttackers = attackers & pieces(stm);
1071 // Don't allow pinned pieces to attack (except the king) as long as
1072 // any pinners are on their original square.
1073 if (st->pinners[~stm] & occupied)
1074 stmAttackers &= ~st->blockersForKing[stm];
1076 // If stm has no more attackers then give up: stm loses
1080 // Locate and remove the next least valuable attacker, and add to
1081 // the bitboard 'attackers' the possibly X-ray attackers behind it.
1082 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1084 stm = ~stm; // Switch side to move
1086 // Negamax the balance with alpha = balance, beta = balance+1 and
1087 // add nextVictim's value.
1089 // (balance, balance+1) -> (-balance-1, -balance)
1091 assert(balance < VALUE_ZERO);
1093 balance = -balance - 1 - PieceValue[MG][nextVictim];
1095 // If balance is still non-negative after giving away nextVictim then we
1096 // win. The only thing to be careful about it is that we should revert
1097 // stm if we captured with the king when the opponent still has attackers.
1098 if (balance >= VALUE_ZERO)
1100 if (nextVictim == KING && (attackers & pieces(stm)))
1104 assert(nextVictim != KING);
1106 return us != stm; // We break the above loop when stm loses
1110 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1111 /// or by repetition. It does not detect stalemates.
1113 bool Position::is_draw(int ply) const {
1115 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1118 int end = std::min(st->rule50, st->pliesFromNull);
1123 StateInfo* stp = st->previous->previous;
1126 for (int i = 4; i <= end; i += 2)
1128 stp = stp->previous->previous;
1130 // Return a draw score if a position repeats once earlier but strictly
1131 // after the root, or repeats twice before or at the root.
1132 if ( stp->key == st->key
1133 && ++cnt + (ply > i) == 2)
1141 // Position::has_repeated() tests whether there has been at least one repetition
1142 // of positions since the last capture or pawn move.
1144 bool Position::has_repeated() const {
1146 StateInfo* stc = st;
1149 int i = 4, end = std::min(stc->rule50, stc->pliesFromNull);
1154 StateInfo* stp = stc->previous->previous;
1157 stp = stp->previous->previous;
1159 if (stp->key == stc->key)
1165 stc = stc->previous;
1170 /// Position::has_game_cycle() tests if the position has a move which draws by repetition,
1171 /// or an earlier position has a move that directly reaches the current position.
1173 bool Position::has_game_cycle(int ply) const {
1177 int end = std::min(st->rule50, st->pliesFromNull);
1182 Key originalKey = st->key;
1183 StateInfo* stp = st->previous;
1185 for (int i = 3; i <= end; i += 2)
1187 stp = stp->previous->previous;
1189 Key moveKey = originalKey ^ stp->key;
1190 if ( (j = H1(moveKey), cuckoo[j] == moveKey)
1191 || (j = H2(moveKey), cuckoo[j] == moveKey))
1193 Move move = cuckooMove[j];
1194 Square s1 = from_sq(move);
1195 Square s2 = to_sq(move);
1197 if (!(between_bb(s1, s2) & pieces()))
1199 // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in the same
1200 // location. We select the legal one by reversing the move variable if necessary.
1202 move = make_move(s2, s1);
1207 // For repetitions before or at the root, require one more
1208 StateInfo* next_stp = stp;
1209 for (int k = i + 2; k <= end; k += 2)
1211 next_stp = next_stp->previous->previous;
1212 if (next_stp->key == stp->key)
1222 /// Position::flip() flips position with the white and black sides reversed. This
1223 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1225 void Position::flip() {
1228 std::stringstream ss(fen());
1230 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1232 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1233 f.insert(0, token + (f.empty() ? " " : "/"));
1236 ss >> token; // Active color
1237 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1239 ss >> token; // Castling availability
1242 std::transform(f.begin(), f.end(), f.begin(),
1243 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1245 ss >> token; // En passant square
1246 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1248 std::getline(ss, token); // Half and full moves
1251 set(f, is_chess960(), st, this_thread());
1253 assert(pos_is_ok());
1257 /// Position::pos_is_ok() performs some consistency checks for the
1258 /// position object and raises an asserts if something wrong is detected.
1259 /// This is meant to be helpful when debugging.
1261 bool Position::pos_is_ok() const {
1263 constexpr bool Fast = true; // Quick (default) or full check?
1265 if ( (sideToMove != WHITE && sideToMove != BLACK)
1266 || piece_on(square<KING>(WHITE)) != W_KING
1267 || piece_on(square<KING>(BLACK)) != B_KING
1268 || ( ep_square() != SQ_NONE
1269 && relative_rank(sideToMove, ep_square()) != RANK_6))
1270 assert(0 && "pos_is_ok: Default");
1275 if ( pieceCount[W_KING] != 1
1276 || pieceCount[B_KING] != 1
1277 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1278 assert(0 && "pos_is_ok: Kings");
1280 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1281 || pieceCount[W_PAWN] > 8
1282 || pieceCount[B_PAWN] > 8)
1283 assert(0 && "pos_is_ok: Pawns");
1285 if ( (pieces(WHITE) & pieces(BLACK))
1286 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1287 || popcount(pieces(WHITE)) > 16
1288 || popcount(pieces(BLACK)) > 16)
1289 assert(0 && "pos_is_ok: Bitboards");
1291 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1292 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1293 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1294 assert(0 && "pos_is_ok: Bitboards");
1298 if (std::memcmp(&si, st, sizeof(StateInfo)))
1299 assert(0 && "pos_is_ok: State");
1301 for (Piece pc : Pieces)
1303 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1304 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1305 assert(0 && "pos_is_ok: Pieces");
1307 for (int i = 0; i < pieceCount[pc]; ++i)
1308 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1309 assert(0 && "pos_is_ok: Index");
1312 for (Color c = WHITE; c <= BLACK; ++c)
1313 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1315 if (!can_castle(c | s))
1318 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1319 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1320 || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1321 assert(0 && "pos_is_ok: Castling");