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. Position is not playable,
385 /// indeed is even not guaranteed to be legal.
387 Position& Position::set(const string& code, Color c, StateInfo* si) {
389 assert(code.length() > 0 && code.length() < 8);
390 assert(code[0] == 'K');
392 string sides[] = { code.substr(code.find('K', 1)), // Weak
393 code.substr(0, code.find('K', 1)) }; // Strong
395 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
397 string fenStr = sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/8/8/"
398 + sides[1] + char(8 - sides[1].length() + '0') + " w - - 0 10";
400 return set(fenStr, false, si, nullptr);
404 /// Position::fen() returns a FEN representation of the position. In case of
405 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
407 const string Position::fen() const {
410 std::ostringstream ss;
412 for (Rank r = RANK_8; r >= RANK_1; --r)
414 for (File f = FILE_A; f <= FILE_H; ++f)
416 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
423 ss << PieceToChar[piece_on(make_square(f, r))];
430 ss << (sideToMove == WHITE ? " w " : " b ");
432 if (can_castle(WHITE_OO))
433 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
435 if (can_castle(WHITE_OOO))
436 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
438 if (can_castle(BLACK_OO))
439 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
441 if (can_castle(BLACK_OOO))
442 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
444 if (!can_castle(WHITE) && !can_castle(BLACK))
447 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
448 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
454 /// Position::game_phase() calculates the game phase interpolating total non-pawn
455 /// material between endgame and midgame limits.
457 Phase Position::game_phase() const {
459 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
461 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
463 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
467 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
468 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
469 /// slider if removing that piece from the board would result in a position where
470 /// square 's' is attacked. For example, a king-attack blocking piece can be either
471 /// a pinned or a discovered check piece, according if its color is the opposite
472 /// or the same of the color of the slider.
474 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
479 // Snipers are sliders that attack 's' when a piece is removed
480 Bitboard snipers = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
481 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
485 Square sniperSq = pop_lsb(&snipers);
486 Bitboard b = between_bb(s, sniperSq) & pieces();
488 if (!more_than_one(b))
491 if (b & pieces(color_of(piece_on(s))))
499 /// Position::attackers_to() computes a bitboard of all pieces which attack a
500 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
502 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
504 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
505 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
506 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
507 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
508 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
509 | (attacks_from<KING>(s) & pieces(KING));
513 /// Position::legal() tests whether a pseudo-legal move is legal
515 bool Position::legal(Move m) const {
519 Color us = sideToMove;
520 Square from = from_sq(m);
522 assert(color_of(moved_piece(m)) == us);
523 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
525 // En passant captures are a tricky special case. Because they are rather
526 // uncommon, we do it simply by testing whether the king is attacked after
528 if (type_of(m) == ENPASSANT)
530 Square ksq = square<KING>(us);
531 Square to = to_sq(m);
532 Square capsq = to - pawn_push(us);
533 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
535 assert(to == ep_square());
536 assert(moved_piece(m) == make_piece(us, PAWN));
537 assert(piece_on(capsq) == make_piece(~us, PAWN));
538 assert(piece_on(to) == NO_PIECE);
540 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
541 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
544 // If the moving piece is a king, check whether the destination
545 // square is attacked by the opponent. Castling moves are checked
546 // for legality during move generation.
547 if (type_of(piece_on(from)) == KING)
548 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
550 // A non-king move is legal if and only if it is not pinned or it
551 // is moving along the ray towards or away from the king.
552 return !(pinned_pieces(us) & from)
553 || aligned(from, to_sq(m), square<KING>(us));
557 /// Position::pseudo_legal() takes a random move and tests whether the move is
558 /// pseudo legal. It is used to validate moves from TT that can be corrupted
559 /// due to SMP concurrent access or hash position key aliasing.
561 bool Position::pseudo_legal(const Move m) const {
563 Color us = sideToMove;
564 Square from = from_sq(m);
565 Square to = to_sq(m);
566 Piece pc = moved_piece(m);
568 // Use a slower but simpler function for uncommon cases
569 if (type_of(m) != NORMAL)
570 return MoveList<LEGAL>(*this).contains(m);
572 // Is not a promotion, so promotion piece must be empty
573 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
576 // If the 'from' square is not occupied by a piece belonging to the side to
577 // move, the move is obviously not legal.
578 if (pc == NO_PIECE || color_of(pc) != us)
581 // The destination square cannot be occupied by a friendly piece
585 // Handle the special case of a pawn move
586 if (type_of(pc) == PAWN)
588 // We have already handled promotion moves, so destination
589 // cannot be on the 8th/1st rank.
590 if (rank_of(to) == relative_rank(us, RANK_8))
593 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
594 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
595 && !( (from + 2 * pawn_push(us) == to) // Not a double push
596 && (rank_of(from) == relative_rank(us, RANK_2))
598 && empty(to - pawn_push(us))))
601 else if (!(attacks_from(type_of(pc), from) & to))
604 // Evasions generator already takes care to avoid some kind of illegal moves
605 // and legal() relies on this. We therefore have to take care that the same
606 // kind of moves are filtered out here.
609 if (type_of(pc) != KING)
611 // Double check? In this case a king move is required
612 if (more_than_one(checkers()))
615 // Our move must be a blocking evasion or a capture of the checking piece
616 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
619 // In case of king moves under check we have to remove king so as to catch
620 // invalid moves like b1a1 when opposite queen is on c1.
621 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
629 /// Position::gives_check() tests whether a pseudo-legal move gives a check
631 bool Position::gives_check(Move m) const {
634 assert(color_of(moved_piece(m)) == sideToMove);
636 Square from = from_sq(m);
637 Square to = to_sq(m);
639 // Is there a direct check?
640 if (st->checkSquares[type_of(piece_on(from))] & to)
643 // Is there a discovered check?
644 if ( (discovered_check_candidates() & from)
645 && !aligned(from, to, square<KING>(~sideToMove)))
654 return attacks_bb(promotion_type(m), to, pieces() ^ from) & square<KING>(~sideToMove);
656 // En passant capture with check? We have already handled the case
657 // of direct checks and ordinary discovered check, so the only case we
658 // need to handle is the unusual case of a discovered check through
659 // the captured pawn.
662 Square capsq = make_square(file_of(to), rank_of(from));
663 Bitboard b = (pieces() ^ from ^ capsq) | to;
665 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
666 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
671 Square rfrom = to; // Castling is encoded as 'King captures the rook'
672 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
673 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
675 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
676 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
685 /// Position::do_move() makes a move, and saves all information necessary
686 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
687 /// moves should be filtered out before this function is called.
689 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
692 assert(&newSt != st);
695 Key k = st->key ^ Zobrist::side;
697 // Copy some fields of the old state to our new StateInfo object except the
698 // ones which are going to be recalculated from scratch anyway and then switch
699 // our state pointer to point to the new (ready to be updated) state.
700 std::memcpy(&newSt, st, offsetof(StateInfo, key));
704 // Increment ply counters. In particular, rule50 will be reset to zero later on
705 // in case of a capture or a pawn move.
710 Color us = sideToMove;
712 Square from = from_sq(m);
713 Square to = to_sq(m);
714 Piece pc = piece_on(from);
715 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
717 assert(color_of(pc) == us);
718 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
719 assert(type_of(captured) != KING);
721 if (type_of(m) == CASTLING)
723 assert(pc == make_piece(us, KING));
724 assert(captured == make_piece(us, ROOK));
727 do_castling<true>(us, from, to, rfrom, rto);
729 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
730 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
738 // If the captured piece is a pawn, update pawn hash key, otherwise
739 // update non-pawn material.
740 if (type_of(captured) == PAWN)
742 if (type_of(m) == ENPASSANT)
744 capsq -= pawn_push(us);
746 assert(pc == make_piece(us, PAWN));
747 assert(to == st->epSquare);
748 assert(relative_rank(us, to) == RANK_6);
749 assert(piece_on(to) == NO_PIECE);
750 assert(piece_on(capsq) == make_piece(them, PAWN));
752 board[capsq] = NO_PIECE; // Not done by remove_piece()
755 st->pawnKey ^= Zobrist::psq[captured][capsq];
758 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
760 // Update board and piece lists
761 remove_piece(captured, capsq);
763 // Update material hash key and prefetch access to materialTable
764 k ^= Zobrist::psq[captured][capsq];
765 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
766 prefetch(thisThread->materialTable[st->materialKey]);
768 // Update incremental scores
769 st->psq -= PSQT::psq[captured][capsq];
771 // Reset rule 50 counter
776 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
778 // Reset en passant square
779 if (st->epSquare != SQ_NONE)
781 k ^= Zobrist::enpassant[file_of(st->epSquare)];
782 st->epSquare = SQ_NONE;
785 // Update castling rights if needed
786 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
788 int cr = castlingRightsMask[from] | castlingRightsMask[to];
789 k ^= Zobrist::castling[st->castlingRights & cr];
790 st->castlingRights &= ~cr;
793 // Move the piece. The tricky Chess960 castling is handled earlier
794 if (type_of(m) != CASTLING)
795 move_piece(pc, from, to);
797 // If the moving piece is a pawn do some special extra work
798 if (type_of(pc) == PAWN)
800 // Set en-passant square if the moved pawn can be captured
801 if ( (int(to) ^ int(from)) == 16
802 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
804 st->epSquare = (from + to) / 2;
805 k ^= Zobrist::enpassant[file_of(st->epSquare)];
808 else if (type_of(m) == PROMOTION)
810 Piece promotion = make_piece(us, promotion_type(m));
812 assert(relative_rank(us, to) == RANK_8);
813 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
815 remove_piece(pc, to);
816 put_piece(promotion, to);
819 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
820 st->pawnKey ^= Zobrist::psq[pc][to];
821 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
822 ^ Zobrist::psq[pc][pieceCount[pc]];
824 // Update incremental score
825 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
828 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
831 // Update pawn hash key and prefetch access to pawnsTable
832 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
833 prefetch2(thisThread->pawnsTable[st->pawnKey]);
835 // Reset rule 50 draw counter
839 // Update incremental scores
840 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
843 st->capturedPiece = captured;
845 // Update the key with the final value
848 // Calculate checkers bitboard (if move gives check)
849 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
851 sideToMove = ~sideToMove;
853 // Update king attacks used for fast check detection
860 /// Position::undo_move() unmakes a move. When it returns, the position should
861 /// be restored to exactly the same state as before the move was made.
863 void Position::undo_move(Move m) {
867 sideToMove = ~sideToMove;
869 Color us = sideToMove;
870 Square from = from_sq(m);
871 Square to = to_sq(m);
872 Piece pc = piece_on(to);
874 assert(empty(from) || type_of(m) == CASTLING);
875 assert(type_of(st->capturedPiece) != KING);
877 if (type_of(m) == PROMOTION)
879 assert(relative_rank(us, to) == RANK_8);
880 assert(type_of(pc) == promotion_type(m));
881 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
883 remove_piece(pc, to);
884 pc = make_piece(us, PAWN);
888 if (type_of(m) == CASTLING)
891 do_castling<false>(us, from, to, rfrom, rto);
895 move_piece(pc, to, from); // Put the piece back at the source square
897 if (st->capturedPiece)
901 if (type_of(m) == ENPASSANT)
903 capsq -= pawn_push(us);
905 assert(type_of(pc) == PAWN);
906 assert(to == st->previous->epSquare);
907 assert(relative_rank(us, to) == RANK_6);
908 assert(piece_on(capsq) == NO_PIECE);
909 assert(st->capturedPiece == make_piece(~us, PAWN));
912 put_piece(st->capturedPiece, capsq); // Restore the captured piece
916 // Finally point our state pointer back to the previous state
924 /// Position::do_castling() is a helper used to do/undo a castling move. This
925 /// is a bit tricky in Chess960 where from/to squares can overlap.
927 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
929 bool kingSide = to > from;
930 rfrom = to; // Castling is encoded as "king captures friendly rook"
931 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
932 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
934 // Remove both pieces first since squares could overlap in Chess960
935 remove_piece(make_piece(us, KING), Do ? from : to);
936 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
937 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
938 put_piece(make_piece(us, KING), Do ? to : from);
939 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
943 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
944 /// the side to move without executing any move on the board.
946 void Position::do_null_move(StateInfo& newSt) {
949 assert(&newSt != st);
951 std::memcpy(&newSt, st, sizeof(StateInfo));
955 if (st->epSquare != SQ_NONE)
957 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
958 st->epSquare = SQ_NONE;
961 st->key ^= Zobrist::side;
962 prefetch(TT.first_entry(st->key));
965 st->pliesFromNull = 0;
967 sideToMove = ~sideToMove;
974 void Position::undo_null_move() {
979 sideToMove = ~sideToMove;
983 /// Position::key_after() computes the new hash key after the given move. Needed
984 /// for speculative prefetch. It doesn't recognize special moves like castling,
985 /// en-passant and promotions.
987 Key Position::key_after(Move m) const {
989 Square from = from_sq(m);
990 Square to = to_sq(m);
991 Piece pc = piece_on(from);
992 Piece captured = piece_on(to);
993 Key k = st->key ^ Zobrist::side;
996 k ^= Zobrist::psq[captured][to];
998 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
1002 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1003 /// SEE value of move is greater or equal to the given value. We'll use an
1004 /// algorithm similar to alpha-beta pruning with a null window.
1006 bool Position::see_ge(Move m, Value v) const {
1010 // Castling moves are implemented as king capturing the rook so cannot be
1011 // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
1012 // correct unless in the rare case the rook ends up under attack.
1013 if (type_of(m) == CASTLING)
1014 return VALUE_ZERO >= v;
1016 Square from = from_sq(m), to = to_sq(m);
1017 PieceType nextVictim = type_of(piece_on(from));
1018 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1019 Value balance; // Values of the pieces taken by us minus opponent's ones
1020 Bitboard occupied, stmAttackers;
1022 if (type_of(m) == ENPASSANT)
1024 occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1025 balance = PieceValue[MG][PAWN];
1029 balance = PieceValue[MG][piece_on(to)];
1036 if (nextVictim == KING)
1039 balance -= PieceValue[MG][nextVictim];
1044 bool relativeStm = true; // True if the opponent is to move
1045 occupied ^= pieces() ^ from ^ to;
1047 // Find all attackers to the destination square, with the moving piece removed,
1048 // but possibly an X-ray attacker added behind it.
1049 Bitboard attackers = attackers_to(to, occupied) & occupied;
1053 stmAttackers = attackers & pieces(stm);
1055 // Don't allow pinned pieces to attack pieces except the king as long all
1056 // pinners are on their original square.
1057 if (!(st->pinnersForKing[stm] & ~occupied))
1058 stmAttackers &= ~st->blockersForKing[stm];
1063 // Locate and remove the next least valuable attacker
1064 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1066 if (nextVictim == KING)
1067 return relativeStm == bool(attackers & pieces(~stm));
1069 balance += relativeStm ? PieceValue[MG][nextVictim]
1070 : -PieceValue[MG][nextVictim];
1072 relativeStm = !relativeStm;
1074 if (relativeStm == (balance >= v))
1082 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1083 /// or by repetition. It does not detect stalemates.
1085 bool Position::is_draw(int ply) const {
1087 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1090 int end = std::min(st->rule50, st->pliesFromNull);
1095 StateInfo* stp = st->previous->previous;
1098 for (int i = 4; i <= end; i += 2)
1100 stp = stp->previous->previous;
1102 // At root position ply is 1, so return a draw score if a position
1103 // repeats once earlier but after or at the root, or repeats twice
1104 // strictly before the root.
1105 if ( stp->key == st->key
1106 && ++cnt + (ply - i > 0) == 2)
1114 /// Position::flip() flips position with the white and black sides reversed. This
1115 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1117 void Position::flip() {
1120 std::stringstream ss(fen());
1122 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1124 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1125 f.insert(0, token + (f.empty() ? " " : "/"));
1128 ss >> token; // Active color
1129 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1131 ss >> token; // Castling availability
1134 std::transform(f.begin(), f.end(), f.begin(),
1135 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1137 ss >> token; // En passant square
1138 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1140 std::getline(ss, token); // Half and full moves
1143 set(f, is_chess960(), st, this_thread());
1145 assert(pos_is_ok());
1149 /// Position::pos_is_ok() performs some consistency checks for the position object.
1150 /// This is meant to be helpful when debugging.
1152 bool Position::pos_is_ok(int* failedStep) const {
1154 const bool Fast = true; // Quick (default) or full check?
1156 enum { Default, King, Bitboards, State, Lists, Castling };
1158 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1163 if (step == Default)
1164 if ( (sideToMove != WHITE && sideToMove != BLACK)
1165 || piece_on(square<KING>(WHITE)) != W_KING
1166 || piece_on(square<KING>(BLACK)) != B_KING
1167 || ( ep_square() != SQ_NONE
1168 && relative_rank(sideToMove, ep_square()) != RANK_6))
1172 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1173 || std::count(board, board + SQUARE_NB, B_KING) != 1
1174 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1177 if (step == Bitboards)
1179 if ( (pieces(WHITE) & pieces(BLACK))
1180 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1183 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1184 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1185 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1193 if (std::memcmp(&si, st, sizeof(StateInfo)))
1198 for (Piece pc : Pieces)
1200 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1203 for (int i = 0; i < pieceCount[pc]; ++i)
1204 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1208 if (step == Castling)
1209 for (Color c = WHITE; c <= BLACK; ++c)
1210 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1212 if (!can_castle(c | s))
1215 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1216 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1217 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))