2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
7 Stockfish is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 #include <cstddef> // For offsetof()
24 #include <cstring> // For std::memset, std::memcmp
39 extern Score psq[PIECE_NB][SQUARE_NB];
44 Key psq[PIECE_NB][SQUARE_NB];
45 Key enpassant[FILE_NB];
46 Key castling[CASTLING_RIGHT_NB];
52 const string PieceToChar(" PNBRQK pnbrqk");
54 // min_attacker() is a helper function used by see() to locate the least
55 // valuable attacker for the side to move, remove the attacker we just found
56 // from the bitboards and scan for new X-ray attacks behind it.
59 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
60 Bitboard& occupied, Bitboard& attackers) {
62 Bitboard b = stmAttackers & bb[Pt];
64 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
66 occupied ^= b & ~(b - 1);
68 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
69 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
71 if (Pt == ROOK || Pt == QUEEN)
72 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
74 attackers &= occupied; // After X-ray that may add already processed pieces
79 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
80 return KING; // No need to update bitboards: it is the last cycle
86 /// operator<<(Position) returns an ASCII representation of the position
88 std::ostream& operator<<(std::ostream& os, const Position& pos) {
90 os << "\n +---+---+---+---+---+---+---+---+\n";
92 for (Rank r = RANK_8; r >= RANK_1; --r)
94 for (File f = FILE_A; f <= FILE_H; ++f)
95 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
97 os << " |\n +---+---+---+---+---+---+---+---+\n";
100 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
101 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
103 for (Bitboard b = pos.checkers(); b; )
104 os << UCI::square(pop_lsb(&b)) << " ";
110 /// Position::init() initializes at startup the various arrays used to compute
113 void Position::init() {
117 for (Piece pc : Pieces)
118 for (Square s = SQ_A1; s <= SQ_H8; ++s)
119 Zobrist::psq[pc][s] = rng.rand<Key>();
121 for (File f = FILE_A; f <= FILE_H; ++f)
122 Zobrist::enpassant[f] = rng.rand<Key>();
124 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
126 Zobrist::castling[cr] = 0;
130 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
131 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
135 Zobrist::side = rng.rand<Key>();
139 /// Position::set() initializes the position object with the given FEN string.
140 /// This function is not very robust - make sure that input FENs are correct,
141 /// this is assumed to be the responsibility of the GUI.
143 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
145 A FEN string defines a particular position using only the ASCII character set.
147 A FEN string contains six fields separated by a space. The fields are:
149 1) Piece placement (from white's perspective). Each rank is described, starting
150 with rank 8 and ending with rank 1. Within each rank, the contents of each
151 square are described from file A through file H. Following the Standard
152 Algebraic Notation (SAN), each piece is identified by a single letter taken
153 from the standard English names. White pieces are designated using upper-case
154 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
155 noted using digits 1 through 8 (the number of blank squares), and "/"
158 2) Active color. "w" means white moves next, "b" means black.
160 3) Castling availability. If neither side can castle, this is "-". Otherwise,
161 this has one or more letters: "K" (White can castle kingside), "Q" (White
162 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
163 can castle queenside).
165 4) En passant target square (in algebraic notation). If there's no en passant
166 target square, this is "-". If a pawn has just made a 2-square move, this
167 is the position "behind" the pawn. This is recorded regardless of whether
168 there is a pawn in position to make an en passant capture.
170 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
171 or capture. This is used to determine if a draw can be claimed under the
174 6) Fullmove number. The number of the full move. It starts at 1, and is
175 incremented after Black's move.
178 unsigned char col, row, token;
181 std::istringstream ss(fenStr);
183 std::memset(this, 0, sizeof(Position));
184 std::memset(si, 0, sizeof(StateInfo));
185 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
190 // 1. Piece placement
191 while ((ss >> token) && !isspace(token))
194 sq += Square(token - '0'); // Advance the given number of files
196 else if (token == '/')
199 else if ((idx = PieceToChar.find(token)) != string::npos)
201 put_piece(Piece(idx), sq);
208 sideToMove = (token == 'w' ? WHITE : BLACK);
211 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
212 // Shredder-FEN that uses the letters of the columns on which the rooks began
213 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
214 // if an inner rook is associated with the castling right, the castling tag is
215 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
216 while ((ss >> token) && !isspace(token))
219 Color c = islower(token) ? BLACK : WHITE;
220 Piece rook = make_piece(c, ROOK);
222 token = char(toupper(token));
225 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
227 else if (token == 'Q')
228 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
230 else if (token >= 'A' && token <= 'H')
231 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
236 set_castling_right(c, rsq);
239 // 4. En passant square. Ignore if no pawn capture is possible
240 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
241 && ((ss >> row) && (row == '3' || row == '6')))
243 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
245 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
246 st->epSquare = SQ_NONE;
249 st->epSquare = SQ_NONE;
251 // 5-6. Halfmove clock and fullmove number
252 ss >> std::skipws >> st->rule50 >> gamePly;
254 // Convert from fullmove starting from 1 to ply starting from 0,
255 // handle also common incorrect FEN with fullmove = 0.
256 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
258 chess960 = isChess960;
268 /// Position::set_castling_right() is a helper function used to set castling
269 /// rights given the corresponding color and the rook starting square.
271 void Position::set_castling_right(Color c, Square rfrom) {
273 Square kfrom = square<KING>(c);
274 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
275 CastlingRight cr = (c | cs);
277 st->castlingRights |= cr;
278 castlingRightsMask[kfrom] |= cr;
279 castlingRightsMask[rfrom] |= cr;
280 castlingRookSquare[cr] = rfrom;
282 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
283 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
285 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
286 if (s != kfrom && s != rfrom)
287 castlingPath[cr] |= s;
289 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
290 if (s != kfrom && s != rfrom)
291 castlingPath[cr] |= s;
295 /// Position::set_check_info() sets king attacks to detect if a move gives check
297 void Position::set_check_info(StateInfo* si) const {
299 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
300 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
302 Square ksq = square<KING>(~sideToMove);
304 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
305 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
306 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
307 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
308 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
309 si->checkSquares[KING] = 0;
313 /// Position::set_state() computes the hash keys of the position, and other
314 /// data that once computed is updated incrementally as moves are made.
315 /// The function is only used when a new position is set up, and to verify
316 /// the correctness of the StateInfo data when running in debug mode.
318 void Position::set_state(StateInfo* si) const {
320 si->key = si->pawnKey = si->materialKey = 0;
321 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
322 si->psq = SCORE_ZERO;
323 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
327 for (Bitboard b = pieces(); b; )
329 Square s = pop_lsb(&b);
330 Piece pc = piece_on(s);
331 si->key ^= Zobrist::psq[pc][s];
332 si->psq += PSQT::psq[pc][s];
335 if (si->epSquare != SQ_NONE)
336 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
338 if (sideToMove == BLACK)
339 si->key ^= Zobrist::side;
341 si->key ^= Zobrist::castling[si->castlingRights];
343 for (Bitboard b = pieces(PAWN); b; )
345 Square s = pop_lsb(&b);
346 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
349 for (Piece pc : Pieces)
351 if (type_of(pc) != PAWN && type_of(pc) != KING)
352 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
354 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
355 si->materialKey ^= Zobrist::psq[pc][cnt];
360 /// Position::fen() returns a FEN representation of the position. In case of
361 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
363 const string Position::fen() const {
366 std::ostringstream ss;
368 for (Rank r = RANK_8; r >= RANK_1; --r)
370 for (File f = FILE_A; f <= FILE_H; ++f)
372 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
379 ss << PieceToChar[piece_on(make_square(f, r))];
386 ss << (sideToMove == WHITE ? " w " : " b ");
388 if (can_castle(WHITE_OO))
389 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
391 if (can_castle(WHITE_OOO))
392 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
394 if (can_castle(BLACK_OO))
395 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
397 if (can_castle(BLACK_OOO))
398 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
400 if (!can_castle(WHITE) && !can_castle(BLACK))
403 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
404 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
410 /// Position::game_phase() calculates the game phase interpolating total non-pawn
411 /// material between endgame and midgame limits.
413 Phase Position::game_phase() const {
415 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
417 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
419 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
423 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
424 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
425 /// slider if removing that piece from the board would result in a position where
426 /// square 's' is attacked. For example, a king-attack blocking piece can be either
427 /// a pinned or a discovered check piece, according if its color is the opposite
428 /// or the same of the color of the slider.
430 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
435 // Snipers are sliders that attack 's' when a piece is removed
436 Bitboard snipers = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
437 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
441 Square sniperSq = pop_lsb(&snipers);
442 Bitboard b = between_bb(s, sniperSq) & pieces();
444 if (!more_than_one(b))
447 if (b & pieces(color_of(piece_on(s))))
455 /// Position::attackers_to() computes a bitboard of all pieces which attack a
456 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
458 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
460 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
461 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
462 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
463 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
464 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
465 | (attacks_from<KING>(s) & pieces(KING));
469 /// Position::legal() tests whether a pseudo-legal move is legal
471 bool Position::legal(Move m) const {
475 Color us = sideToMove;
476 Square from = from_sq(m);
478 assert(color_of(moved_piece(m)) == us);
479 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
481 // En passant captures are a tricky special case. Because they are rather
482 // uncommon, we do it simply by testing whether the king is attacked after
484 if (type_of(m) == ENPASSANT)
486 Square ksq = square<KING>(us);
487 Square to = to_sq(m);
488 Square capsq = to - pawn_push(us);
489 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
491 assert(to == ep_square());
492 assert(moved_piece(m) == make_piece(us, PAWN));
493 assert(piece_on(capsq) == make_piece(~us, PAWN));
494 assert(piece_on(to) == NO_PIECE);
496 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
497 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
500 // If the moving piece is a king, check whether the destination
501 // square is attacked by the opponent. Castling moves are checked
502 // for legality during move generation.
503 if (type_of(piece_on(from)) == KING)
504 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
506 // A non-king move is legal if and only if it is not pinned or it
507 // is moving along the ray towards or away from the king.
508 return !(pinned_pieces(us) & from)
509 || aligned(from, to_sq(m), square<KING>(us));
513 /// Position::pseudo_legal() takes a random move and tests whether the move is
514 /// pseudo legal. It is used to validate moves from TT that can be corrupted
515 /// due to SMP concurrent access or hash position key aliasing.
517 bool Position::pseudo_legal(const Move m) const {
519 Color us = sideToMove;
520 Square from = from_sq(m);
521 Square to = to_sq(m);
522 Piece pc = moved_piece(m);
524 // Use a slower but simpler function for uncommon cases
525 if (type_of(m) != NORMAL)
526 return MoveList<LEGAL>(*this).contains(m);
528 // Is not a promotion, so promotion piece must be empty
529 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
532 // If the 'from' square is not occupied by a piece belonging to the side to
533 // move, the move is obviously not legal.
534 if (pc == NO_PIECE || color_of(pc) != us)
537 // The destination square cannot be occupied by a friendly piece
541 // Handle the special case of a pawn move
542 if (type_of(pc) == PAWN)
544 // We have already handled promotion moves, so destination
545 // cannot be on the 8th/1st rank.
546 if (rank_of(to) == relative_rank(us, RANK_8))
549 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
550 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
551 && !( (from + 2 * pawn_push(us) == to) // Not a double push
552 && (rank_of(from) == relative_rank(us, RANK_2))
554 && empty(to - pawn_push(us))))
557 else if (!(attacks_from(pc, from) & to))
560 // Evasions generator already takes care to avoid some kind of illegal moves
561 // and legal() relies on this. We therefore have to take care that the same
562 // kind of moves are filtered out here.
565 if (type_of(pc) != KING)
567 // Double check? In this case a king move is required
568 if (more_than_one(checkers()))
571 // Our move must be a blocking evasion or a capture of the checking piece
572 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
575 // In case of king moves under check we have to remove king so as to catch
576 // invalid moves like b1a1 when opposite queen is on c1.
577 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
585 /// Position::gives_check() tests whether a pseudo-legal move gives a check
587 bool Position::gives_check(Move m) const {
590 assert(color_of(moved_piece(m)) == sideToMove);
592 Square from = from_sq(m);
593 Square to = to_sq(m);
595 // Is there a direct check?
596 if (st->checkSquares[type_of(piece_on(from))] & to)
599 // Is there a discovered check?
600 if ( (discovered_check_candidates() & from)
601 && !aligned(from, to, square<KING>(~sideToMove)))
610 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
612 // En passant capture with check? We have already handled the case
613 // of direct checks and ordinary discovered check, so the only case we
614 // need to handle is the unusual case of a discovered check through
615 // the captured pawn.
618 Square capsq = make_square(file_of(to), rank_of(from));
619 Bitboard b = (pieces() ^ from ^ capsq) | to;
621 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
622 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
627 Square rfrom = to; // Castling is encoded as 'King captures the rook'
628 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
629 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
631 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
632 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
641 /// Position::do_move() makes a move, and saves all information necessary
642 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
643 /// moves should be filtered out before this function is called.
645 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
648 assert(&newSt != st);
651 Key k = st->key ^ Zobrist::side;
653 // Copy some fields of the old state to our new StateInfo object except the
654 // ones which are going to be recalculated from scratch anyway and then switch
655 // our state pointer to point to the new (ready to be updated) state.
656 std::memcpy(&newSt, st, offsetof(StateInfo, key));
660 // Increment ply counters. In particular, rule50 will be reset to zero later on
661 // in case of a capture or a pawn move.
666 Color us = sideToMove;
668 Square from = from_sq(m);
669 Square to = to_sq(m);
670 Piece pc = piece_on(from);
671 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
673 assert(color_of(pc) == us);
674 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
675 assert(type_of(captured) != KING);
677 if (type_of(m) == CASTLING)
679 assert(pc == make_piece(us, KING));
680 assert(captured == make_piece(us, ROOK));
683 do_castling<true>(us, from, to, rfrom, rto);
685 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
686 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
694 // If the captured piece is a pawn, update pawn hash key, otherwise
695 // update non-pawn material.
696 if (type_of(captured) == PAWN)
698 if (type_of(m) == ENPASSANT)
700 capsq -= pawn_push(us);
702 assert(pc == make_piece(us, PAWN));
703 assert(to == st->epSquare);
704 assert(relative_rank(us, to) == RANK_6);
705 assert(piece_on(to) == NO_PIECE);
706 assert(piece_on(capsq) == make_piece(them, PAWN));
708 board[capsq] = NO_PIECE; // Not done by remove_piece()
711 st->pawnKey ^= Zobrist::psq[captured][capsq];
714 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
716 // Update board and piece lists
717 remove_piece(captured, capsq);
719 // Update material hash key and prefetch access to materialTable
720 k ^= Zobrist::psq[captured][capsq];
721 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
722 prefetch(thisThread->materialTable[st->materialKey]);
724 // Update incremental scores
725 st->psq -= PSQT::psq[captured][capsq];
727 // Reset rule 50 counter
732 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
734 // Reset en passant square
735 if (st->epSquare != SQ_NONE)
737 k ^= Zobrist::enpassant[file_of(st->epSquare)];
738 st->epSquare = SQ_NONE;
741 // Update castling rights if needed
742 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
744 int cr = castlingRightsMask[from] | castlingRightsMask[to];
745 k ^= Zobrist::castling[st->castlingRights & cr];
746 st->castlingRights &= ~cr;
749 // Move the piece. The tricky Chess960 castling is handled earlier
750 if (type_of(m) != CASTLING)
751 move_piece(pc, from, to);
753 // If the moving piece is a pawn do some special extra work
754 if (type_of(pc) == PAWN)
756 // Set en-passant square if the moved pawn can be captured
757 if ( (int(to) ^ int(from)) == 16
758 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
760 st->epSquare = (from + to) / 2;
761 k ^= Zobrist::enpassant[file_of(st->epSquare)];
764 else if (type_of(m) == PROMOTION)
766 Piece promotion = make_piece(us, promotion_type(m));
768 assert(relative_rank(us, to) == RANK_8);
769 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
771 remove_piece(pc, to);
772 put_piece(promotion, to);
775 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
776 st->pawnKey ^= Zobrist::psq[pc][to];
777 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
778 ^ Zobrist::psq[pc][pieceCount[pc]];
780 // Update incremental score
781 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
784 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
787 // Update pawn hash key and prefetch access to pawnsTable
788 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
789 prefetch(thisThread->pawnsTable[st->pawnKey]);
791 // Reset rule 50 draw counter
795 // Update incremental scores
796 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
799 st->capturedPiece = captured;
801 // Update the key with the final value
804 // Calculate checkers bitboard (if move gives check)
805 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
807 sideToMove = ~sideToMove;
809 // Update king attacks used for fast check detection
816 /// Position::undo_move() unmakes a move. When it returns, the position should
817 /// be restored to exactly the same state as before the move was made.
819 void Position::undo_move(Move m) {
823 sideToMove = ~sideToMove;
825 Color us = sideToMove;
826 Square from = from_sq(m);
827 Square to = to_sq(m);
828 Piece pc = piece_on(to);
830 assert(empty(from) || type_of(m) == CASTLING);
831 assert(type_of(st->capturedPiece) != KING);
833 if (type_of(m) == PROMOTION)
835 assert(relative_rank(us, to) == RANK_8);
836 assert(type_of(pc) == promotion_type(m));
837 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
839 remove_piece(pc, to);
840 pc = make_piece(us, PAWN);
844 if (type_of(m) == CASTLING)
847 do_castling<false>(us, from, to, rfrom, rto);
851 move_piece(pc, to, from); // Put the piece back at the source square
853 if (st->capturedPiece)
857 if (type_of(m) == ENPASSANT)
859 capsq -= pawn_push(us);
861 assert(type_of(pc) == PAWN);
862 assert(to == st->previous->epSquare);
863 assert(relative_rank(us, to) == RANK_6);
864 assert(piece_on(capsq) == NO_PIECE);
865 assert(st->capturedPiece == make_piece(~us, PAWN));
868 put_piece(st->capturedPiece, capsq); // Restore the captured piece
872 // Finally point our state pointer back to the previous state
880 /// Position::do_castling() is a helper used to do/undo a castling move. This
881 /// is a bit tricky in Chess960 where from/to squares can overlap.
883 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
885 bool kingSide = to > from;
886 rfrom = to; // Castling is encoded as "king captures friendly rook"
887 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
888 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
890 // Remove both pieces first since squares could overlap in Chess960
891 remove_piece(make_piece(us, KING), Do ? from : to);
892 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
893 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
894 put_piece(make_piece(us, KING), Do ? to : from);
895 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
899 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
900 /// the side to move without executing any move on the board.
902 void Position::do_null_move(StateInfo& newSt) {
905 assert(&newSt != st);
907 std::memcpy(&newSt, st, sizeof(StateInfo));
911 if (st->epSquare != SQ_NONE)
913 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
914 st->epSquare = SQ_NONE;
917 st->key ^= Zobrist::side;
918 prefetch(TT.first_entry(st->key));
921 st->pliesFromNull = 0;
923 sideToMove = ~sideToMove;
930 void Position::undo_null_move() {
935 sideToMove = ~sideToMove;
939 /// Position::key_after() computes the new hash key after the given move. Needed
940 /// for speculative prefetch. It doesn't recognize special moves like castling,
941 /// en-passant and promotions.
943 Key Position::key_after(Move m) const {
945 Square from = from_sq(m);
946 Square to = to_sq(m);
947 Piece pc = piece_on(from);
948 Piece captured = piece_on(to);
949 Key k = st->key ^ Zobrist::side;
952 k ^= Zobrist::psq[captured][to];
954 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
958 /// Position::see() is a static exchange evaluator: It tries to estimate the
959 /// material gain or loss resulting from a move.
961 Value Position::see_sign(Move m) const {
965 // Early return if SEE cannot be negative because captured piece value
966 // is not less then capturing one. Note that king moves always return
967 // here because king midgame value is set to 0.
968 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
969 return VALUE_KNOWN_WIN;
974 Value Position::see(Move m) const {
977 Bitboard occupied, attackers, stmAttackers;
980 PieceType nextVictim;
987 swapList[0] = PieceValue[MG][piece_on(to)];
988 stm = color_of(piece_on(from));
989 occupied = pieces() ^ from;
991 // Castling moves are implemented as king capturing the rook so cannot
992 // be handled correctly. Simply return VALUE_ZERO that is always correct
993 // unless in the rare case the rook ends up under attack.
994 if (type_of(m) == CASTLING)
997 if (type_of(m) == ENPASSANT)
999 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1000 swapList[0] = PieceValue[MG][PAWN];
1003 // Find all attackers to the destination square, with the moving piece
1004 // removed, but possibly an X-ray attacker added behind it.
1005 attackers = attackers_to(to, occupied) & occupied;
1007 // If the opponent has no attackers we are finished
1009 stmAttackers = attackers & pieces(stm);
1010 occupied ^= to; // For the case when captured piece is a pinner
1012 // Don't allow pinned pieces to attack pieces except the king as long all
1013 // pinners are on their original square. When a pinner moves to the
1014 // exchange-square or get captured on it, we fall back to standard SEE behaviour.
1015 if ( (stmAttackers & pinned_pieces(stm))
1016 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1017 stmAttackers &= ~pinned_pieces(stm);
1022 // The destination square is defended, which makes things rather more
1023 // difficult to compute. We proceed by building up a "swap list" containing
1024 // the material gain or loss at each stop in a sequence of captures to the
1025 // destination square, where the sides alternately capture, and always
1026 // capture with the least valuable piece. After each capture, we look for
1027 // new X-ray attacks from behind the capturing piece.
1028 nextVictim = type_of(piece_on(from));
1031 assert(slIndex < 32);
1033 // Add the new entry to the swap list
1034 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][nextVictim];
1036 // Locate and remove the next least valuable attacker
1037 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1039 stmAttackers = attackers & pieces(stm);
1040 if ( nextVictim != KING
1041 && (stmAttackers & pinned_pieces(stm))
1042 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1043 stmAttackers &= ~pinned_pieces(stm);
1047 } while (stmAttackers && (nextVictim != KING || (--slIndex, false))); // Stop before a king capture
1049 // Having built the swap list, we negamax through it to find the best
1050 // achievable score from the point of view of the side to move.
1052 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1058 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1059 /// or by repetition. It does not detect stalemates.
1061 bool Position::is_draw() const {
1063 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1066 StateInfo* stp = st;
1067 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1069 stp = stp->previous->previous;
1071 if (stp->key == st->key)
1072 return true; // Draw at first repetition
1079 /// Position::flip() flips position with the white and black sides reversed. This
1080 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1082 void Position::flip() {
1085 std::stringstream ss(fen());
1087 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1089 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1090 f.insert(0, token + (f.empty() ? " " : "/"));
1093 ss >> token; // Active color
1094 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1096 ss >> token; // Castling availability
1099 std::transform(f.begin(), f.end(), f.begin(),
1100 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1102 ss >> token; // En passant square
1103 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1105 std::getline(ss, token); // Half and full moves
1108 set(f, is_chess960(), st, this_thread());
1110 assert(pos_is_ok());
1114 /// Position::pos_is_ok() performs some consistency checks for the position object.
1115 /// This is meant to be helpful when debugging.
1117 bool Position::pos_is_ok(int* failedStep) const {
1119 const bool Fast = true; // Quick (default) or full check?
1121 enum { Default, King, Bitboards, State, Lists, Castling };
1123 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1128 if (step == Default)
1129 if ( (sideToMove != WHITE && sideToMove != BLACK)
1130 || piece_on(square<KING>(WHITE)) != W_KING
1131 || piece_on(square<KING>(BLACK)) != B_KING
1132 || ( ep_square() != SQ_NONE
1133 && relative_rank(sideToMove, ep_square()) != RANK_6))
1137 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1138 || std::count(board, board + SQUARE_NB, B_KING) != 1
1139 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1142 if (step == Bitboards)
1144 if ( (pieces(WHITE) & pieces(BLACK))
1145 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1148 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1149 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1150 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1158 if (std::memcmp(&si, st, sizeof(StateInfo)))
1163 for (Piece pc : Pieces)
1165 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1168 for (int i = 0; i < pieceCount[pc]; ++i)
1169 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1173 if (step == Castling)
1174 for (Color c = WHITE; c <= BLACK; ++c)
1175 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1177 if (!can_castle(c | s))
1180 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1181 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1182 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))