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 <cstring> // For std::memset, std::memcmp
39 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
46 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
50 const string PieceToChar(" PNBRQK pnbrqk");
52 // min_attacker() is a helper function used by see() to locate the least
53 // valuable attacker for the side to move, remove the attacker we just found
54 // from the bitboards and scan for new X-ray attacks behind it.
57 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
58 Bitboard& occupied, Bitboard& attackers) {
60 Bitboard b = stmAttackers & bb[Pt];
62 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
64 occupied ^= b & ~(b - 1);
66 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
67 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
69 if (Pt == ROOK || Pt == QUEEN)
70 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
72 attackers &= occupied; // After X-ray that may add already processed pieces
77 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
78 return KING; // No need to update bitboards: it is the last cycle
84 /// CheckInfo constructor
86 CheckInfo::CheckInfo(const Position& pos) {
88 Color them = ~pos.side_to_move();
89 ksq = pos.square<KING>(them);
91 pinned = pos.pinned_pieces(pos.side_to_move());
92 dcCandidates = pos.discovered_check_candidates();
94 checkSquares[PAWN] = pos.attacks_from<PAWN>(ksq, them);
95 checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
96 checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);
97 checkSquares[ROOK] = pos.attacks_from<ROOK>(ksq);
98 checkSquares[QUEEN] = checkSquares[BISHOP] | checkSquares[ROOK];
99 checkSquares[KING] = 0;
103 /// operator<<(Position) returns an ASCII representation of the position
105 std::ostream& operator<<(std::ostream& os, const Position& pos) {
107 os << "\n +---+---+---+---+---+---+---+---+\n";
109 for (Rank r = RANK_8; r >= RANK_1; --r)
111 for (File f = FILE_A; f <= FILE_H; ++f)
112 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
114 os << " |\n +---+---+---+---+---+---+---+---+\n";
117 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
118 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
120 for (Bitboard b = pos.checkers(); b; )
121 os << UCI::square(pop_lsb(&b)) << " ";
127 /// Position::init() initializes at startup the various arrays used to compute
130 void Position::init() {
134 for (Color c = WHITE; c <= BLACK; ++c)
135 for (PieceType pt = PAWN; pt <= KING; ++pt)
136 for (Square s = SQ_A1; s <= SQ_H8; ++s)
137 Zobrist::psq[c][pt][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::exclusion = 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 regardless of whether
187 there is a pawn in position to make an en passant capture.
189 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
190 or capture. This is used to determine if a draw can be claimed under the
193 6) Fullmove number. The number of the full move. It starts at 1, and is
194 incremented after Black's move.
197 unsigned char col, row, token;
200 std::istringstream ss(fenStr);
202 std::memset(this, 0, sizeof(Position));
203 std::memset(si, 0, sizeof(StateInfo));
204 std::fill_n(&pieceList[0][0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
209 // 1. Piece placement
210 while ((ss >> token) && !isspace(token))
213 sq += Square(token - '0'); // Advance the given number of files
215 else if (token == '/')
218 else if ((idx = PieceToChar.find(token)) != string::npos)
220 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
227 sideToMove = (token == 'w' ? WHITE : BLACK);
230 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
231 // Shredder-FEN that uses the letters of the columns on which the rooks began
232 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
233 // if an inner rook is associated with the castling right, the castling tag is
234 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
235 while ((ss >> token) && !isspace(token))
238 Color c = islower(token) ? BLACK : WHITE;
239 Piece rook = make_piece(c, ROOK);
241 token = char(toupper(token));
244 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
246 else if (token == 'Q')
247 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
249 else if (token >= 'A' && token <= 'H')
250 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
255 set_castling_right(c, rsq);
258 // 4. En passant square. Ignore if no pawn capture is possible
259 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
260 && ((ss >> row) && (row == '3' || row == '6')))
262 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
264 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
265 st->epSquare = SQ_NONE;
268 st->epSquare = SQ_NONE;
270 // 5-6. Halfmove clock and fullmove number
271 ss >> std::skipws >> st->rule50 >> gamePly;
273 // Convert from fullmove starting from 1 to ply starting from 0,
274 // handle also common incorrect FEN with fullmove = 0.
275 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
277 chess960 = isChess960;
287 /// Position::set_castling_right() is a helper function used to set castling
288 /// rights given the corresponding color and the rook starting square.
290 void Position::set_castling_right(Color c, Square rfrom) {
292 Square kfrom = square<KING>(c);
293 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
294 CastlingRight cr = (c | cs);
296 st->castlingRights |= cr;
297 castlingRightsMask[kfrom] |= cr;
298 castlingRightsMask[rfrom] |= cr;
299 castlingRookSquare[cr] = rfrom;
301 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
302 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
304 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
305 if (s != kfrom && s != rfrom)
306 castlingPath[cr] |= s;
308 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
309 if (s != kfrom && s != rfrom)
310 castlingPath[cr] |= s;
314 /// Position::set_state() computes the hash keys of the position, and other
315 /// data that once computed is updated incrementally as moves are made.
316 /// The function is only used when a new position is set up, and to verify
317 /// the correctness of the StateInfo data when running in debug mode.
319 void Position::set_state(StateInfo* si) const {
321 si->key = si->pawnKey = si->materialKey = 0;
322 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
323 si->psq = SCORE_ZERO;
325 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[color_of(pc)][type_of(pc)][s];
332 si->psq += PSQT::psq[color_of(pc)][type_of(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[color_of(piece_on(s))][PAWN][s];
349 for (Color c = WHITE; c <= BLACK; ++c)
350 for (PieceType pt = PAWN; pt <= KING; ++pt)
351 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
352 si->materialKey ^= Zobrist::psq[c][pt][cnt];
354 for (Color c = WHITE; c <= BLACK; ++c)
355 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
356 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
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::check_blockers() returns a bitboard of all the pieces with color
424 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
425 /// blocks a check if removing that piece from the board would result in a
426 /// position where the king is in check. A check blocking piece can be either a
427 /// pinned or a discovered check piece, according if its color 'c' is the same
428 /// or the opposite of 'kingColor'.
430 Bitboard Position::check_blockers(Color c, Color kingColor) const {
432 Bitboard b, pinners, result = 0;
433 Square ksq = square<KING>(kingColor);
435 // Pinners are sliders that give check when a pinned piece is removed
436 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
437 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
441 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
443 if (!more_than_one(b))
444 result |= b & pieces(c);
450 /// Position::attackers_to() computes a bitboard of all pieces which attack a
451 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
453 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
455 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
456 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
457 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
458 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
459 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
460 | (attacks_from<KING>(s) & pieces(KING));
464 /// Position::legal() tests whether a pseudo-legal move is legal
466 bool Position::legal(Move m, Bitboard pinned) const {
469 assert(pinned == pinned_pieces(sideToMove));
471 Color us = sideToMove;
472 Square from = from_sq(m);
474 assert(color_of(moved_piece(m)) == us);
475 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
477 // En passant captures are a tricky special case. Because they are rather
478 // uncommon, we do it simply by testing whether the king is attacked after
480 if (type_of(m) == ENPASSANT)
482 Square ksq = square<KING>(us);
483 Square to = to_sq(m);
484 Square capsq = to - pawn_push(us);
485 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
487 assert(to == ep_square());
488 assert(moved_piece(m) == make_piece(us, PAWN));
489 assert(piece_on(capsq) == make_piece(~us, PAWN));
490 assert(piece_on(to) == NO_PIECE);
492 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
493 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
496 // If the moving piece is a king, check whether the destination
497 // square is attacked by the opponent. Castling moves are checked
498 // for legality during move generation.
499 if (type_of(piece_on(from)) == KING)
500 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
502 // A non-king move is legal if and only if it is not pinned or it
503 // is moving along the ray towards or away from the king.
506 || aligned(from, to_sq(m), square<KING>(us));
510 /// Position::pseudo_legal() takes a random move and tests whether the move is
511 /// pseudo legal. It is used to validate moves from TT that can be corrupted
512 /// due to SMP concurrent access or hash position key aliasing.
514 bool Position::pseudo_legal(const Move m) const {
516 Color us = sideToMove;
517 Square from = from_sq(m);
518 Square to = to_sq(m);
519 Piece pc = moved_piece(m);
521 // Use a slower but simpler function for uncommon cases
522 if (type_of(m) != NORMAL)
523 return MoveList<LEGAL>(*this).contains(m);
525 // Is not a promotion, so promotion piece must be empty
526 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
529 // If the 'from' square is not occupied by a piece belonging to the side to
530 // move, the move is obviously not legal.
531 if (pc == NO_PIECE || color_of(pc) != us)
534 // The destination square cannot be occupied by a friendly piece
538 // Handle the special case of a pawn move
539 if (type_of(pc) == PAWN)
541 // We have already handled promotion moves, so destination
542 // cannot be on the 8th/1st rank.
543 if (rank_of(to) == relative_rank(us, RANK_8))
546 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
547 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
548 && !( (from + 2 * pawn_push(us) == to) // Not a double push
549 && (rank_of(from) == relative_rank(us, RANK_2))
551 && empty(to - pawn_push(us))))
554 else if (!(attacks_from(pc, from) & to))
557 // Evasions generator already takes care to avoid some kind of illegal moves
558 // and legal() relies on this. We therefore have to take care that the same
559 // kind of moves are filtered out here.
562 if (type_of(pc) != KING)
564 // Double check? In this case a king move is required
565 if (more_than_one(checkers()))
568 // Our move must be a blocking evasion or a capture of the checking piece
569 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
572 // In case of king moves under check we have to remove king so as to catch
573 // invalid moves like b1a1 when opposite queen is on c1.
574 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
582 /// Position::gives_check() tests whether a pseudo-legal move gives a check
584 bool Position::gives_check(Move m, const CheckInfo& ci) const {
587 assert(ci.dcCandidates == discovered_check_candidates());
588 assert(color_of(moved_piece(m)) == sideToMove);
590 Square from = from_sq(m);
591 Square to = to_sq(m);
593 // Is there a direct check?
594 if (ci.checkSquares[type_of(piece_on(from))] & to)
597 // Is there a discovered check?
599 && (ci.dcCandidates & from)
600 && !aligned(from, to, ci.ksq))
609 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
611 // En passant capture with check? We have already handled the case
612 // of direct checks and ordinary discovered check, so the only case we
613 // need to handle is the unusual case of a discovered check through
614 // the captured pawn.
617 Square capsq = make_square(file_of(to), rank_of(from));
618 Bitboard b = (pieces() ^ from ^ capsq) | to;
620 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
621 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
626 Square rfrom = to; // Castling is encoded as 'King captures the rook'
627 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
628 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
630 return (PseudoAttacks[ROOK][rto] & ci.ksq)
631 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
640 /// Position::do_move() makes a move, and saves all information necessary
641 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
642 /// moves should be filtered out before this function is called.
644 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
647 assert(&newSt != st);
650 Key k = st->key ^ Zobrist::side;
652 // Copy some fields of the old state to our new StateInfo object except the
653 // ones which are going to be recalculated from scratch anyway and then switch
654 // our state pointer to point to the new (ready to be updated) state.
655 std::memcpy(&newSt, st, offsetof(StateInfo, key));
659 // Increment ply counters. In particular, rule50 will be reset to zero later on
660 // in case of a capture or a pawn move.
665 Color us = sideToMove;
667 Square from = from_sq(m);
668 Square to = to_sq(m);
669 PieceType pt = type_of(piece_on(from));
670 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
672 assert(color_of(piece_on(from)) == us);
673 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
674 assert(captured != KING);
676 if (type_of(m) == CASTLING)
681 do_castling<true>(us, from, to, rfrom, rto);
683 captured = NO_PIECE_TYPE;
684 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
685 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
692 // If the captured piece is a pawn, update pawn hash key, otherwise
693 // update non-pawn material.
694 if (captured == PAWN)
696 if (type_of(m) == ENPASSANT)
698 capsq -= pawn_push(us);
701 assert(to == st->epSquare);
702 assert(relative_rank(us, to) == RANK_6);
703 assert(piece_on(to) == NO_PIECE);
704 assert(piece_on(capsq) == make_piece(them, PAWN));
706 board[capsq] = NO_PIECE; // Not done by remove_piece()
709 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
712 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
714 // Update board and piece lists
715 remove_piece(them, captured, capsq);
717 // Update material hash key and prefetch access to materialTable
718 k ^= Zobrist::psq[them][captured][capsq];
719 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
720 prefetch(thisThread->materialTable[st->materialKey]);
722 // Update incremental scores
723 st->psq -= PSQT::psq[them][captured][capsq];
725 // Reset rule 50 counter
730 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
732 // Reset en passant square
733 if (st->epSquare != SQ_NONE)
735 k ^= Zobrist::enpassant[file_of(st->epSquare)];
736 st->epSquare = SQ_NONE;
739 // Update castling rights if needed
740 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
742 int cr = castlingRightsMask[from] | castlingRightsMask[to];
743 k ^= Zobrist::castling[st->castlingRights & cr];
744 st->castlingRights &= ~cr;
747 // Move the piece. The tricky Chess960 castling is handled earlier
748 if (type_of(m) != CASTLING)
749 move_piece(us, pt, from, to);
751 // If the moving piece is a pawn do some special extra work
754 // Set en-passant square if the moved pawn can be captured
755 if ( (int(to) ^ int(from)) == 16
756 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
758 st->epSquare = (from + to) / 2;
759 k ^= Zobrist::enpassant[file_of(st->epSquare)];
762 else if (type_of(m) == PROMOTION)
764 PieceType promotion = promotion_type(m);
766 assert(relative_rank(us, to) == RANK_8);
767 assert(promotion >= KNIGHT && promotion <= QUEEN);
769 remove_piece(us, PAWN, to);
770 put_piece(us, promotion, to);
773 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
774 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
775 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
776 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
778 // Update incremental score
779 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
782 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
785 // Update pawn hash key and prefetch access to pawnsTable
786 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
787 prefetch(thisThread->pawnsTable[st->pawnKey]);
789 // Reset rule 50 draw counter
793 // Update incremental scores
794 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
797 st->capturedType = captured;
799 // Update the key with the final value
802 // Calculate checkers bitboard (if move gives check)
803 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
805 sideToMove = ~sideToMove;
811 /// Position::undo_move() unmakes a move. When it returns, the position should
812 /// be restored to exactly the same state as before the move was made.
814 void Position::undo_move(Move m) {
818 sideToMove = ~sideToMove;
820 Color us = sideToMove;
821 Square from = from_sq(m);
822 Square to = to_sq(m);
823 PieceType pt = type_of(piece_on(to));
825 assert(empty(from) || type_of(m) == CASTLING);
826 assert(st->capturedType != KING);
828 if (type_of(m) == PROMOTION)
830 assert(relative_rank(us, to) == RANK_8);
831 assert(pt == promotion_type(m));
832 assert(pt >= KNIGHT && pt <= QUEEN);
834 remove_piece(us, pt, to);
835 put_piece(us, PAWN, to);
839 if (type_of(m) == CASTLING)
842 do_castling<false>(us, from, to, rfrom, rto);
846 move_piece(us, pt, to, from); // Put the piece back at the source square
848 if (st->capturedType)
852 if (type_of(m) == ENPASSANT)
854 capsq -= pawn_push(us);
857 assert(to == st->previous->epSquare);
858 assert(relative_rank(us, to) == RANK_6);
859 assert(piece_on(capsq) == NO_PIECE);
860 assert(st->capturedType == PAWN);
863 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
867 // Finally point our state pointer back to the previous state
875 /// Position::do_castling() is a helper used to do/undo a castling move. This
876 /// is a bit tricky, especially in Chess960.
878 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
880 bool kingSide = to > from;
881 rfrom = to; // Castling is encoded as "king captures friendly rook"
882 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
883 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
885 // Remove both pieces first since squares could overlap in Chess960
886 remove_piece(us, KING, Do ? from : to);
887 remove_piece(us, ROOK, Do ? rfrom : rto);
888 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
889 put_piece(us, KING, Do ? to : from);
890 put_piece(us, ROOK, Do ? rto : rfrom);
894 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
895 /// the side to move without executing any move on the board.
897 void Position::do_null_move(StateInfo& newSt) {
900 assert(&newSt != st);
902 std::memcpy(&newSt, st, sizeof(StateInfo));
906 if (st->epSquare != SQ_NONE)
908 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
909 st->epSquare = SQ_NONE;
912 st->key ^= Zobrist::side;
913 prefetch(TT.first_entry(st->key));
916 st->pliesFromNull = 0;
918 sideToMove = ~sideToMove;
923 void Position::undo_null_move() {
928 sideToMove = ~sideToMove;
932 /// Position::key_after() computes the new hash key after the given move. Needed
933 /// for speculative prefetch. It doesn't recognize special moves like castling,
934 /// en-passant and promotions.
936 Key Position::key_after(Move m) const {
938 Color us = sideToMove;
939 Square from = from_sq(m);
940 Square to = to_sq(m);
941 PieceType pt = type_of(piece_on(from));
942 PieceType captured = type_of(piece_on(to));
943 Key k = st->key ^ Zobrist::side;
946 k ^= Zobrist::psq[~us][captured][to];
948 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
952 /// Position::see() is a static exchange evaluator: It tries to estimate the
953 /// material gain or loss resulting from a move.
955 Value Position::see_sign(Move m) const {
959 // Early return if SEE cannot be negative because captured piece value
960 // is not less then capturing one. Note that king moves always return
961 // here because king midgame value is set to 0.
962 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
963 return VALUE_KNOWN_WIN;
968 Value Position::see(Move m) const {
971 Bitboard occupied, attackers, stmAttackers;
981 swapList[0] = PieceValue[MG][piece_on(to)];
982 stm = color_of(piece_on(from));
983 occupied = pieces() ^ from;
985 // Castling moves are implemented as king capturing the rook so cannot
986 // be handled correctly. Simply return VALUE_ZERO that is always correct
987 // unless in the rare case the rook ends up under attack.
988 if (type_of(m) == CASTLING)
991 if (type_of(m) == ENPASSANT)
993 occupied ^= to - pawn_push(stm); // Remove the captured pawn
994 swapList[0] = PieceValue[MG][PAWN];
997 // Find all attackers to the destination square, with the moving piece
998 // removed, but possibly an X-ray attacker added behind it.
999 attackers = attackers_to(to, occupied) & occupied;
1001 // If the opponent has no attackers we are finished
1003 stmAttackers = attackers & pieces(stm);
1007 // The destination square is defended, which makes things rather more
1008 // difficult to compute. We proceed by building up a "swap list" containing
1009 // the material gain or loss at each stop in a sequence of captures to the
1010 // destination square, where the sides alternately capture, and always
1011 // capture with the least valuable piece. After each capture, we look for
1012 // new X-ray attacks from behind the capturing piece.
1013 captured = type_of(piece_on(from));
1016 assert(slIndex < 32);
1018 // Add the new entry to the swap list
1019 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1021 // Locate and remove the next least valuable attacker
1022 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1024 stmAttackers = attackers & pieces(stm);
1027 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1029 // Having built the swap list, we negamax through it to find the best
1030 // achievable score from the point of view of the side to move.
1032 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1038 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1039 /// or by repetition. It does not detect stalemates.
1041 bool Position::is_draw() const {
1043 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1046 StateInfo* stp = st;
1047 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1049 stp = stp->previous->previous;
1051 if (stp->key == st->key)
1052 return true; // Draw at first repetition
1059 /// Position::flip() flips position with the white and black sides reversed. This
1060 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1062 void Position::flip() {
1065 std::stringstream ss(fen());
1067 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1069 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1070 f.insert(0, token + (f.empty() ? " " : "/"));
1073 ss >> token; // Active color
1074 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1076 ss >> token; // Castling availability
1079 std::transform(f.begin(), f.end(), f.begin(),
1080 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1082 ss >> token; // En passant square
1083 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1085 std::getline(ss, token); // Half and full moves
1088 set(f, is_chess960(), st, this_thread());
1090 assert(pos_is_ok());
1094 /// Position::pos_is_ok() performs some consistency checks for the position object.
1095 /// This is meant to be helpful when debugging.
1097 bool Position::pos_is_ok(int* failedStep) const {
1099 const bool Fast = true; // Quick (default) or full check?
1101 enum { Default, King, Bitboards, State, Lists, Castling };
1103 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1108 if (step == Default)
1109 if ( (sideToMove != WHITE && sideToMove != BLACK)
1110 || piece_on(square<KING>(WHITE)) != W_KING
1111 || piece_on(square<KING>(BLACK)) != B_KING
1112 || ( ep_square() != SQ_NONE
1113 && relative_rank(sideToMove, ep_square()) != RANK_6))
1117 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1118 || std::count(board, board + SQUARE_NB, B_KING) != 1
1119 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1122 if (step == Bitboards)
1124 if ( (pieces(WHITE) & pieces(BLACK))
1125 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1128 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1129 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1130 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1138 if (std::memcmp(&si, st, sizeof(StateInfo)))
1143 for (Color c = WHITE; c <= BLACK; ++c)
1144 for (PieceType pt = PAWN; pt <= KING; ++pt)
1146 if (pieceCount[c][pt] != popcount(pieces(c, pt)))
1149 for (int i = 0; i < pieceCount[c][pt]; ++i)
1150 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1151 || index[pieceList[c][pt][i]] != i)
1155 if (step == Castling)
1156 for (Color c = WHITE; c <= BLACK; ++c)
1157 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1159 if (!can_castle(c | s))
1162 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1163 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1164 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))