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::game_phase() calculates the game phase interpolating total non-pawn
454 /// material between endgame and midgame limits.
456 Phase Position::game_phase() const {
458 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
460 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
462 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
466 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
467 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
468 /// slider if removing that piece from the board would result in a position where
469 /// square 's' is attacked. For example, a king-attack blocking piece can be either
470 /// a pinned or a discovered check piece, according if its color is the opposite
471 /// or the same of the color of the slider.
473 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
478 // Snipers are sliders that attack 's' when a piece is removed
479 Bitboard snipers = ( (PseudoAttacks[ ROOK][s] & pieces(QUEEN, ROOK))
480 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
484 Square sniperSq = pop_lsb(&snipers);
485 Bitboard b = between_bb(s, sniperSq) & pieces();
487 if (!more_than_one(b))
490 if (b & pieces(color_of(piece_on(s))))
498 /// Position::attackers_to() computes a bitboard of all pieces which attack a
499 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
501 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
503 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
504 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
505 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
506 | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN))
507 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
508 | (attacks_from<KING>(s) & pieces(KING));
512 /// Position::legal() tests whether a pseudo-legal move is legal
514 bool Position::legal(Move m) const {
518 Color us = sideToMove;
519 Square from = from_sq(m);
521 assert(color_of(moved_piece(m)) == us);
522 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
524 // En passant captures are a tricky special case. Because they are rather
525 // uncommon, we do it simply by testing whether the king is attacked after
527 if (type_of(m) == ENPASSANT)
529 Square ksq = square<KING>(us);
530 Square to = to_sq(m);
531 Square capsq = to - pawn_push(us);
532 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
534 assert(to == ep_square());
535 assert(moved_piece(m) == make_piece(us, PAWN));
536 assert(piece_on(capsq) == make_piece(~us, PAWN));
537 assert(piece_on(to) == NO_PIECE);
539 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
540 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
543 // If the moving piece is a king, check whether the destination
544 // square is attacked by the opponent. Castling moves are checked
545 // for legality during move generation.
546 if (type_of(piece_on(from)) == KING)
547 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
549 // A non-king move is legal if and only if it is not pinned or it
550 // is moving along the ray towards or away from the king.
551 return !(pinned_pieces(us) & from)
552 || aligned(from, to_sq(m), square<KING>(us));
556 /// Position::pseudo_legal() takes a random move and tests whether the move is
557 /// pseudo legal. It is used to validate moves from TT that can be corrupted
558 /// due to SMP concurrent access or hash position key aliasing.
560 bool Position::pseudo_legal(const Move m) const {
562 Color us = sideToMove;
563 Square from = from_sq(m);
564 Square to = to_sq(m);
565 Piece pc = moved_piece(m);
567 // Use a slower but simpler function for uncommon cases
568 if (type_of(m) != NORMAL)
569 return MoveList<LEGAL>(*this).contains(m);
571 // Is not a promotion, so promotion piece must be empty
572 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
575 // If the 'from' square is not occupied by a piece belonging to the side to
576 // move, the move is obviously not legal.
577 if (pc == NO_PIECE || color_of(pc) != us)
580 // The destination square cannot be occupied by a friendly piece
584 // Handle the special case of a pawn move
585 if (type_of(pc) == PAWN)
587 // We have already handled promotion moves, so destination
588 // cannot be on the 8th/1st rank.
589 if (rank_of(to) == relative_rank(us, RANK_8))
592 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
593 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
594 && !( (from + 2 * pawn_push(us) == to) // Not a double push
595 && (rank_of(from) == relative_rank(us, RANK_2))
597 && empty(to - pawn_push(us))))
600 else if (!(attacks_from(type_of(pc), from) & to))
603 // Evasions generator already takes care to avoid some kind of illegal moves
604 // and legal() relies on this. We therefore have to take care that the same
605 // kind of moves are filtered out here.
608 if (type_of(pc) != KING)
610 // Double check? In this case a king move is required
611 if (more_than_one(checkers()))
614 // Our move must be a blocking evasion or a capture of the checking piece
615 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
618 // In case of king moves under check we have to remove king so as to catch
619 // invalid moves like b1a1 when opposite queen is on c1.
620 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
628 /// Position::gives_check() tests whether a pseudo-legal move gives a check
630 bool Position::gives_check(Move m) const {
633 assert(color_of(moved_piece(m)) == sideToMove);
635 Square from = from_sq(m);
636 Square to = to_sq(m);
638 // Is there a direct check?
639 if (st->checkSquares[type_of(piece_on(from))] & to)
642 // Is there a discovered check?
643 if ( (discovered_check_candidates() & from)
644 && !aligned(from, to, square<KING>(~sideToMove)))
653 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
655 // En passant capture with check? We have already handled the case
656 // of direct checks and ordinary discovered check, so the only case we
657 // need to handle is the unusual case of a discovered check through
658 // the captured pawn.
661 Square capsq = make_square(file_of(to), rank_of(from));
662 Bitboard b = (pieces() ^ from ^ capsq) | to;
664 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
665 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
670 Square rfrom = to; // Castling is encoded as 'King captures the rook'
671 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
672 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
674 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
675 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
684 /// Position::do_move() makes a move, and saves all information necessary
685 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
686 /// moves should be filtered out before this function is called.
688 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
691 assert(&newSt != st);
694 Key k = st->key ^ Zobrist::side;
696 // Copy some fields of the old state to our new StateInfo object except the
697 // ones which are going to be recalculated from scratch anyway and then switch
698 // our state pointer to point to the new (ready to be updated) state.
699 std::memcpy(&newSt, st, offsetof(StateInfo, key));
703 // Increment ply counters. In particular, rule50 will be reset to zero later on
704 // in case of a capture or a pawn move.
709 Color us = sideToMove;
711 Square from = from_sq(m);
712 Square to = to_sq(m);
713 Piece pc = piece_on(from);
714 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
716 assert(color_of(pc) == us);
717 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
718 assert(type_of(captured) != KING);
720 if (type_of(m) == CASTLING)
722 assert(pc == make_piece(us, KING));
723 assert(captured == make_piece(us, ROOK));
726 do_castling<true>(us, from, to, rfrom, rto);
728 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
729 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
737 // If the captured piece is a pawn, update pawn hash key, otherwise
738 // update non-pawn material.
739 if (type_of(captured) == PAWN)
741 if (type_of(m) == ENPASSANT)
743 capsq -= pawn_push(us);
745 assert(pc == make_piece(us, PAWN));
746 assert(to == st->epSquare);
747 assert(relative_rank(us, to) == RANK_6);
748 assert(piece_on(to) == NO_PIECE);
749 assert(piece_on(capsq) == make_piece(them, PAWN));
751 board[capsq] = NO_PIECE; // Not done by remove_piece()
754 st->pawnKey ^= Zobrist::psq[captured][capsq];
757 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
759 // Update board and piece lists
760 remove_piece(captured, capsq);
762 // Update material hash key and prefetch access to materialTable
763 k ^= Zobrist::psq[captured][capsq];
764 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
765 prefetch(thisThread->materialTable[st->materialKey]);
767 // Update incremental scores
768 st->psq -= PSQT::psq[captured][capsq];
770 // Reset rule 50 counter
775 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
777 // Reset en passant square
778 if (st->epSquare != SQ_NONE)
780 k ^= Zobrist::enpassant[file_of(st->epSquare)];
781 st->epSquare = SQ_NONE;
784 // Update castling rights if needed
785 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
787 int cr = castlingRightsMask[from] | castlingRightsMask[to];
788 k ^= Zobrist::castling[st->castlingRights & cr];
789 st->castlingRights &= ~cr;
792 // Move the piece. The tricky Chess960 castling is handled earlier
793 if (type_of(m) != CASTLING)
794 move_piece(pc, from, to);
796 // If the moving piece is a pawn do some special extra work
797 if (type_of(pc) == PAWN)
799 // Set en-passant square if the moved pawn can be captured
800 if ( (int(to) ^ int(from)) == 16
801 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
803 st->epSquare = (from + to) / 2;
804 k ^= Zobrist::enpassant[file_of(st->epSquare)];
807 else if (type_of(m) == PROMOTION)
809 Piece promotion = make_piece(us, promotion_type(m));
811 assert(relative_rank(us, to) == RANK_8);
812 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
814 remove_piece(pc, to);
815 put_piece(promotion, to);
818 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
819 st->pawnKey ^= Zobrist::psq[pc][to];
820 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
821 ^ Zobrist::psq[pc][pieceCount[pc]];
823 // Update incremental score
824 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
827 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
830 // Update pawn hash key and prefetch access to pawnsTable
831 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
832 prefetch2(thisThread->pawnsTable[st->pawnKey]);
834 // Reset rule 50 draw counter
838 // Update incremental scores
839 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
842 st->capturedPiece = captured;
844 // Update the key with the final value
847 // Calculate checkers bitboard (if move gives check)
848 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
850 sideToMove = ~sideToMove;
852 // Update king attacks used for fast check detection
859 /// Position::undo_move() unmakes a move. When it returns, the position should
860 /// be restored to exactly the same state as before the move was made.
862 void Position::undo_move(Move m) {
866 sideToMove = ~sideToMove;
868 Color us = sideToMove;
869 Square from = from_sq(m);
870 Square to = to_sq(m);
871 Piece pc = piece_on(to);
873 assert(empty(from) || type_of(m) == CASTLING);
874 assert(type_of(st->capturedPiece) != KING);
876 if (type_of(m) == PROMOTION)
878 assert(relative_rank(us, to) == RANK_8);
879 assert(type_of(pc) == promotion_type(m));
880 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
882 remove_piece(pc, to);
883 pc = make_piece(us, PAWN);
887 if (type_of(m) == CASTLING)
890 do_castling<false>(us, from, to, rfrom, rto);
894 move_piece(pc, to, from); // Put the piece back at the source square
896 if (st->capturedPiece)
900 if (type_of(m) == ENPASSANT)
902 capsq -= pawn_push(us);
904 assert(type_of(pc) == PAWN);
905 assert(to == st->previous->epSquare);
906 assert(relative_rank(us, to) == RANK_6);
907 assert(piece_on(capsq) == NO_PIECE);
908 assert(st->capturedPiece == make_piece(~us, PAWN));
911 put_piece(st->capturedPiece, capsq); // Restore the captured piece
915 // Finally point our state pointer back to the previous state
923 /// Position::do_castling() is a helper used to do/undo a castling move. This
924 /// is a bit tricky in Chess960 where from/to squares can overlap.
926 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
928 bool kingSide = to > from;
929 rfrom = to; // Castling is encoded as "king captures friendly rook"
930 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
931 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
933 // Remove both pieces first since squares could overlap in Chess960
934 remove_piece(make_piece(us, KING), Do ? from : to);
935 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
936 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
937 put_piece(make_piece(us, KING), Do ? to : from);
938 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
942 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
943 /// the side to move without executing any move on the board.
945 void Position::do_null_move(StateInfo& newSt) {
948 assert(&newSt != st);
950 std::memcpy(&newSt, st, sizeof(StateInfo));
954 if (st->epSquare != SQ_NONE)
956 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
957 st->epSquare = SQ_NONE;
960 st->key ^= Zobrist::side;
961 prefetch(TT.first_entry(st->key));
964 st->pliesFromNull = 0;
966 sideToMove = ~sideToMove;
973 void Position::undo_null_move() {
978 sideToMove = ~sideToMove;
982 /// Position::key_after() computes the new hash key after the given move. Needed
983 /// for speculative prefetch. It doesn't recognize special moves like castling,
984 /// en-passant and promotions.
986 Key Position::key_after(Move m) const {
988 Square from = from_sq(m);
989 Square to = to_sq(m);
990 Piece pc = piece_on(from);
991 Piece captured = piece_on(to);
992 Key k = st->key ^ Zobrist::side;
995 k ^= Zobrist::psq[captured][to];
997 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1001 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1002 /// SEE value of move is greater or equal to the given threshold. We'll use an
1003 /// algorithm similar to alpha-beta pruning with a null window.
1005 bool Position::see_ge(Move m, Value threshold) const {
1009 // Castling moves are implemented as king capturing the rook so cannot be
1010 // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
1011 // correct unless in the rare case the rook ends up under attack.
1012 if (type_of(m) == CASTLING)
1013 return VALUE_ZERO >= threshold;
1015 Square from = from_sq(m), to = to_sq(m);
1016 PieceType nextVictim = type_of(piece_on(from));
1017 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1018 Value balance; // Values of the pieces taken by us minus opponent's ones
1019 Bitboard occupied, stmAttackers;
1021 if (type_of(m) == ENPASSANT)
1023 occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1024 balance = PieceValue[MG][PAWN];
1028 balance = PieceValue[MG][piece_on(to)];
1032 if (balance < threshold)
1035 if (nextVictim == KING)
1038 balance -= PieceValue[MG][nextVictim];
1040 if (balance >= threshold)
1043 bool relativeStm = true; // True if the opponent is to move
1044 occupied ^= pieces() ^ from ^ to;
1046 // Find all attackers to the destination square, with the moving piece removed,
1047 // but possibly an X-ray attacker added behind it.
1048 Bitboard attackers = attackers_to(to, occupied) & occupied;
1052 stmAttackers = attackers & pieces(stm);
1054 // Don't allow pinned pieces to attack pieces except the king as long all
1055 // pinners are on their original square.
1056 if (!(st->pinnersForKing[stm] & ~occupied))
1057 stmAttackers &= ~st->blockersForKing[stm];
1062 // Locate and remove the next least valuable attacker
1063 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1065 if (nextVictim == KING)
1066 return relativeStm == bool(attackers & pieces(~stm));
1068 balance += relativeStm ? PieceValue[MG][nextVictim]
1069 : -PieceValue[MG][nextVictim];
1071 relativeStm = !relativeStm;
1073 if (relativeStm == (balance >= threshold))
1081 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1082 /// or by repetition. It does not detect stalemates.
1084 bool Position::is_draw(int ply) const {
1086 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1089 int end = std::min(st->rule50, st->pliesFromNull);
1094 StateInfo* stp = st->previous->previous;
1097 for (int i = 4; i <= end; i += 2)
1099 stp = stp->previous->previous;
1101 // At root position ply is 1, so return a draw score if a position
1102 // repeats once earlier but strictly after the root, or repeats twice
1103 // before or at the root.
1104 if ( stp->key == st->key
1105 && ++cnt + (ply - 1 > i) == 2)
1113 /// Position::flip() flips position with the white and black sides reversed. This
1114 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1116 void Position::flip() {
1119 std::stringstream ss(fen());
1121 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1123 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1124 f.insert(0, token + (f.empty() ? " " : "/"));
1127 ss >> token; // Active color
1128 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1130 ss >> token; // Castling availability
1133 std::transform(f.begin(), f.end(), f.begin(),
1134 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1136 ss >> token; // En passant square
1137 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1139 std::getline(ss, token); // Half and full moves
1142 set(f, is_chess960(), st, this_thread());
1144 assert(pos_is_ok());
1148 /// Position::pos_is_ok() performs some consistency checks for the
1149 /// position object and raises an asserts if something wrong is detected.
1150 /// This is meant to be helpful when debugging.
1152 bool Position::pos_is_ok() const {
1154 const bool Fast = true; // Quick (default) or full check?
1156 if ( (sideToMove != WHITE && sideToMove != BLACK)
1157 || piece_on(square<KING>(WHITE)) != W_KING
1158 || piece_on(square<KING>(BLACK)) != B_KING
1159 || ( ep_square() != SQ_NONE
1160 && relative_rank(sideToMove, ep_square()) != RANK_6))
1161 assert(0 && "pos_is_ok: Default");
1166 if ( pieceCount[W_KING] != 1
1167 || pieceCount[B_KING] != 1
1168 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1169 assert(0 && "pos_is_ok: Kings");
1171 if ( (pieces(PAWN) & (Rank1BB | Rank8BB))
1172 || pieceCount[W_PAWN] > 8
1173 || pieceCount[B_PAWN] > 8)
1174 assert(0 && "pos_is_ok: Pawns");
1176 if ( (pieces(WHITE) & pieces(BLACK))
1177 || (pieces(WHITE) | pieces(BLACK)) != pieces()
1178 || popcount(pieces(WHITE)) > 16
1179 || popcount(pieces(BLACK)) > 16)
1180 assert(0 && "pos_is_ok: Bitboards");
1182 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1183 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1184 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1185 assert(0 && "pos_is_ok: Bitboards");
1189 if (std::memcmp(&si, st, sizeof(StateInfo)))
1190 assert(0 && "pos_is_ok: State");
1192 for (Piece pc : Pieces)
1194 if ( pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc)))
1195 || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc))
1196 assert(0 && "pos_is_ok: Pieces");
1198 for (int i = 0; i < pieceCount[pc]; ++i)
1199 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1200 assert(0 && "pos_is_ok: Index");
1203 for (Color c = WHITE; c <= BLACK; ++c)
1204 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1206 if (!can_castle(c | s))
1209 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1210 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1211 || (castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))
1212 assert(0 && "pos_is_ok: Castling");