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[PIECE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
47 const string PieceToChar(" PNBRQK pnbrqk");
49 // min_attacker() is a helper function used by see() to locate the least
50 // valuable attacker for the side to move, remove the attacker we just found
51 // from the bitboards and scan for new X-ray attacks behind it.
54 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
55 Bitboard& occupied, Bitboard& attackers) {
57 Bitboard b = stmAttackers & bb[Pt];
59 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
61 occupied ^= b & ~(b - 1);
63 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
64 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
66 if (Pt == ROOK || Pt == QUEEN)
67 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
69 attackers &= occupied; // After X-ray that may add already processed pieces
74 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
75 return KING; // No need to update bitboards: it is the last cycle
81 /// operator<<(Position) returns an ASCII representation of the position
83 std::ostream& operator<<(std::ostream& os, const Position& pos) {
85 os << "\n +---+---+---+---+---+---+---+---+\n";
87 for (Rank r = RANK_8; r >= RANK_1; --r)
89 for (File f = FILE_A; f <= FILE_H; ++f)
90 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
92 os << " |\n +---+---+---+---+---+---+---+---+\n";
95 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
96 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
98 for (Bitboard b = pos.checkers(); b; )
99 os << UCI::square(pop_lsb(&b)) << " ";
105 /// Position::init() initializes at startup the various arrays used to compute
108 void Position::init() {
112 for (Piece pc : Pieces)
113 for (Square s = SQ_A1; s <= SQ_H8; ++s)
114 Zobrist::psq[pc][s] = rng.rand<Key>();
116 for (File f = FILE_A; f <= FILE_H; ++f)
117 Zobrist::enpassant[f] = rng.rand<Key>();
119 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
121 Zobrist::castling[cr] = 0;
125 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
126 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
130 Zobrist::side = rng.rand<Key>();
134 /// Position::set() initializes the position object with the given FEN string.
135 /// This function is not very robust - make sure that input FENs are correct,
136 /// this is assumed to be the responsibility of the GUI.
138 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
140 A FEN string defines a particular position using only the ASCII character set.
142 A FEN string contains six fields separated by a space. The fields are:
144 1) Piece placement (from white's perspective). Each rank is described, starting
145 with rank 8 and ending with rank 1. Within each rank, the contents of each
146 square are described from file A through file H. Following the Standard
147 Algebraic Notation (SAN), each piece is identified by a single letter taken
148 from the standard English names. White pieces are designated using upper-case
149 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
150 noted using digits 1 through 8 (the number of blank squares), and "/"
153 2) Active color. "w" means white moves next, "b" means black.
155 3) Castling availability. If neither side can castle, this is "-". Otherwise,
156 this has one or more letters: "K" (White can castle kingside), "Q" (White
157 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
158 can castle queenside).
160 4) En passant target square (in algebraic notation). If there's no en passant
161 target square, this is "-". If a pawn has just made a 2-square move, this
162 is the position "behind" the pawn. This is recorded regardless of whether
163 there is a pawn in position to make an en passant capture.
165 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
166 or capture. This is used to determine if a draw can be claimed under the
169 6) Fullmove number. The number of the full move. It starts at 1, and is
170 incremented after Black's move.
173 unsigned char col, row, token;
176 std::istringstream ss(fenStr);
178 std::memset(this, 0, sizeof(Position));
179 std::memset(si, 0, sizeof(StateInfo));
180 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
185 // 1. Piece placement
186 while ((ss >> token) && !isspace(token))
189 sq += Square(token - '0'); // Advance the given number of files
191 else if (token == '/')
194 else if ((idx = PieceToChar.find(token)) != string::npos)
196 put_piece(Piece(idx), sq);
203 sideToMove = (token == 'w' ? WHITE : BLACK);
206 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
207 // Shredder-FEN that uses the letters of the columns on which the rooks began
208 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
209 // if an inner rook is associated with the castling right, the castling tag is
210 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
211 while ((ss >> token) && !isspace(token))
214 Color c = islower(token) ? BLACK : WHITE;
215 Piece rook = make_piece(c, ROOK);
217 token = char(toupper(token));
220 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
222 else if (token == 'Q')
223 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
225 else if (token >= 'A' && token <= 'H')
226 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
231 set_castling_right(c, rsq);
234 // 4. En passant square. Ignore if no pawn capture is possible
235 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
236 && ((ss >> row) && (row == '3' || row == '6')))
238 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
240 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
241 st->epSquare = SQ_NONE;
244 st->epSquare = SQ_NONE;
246 // 5-6. Halfmove clock and fullmove number
247 ss >> std::skipws >> st->rule50 >> gamePly;
249 // Convert from fullmove starting from 1 to ply starting from 0,
250 // handle also common incorrect FEN with fullmove = 0.
251 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
253 chess960 = isChess960;
263 /// Position::set_castling_right() is a helper function used to set castling
264 /// rights given the corresponding color and the rook starting square.
266 void Position::set_castling_right(Color c, Square rfrom) {
268 Square kfrom = square<KING>(c);
269 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
270 CastlingRight cr = (c | cs);
272 st->castlingRights |= cr;
273 castlingRightsMask[kfrom] |= cr;
274 castlingRightsMask[rfrom] |= cr;
275 castlingRookSquare[cr] = rfrom;
277 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
278 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
280 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
281 if (s != kfrom && s != rfrom)
282 castlingPath[cr] |= s;
284 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
285 if (s != kfrom && s != rfrom)
286 castlingPath[cr] |= s;
290 /// Position::set_check_info() sets king attacks to detect if a move gives check
292 void Position::set_check_info(StateInfo* si) const {
294 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
295 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
297 Square ksq = square<KING>(~sideToMove);
299 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
300 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
301 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
302 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
303 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
304 si->checkSquares[KING] = 0;
308 /// Position::set_state() computes the hash keys of the position, and other
309 /// data that once computed is updated incrementally as moves are made.
310 /// The function is only used when a new position is set up, and to verify
311 /// the correctness of the StateInfo data when running in debug mode.
313 void Position::set_state(StateInfo* si) const {
315 si->key = si->pawnKey = si->materialKey = 0;
316 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
317 si->psq = SCORE_ZERO;
318 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
322 for (Bitboard b = pieces(); b; )
324 Square s = pop_lsb(&b);
325 Piece pc = piece_on(s);
326 si->key ^= Zobrist::psq[pc][s];
327 si->psq += PSQT::psq[pc][s];
330 if (si->epSquare != SQ_NONE)
331 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
333 if (sideToMove == BLACK)
334 si->key ^= Zobrist::side;
336 si->key ^= Zobrist::castling[si->castlingRights];
338 for (Bitboard b = pieces(PAWN); b; )
340 Square s = pop_lsb(&b);
341 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
344 for (Piece pc : Pieces)
346 if (type_of(pc) != PAWN && type_of(pc) != KING)
347 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
349 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
350 si->materialKey ^= Zobrist::psq[pc][cnt];
355 /// Position::fen() returns a FEN representation of the position. In case of
356 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
358 const string Position::fen() const {
361 std::ostringstream ss;
363 for (Rank r = RANK_8; r >= RANK_1; --r)
365 for (File f = FILE_A; f <= FILE_H; ++f)
367 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
374 ss << PieceToChar[piece_on(make_square(f, r))];
381 ss << (sideToMove == WHITE ? " w " : " b ");
383 if (can_castle(WHITE_OO))
384 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
386 if (can_castle(WHITE_OOO))
387 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
389 if (can_castle(BLACK_OO))
390 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
392 if (can_castle(BLACK_OOO))
393 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
395 if (!can_castle(WHITE) && !can_castle(BLACK))
398 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
399 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
405 /// Position::game_phase() calculates the game phase interpolating total non-pawn
406 /// material between endgame and midgame limits.
408 Phase Position::game_phase() const {
410 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
412 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
414 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
418 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
419 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
420 /// slider if removing that piece from the board would result in a position where
421 /// square 's' is attacked. For example, a king-attack blocking piece can be either
422 /// a pinned or a discovered check piece, according if its color is the opposite
423 /// or the same of the color of the slider. The pinners bitboard get filled with
424 /// real and potential pinners.
426 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
428 Bitboard b, p, result = 0;
430 // Pinners are sliders that attack 's' when a pinned piece is removed
431 pinners = p = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
432 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
436 b = between_bb(s, pop_lsb(&p)) & pieces();
438 if (!more_than_one(b))
445 /// Position::attackers_to() computes a bitboard of all pieces which attack a
446 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
448 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
450 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
451 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
452 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
453 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
454 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
455 | (attacks_from<KING>(s) & pieces(KING));
459 /// Position::legal() tests whether a pseudo-legal move is legal
461 bool Position::legal(Move m) const {
465 Color us = sideToMove;
466 Square from = from_sq(m);
468 assert(color_of(moved_piece(m)) == us);
469 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
471 // En passant captures are a tricky special case. Because they are rather
472 // uncommon, we do it simply by testing whether the king is attacked after
474 if (type_of(m) == ENPASSANT)
476 Square ksq = square<KING>(us);
477 Square to = to_sq(m);
478 Square capsq = to - pawn_push(us);
479 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
481 assert(to == ep_square());
482 assert(moved_piece(m) == make_piece(us, PAWN));
483 assert(piece_on(capsq) == make_piece(~us, PAWN));
484 assert(piece_on(to) == NO_PIECE);
486 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
487 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
490 // If the moving piece is a king, check whether the destination
491 // square is attacked by the opponent. Castling moves are checked
492 // for legality during move generation.
493 if (type_of(piece_on(from)) == KING)
494 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
496 // A non-king move is legal if and only if it is not pinned or it
497 // is moving along the ray towards or away from the king.
498 return !(pinned_pieces(us) & from)
499 || aligned(from, to_sq(m), square<KING>(us));
503 /// Position::pseudo_legal() takes a random move and tests whether the move is
504 /// pseudo legal. It is used to validate moves from TT that can be corrupted
505 /// due to SMP concurrent access or hash position key aliasing.
507 bool Position::pseudo_legal(const Move m) const {
509 Color us = sideToMove;
510 Square from = from_sq(m);
511 Square to = to_sq(m);
512 Piece pc = moved_piece(m);
514 // Use a slower but simpler function for uncommon cases
515 if (type_of(m) != NORMAL)
516 return MoveList<LEGAL>(*this).contains(m);
518 // Is not a promotion, so promotion piece must be empty
519 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
522 // If the 'from' square is not occupied by a piece belonging to the side to
523 // move, the move is obviously not legal.
524 if (pc == NO_PIECE || color_of(pc) != us)
527 // The destination square cannot be occupied by a friendly piece
531 // Handle the special case of a pawn move
532 if (type_of(pc) == PAWN)
534 // We have already handled promotion moves, so destination
535 // cannot be on the 8th/1st rank.
536 if (rank_of(to) == relative_rank(us, RANK_8))
539 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
540 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
541 && !( (from + 2 * pawn_push(us) == to) // Not a double push
542 && (rank_of(from) == relative_rank(us, RANK_2))
544 && empty(to - pawn_push(us))))
547 else if (!(attacks_from(pc, from) & to))
550 // Evasions generator already takes care to avoid some kind of illegal moves
551 // and legal() relies on this. We therefore have to take care that the same
552 // kind of moves are filtered out here.
555 if (type_of(pc) != KING)
557 // Double check? In this case a king move is required
558 if (more_than_one(checkers()))
561 // Our move must be a blocking evasion or a capture of the checking piece
562 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
565 // In case of king moves under check we have to remove king so as to catch
566 // invalid moves like b1a1 when opposite queen is on c1.
567 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
575 /// Position::gives_check() tests whether a pseudo-legal move gives a check
577 bool Position::gives_check(Move m) const {
580 assert(color_of(moved_piece(m)) == sideToMove);
582 Square from = from_sq(m);
583 Square to = to_sq(m);
585 // Is there a direct check?
586 if (st->checkSquares[type_of(piece_on(from))] & to)
589 // Is there a discovered check?
590 if ( (discovered_check_candidates() & from)
591 && !aligned(from, to, square<KING>(~sideToMove)))
600 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
602 // En passant capture with check? We have already handled the case
603 // of direct checks and ordinary discovered check, so the only case we
604 // need to handle is the unusual case of a discovered check through
605 // the captured pawn.
608 Square capsq = make_square(file_of(to), rank_of(from));
609 Bitboard b = (pieces() ^ from ^ capsq) | to;
611 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
612 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
617 Square rfrom = to; // Castling is encoded as 'King captures the rook'
618 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
619 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
621 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
622 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
631 /// Position::do_move() makes a move, and saves all information necessary
632 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
633 /// moves should be filtered out before this function is called.
635 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
638 assert(&newSt != st);
641 Key k = st->key ^ Zobrist::side;
643 // Copy some fields of the old state to our new StateInfo object except the
644 // ones which are going to be recalculated from scratch anyway and then switch
645 // our state pointer to point to the new (ready to be updated) state.
646 std::memcpy(&newSt, st, offsetof(StateInfo, key));
650 // Increment ply counters. In particular, rule50 will be reset to zero later on
651 // in case of a capture or a pawn move.
656 Color us = sideToMove;
658 Square from = from_sq(m);
659 Square to = to_sq(m);
660 Piece pc = piece_on(from);
661 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
663 assert(color_of(pc) == us);
664 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
665 assert(type_of(captured) != KING);
667 if (type_of(m) == CASTLING)
669 assert(pc == make_piece(us, KING));
670 assert(captured == make_piece(us, ROOK));
673 do_castling<true>(us, from, to, rfrom, rto);
675 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
676 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
684 // If the captured piece is a pawn, update pawn hash key, otherwise
685 // update non-pawn material.
686 if (type_of(captured) == PAWN)
688 if (type_of(m) == ENPASSANT)
690 capsq -= pawn_push(us);
692 assert(pc == make_piece(us, PAWN));
693 assert(to == st->epSquare);
694 assert(relative_rank(us, to) == RANK_6);
695 assert(piece_on(to) == NO_PIECE);
696 assert(piece_on(capsq) == make_piece(them, PAWN));
698 board[capsq] = NO_PIECE; // Not done by remove_piece()
701 st->pawnKey ^= Zobrist::psq[captured][capsq];
704 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
706 // Update board and piece lists
707 remove_piece(captured, capsq);
709 // Update material hash key and prefetch access to materialTable
710 k ^= Zobrist::psq[captured][capsq];
711 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
712 prefetch(thisThread->materialTable[st->materialKey]);
714 // Update incremental scores
715 st->psq -= PSQT::psq[captured][capsq];
717 // Reset rule 50 counter
722 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
724 // Reset en passant square
725 if (st->epSquare != SQ_NONE)
727 k ^= Zobrist::enpassant[file_of(st->epSquare)];
728 st->epSquare = SQ_NONE;
731 // Update castling rights if needed
732 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
734 int cr = castlingRightsMask[from] | castlingRightsMask[to];
735 k ^= Zobrist::castling[st->castlingRights & cr];
736 st->castlingRights &= ~cr;
739 // Move the piece. The tricky Chess960 castling is handled earlier
740 if (type_of(m) != CASTLING)
741 move_piece(pc, from, to);
743 // If the moving piece is a pawn do some special extra work
744 if (type_of(pc) == PAWN)
746 // Set en-passant square if the moved pawn can be captured
747 if ( (int(to) ^ int(from)) == 16
748 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
750 st->epSquare = (from + to) / 2;
751 k ^= Zobrist::enpassant[file_of(st->epSquare)];
754 else if (type_of(m) == PROMOTION)
756 Piece promotion = make_piece(us, promotion_type(m));
758 assert(relative_rank(us, to) == RANK_8);
759 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
761 remove_piece(pc, to);
762 put_piece(promotion, to);
765 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
766 st->pawnKey ^= Zobrist::psq[pc][to];
767 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
768 ^ Zobrist::psq[pc][pieceCount[pc]];
770 // Update incremental score
771 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
774 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
777 // Update pawn hash key and prefetch access to pawnsTable
778 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
779 prefetch(thisThread->pawnsTable[st->pawnKey]);
781 // Reset rule 50 draw counter
785 // Update incremental scores
786 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
789 st->capturedPiece = captured;
791 // Update the key with the final value
794 // Calculate checkers bitboard (if move gives check)
795 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
797 sideToMove = ~sideToMove;
799 // Update king attacks used for fast check detection
806 /// Position::undo_move() unmakes a move. When it returns, the position should
807 /// be restored to exactly the same state as before the move was made.
809 void Position::undo_move(Move m) {
813 sideToMove = ~sideToMove;
815 Color us = sideToMove;
816 Square from = from_sq(m);
817 Square to = to_sq(m);
818 Piece pc = piece_on(to);
820 assert(empty(from) || type_of(m) == CASTLING);
821 assert(type_of(st->capturedPiece) != KING);
823 if (type_of(m) == PROMOTION)
825 assert(relative_rank(us, to) == RANK_8);
826 assert(type_of(pc) == promotion_type(m));
827 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
829 remove_piece(pc, to);
830 pc = make_piece(us, PAWN);
834 if (type_of(m) == CASTLING)
837 do_castling<false>(us, from, to, rfrom, rto);
841 move_piece(pc, to, from); // Put the piece back at the source square
843 if (st->capturedPiece)
847 if (type_of(m) == ENPASSANT)
849 capsq -= pawn_push(us);
851 assert(type_of(pc) == PAWN);
852 assert(to == st->previous->epSquare);
853 assert(relative_rank(us, to) == RANK_6);
854 assert(piece_on(capsq) == NO_PIECE);
855 assert(st->capturedPiece == make_piece(~us, PAWN));
858 put_piece(st->capturedPiece, capsq); // Restore the captured piece
862 // Finally point our state pointer back to the previous state
870 /// Position::do_castling() is a helper used to do/undo a castling move. This
871 /// is a bit tricky in Chess960 where from/to squares can overlap.
873 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
875 bool kingSide = to > from;
876 rfrom = to; // Castling is encoded as "king captures friendly rook"
877 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
878 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
880 // Remove both pieces first since squares could overlap in Chess960
881 remove_piece(make_piece(us, KING), Do ? from : to);
882 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
883 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
884 put_piece(make_piece(us, KING), Do ? to : from);
885 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
889 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
890 /// the side to move without executing any move on the board.
892 void Position::do_null_move(StateInfo& newSt) {
895 assert(&newSt != st);
897 std::memcpy(&newSt, st, sizeof(StateInfo));
901 if (st->epSquare != SQ_NONE)
903 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
904 st->epSquare = SQ_NONE;
907 st->key ^= Zobrist::side;
908 prefetch(TT.first_entry(st->key));
911 st->pliesFromNull = 0;
913 sideToMove = ~sideToMove;
920 void Position::undo_null_move() {
925 sideToMove = ~sideToMove;
929 /// Position::key_after() computes the new hash key after the given move. Needed
930 /// for speculative prefetch. It doesn't recognize special moves like castling,
931 /// en-passant and promotions.
933 Key Position::key_after(Move m) const {
935 Square from = from_sq(m);
936 Square to = to_sq(m);
937 Piece pc = piece_on(from);
938 Piece captured = piece_on(to);
939 Key k = st->key ^ Zobrist::side;
942 k ^= Zobrist::psq[captured][to];
944 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
948 /// Position::see() is a static exchange evaluator: It tries to estimate the
949 /// material gain or loss resulting from a move.
951 Value Position::see_sign(Move m) const {
955 // Early return if SEE cannot be negative because captured piece value
956 // is not less then capturing one. Note that king moves always return
957 // here because king midgame value is set to 0.
958 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
959 return VALUE_KNOWN_WIN;
964 Value Position::see(Move m) const {
967 Bitboard occupied, attackers, stmAttackers;
977 swapList[0] = PieceValue[MG][piece_on(to)];
978 stm = color_of(piece_on(from));
979 occupied = pieces() ^ from;
981 // Castling moves are implemented as king capturing the rook so cannot
982 // be handled correctly. Simply return VALUE_ZERO that is always correct
983 // unless in the rare case the rook ends up under attack.
984 if (type_of(m) == CASTLING)
987 if (type_of(m) == ENPASSANT)
989 occupied ^= to - pawn_push(stm); // Remove the captured pawn
990 swapList[0] = PieceValue[MG][PAWN];
993 // Find all attackers to the destination square, with the moving piece
994 // removed, but possibly an X-ray attacker added behind it.
995 attackers = attackers_to(to, occupied) & occupied;
997 // If the opponent has no attackers we are finished
999 stmAttackers = attackers & pieces(stm);
1000 occupied ^= to; // For the case when captured piece is a pinner
1002 // Don't allow pinned pieces to attack as long all pinners (this includes also
1003 // potential ones) are on their original square. When a pinner moves to the
1004 // exchange-square or get captured on it, we fall back to standard SEE behaviour.
1005 if ( (stmAttackers & pinned_pieces(stm))
1006 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1007 stmAttackers &= ~pinned_pieces(stm);
1012 // The destination square is defended, which makes things rather more
1013 // difficult to compute. We proceed by building up a "swap list" containing
1014 // the material gain or loss at each stop in a sequence of captures to the
1015 // destination square, where the sides alternately capture, and always
1016 // capture with the least valuable piece. After each capture, we look for
1017 // new X-ray attacks from behind the capturing piece.
1018 captured = type_of(piece_on(from));
1021 assert(slIndex < 32);
1023 // Add the new entry to the swap list
1024 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1026 // Locate and remove the next least valuable attacker
1027 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1029 stmAttackers = attackers & pieces(stm);
1030 if ( (stmAttackers & pinned_pieces(stm))
1031 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1032 stmAttackers &= ~pinned_pieces(stm);
1036 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1038 // Having built the swap list, we negamax through it to find the best
1039 // achievable score from the point of view of the side to move.
1041 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1047 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1048 /// or by repetition. It does not detect stalemates.
1050 bool Position::is_draw() const {
1052 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1055 StateInfo* stp = st;
1056 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1058 stp = stp->previous->previous;
1060 if (stp->key == st->key)
1061 return true; // Draw at first repetition
1068 /// Position::flip() flips position with the white and black sides reversed. This
1069 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1071 void Position::flip() {
1074 std::stringstream ss(fen());
1076 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1078 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1079 f.insert(0, token + (f.empty() ? " " : "/"));
1082 ss >> token; // Active color
1083 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1085 ss >> token; // Castling availability
1088 std::transform(f.begin(), f.end(), f.begin(),
1089 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1091 ss >> token; // En passant square
1092 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1094 std::getline(ss, token); // Half and full moves
1097 set(f, is_chess960(), st, this_thread());
1099 assert(pos_is_ok());
1103 /// Position::pos_is_ok() performs some consistency checks for the position object.
1104 /// This is meant to be helpful when debugging.
1106 bool Position::pos_is_ok(int* failedStep) const {
1108 const bool Fast = true; // Quick (default) or full check?
1110 enum { Default, King, Bitboards, State, Lists, Castling };
1112 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1117 if (step == Default)
1118 if ( (sideToMove != WHITE && sideToMove != BLACK)
1119 || piece_on(square<KING>(WHITE)) != W_KING
1120 || piece_on(square<KING>(BLACK)) != B_KING
1121 || ( ep_square() != SQ_NONE
1122 && relative_rank(sideToMove, ep_square()) != RANK_6))
1126 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1127 || std::count(board, board + SQUARE_NB, B_KING) != 1
1128 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1131 if (step == Bitboards)
1133 if ( (pieces(WHITE) & pieces(BLACK))
1134 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1137 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1138 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1139 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1147 if (std::memcmp(&si, st, sizeof(StateInfo)))
1152 for (Piece pc : Pieces)
1154 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1157 for (int i = 0; i < pieceCount[pc]; ++i)
1158 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1162 if (step == Castling)
1163 for (Color c = WHITE; c <= BLACK; ++c)
1164 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1166 if (!can_castle(c | s))
1169 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1170 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1171 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))