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 gamePly 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 // Only deal with normal moves, assume others pass a simple see
997 if (type_of(m) != NORMAL)
998 return VALUE_ZERO >= threshold;
1000 Square from = from_sq(m), to = to_sq(m);
1001 PieceType nextVictim = type_of(piece_on(from));
1002 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1003 Value balance; // Values of the pieces taken by us minus opponent's ones
1004 Bitboard occupied, stmAttackers;
1006 // The opponent may be able to recapture so this is the best result
1008 balance = PieceValue[MG][piece_on(to)] - threshold;
1010 if (balance < VALUE_ZERO)
1013 // Now assume the worst possible result: that the opponent can
1014 // capture our piece for free.
1015 balance -= PieceValue[MG][nextVictim];
1017 if (balance >= VALUE_ZERO) // Always true if nextVictim == KING
1020 bool opponentToMove = true;
1021 occupied = pieces() ^ from ^ to;
1023 // Find all attackers to the destination square, with the moving piece removed,
1024 // but possibly an X-ray attacker added behind it.
1025 Bitboard attackers = attackers_to(to, occupied) & occupied;
1029 // The balance is negative only because we assumed we could win
1030 // the last piece for free. We are truly winning only if we can
1031 // win the last piece _cheaply enough_. Test if we can actually
1032 // do this otherwise "give up".
1033 assert(balance < VALUE_ZERO);
1035 stmAttackers = attackers & pieces(stm);
1037 // Don't allow pinned pieces to attack pieces except the king as long all
1038 // pinners are on their original square.
1039 if (!(st->pinnersForKing[stm] & ~occupied))
1040 stmAttackers &= ~st->blockersForKing[stm];
1042 // If we have no more attackers we must give up
1046 // Locate and remove the next least valuable attacker
1047 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1049 if (nextVictim == KING)
1051 // Our only attacker is the king. If the opponent still has
1052 // attackers we must give up. Otherwise we make the move and
1053 // (having no more attackers) the opponent must give up.
1054 if (!(attackers & pieces(~stm)))
1055 opponentToMove = !opponentToMove;
1059 // Assume the opponent can win the next piece for free and switch sides
1060 balance += PieceValue[MG][nextVictim];
1061 opponentToMove = !opponentToMove;
1063 // If balance is negative after receiving a free piece then give up
1064 if (balance < VALUE_ZERO)
1067 // Complete the process of switching sides. The first line swaps
1068 // all negative numbers with non-negative numbers. The compiler
1069 // probably knows that it is just the bitwise negation ~balance.
1070 balance = -balance-1;
1074 // If the opponent gave up we win, otherwise we lose.
1075 return opponentToMove;
1079 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1080 /// or by repetition. It does not detect stalemates.
1082 bool Position::is_draw(int ply) const {
1084 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1087 int end = std::min(st->rule50, st->pliesFromNull);
1092 StateInfo* stp = st->previous->previous;
1095 for (int i = 4; i <= end; i += 2)
1097 stp = stp->previous->previous;
1099 // Return a draw score if a position repeats once earlier but strictly
1100 // after the root, or repeats twice before or at the root.
1101 if ( stp->key == st->key
1102 && ++cnt + (ply > i) == 2)
1110 /// Position::flip() flips position with the white and black sides reversed. This
1111 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1113 void Position::flip() {
1116 std::stringstream ss(fen());
1118 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1120 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1121 f.insert(0, token + (f.empty() ? " " : "/"));
1124 ss >> token; // Active color
1125 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1127 ss >> token; // Castling availability
1130 std::transform(f.begin(), f.end(), f.begin(),
1131 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1133 ss >> token; // En passant square
1134 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1136 std::getline(ss, token); // Half and full moves
1139 set(f, is_chess960(), st, this_thread());
1141 assert(pos_is_ok());
1145 /// Position::pos_is_ok() performs some consistency checks for the
1146 /// position object and raises an asserts if something wrong is detected.
1147 /// This is meant to be helpful when debugging.
1149 bool Position::pos_is_ok() const {
1151 const bool Fast = true; // Quick (default) or full check?
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))
1158 assert(0 && "pos_is_ok: Default");
1163 if ( pieceCount[W_KING] != 1
1164 || pieceCount[B_KING] != 1
1165 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1166 assert(0 && "pos_is_ok: Kings");
1168 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1169 || pieceCount[W_PAWN] > 8
1170 || pieceCount[B_PAWN] > 8)
1171 assert(0 && "pos_is_ok: Pawns");
1173 if ( (pieces(WHITE) & pieces(BLACK))
1174 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1175 || popcount(pieces(WHITE)) > 16
1176 || popcount(pieces(BLACK)) > 16)
1177 assert(0 && "pos_is_ok: Bitboards");
1179 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1180 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1181 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1182 assert(0 && "pos_is_ok: Bitboards");
1186 if (std::memcmp(&si, st, sizeof(StateInfo)))
1187 assert(0 && "pos_is_ok: State");
1189 for (Piece pc : Pieces)
1191 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1192 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1193 assert(0 && "pos_is_ok: Pieces");
1195 for (int i = 0; i < pieceCount[pc]; ++i)
1196 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1197 assert(0 && "pos_is_ok: Index");
1200 for (Color c = WHITE; c <= BLACK; ++c)
1201 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1203 if (!can_castle(c | s))
1206 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1207 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1208 || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1209 assert(0 && "pos_is_ok: Castling");