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-2016 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"
40 extern Score psq[PIECE_NB][SQUARE_NB];
45 Key psq[PIECE_NB][SQUARE_NB];
46 Key enpassant[FILE_NB];
47 Key castling[CASTLING_RIGHT_NB];
53 const string PieceToChar(" PNBRQK pnbrqk");
55 // min_attacker() is a helper function used by see_ge() to locate the least
56 // valuable attacker for the side to move, remove the attacker we just found
57 // from the bitboards and scan for new X-ray attacks behind it.
60 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
61 Bitboard& occupied, Bitboard& attackers) {
63 Bitboard b = stmAttackers & bb[Pt];
65 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
67 occupied ^= b & ~(b - 1);
69 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
70 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
72 if (Pt == ROOK || Pt == QUEEN)
73 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
75 attackers &= occupied; // After X-ray that may add already processed pieces
80 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
81 return KING; // No need to update bitboards: it is the last cycle
87 /// operator<<(Position) returns an ASCII representation of the position
89 std::ostream& operator<<(std::ostream& os, Position& pos) {
91 os << "\n +---+---+---+---+---+---+---+---+\n";
93 for (Rank r = RANK_8; r >= RANK_1; --r)
95 for (File f = FILE_A; f <= FILE_H; ++f)
96 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
98 os << " |\n +---+---+---+---+---+---+---+---+\n";
101 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
102 << std::setfill('0') << std::setw(16) << pos.key()
103 << std::setfill(' ') << std::dec << "\nCheckers: ";
105 for (Bitboard b = pos.checkers(); b; )
106 os << UCI::square(pop_lsb(&b)) << " ";
108 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
109 && !pos.can_castle(ANY_CASTLING))
111 Tablebases::ProbeState s1, s2;
112 Tablebases::WDLScore wdl = Tablebases::probe_wdl(pos, &s1);
113 int dtz = Tablebases::probe_dtz(pos, &s2);
114 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
115 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
122 /// Position::init() initializes at startup the various arrays used to compute
125 void Position::init() {
129 for (Piece pc : Pieces)
130 for (Square s = SQ_A1; s <= SQ_H8; ++s)
131 Zobrist::psq[pc][s] = rng.rand<Key>();
133 for (File f = FILE_A; f <= FILE_H; ++f)
134 Zobrist::enpassant[f] = rng.rand<Key>();
136 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
138 Zobrist::castling[cr] = 0;
142 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
143 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
147 Zobrist::side = rng.rand<Key>();
148 Zobrist::noPawns = rng.rand<Key>();
152 /// Position::set() initializes the position object with the given FEN string.
153 /// This function is not very robust - make sure that input FENs are correct,
154 /// this is assumed to be the responsibility of the GUI.
156 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
158 A FEN string defines a particular position using only the ASCII character set.
160 A FEN string contains six fields separated by a space. The fields are:
162 1) Piece placement (from white's perspective). Each rank is described, starting
163 with rank 8 and ending with rank 1. Within each rank, the contents of each
164 square are described from file A through file H. Following the Standard
165 Algebraic Notation (SAN), each piece is identified by a single letter taken
166 from the standard English names. White pieces are designated using upper-case
167 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
168 noted using digits 1 through 8 (the number of blank squares), and "/"
171 2) Active color. "w" means white moves next, "b" means black.
173 3) Castling availability. If neither side can castle, this is "-". Otherwise,
174 this has one or more letters: "K" (White can castle kingside), "Q" (White
175 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
176 can castle queenside).
178 4) En passant target square (in algebraic notation). If there's no en passant
179 target square, this is "-". If a pawn has just made a 2-square move, this
180 is the position "behind" the pawn. This is recorded only if there is a pawn
181 in position to make an en passant capture, and if there really is a pawn
182 that might have advanced two squares.
184 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
185 or capture. This is used to determine if a draw can be claimed under the
188 6) Fullmove number. The number of the full move. It starts at 1, and is
189 incremented after Black's move.
192 unsigned char col, row, token;
195 std::istringstream ss(fenStr);
197 std::memset(this, 0, sizeof(Position));
198 std::memset(si, 0, sizeof(StateInfo));
199 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
204 // 1. Piece placement
205 while ((ss >> token) && !isspace(token))
208 sq += Square(token - '0'); // Advance the given number of files
210 else if (token == '/')
213 else if ((idx = PieceToChar.find(token)) != string::npos)
215 put_piece(Piece(idx), sq);
222 sideToMove = (token == 'w' ? WHITE : BLACK);
225 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
226 // Shredder-FEN that uses the letters of the columns on which the rooks began
227 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
228 // if an inner rook is associated with the castling right, the castling tag is
229 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
230 while ((ss >> token) && !isspace(token))
233 Color c = islower(token) ? BLACK : WHITE;
234 Piece rook = make_piece(c, ROOK);
236 token = char(toupper(token));
239 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
241 else if (token == 'Q')
242 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
244 else if (token >= 'A' && token <= 'H')
245 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
250 set_castling_right(c, rsq);
253 // 4. En passant square. Ignore if no pawn capture is possible
254 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
255 && ((ss >> row) && (row == '3' || row == '6')))
257 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
259 if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
260 || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
261 st->epSquare = SQ_NONE;
264 st->epSquare = SQ_NONE;
266 // 5-6. Halfmove clock and fullmove number
267 ss >> std::skipws >> st->rule50 >> gamePly;
269 // Convert from fullmove starting from 1 to ply starting from 0,
270 // handle also common incorrect FEN with fullmove = 0.
271 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
273 chess960 = isChess960;
283 /// Position::set_castling_right() is a helper function used to set castling
284 /// rights given the corresponding color and the rook starting square.
286 void Position::set_castling_right(Color c, Square rfrom) {
288 Square kfrom = square<KING>(c);
289 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
290 CastlingRight cr = (c | cs);
292 st->castlingRights |= cr;
293 castlingRightsMask[kfrom] |= cr;
294 castlingRightsMask[rfrom] |= cr;
295 castlingRookSquare[cr] = rfrom;
297 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
298 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
300 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
301 if (s != kfrom && s != rfrom)
302 castlingPath[cr] |= s;
304 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
305 if (s != kfrom && s != rfrom)
306 castlingPath[cr] |= s;
310 /// Position::set_check_info() sets king attacks to detect if a move gives check
312 void Position::set_check_info(StateInfo* si) const {
314 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
315 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
317 Square ksq = square<KING>(~sideToMove);
319 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
320 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
321 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
322 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
323 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
324 si->checkSquares[KING] = 0;
328 /// Position::set_state() computes the hash keys of the position, and other
329 /// data that once computed is updated incrementally as moves are made.
330 /// The function is only used when a new position is set up, and to verify
331 /// the correctness of the StateInfo data when running in debug mode.
333 void Position::set_state(StateInfo* si) const {
335 si->key = si->materialKey = 0;
336 si->pawnKey = Zobrist::noPawns;
337 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
338 si->psq = SCORE_ZERO;
339 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
343 for (Bitboard b = pieces(); b; )
345 Square s = pop_lsb(&b);
346 Piece pc = piece_on(s);
347 si->key ^= Zobrist::psq[pc][s];
348 si->psq += PSQT::psq[pc][s];
351 if (si->epSquare != SQ_NONE)
352 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
354 if (sideToMove == BLACK)
355 si->key ^= Zobrist::side;
357 si->key ^= Zobrist::castling[si->castlingRights];
359 for (Bitboard b = pieces(PAWN); b; )
361 Square s = pop_lsb(&b);
362 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
365 for (Piece pc : Pieces)
367 if (type_of(pc) != PAWN && type_of(pc) != KING)
368 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
370 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
371 si->materialKey ^= Zobrist::psq[pc][cnt];
376 /// Position::set() is an overload to initialize the position object with
377 /// the given endgame code string like "KBPKN". It is manily an helper to
378 /// get the material key out of an endgame code. Position is not playable,
379 /// indeed is even not guaranteed to be legal.
381 Position& Position::set(const string& code, Color c, StateInfo* si) {
383 assert(code.length() > 0 && code.length() < 8);
384 assert(code[0] == 'K');
386 string sides[] = { code.substr(code.find('K', 1)), // Weak
387 code.substr(0, code.find('K', 1)) }; // Strong
389 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
391 string fenStr = sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/8/8/"
392 + sides[1] + char(8 - sides[1].length() + '0') + " w - - 0 10";
394 return set(fenStr, false, si, nullptr);
398 /// Position::fen() returns a FEN representation of the position. In case of
399 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
401 const string Position::fen() const {
404 std::ostringstream ss;
406 for (Rank r = RANK_8; r >= RANK_1; --r)
408 for (File f = FILE_A; f <= FILE_H; ++f)
410 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
417 ss << PieceToChar[piece_on(make_square(f, r))];
424 ss << (sideToMove == WHITE ? " w " : " b ");
426 if (can_castle(WHITE_OO))
427 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
429 if (can_castle(WHITE_OOO))
430 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
432 if (can_castle(BLACK_OO))
433 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
435 if (can_castle(BLACK_OOO))
436 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
438 if (!can_castle(WHITE) && !can_castle(BLACK))
441 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
442 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
448 /// Position::game_phase() calculates the game phase interpolating total non-pawn
449 /// material between endgame and midgame limits.
451 Phase Position::game_phase() const {
453 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
455 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
457 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
461 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
462 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
463 /// slider if removing that piece from the board would result in a position where
464 /// square 's' is attacked. For example, a king-attack blocking piece can be either
465 /// a pinned or a discovered check piece, according if its color is the opposite
466 /// or the same of the color of the slider.
468 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
473 // Snipers are sliders that attack 's' when a piece is removed
474 Bitboard snipers = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
475 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
479 Square sniperSq = pop_lsb(&snipers);
480 Bitboard b = between_bb(s, sniperSq) & pieces();
482 if (!more_than_one(b))
485 if (b & pieces(color_of(piece_on(s))))
493 /// Position::attackers_to() computes a bitboard of all pieces which attack a
494 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
496 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
498 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
499 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
500 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
501 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
502 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
503 | (attacks_from<KING>(s) & pieces(KING));
507 /// Position::legal() tests whether a pseudo-legal move is legal
509 bool Position::legal(Move m) const {
513 Color us = sideToMove;
514 Square from = from_sq(m);
516 assert(color_of(moved_piece(m)) == us);
517 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
519 // En passant captures are a tricky special case. Because they are rather
520 // uncommon, we do it simply by testing whether the king is attacked after
522 if (type_of(m) == ENPASSANT)
524 Square ksq = square<KING>(us);
525 Square to = to_sq(m);
526 Square capsq = to - pawn_push(us);
527 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
529 assert(to == ep_square());
530 assert(moved_piece(m) == make_piece(us, PAWN));
531 assert(piece_on(capsq) == make_piece(~us, PAWN));
532 assert(piece_on(to) == NO_PIECE);
534 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
535 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
538 // If the moving piece is a king, check whether the destination
539 // square is attacked by the opponent. Castling moves are checked
540 // for legality during move generation.
541 if (type_of(piece_on(from)) == KING)
542 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
544 // A non-king move is legal if and only if it is not pinned or it
545 // is moving along the ray towards or away from the king.
546 return !(pinned_pieces(us) & from)
547 || aligned(from, to_sq(m), square<KING>(us));
551 /// Position::pseudo_legal() takes a random move and tests whether the move is
552 /// pseudo legal. It is used to validate moves from TT that can be corrupted
553 /// due to SMP concurrent access or hash position key aliasing.
555 bool Position::pseudo_legal(const Move m) const {
557 Color us = sideToMove;
558 Square from = from_sq(m);
559 Square to = to_sq(m);
560 Piece pc = moved_piece(m);
562 // Use a slower but simpler function for uncommon cases
563 if (type_of(m) != NORMAL)
564 return MoveList<LEGAL>(*this).contains(m);
566 // Is not a promotion, so promotion piece must be empty
567 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
570 // If the 'from' square is not occupied by a piece belonging to the side to
571 // move, the move is obviously not legal.
572 if (pc == NO_PIECE || color_of(pc) != us)
575 // The destination square cannot be occupied by a friendly piece
579 // Handle the special case of a pawn move
580 if (type_of(pc) == PAWN)
582 // We have already handled promotion moves, so destination
583 // cannot be on the 8th/1st rank.
584 if (rank_of(to) == relative_rank(us, RANK_8))
587 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
588 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
589 && !( (from + 2 * pawn_push(us) == to) // Not a double push
590 && (rank_of(from) == relative_rank(us, RANK_2))
592 && empty(to - pawn_push(us))))
595 else if (!(attacks_from(pc, from) & to))
598 // Evasions generator already takes care to avoid some kind of illegal moves
599 // and legal() relies on this. We therefore have to take care that the same
600 // kind of moves are filtered out here.
603 if (type_of(pc) != KING)
605 // Double check? In this case a king move is required
606 if (more_than_one(checkers()))
609 // Our move must be a blocking evasion or a capture of the checking piece
610 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
613 // In case of king moves under check we have to remove king so as to catch
614 // invalid moves like b1a1 when opposite queen is on c1.
615 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
623 /// Position::gives_check() tests whether a pseudo-legal move gives a check
625 bool Position::gives_check(Move m) const {
628 assert(color_of(moved_piece(m)) == sideToMove);
630 Square from = from_sq(m);
631 Square to = to_sq(m);
633 // Is there a direct check?
634 if (st->checkSquares[type_of(piece_on(from))] & to)
637 // Is there a discovered check?
638 if ( (discovered_check_candidates() & from)
639 && !aligned(from, to, square<KING>(~sideToMove)))
648 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
650 // En passant capture with check? We have already handled the case
651 // of direct checks and ordinary discovered check, so the only case we
652 // need to handle is the unusual case of a discovered check through
653 // the captured pawn.
656 Square capsq = make_square(file_of(to), rank_of(from));
657 Bitboard b = (pieces() ^ from ^ capsq) | to;
659 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
660 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
665 Square rfrom = to; // Castling is encoded as 'King captures the rook'
666 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
667 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
669 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
670 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
679 /// Position::do_move() makes a move, and saves all information necessary
680 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
681 /// moves should be filtered out before this function is called.
683 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
686 assert(&newSt != st);
689 Key k = st->key ^ Zobrist::side;
691 // Copy some fields of the old state to our new StateInfo object except the
692 // ones which are going to be recalculated from scratch anyway and then switch
693 // our state pointer to point to the new (ready to be updated) state.
694 std::memcpy(&newSt, st, offsetof(StateInfo, key));
698 // Increment ply counters. In particular, rule50 will be reset to zero later on
699 // in case of a capture or a pawn move.
704 Color us = sideToMove;
706 Square from = from_sq(m);
707 Square to = to_sq(m);
708 Piece pc = piece_on(from);
709 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
711 assert(color_of(pc) == us);
712 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
713 assert(type_of(captured) != KING);
715 if (type_of(m) == CASTLING)
717 assert(pc == make_piece(us, KING));
718 assert(captured == make_piece(us, ROOK));
721 do_castling<true>(us, from, to, rfrom, rto);
723 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
724 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
732 // If the captured piece is a pawn, update pawn hash key, otherwise
733 // update non-pawn material.
734 if (type_of(captured) == PAWN)
736 if (type_of(m) == ENPASSANT)
738 capsq -= pawn_push(us);
740 assert(pc == make_piece(us, PAWN));
741 assert(to == st->epSquare);
742 assert(relative_rank(us, to) == RANK_6);
743 assert(piece_on(to) == NO_PIECE);
744 assert(piece_on(capsq) == make_piece(them, PAWN));
746 board[capsq] = NO_PIECE; // Not done by remove_piece()
749 st->pawnKey ^= Zobrist::psq[captured][capsq];
752 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
754 // Update board and piece lists
755 remove_piece(captured, capsq);
757 // Update material hash key and prefetch access to materialTable
758 k ^= Zobrist::psq[captured][capsq];
759 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
760 prefetch(thisThread->materialTable[st->materialKey]);
762 // Update incremental scores
763 st->psq -= PSQT::psq[captured][capsq];
765 // Reset rule 50 counter
770 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
772 // Reset en passant square
773 if (st->epSquare != SQ_NONE)
775 k ^= Zobrist::enpassant[file_of(st->epSquare)];
776 st->epSquare = SQ_NONE;
779 // Update castling rights if needed
780 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
782 int cr = castlingRightsMask[from] | castlingRightsMask[to];
783 k ^= Zobrist::castling[st->castlingRights & cr];
784 st->castlingRights &= ~cr;
787 // Move the piece. The tricky Chess960 castling is handled earlier
788 if (type_of(m) != CASTLING)
789 move_piece(pc, from, to);
791 // If the moving piece is a pawn do some special extra work
792 if (type_of(pc) == PAWN)
794 // Set en-passant square if the moved pawn can be captured
795 if ( (int(to) ^ int(from)) == 16
796 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
798 st->epSquare = (from + to) / 2;
799 k ^= Zobrist::enpassant[file_of(st->epSquare)];
802 else if (type_of(m) == PROMOTION)
804 Piece promotion = make_piece(us, promotion_type(m));
806 assert(relative_rank(us, to) == RANK_8);
807 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
809 remove_piece(pc, to);
810 put_piece(promotion, to);
813 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
814 st->pawnKey ^= Zobrist::psq[pc][to];
815 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
816 ^ Zobrist::psq[pc][pieceCount[pc]];
818 // Update incremental score
819 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
822 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
825 // Update pawn hash key and prefetch access to pawnsTable
826 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
827 prefetch(thisThread->pawnsTable[st->pawnKey]);
829 // Reset rule 50 draw counter
833 // Update incremental scores
834 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
837 st->capturedPiece = captured;
839 // Update the key with the final value
842 // Calculate checkers bitboard (if move gives check)
843 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
845 sideToMove = ~sideToMove;
847 // Update king attacks used for fast check detection
854 /// Position::undo_move() unmakes a move. When it returns, the position should
855 /// be restored to exactly the same state as before the move was made.
857 void Position::undo_move(Move m) {
861 sideToMove = ~sideToMove;
863 Color us = sideToMove;
864 Square from = from_sq(m);
865 Square to = to_sq(m);
866 Piece pc = piece_on(to);
868 assert(empty(from) || type_of(m) == CASTLING);
869 assert(type_of(st->capturedPiece) != KING);
871 if (type_of(m) == PROMOTION)
873 assert(relative_rank(us, to) == RANK_8);
874 assert(type_of(pc) == promotion_type(m));
875 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
877 remove_piece(pc, to);
878 pc = make_piece(us, PAWN);
882 if (type_of(m) == CASTLING)
885 do_castling<false>(us, from, to, rfrom, rto);
889 move_piece(pc, to, from); // Put the piece back at the source square
891 if (st->capturedPiece)
895 if (type_of(m) == ENPASSANT)
897 capsq -= pawn_push(us);
899 assert(type_of(pc) == PAWN);
900 assert(to == st->previous->epSquare);
901 assert(relative_rank(us, to) == RANK_6);
902 assert(piece_on(capsq) == NO_PIECE);
903 assert(st->capturedPiece == make_piece(~us, PAWN));
906 put_piece(st->capturedPiece, capsq); // Restore the captured piece
910 // Finally point our state pointer back to the previous state
918 /// Position::do_castling() is a helper used to do/undo a castling move. This
919 /// is a bit tricky in Chess960 where from/to squares can overlap.
921 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
923 bool kingSide = to > from;
924 rfrom = to; // Castling is encoded as "king captures friendly rook"
925 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
926 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
928 // Remove both pieces first since squares could overlap in Chess960
929 remove_piece(make_piece(us, KING), Do ? from : to);
930 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
931 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
932 put_piece(make_piece(us, KING), Do ? to : from);
933 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
937 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
938 /// the side to move without executing any move on the board.
940 void Position::do_null_move(StateInfo& newSt) {
943 assert(&newSt != st);
945 std::memcpy(&newSt, st, sizeof(StateInfo));
949 if (st->epSquare != SQ_NONE)
951 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
952 st->epSquare = SQ_NONE;
955 st->key ^= Zobrist::side;
956 prefetch(TT.first_entry(st->key));
959 st->pliesFromNull = 0;
961 sideToMove = ~sideToMove;
968 void Position::undo_null_move() {
973 sideToMove = ~sideToMove;
977 /// Position::key_after() computes the new hash key after the given move. Needed
978 /// for speculative prefetch. It doesn't recognize special moves like castling,
979 /// en-passant and promotions.
981 Key Position::key_after(Move m) const {
983 Square from = from_sq(m);
984 Square to = to_sq(m);
985 Piece pc = piece_on(from);
986 Piece captured = piece_on(to);
987 Key k = st->key ^ Zobrist::side;
990 k ^= Zobrist::psq[captured][to];
992 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
996 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
997 /// SEE value of move is greater or equal to the given value. We'll use an
998 /// algorithm similar to alpha-beta pruning with a null window.
1000 bool Position::see_ge(Move m, Value v) const {
1004 // Castling moves are implemented as king capturing the rook so cannot be
1005 // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
1006 // correct unless in the rare case the rook ends up under attack.
1007 if (type_of(m) == CASTLING)
1008 return VALUE_ZERO >= v;
1010 Square from = from_sq(m), to = to_sq(m);
1011 PieceType nextVictim = type_of(piece_on(from));
1012 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1013 Value balance; // Values of the pieces taken by us minus opponent's ones
1014 Bitboard occupied, stmAttackers;
1016 if (type_of(m) == ENPASSANT)
1018 occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1019 balance = PieceValue[MG][PAWN];
1023 balance = PieceValue[MG][piece_on(to)];
1030 if (nextVictim == KING)
1033 balance -= PieceValue[MG][nextVictim];
1038 bool relativeStm = true; // True if the opponent is to move
1039 occupied ^= pieces() ^ from ^ to;
1041 // Find all attackers to the destination square, with the moving piece removed,
1042 // but possibly an X-ray attacker added behind it.
1043 Bitboard attackers = attackers_to(to, occupied) & occupied;
1047 stmAttackers = attackers & pieces(stm);
1049 // Don't allow pinned pieces to attack pieces except the king as long all
1050 // pinners are on their original square.
1051 if (!(st->pinnersForKing[stm] & ~occupied))
1052 stmAttackers &= ~st->blockersForKing[stm];
1057 // Locate and remove the next least valuable attacker
1058 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1060 if (nextVictim == KING)
1061 return relativeStm == bool(attackers & pieces(~stm));
1063 balance += relativeStm ? PieceValue[MG][nextVictim]
1064 : -PieceValue[MG][nextVictim];
1066 relativeStm = !relativeStm;
1068 if (relativeStm == (balance >= v))
1076 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1077 /// or by repetition. It does not detect stalemates.
1079 bool Position::is_draw() const {
1081 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1084 int e = std::min(st->rule50, st->pliesFromNull);
1089 StateInfo* stp = st->previous->previous;
1092 stp = stp->previous->previous;
1094 if (stp->key == st->key)
1095 return true; // Draw at first repetition
1097 } while ((e -= 2) >= 4);
1103 /// Position::flip() flips position with the white and black sides reversed. This
1104 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1106 void Position::flip() {
1109 std::stringstream ss(fen());
1111 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1113 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1114 f.insert(0, token + (f.empty() ? " " : "/"));
1117 ss >> token; // Active color
1118 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1120 ss >> token; // Castling availability
1123 std::transform(f.begin(), f.end(), f.begin(),
1124 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1126 ss >> token; // En passant square
1127 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1129 std::getline(ss, token); // Half and full moves
1132 set(f, is_chess960(), st, this_thread());
1134 assert(pos_is_ok());
1138 /// Position::pos_is_ok() performs some consistency checks for the position object.
1139 /// This is meant to be helpful when debugging.
1141 bool Position::pos_is_ok(int* failedStep) const {
1143 const bool Fast = true; // Quick (default) or full check?
1145 enum { Default, King, Bitboards, State, Lists, Castling };
1147 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1152 if (step == Default)
1153 if ( (sideToMove != WHITE && sideToMove != BLACK)
1154 || piece_on(square<KING>(WHITE)) != W_KING
1155 || piece_on(square<KING>(BLACK)) != B_KING
1156 || ( ep_square() != SQ_NONE
1157 && relative_rank(sideToMove, ep_square()) != RANK_6))
1161 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1162 || std::count(board, board + SQUARE_NB, B_KING) != 1
1163 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1166 if (step == Bitboards)
1168 if ( (pieces(WHITE) & pieces(BLACK))
1169 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1172 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1173 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1174 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1182 if (std::memcmp(&si, st, sizeof(StateInfo)))
1187 for (Piece pc : Pieces)
1189 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1192 for (int i = 0; i < pieceCount[pc]; ++i)
1193 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1197 if (step == Castling)
1198 for (Color c = WHITE; c <= BLACK; ++c)
1199 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1201 if (!can_castle(c | s))
1204 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1205 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1206 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))