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-2017 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 const Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
56 B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING };
58 // min_attacker() is a helper function used by see_ge() to locate the least
59 // valuable attacker for the side to move, remove the attacker we just found
60 // from the bitboards and scan for new X-ray attacks behind it.
63 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
64 Bitboard& occupied, Bitboard& attackers) {
66 Bitboard b = stmAttackers & bb[Pt];
68 return min_attacker<Pt + 1>(bb, to, stmAttackers, occupied, attackers);
70 occupied ^= b & ~(b - 1);
72 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
73 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
75 if (Pt == ROOK || Pt == QUEEN)
76 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
78 attackers &= occupied; // After X-ray that may add already processed pieces
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 /// Position::init() initializes at startup the various arrays used to compute
131 void Position::init() {
135 for (Piece pc : Pieces)
136 for (Square s = SQ_A1; s <= SQ_H8; ++s)
137 Zobrist::psq[pc][s] = rng.rand<Key>();
139 for (File f = FILE_A; f <= FILE_H; ++f)
140 Zobrist::enpassant[f] = rng.rand<Key>();
142 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
144 Zobrist::castling[cr] = 0;
148 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
149 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
153 Zobrist::side = rng.rand<Key>();
154 Zobrist::noPawns = rng.rand<Key>();
158 /// Position::set() initializes the position object with the given FEN string.
159 /// This function is not very robust - make sure that input FENs are correct,
160 /// this is assumed to be the responsibility of the GUI.
162 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
164 A FEN string defines a particular position using only the ASCII character set.
166 A FEN string contains six fields separated by a space. The fields are:
168 1) Piece placement (from white's perspective). Each rank is described, starting
169 with rank 8 and ending with rank 1. Within each rank, the contents of each
170 square are described from file A through file H. Following the Standard
171 Algebraic Notation (SAN), each piece is identified by a single letter taken
172 from the standard English names. White pieces are designated using upper-case
173 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
174 noted using digits 1 through 8 (the number of blank squares), and "/"
177 2) Active color. "w" means white moves next, "b" means black.
179 3) Castling availability. If neither side can castle, this is "-". Otherwise,
180 this has one or more letters: "K" (White can castle kingside), "Q" (White
181 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
182 can castle queenside).
184 4) En passant target square (in algebraic notation). If there's no en passant
185 target square, this is "-". If a pawn has just made a 2-square move, this
186 is the position "behind" the pawn. This is recorded only if there is a pawn
187 in position to make an en passant capture, and if there really is a pawn
188 that might have advanced two squares.
190 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
191 or capture. This is used to determine if a draw can be claimed under the
194 6) Fullmove number. The number of the full move. It starts at 1, and is
195 incremented after Black's move.
198 unsigned char col, row, token;
201 std::istringstream ss(fenStr);
203 std::memset(this, 0, sizeof(Position));
204 std::memset(si, 0, sizeof(StateInfo));
205 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
210 // 1. Piece placement
211 while ((ss >> token) && !isspace(token))
214 sq += Square(token - '0'); // Advance the given number of files
216 else if (token == '/')
219 else if ((idx = PieceToChar.find(token)) != string::npos)
221 put_piece(Piece(idx), sq);
228 sideToMove = (token == 'w' ? WHITE : BLACK);
231 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
232 // Shredder-FEN that uses the letters of the columns on which the rooks began
233 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
234 // if an inner rook is associated with the castling right, the castling tag is
235 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
236 while ((ss >> token) && !isspace(token))
239 Color c = islower(token) ? BLACK : WHITE;
240 Piece rook = make_piece(c, ROOK);
242 token = char(toupper(token));
245 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
247 else if (token == 'Q')
248 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
250 else if (token >= 'A' && token <= 'H')
251 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
256 set_castling_right(c, rsq);
259 // 4. En passant square. Ignore if no pawn capture is possible
260 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
261 && ((ss >> row) && (row == '3' || row == '6')))
263 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
265 if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
266 || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
267 st->epSquare = SQ_NONE;
270 st->epSquare = SQ_NONE;
272 // 5-6. Halfmove clock and fullmove number
273 ss >> std::skipws >> st->rule50 >> gamePly;
275 // Convert from fullmove starting from 1 to ply starting from 0,
276 // handle also common incorrect FEN with fullmove = 0.
277 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
279 chess960 = isChess960;
289 /// Position::set_castling_right() is a helper function used to set castling
290 /// rights given the corresponding color and the rook starting square.
292 void Position::set_castling_right(Color c, Square rfrom) {
294 Square kfrom = square<KING>(c);
295 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
296 CastlingRight cr = (c | cs);
298 st->castlingRights |= cr;
299 castlingRightsMask[kfrom] |= cr;
300 castlingRightsMask[rfrom] |= cr;
301 castlingRookSquare[cr] = rfrom;
303 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
304 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
306 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
307 if (s != kfrom && s != rfrom)
308 castlingPath[cr] |= s;
310 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
311 if (s != kfrom && s != rfrom)
312 castlingPath[cr] |= s;
316 /// Position::set_check_info() sets king attacks to detect if a move gives check
318 void Position::set_check_info(StateInfo* si) const {
320 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
321 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
323 Square ksq = square<KING>(~sideToMove);
325 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
326 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
327 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
328 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
329 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
330 si->checkSquares[KING] = 0;
334 /// Position::set_state() computes the hash keys of the position, and other
335 /// data that once computed is updated incrementally as moves are made.
336 /// The function is only used when a new position is set up, and to verify
337 /// the correctness of the StateInfo data when running in debug mode.
339 void Position::set_state(StateInfo* si) const {
341 si->key = si->materialKey = 0;
342 si->pawnKey = Zobrist::noPawns;
343 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
344 si->psq = SCORE_ZERO;
345 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
349 for (Bitboard b = pieces(); b; )
351 Square s = pop_lsb(&b);
352 Piece pc = piece_on(s);
353 si->key ^= Zobrist::psq[pc][s];
354 si->psq += PSQT::psq[pc][s];
357 if (si->epSquare != SQ_NONE)
358 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
360 if (sideToMove == BLACK)
361 si->key ^= Zobrist::side;
363 si->key ^= Zobrist::castling[si->castlingRights];
365 for (Bitboard b = pieces(PAWN); b; )
367 Square s = pop_lsb(&b);
368 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
371 for (Piece pc : Pieces)
373 if (type_of(pc) != PAWN && type_of(pc) != KING)
374 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
376 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
377 si->materialKey ^= Zobrist::psq[pc][cnt];
382 /// Position::set() is an overload to initialize the position object with
383 /// the given endgame code string like "KBPKN". It is mainly a helper to
384 /// get the material key out of an endgame code.
386 Position& Position::set(const string& code, Color c, StateInfo* si) {
388 assert(code.length() > 0 && code.length() < 8);
389 assert(code[0] == 'K');
391 string sides[] = { code.substr(code.find('K', 1)), // Weak
392 code.substr(0, code.find('K', 1)) }; // Strong
394 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
396 string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/"
397 + sides[1] + char(8 - sides[1].length() + '0') + "/8 w - - 0 10";
399 return set(fenStr, false, si, nullptr);
403 /// Position::fen() returns a FEN representation of the position. In case of
404 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
406 const string Position::fen() const {
409 std::ostringstream ss;
411 for (Rank r = RANK_8; r >= RANK_1; --r)
413 for (File f = FILE_A; f <= FILE_H; ++f)
415 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
422 ss << PieceToChar[piece_on(make_square(f, r))];
429 ss << (sideToMove == WHITE ? " w " : " b ");
431 if (can_castle(WHITE_OO))
432 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
434 if (can_castle(WHITE_OOO))
435 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
437 if (can_castle(BLACK_OO))
438 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
440 if (can_castle(BLACK_OOO))
441 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
443 if (!can_castle(WHITE) && !can_castle(BLACK))
446 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
447 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
453 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
454 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
455 /// slider if removing that piece from the board would result in a position where
456 /// square 's' is attacked. For example, a king-attack blocking piece can be either
457 /// a pinned or a discovered check piece, according if its color is the opposite
458 /// or the same of the color of the slider.
460 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
465 // Snipers are sliders that attack 's' when a piece is removed
466 Bitboard snipers = ( (PseudoAttacks[ ROOK][s] & pieces(QUEEN, ROOK))
467 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
471 Square sniperSq = pop_lsb(&snipers);
472 Bitboard b = between_bb(s, sniperSq) & pieces();
474 if (!more_than_one(b))
477 if (b & pieces(color_of(piece_on(s))))
485 /// Position::attackers_to() computes a bitboard of all pieces which attack a
486 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
488 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
490 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
491 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
492 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
493 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
494 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
495 | (attacks_from<KING>(s) & pieces(KING));
499 /// Position::legal() tests whether a pseudo-legal move is legal
501 bool Position::legal(Move m) const {
505 Color us = sideToMove;
506 Square from = from_sq(m);
508 assert(color_of(moved_piece(m)) == us);
509 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
511 // En passant captures are a tricky special case. Because they are rather
512 // uncommon, we do it simply by testing whether the king is attacked after
514 if (type_of(m) == ENPASSANT)
516 Square ksq = square<KING>(us);
517 Square to = to_sq(m);
518 Square capsq = to - pawn_push(us);
519 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
521 assert(to == ep_square());
522 assert(moved_piece(m) == make_piece(us, PAWN));
523 assert(piece_on(capsq) == make_piece(~us, PAWN));
524 assert(piece_on(to) == NO_PIECE);
526 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
527 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
530 // If the moving piece is a king, check whether the destination
531 // square is attacked by the opponent. Castling moves are checked
532 // for legality during move generation.
533 if (type_of(piece_on(from)) == KING)
534 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
536 // A non-king move is legal if and only if it is not pinned or it
537 // is moving along the ray towards or away from the king.
538 return !(pinned_pieces(us) & from)
539 || aligned(from, to_sq(m), square<KING>(us));
543 /// Position::pseudo_legal() takes a random move and tests whether the move is
544 /// pseudo legal. It is used to validate moves from TT that can be corrupted
545 /// due to SMP concurrent access or hash position key aliasing.
547 bool Position::pseudo_legal(const Move m) const {
549 Color us = sideToMove;
550 Square from = from_sq(m);
551 Square to = to_sq(m);
552 Piece pc = moved_piece(m);
554 // Use a slower but simpler function for uncommon cases
555 if (type_of(m) != NORMAL)
556 return MoveList<LEGAL>(*this).contains(m);
558 // Is not a promotion, so promotion piece must be empty
559 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
562 // If the 'from' square is not occupied by a piece belonging to the side to
563 // move, the move is obviously not legal.
564 if (pc == NO_PIECE || color_of(pc) != us)
567 // The destination square cannot be occupied by a friendly piece
571 // Handle the special case of a pawn move
572 if (type_of(pc) == PAWN)
574 // We have already handled promotion moves, so destination
575 // cannot be on the 8th/1st rank.
576 if (rank_of(to) == relative_rank(us, RANK_8))
579 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
580 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
581 && !( (from + 2 * pawn_push(us) == to) // Not a double push
582 && (rank_of(from) == relative_rank(us, RANK_2))
584 && empty(to - pawn_push(us))))
587 else if (!(attacks_from(type_of(pc), from) & to))
590 // Evasions generator already takes care to avoid some kind of illegal moves
591 // and legal() relies on this. We therefore have to take care that the same
592 // kind of moves are filtered out here.
595 if (type_of(pc) != KING)
597 // Double check? In this case a king move is required
598 if (more_than_one(checkers()))
601 // Our move must be a blocking evasion or a capture of the checking piece
602 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
605 // In case of king moves under check we have to remove king so as to catch
606 // invalid moves like b1a1 when opposite queen is on c1.
607 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
615 /// Position::gives_check() tests whether a pseudo-legal move gives a check
617 bool Position::gives_check(Move m) const {
620 assert(color_of(moved_piece(m)) == sideToMove);
622 Square from = from_sq(m);
623 Square to = to_sq(m);
625 // Is there a direct check?
626 if (st->checkSquares[type_of(piece_on(from))] & to)
629 // Is there a discovered check?
630 if ( (discovered_check_candidates() & from)
631 && !aligned(from, to, square<KING>(~sideToMove)))
640 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
642 // En passant capture with check? We have already handled the case
643 // of direct checks and ordinary discovered check, so the only case we
644 // need to handle is the unusual case of a discovered check through
645 // the captured pawn.
648 Square capsq = make_square(file_of(to), rank_of(from));
649 Bitboard b = (pieces() ^ from ^ capsq) | to;
651 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
652 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
657 Square rfrom = to; // Castling is encoded as 'King captures the rook'
658 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
659 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
661 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
662 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
671 /// Position::do_move() makes a move, and saves all information necessary
672 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
673 /// moves should be filtered out before this function is called.
675 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
678 assert(&newSt != st);
680 thisThread->nodes.fetch_add(1, std::memory_order_relaxed);
681 Key k = st->key ^ Zobrist::side;
683 // Copy some fields of the old state to our new StateInfo object except the
684 // ones which are going to be recalculated from scratch anyway and then switch
685 // our state pointer to point to the new (ready to be updated) state.
686 std::memcpy(&newSt, st, offsetof(StateInfo, key));
690 // Increment ply counters. In particular, rule50 will be reset to zero later on
691 // in case of a capture or a pawn move.
696 Color us = sideToMove;
698 Square from = from_sq(m);
699 Square to = to_sq(m);
700 Piece pc = piece_on(from);
701 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
703 assert(color_of(pc) == us);
704 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
705 assert(type_of(captured) != KING);
707 if (type_of(m) == CASTLING)
709 assert(pc == make_piece(us, KING));
710 assert(captured == make_piece(us, ROOK));
713 do_castling<true>(us, from, to, rfrom, rto);
715 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
716 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
724 // If the captured piece is a pawn, update pawn hash key, otherwise
725 // update non-pawn material.
726 if (type_of(captured) == PAWN)
728 if (type_of(m) == ENPASSANT)
730 capsq -= pawn_push(us);
732 assert(pc == make_piece(us, PAWN));
733 assert(to == st->epSquare);
734 assert(relative_rank(us, to) == RANK_6);
735 assert(piece_on(to) == NO_PIECE);
736 assert(piece_on(capsq) == make_piece(them, PAWN));
738 board[capsq] = NO_PIECE; // Not done by remove_piece()
741 st->pawnKey ^= Zobrist::psq[captured][capsq];
744 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
746 // Update board and piece lists
747 remove_piece(captured, capsq);
749 // Update material hash key and prefetch access to materialTable
750 k ^= Zobrist::psq[captured][capsq];
751 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
752 prefetch(thisThread->materialTable[st->materialKey]);
754 // Update incremental scores
755 st->psq -= PSQT::psq[captured][capsq];
757 // Reset rule 50 counter
762 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
764 // Reset en passant square
765 if (st->epSquare != SQ_NONE)
767 k ^= Zobrist::enpassant[file_of(st->epSquare)];
768 st->epSquare = SQ_NONE;
771 // Update castling rights if needed
772 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
774 int cr = castlingRightsMask[from] | castlingRightsMask[to];
775 k ^= Zobrist::castling[st->castlingRights & cr];
776 st->castlingRights &= ~cr;
779 // Move the piece. The tricky Chess960 castling is handled earlier
780 if (type_of(m) != CASTLING)
781 move_piece(pc, from, to);
783 // If the moving piece is a pawn do some special extra work
784 if (type_of(pc) == PAWN)
786 // Set en-passant square if the moved pawn can be captured
787 if ( (int(to) ^ int(from)) == 16
788 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
790 st->epSquare = (from + to) / 2;
791 k ^= Zobrist::enpassant[file_of(st->epSquare)];
794 else if (type_of(m) == PROMOTION)
796 Piece promotion = make_piece(us, promotion_type(m));
798 assert(relative_rank(us, to) == RANK_8);
799 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
801 remove_piece(pc, to);
802 put_piece(promotion, to);
805 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
806 st->pawnKey ^= Zobrist::psq[pc][to];
807 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
808 ^ Zobrist::psq[pc][pieceCount[pc]];
810 // Update incremental score
811 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
814 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
817 // Update pawn hash key and prefetch access to pawnsTable
818 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
819 prefetch2(thisThread->pawnsTable[st->pawnKey]);
821 // Reset rule 50 draw counter
825 // Update incremental scores
826 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
829 st->capturedPiece = captured;
831 // Update the key with the final value
834 // Calculate checkers bitboard (if move gives check)
835 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
837 sideToMove = ~sideToMove;
839 // Update king attacks used for fast check detection
846 /// Position::undo_move() unmakes a move. When it returns, the position should
847 /// be restored to exactly the same state as before the move was made.
849 void Position::undo_move(Move m) {
853 sideToMove = ~sideToMove;
855 Color us = sideToMove;
856 Square from = from_sq(m);
857 Square to = to_sq(m);
858 Piece pc = piece_on(to);
860 assert(empty(from) || type_of(m) == CASTLING);
861 assert(type_of(st->capturedPiece) != KING);
863 if (type_of(m) == PROMOTION)
865 assert(relative_rank(us, to) == RANK_8);
866 assert(type_of(pc) == promotion_type(m));
867 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
869 remove_piece(pc, to);
870 pc = make_piece(us, PAWN);
874 if (type_of(m) == CASTLING)
877 do_castling<false>(us, from, to, rfrom, rto);
881 move_piece(pc, to, from); // Put the piece back at the source square
883 if (st->capturedPiece)
887 if (type_of(m) == ENPASSANT)
889 capsq -= pawn_push(us);
891 assert(type_of(pc) == PAWN);
892 assert(to == st->previous->epSquare);
893 assert(relative_rank(us, to) == RANK_6);
894 assert(piece_on(capsq) == NO_PIECE);
895 assert(st->capturedPiece == make_piece(~us, PAWN));
898 put_piece(st->capturedPiece, capsq); // Restore the captured piece
902 // Finally point our state pointer back to the previous state
910 /// Position::do_castling() is a helper used to do/undo a castling move. This
911 /// is a bit tricky in Chess960 where from/to squares can overlap.
913 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
915 bool kingSide = to > from;
916 rfrom = to; // Castling is encoded as "king captures friendly rook"
917 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
918 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
920 // Remove both pieces first since squares could overlap in Chess960
921 remove_piece(make_piece(us, KING), Do ? from : to);
922 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
923 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
924 put_piece(make_piece(us, KING), Do ? to : from);
925 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
929 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
930 /// the side to move without executing any move on the board.
932 void Position::do_null_move(StateInfo& newSt) {
935 assert(&newSt != st);
937 std::memcpy(&newSt, st, sizeof(StateInfo));
941 if (st->epSquare != SQ_NONE)
943 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
944 st->epSquare = SQ_NONE;
947 st->key ^= Zobrist::side;
948 prefetch(TT.first_entry(st->key));
951 st->pliesFromNull = 0;
953 sideToMove = ~sideToMove;
960 void Position::undo_null_move() {
965 sideToMove = ~sideToMove;
969 /// Position::key_after() computes the new hash key after the given move. Needed
970 /// for speculative prefetch. It doesn't recognize special moves like castling,
971 /// en-passant and promotions.
973 Key Position::key_after(Move m) const {
975 Square from = from_sq(m);
976 Square to = to_sq(m);
977 Piece pc = piece_on(from);
978 Piece captured = piece_on(to);
979 Key k = st->key ^ Zobrist::side;
982 k ^= Zobrist::psq[captured][to];
984 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
988 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
989 /// SEE value of move is greater or equal to the given threshold. We'll use an
990 /// algorithm similar to alpha-beta pruning with a null window.
992 bool Position::see_ge(Move m, Value threshold) const {
996 // Castling moves are implemented as king capturing the rook so cannot be
997 // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
998 // correct unless in the rare case the rook ends up under attack.
999 if (type_of(m) == CASTLING)
1000 return VALUE_ZERO >= threshold;
1002 Square from = from_sq(m), to = to_sq(m);
1003 PieceType nextVictim = type_of(piece_on(from));
1004 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1005 Value balance; // Values of the pieces taken by us minus opponent's ones
1006 Bitboard occupied, stmAttackers;
1008 if (type_of(m) == ENPASSANT)
1010 occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1011 balance = PieceValue[MG][PAWN];
1015 balance = PieceValue[MG][piece_on(to)];
1019 if (balance < threshold)
1022 if (nextVictim == KING)
1025 balance -= PieceValue[MG][nextVictim];
1027 if (balance >= threshold)
1030 bool relativeStm = true; // True if the opponent is to move
1031 occupied ^= pieces() ^ from ^ to;
1033 // Find all attackers to the destination square, with the moving piece removed,
1034 // but possibly an X-ray attacker added behind it.
1035 Bitboard attackers = attackers_to(to, occupied) & occupied;
1039 stmAttackers = attackers & pieces(stm);
1041 // Don't allow pinned pieces to attack pieces except the king as long all
1042 // pinners are on their original square.
1043 if (!(st->pinnersForKing[stm] & ~occupied))
1044 stmAttackers &= ~st->blockersForKing[stm];
1049 // Locate and remove the next least valuable attacker
1050 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1052 if (nextVictim == KING)
1053 return relativeStm == bool(attackers & pieces(~stm));
1055 balance += relativeStm ? PieceValue[MG][nextVictim]
1056 : -PieceValue[MG][nextVictim];
1058 relativeStm = !relativeStm;
1060 if (relativeStm == (balance >= threshold))
1068 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1069 /// or by repetition. It does not detect stalemates.
1071 bool Position::is_draw(int ply) const {
1073 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1076 int end = std::min(st->rule50, st->pliesFromNull);
1081 StateInfo* stp = st->previous->previous;
1084 for (int i = 4; i <= end; i += 2)
1086 stp = stp->previous->previous;
1088 // At root position ply is 1, so return a draw score if a position
1089 // repeats once earlier but strictly after the root, or repeats twice
1090 // before or at the root.
1091 if ( stp->key == st->key
1092 && ++cnt + (ply - 1 > i) == 2)
1100 /// Position::flip() flips position with the white and black sides reversed. This
1101 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1103 void Position::flip() {
1106 std::stringstream ss(fen());
1108 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1110 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1111 f.insert(0, token + (f.empty() ? " " : "/"));
1114 ss >> token; // Active color
1115 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1117 ss >> token; // Castling availability
1120 std::transform(f.begin(), f.end(), f.begin(),
1121 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1123 ss >> token; // En passant square
1124 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1126 std::getline(ss, token); // Half and full moves
1129 set(f, is_chess960(), st, this_thread());
1131 assert(pos_is_ok());
1135 /// Position::pos_is_ok() performs some consistency checks for the
1136 /// position object and raises an asserts if something wrong is detected.
1137 /// This is meant to be helpful when debugging.
1139 bool Position::pos_is_ok() const {
1141 const bool Fast = true; // Quick (default) or full check?
1143 if ( (sideToMove != WHITE && sideToMove != BLACK)
1144 || piece_on(square<KING>(WHITE)) != W_KING
1145 || piece_on(square<KING>(BLACK)) != B_KING
1146 || ( ep_square() != SQ_NONE
1147 && relative_rank(sideToMove, ep_square()) != RANK_6))
1148 assert(0 && "pos_is_ok: Default");
1153 if ( pieceCount[W_KING] != 1
1154 || pieceCount[B_KING] != 1
1155 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1156 assert(0 && "pos_is_ok: Kings");
1158 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1159 || pieceCount[W_PAWN] > 8
1160 || pieceCount[B_PAWN] > 8)
1161 assert(0 && "pos_is_ok: Pawns");
1163 if ( (pieces(WHITE) & pieces(BLACK))
1164 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1165 || popcount(pieces(WHITE)) > 16
1166 || popcount(pieces(BLACK)) > 16)
1167 assert(0 && "pos_is_ok: Bitboards");
1169 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1170 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1171 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1172 assert(0 && "pos_is_ok: Bitboards");
1176 if (std::memcmp(&si, st, sizeof(StateInfo)))
1177 assert(0 && "pos_is_ok: State");
1179 for (Piece pc : Pieces)
1181 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1182 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1183 assert(0 && "pos_is_ok: Pieces");
1185 for (int i = 0; i < pieceCount[pc]; ++i)
1186 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1187 assert(0 && "pos_is_ok: Index");
1190 for (Color c = WHITE; c <= BLACK; ++c)
1191 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1193 if (!can_castle(c | s))
1196 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1197 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1198 || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1199 assert(0 && "pos_is_ok: Castling");