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
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 #include <cstring> // For std::memset
37 Value PieceValue[PHASE_NB][PIECE_NB] = {
38 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
39 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
43 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
44 Key enpassant[FILE_NB];
45 Key castling[CASTLING_RIGHT_NB];
50 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
54 const string PieceToChar(" PNBRQK pnbrqk");
55 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
57 // min_attacker() is a helper function used by see() to locate the least
58 // valuable attacker for the side to move, remove the attacker we just found
59 // from the bitboards and scan for new X-ray attacks behind it.
61 template<int Pt> FORCE_INLINE
62 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
63 Bitboard& occupied, Bitboard& attackers) {
65 Bitboard b = stmAttackers & bb[Pt];
67 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
69 occupied ^= b & ~(b - 1);
71 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
72 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
74 if (Pt == ROOK || Pt == QUEEN)
75 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
77 attackers &= occupied; // After X-ray that may add already processed pieces
81 template<> FORCE_INLINE
82 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
83 return KING; // No need to update bitboards: it is the last cycle
91 CheckInfo::CheckInfo(const Position& pos) {
93 Color them = ~pos.side_to_move();
94 ksq = pos.king_square(them);
96 pinned = pos.pinned_pieces(pos.side_to_move());
97 dcCandidates = pos.discovered_check_candidates();
99 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
100 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
101 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
102 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
103 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
108 /// operator<<(Position) returns an ASCII representation of the position
110 std::ostream& operator<<(std::ostream& os, const Position& pos) {
112 os << "\n +---+---+---+---+---+---+---+---+\n";
114 for (Rank r = RANK_8; r >= RANK_1; --r)
116 for (File f = FILE_A; f <= FILE_H; ++f)
117 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
119 os << " |\n +---+---+---+---+---+---+---+---+\n";
122 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
123 << std::setfill('0') << std::setw(16) << pos.st->key << std::dec << "\nCheckers: ";
125 for (Bitboard b = pos.checkers(); b; )
126 os << UCI::square(pop_lsb(&b)) << " ";
132 /// Position::init() initializes at startup the various arrays used to compute
133 /// hash keys and the piece square tables. The latter is a two-step operation:
134 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
135 /// Secondly, the black halves of the tables are initialized by flipping and
136 /// changing the sign of the white scores.
138 void Position::init() {
142 for (Color c = WHITE; c <= BLACK; ++c)
143 for (PieceType pt = PAWN; pt <= KING; ++pt)
144 for (Square s = SQ_A1; s <= SQ_H8; ++s)
145 Zobrist::psq[c][pt][s] = rng.rand<Key>();
147 for (File f = FILE_A; f <= FILE_H; ++f)
148 Zobrist::enpassant[f] = rng.rand<Key>();
150 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
155 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
156 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
160 Zobrist::side = rng.rand<Key>();
161 Zobrist::exclusion = rng.rand<Key>();
163 for (PieceType pt = PAWN; pt <= KING; ++pt)
165 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
166 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
168 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
170 for (Square s = SQ_A1; s <= SQ_H8; ++s)
172 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
173 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
179 /// Position::operator=() creates a copy of 'pos' but detaching the state pointer
180 /// from the source to be self-consistent and not depending on any external data.
182 Position& Position::operator=(const Position& pos) {
184 std::memcpy(this, &pos, sizeof(Position));
195 /// Position::clear() erases the position object to a pristine state, with an
196 /// empty board, white to move, and no castling rights.
198 void Position::clear() {
200 std::memset(this, 0, sizeof(Position));
201 startState.epSquare = SQ_NONE;
204 for (int i = 0; i < PIECE_TYPE_NB; ++i)
205 for (int j = 0; j < 16; ++j)
206 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
210 /// Position::set() initializes the position object with the given FEN string.
211 /// This function is not very robust - make sure that input FENs are correct,
212 /// this is assumed to be the responsibility of the GUI.
214 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
216 A FEN string defines a particular position using only the ASCII character set.
218 A FEN string contains six fields separated by a space. The fields are:
220 1) Piece placement (from white's perspective). Each rank is described, starting
221 with rank 8 and ending with rank 1. Within each rank, the contents of each
222 square are described from file A through file H. Following the Standard
223 Algebraic Notation (SAN), each piece is identified by a single letter taken
224 from the standard English names. White pieces are designated using upper-case
225 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
226 noted using digits 1 through 8 (the number of blank squares), and "/"
229 2) Active color. "w" means white moves next, "b" means black.
231 3) Castling availability. If neither side can castle, this is "-". Otherwise,
232 this has one or more letters: "K" (White can castle kingside), "Q" (White
233 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
234 can castle queenside).
236 4) En passant target square (in algebraic notation). If there's no en passant
237 target square, this is "-". If a pawn has just made a 2-square move, this
238 is the position "behind" the pawn. This is recorded regardless of whether
239 there is a pawn in position to make an en passant capture.
241 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
242 or capture. This is used to determine if a draw can be claimed under the
245 6) Fullmove number. The number of the full move. It starts at 1, and is
246 incremented after Black's move.
249 unsigned char col, row, token;
252 std::istringstream ss(fenStr);
257 // 1. Piece placement
258 while ((ss >> token) && !isspace(token))
261 sq += Square(token - '0'); // Advance the given number of files
263 else if (token == '/')
266 else if ((idx = PieceToChar.find(token)) != string::npos)
268 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
275 sideToMove = (token == 'w' ? WHITE : BLACK);
278 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
279 // Shredder-FEN that uses the letters of the columns on which the rooks began
280 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
281 // if an inner rook is associated with the castling right, the castling tag is
282 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
283 while ((ss >> token) && !isspace(token))
286 Color c = islower(token) ? BLACK : WHITE;
288 token = char(toupper(token));
291 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
293 else if (token == 'Q')
294 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
296 else if (token >= 'A' && token <= 'H')
297 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
302 set_castling_right(c, rsq);
305 // 4. En passant square. Ignore if no pawn capture is possible
306 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
307 && ((ss >> row) && (row == '3' || row == '6')))
309 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
311 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
312 st->epSquare = SQ_NONE;
315 // 5-6. Halfmove clock and fullmove number
316 ss >> std::skipws >> st->rule50 >> gamePly;
318 // Convert from fullmove starting from 1 to ply starting from 0,
319 // handle also common incorrect FEN with fullmove = 0.
320 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
322 chess960 = isChess960;
330 /// Position::set_castling_right() is a helper function used to set castling
331 /// rights given the corresponding color and the rook starting square.
333 void Position::set_castling_right(Color c, Square rfrom) {
335 Square kfrom = king_square(c);
336 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
337 CastlingRight cr = (c | cs);
339 st->castlingRights |= cr;
340 castlingRightsMask[kfrom] |= cr;
341 castlingRightsMask[rfrom] |= cr;
342 castlingRookSquare[cr] = rfrom;
344 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
345 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
347 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
348 if (s != kfrom && s != rfrom)
349 castlingPath[cr] |= s;
351 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
352 if (s != kfrom && s != rfrom)
353 castlingPath[cr] |= s;
357 /// Position::set_state() computes the hash keys of the position, and other
358 /// data that once computed is updated incrementally as moves are made.
359 /// The function is only used when a new position is set up, and to verify
360 /// the correctness of the StateInfo data when running in debug mode.
362 void Position::set_state(StateInfo* si) const {
364 si->key = si->pawnKey = si->materialKey = 0;
365 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
366 si->psq = SCORE_ZERO;
368 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
370 for (Bitboard b = pieces(); b; )
372 Square s = pop_lsb(&b);
373 Piece pc = piece_on(s);
374 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
375 si->psq += psq[color_of(pc)][type_of(pc)][s];
378 if (ep_square() != SQ_NONE)
379 si->key ^= Zobrist::enpassant[file_of(ep_square())];
381 if (sideToMove == BLACK)
382 si->key ^= Zobrist::side;
384 si->key ^= Zobrist::castling[st->castlingRights];
386 for (Bitboard b = pieces(PAWN); b; )
388 Square s = pop_lsb(&b);
389 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
392 for (Color c = WHITE; c <= BLACK; ++c)
393 for (PieceType pt = PAWN; pt <= KING; ++pt)
394 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
395 si->materialKey ^= Zobrist::psq[c][pt][cnt];
397 for (Color c = WHITE; c <= BLACK; ++c)
398 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
399 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
403 /// Position::fen() returns a FEN representation of the position. In case of
404 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
406 const string Position::fen() const {
409 std::ostringstream ss;
411 for (Rank r = RANK_8; r >= RANK_1; --r)
413 for (File f = FILE_A; f <= FILE_H; ++f)
415 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
422 ss << PieceToChar[piece_on(make_square(f, r))];
429 ss << (sideToMove == WHITE ? " w " : " b ");
431 if (can_castle(WHITE_OO))
432 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
434 if (can_castle(WHITE_OOO))
435 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
437 if (can_castle(BLACK_OO))
438 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
440 if (can_castle(BLACK_OOO))
441 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
443 if (!can_castle(WHITE) && !can_castle(BLACK))
446 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
447 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
453 /// Position::game_phase() calculates the game phase interpolating total non-pawn
454 /// material between endgame and midgame limits.
456 Phase Position::game_phase() const {
458 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
460 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
462 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
466 /// Position::check_blockers() returns a bitboard of all the pieces with color
467 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
468 /// blocks a check if removing that piece from the board would result in a
469 /// position where the king is in check. A check blocking piece can be either a
470 /// pinned or a discovered check piece, according if its color 'c' is the same
471 /// or the opposite of 'kingColor'.
473 Bitboard Position::check_blockers(Color c, Color kingColor) const {
475 Bitboard b, pinners, result = 0;
476 Square ksq = king_square(kingColor);
478 // Pinners are sliders that give check when a pinned piece is removed
479 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
480 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
484 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
486 if (!more_than_one(b))
487 result |= b & pieces(c);
493 /// Position::attackers_to() computes a bitboard of all pieces which attack a
494 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
496 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
498 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
499 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
500 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
501 | (attacks_bb<ROOK>(s, occupied) & pieces(ROOK, QUEEN))
502 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
503 | (attacks_from<KING>(s) & pieces(KING));
507 /// Position::legal() tests whether a pseudo-legal move is legal
509 bool Position::legal(Move m, Bitboard pinned) const {
512 assert(pinned == pinned_pieces(sideToMove));
514 Color us = sideToMove;
515 Square from = from_sq(m);
517 assert(color_of(moved_piece(m)) == us);
518 assert(piece_on(king_square(us)) == make_piece(us, KING));
520 // En passant captures are a tricky special case. Because they are rather
521 // uncommon, we do it simply by testing whether the king is attacked after
523 if (type_of(m) == ENPASSANT)
525 Square ksq = king_square(us);
526 Square to = to_sq(m);
527 Square capsq = to - pawn_push(us);
528 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
530 assert(to == ep_square());
531 assert(moved_piece(m) == make_piece(us, PAWN));
532 assert(piece_on(capsq) == make_piece(~us, PAWN));
533 assert(piece_on(to) == NO_PIECE);
535 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
536 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
539 // If the moving piece is a king, check whether the destination
540 // square is attacked by the opponent. Castling moves are checked
541 // for legality during move generation.
542 if (type_of(piece_on(from)) == KING)
543 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
545 // A non-king move is legal if and only if it is not pinned or it
546 // is moving along the ray towards or away from the king.
549 || aligned(from, to_sq(m), king_square(us));
553 /// Position::pseudo_legal() takes a random move and tests whether the move is
554 /// pseudo legal. It is used to validate moves from TT that can be corrupted
555 /// due to SMP concurrent access or hash position key aliasing.
557 bool Position::pseudo_legal(const Move m) const {
559 Color us = sideToMove;
560 Square from = from_sq(m);
561 Square to = to_sq(m);
562 Piece pc = moved_piece(m);
564 // Use a slower but simpler function for uncommon cases
565 if (type_of(m) != NORMAL)
566 return MoveList<LEGAL>(*this).contains(m);
568 // Is not a promotion, so promotion piece must be empty
569 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
572 // If the 'from' square is not occupied by a piece belonging to the side to
573 // move, the move is obviously not legal.
574 if (pc == NO_PIECE || color_of(pc) != us)
577 // The destination square cannot be occupied by a friendly piece
581 // Handle the special case of a pawn move
582 if (type_of(pc) == PAWN)
584 // We have already handled promotion moves, so destination
585 // cannot be on the 8th/1st rank.
586 if (rank_of(to) == relative_rank(us, RANK_8))
589 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
591 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
593 && !( (from + 2 * pawn_push(us) == to) // Not a double push
594 && (rank_of(from) == relative_rank(us, RANK_2))
596 && empty(to - pawn_push(us))))
599 else if (!(attacks_from(pc, from) & to))
602 // Evasions generator already takes care to avoid some kind of illegal moves
603 // and legal() relies on this. We therefore have to take care that the same
604 // kind of moves are filtered out here.
607 if (type_of(pc) != KING)
609 // Double check? In this case a king move is required
610 if (more_than_one(checkers()))
613 // Our move must be a blocking evasion or a capture of the checking piece
614 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
617 // In case of king moves under check we have to remove king so as to catch
618 // invalid moves like b1a1 when opposite queen is on c1.
619 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
627 /// Position::gives_check() tests whether a pseudo-legal move gives a check
629 bool Position::gives_check(Move m, const CheckInfo& ci) const {
632 assert(ci.dcCandidates == discovered_check_candidates());
633 assert(color_of(moved_piece(m)) == sideToMove);
635 Square from = from_sq(m);
636 Square to = to_sq(m);
637 PieceType pt = type_of(piece_on(from));
639 // Is there a direct check?
640 if (ci.checkSq[pt] & to)
643 // Is there a discovered check?
645 && (ci.dcCandidates & from)
646 && !aligned(from, to, ci.ksq))
655 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
657 // En passant capture with check? We have already handled the case
658 // of direct checks and ordinary discovered check, so the only case we
659 // need to handle is the unusual case of a discovered check through
660 // the captured pawn.
663 Square capsq = make_square(file_of(to), rank_of(from));
664 Bitboard b = (pieces() ^ from ^ capsq) | to;
666 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
667 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
672 Square rfrom = to; // Castling is encoded as 'King captures the rook'
673 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
674 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
676 return (PseudoAttacks[ROOK][rto] & ci.ksq)
677 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
686 /// Position::do_move() makes a move, and saves all information necessary
687 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
688 /// moves should be filtered out before this function is called.
690 void Position::do_move(Move m, StateInfo& newSt) {
693 do_move(m, newSt, ci, gives_check(m, ci));
696 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
699 assert(&newSt != st);
704 // Copy some fields of the old state to our new StateInfo object except the
705 // ones which are going to be recalculated from scratch anyway and then switch
706 // our state pointer to point to the new (ready to be updated) state.
707 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
712 // Update side to move
715 // Increment ply counters. In particular, rule50 will be reset to zero later on
716 // in case of a capture or a pawn move.
721 Color us = sideToMove;
723 Square from = from_sq(m);
724 Square to = to_sq(m);
725 Piece pc = piece_on(from);
726 PieceType pt = type_of(pc);
727 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
729 assert(color_of(pc) == us);
730 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
731 assert(captured != KING);
733 if (type_of(m) == CASTLING)
735 assert(pc == make_piece(us, KING));
738 do_castling<true>(from, to, rfrom, rto);
740 captured = NO_PIECE_TYPE;
741 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
742 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
749 // If the captured piece is a pawn, update pawn hash key, otherwise
750 // update non-pawn material.
751 if (captured == PAWN)
753 if (type_of(m) == ENPASSANT)
755 capsq += pawn_push(them);
758 assert(to == st->epSquare);
759 assert(relative_rank(us, to) == RANK_6);
760 assert(piece_on(to) == NO_PIECE);
761 assert(piece_on(capsq) == make_piece(them, PAWN));
763 board[capsq] = NO_PIECE;
766 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
769 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
771 // Update board and piece lists
772 remove_piece(capsq, them, captured);
774 // Update material hash key and prefetch access to materialTable
775 k ^= Zobrist::psq[them][captured][capsq];
776 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
777 prefetch((char*)thisThread->materialTable[st->materialKey]);
779 // Update incremental scores
780 st->psq -= psq[them][captured][capsq];
782 // Reset rule 50 counter
787 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
789 // Reset en passant square
790 if (st->epSquare != SQ_NONE)
792 k ^= Zobrist::enpassant[file_of(st->epSquare)];
793 st->epSquare = SQ_NONE;
796 // Update castling rights if needed
797 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
799 int cr = castlingRightsMask[from] | castlingRightsMask[to];
800 k ^= Zobrist::castling[st->castlingRights & cr];
801 st->castlingRights &= ~cr;
804 // Move the piece. The tricky Chess960 castling is handled earlier
805 if (type_of(m) != CASTLING)
806 move_piece(from, to, us, pt);
808 // If the moving piece is a pawn do some special extra work
811 // Set en-passant square if the moved pawn can be captured
812 if ( (int(to) ^ int(from)) == 16
813 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
815 st->epSquare = Square((from + to) / 2);
816 k ^= Zobrist::enpassant[file_of(st->epSquare)];
819 else if (type_of(m) == PROMOTION)
821 PieceType promotion = promotion_type(m);
823 assert(relative_rank(us, to) == RANK_8);
824 assert(promotion >= KNIGHT && promotion <= QUEEN);
826 remove_piece(to, us, PAWN);
827 put_piece(to, us, promotion);
830 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
831 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
832 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
833 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
835 // Update incremental score
836 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
839 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
842 // Update pawn hash key and prefetch access to pawnsTable
843 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
844 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
846 // Reset rule 50 draw counter
850 // Update incremental scores
851 st->psq += psq[us][pt][to] - psq[us][pt][from];
854 st->capturedType = captured;
856 // Update the key with the final value
859 // Update checkers bitboard: piece must be already moved due to attacks_from()
864 if (type_of(m) != NORMAL)
865 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
869 if (ci.checkSq[pt] & to)
870 st->checkersBB |= to;
873 if (ci.dcCandidates && (ci.dcCandidates & from))
876 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
879 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
884 sideToMove = ~sideToMove;
890 /// Position::undo_move() unmakes a move. When it returns, the position should
891 /// be restored to exactly the same state as before the move was made.
893 void Position::undo_move(Move m) {
897 sideToMove = ~sideToMove;
899 Color us = sideToMove;
900 Square from = from_sq(m);
901 Square to = to_sq(m);
902 PieceType pt = type_of(piece_on(to));
904 assert(empty(from) || type_of(m) == CASTLING);
905 assert(st->capturedType != KING);
907 if (type_of(m) == PROMOTION)
909 assert(pt == promotion_type(m));
910 assert(relative_rank(us, to) == RANK_8);
911 assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
913 remove_piece(to, us, promotion_type(m));
914 put_piece(to, us, PAWN);
918 if (type_of(m) == CASTLING)
921 do_castling<false>(from, to, rfrom, rto);
925 move_piece(to, from, us, pt); // Put the piece back at the source square
927 if (st->capturedType)
931 if (type_of(m) == ENPASSANT)
933 capsq -= pawn_push(us);
936 assert(to == st->previous->epSquare);
937 assert(relative_rank(us, to) == RANK_6);
938 assert(piece_on(capsq) == NO_PIECE);
941 put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
945 // Finally point our state pointer back to the previous state
953 /// Position::do_castling() is a helper used to do/undo a castling move. This
954 /// is a bit tricky, especially in Chess960.
956 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
958 bool kingSide = to > from;
959 rfrom = to; // Castling is encoded as "king captures friendly rook"
960 rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
961 to = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
963 // Remove both pieces first since squares could overlap in Chess960
964 remove_piece(Do ? from : to, sideToMove, KING);
965 remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
966 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
967 put_piece(Do ? to : from, sideToMove, KING);
968 put_piece(Do ? rto : rfrom, sideToMove, ROOK);
972 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
973 /// the side to move without executing any move on the board.
975 void Position::do_null_move(StateInfo& newSt) {
979 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
984 if (st->epSquare != SQ_NONE)
986 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
987 st->epSquare = SQ_NONE;
990 st->key ^= Zobrist::side;
991 prefetch((char*)TT.first_entry(st->key));
994 st->pliesFromNull = 0;
996 sideToMove = ~sideToMove;
1001 void Position::undo_null_move() {
1003 assert(!checkers());
1006 sideToMove = ~sideToMove;
1010 /// Position::key_after() computes the new hash key after the given move. Needed
1011 /// for speculative prefetch. It doesn't recognize special moves like castling,
1012 /// en-passant and promotions.
1014 Key Position::key_after(Move m) const {
1016 Color us = sideToMove;
1017 Square from = from_sq(m);
1018 Square to = to_sq(m);
1019 PieceType pt = type_of(piece_on(from));
1020 PieceType captured = type_of(piece_on(to));
1021 Key k = st->key ^ Zobrist::side;
1024 k ^= Zobrist::psq[~us][captured][to];
1026 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1030 /// Position::see() is a static exchange evaluator: It tries to estimate the
1031 /// material gain or loss resulting from a move.
1033 Value Position::see_sign(Move m) const {
1037 // Early return if SEE cannot be negative because captured piece value
1038 // is not less then capturing one. Note that king moves always return
1039 // here because king midgame value is set to 0.
1040 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1041 return VALUE_KNOWN_WIN;
1046 Value Position::see(Move m) const {
1049 Bitboard occupied, attackers, stmAttackers;
1059 swapList[0] = PieceValue[MG][piece_on(to)];
1060 stm = color_of(piece_on(from));
1061 occupied = pieces() ^ from;
1063 // Castling moves are implemented as king capturing the rook so cannot be
1064 // handled correctly. Simply return 0 that is always the correct value
1065 // unless in the rare case the rook ends up under attack.
1066 if (type_of(m) == CASTLING)
1069 if (type_of(m) == ENPASSANT)
1071 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1072 swapList[0] = PieceValue[MG][PAWN];
1075 // Find all attackers to the destination square, with the moving piece
1076 // removed, but possibly an X-ray attacker added behind it.
1077 attackers = attackers_to(to, occupied) & occupied;
1079 // If the opponent has no attackers we are finished
1081 stmAttackers = attackers & pieces(stm);
1085 // The destination square is defended, which makes things rather more
1086 // difficult to compute. We proceed by building up a "swap list" containing
1087 // the material gain or loss at each stop in a sequence of captures to the
1088 // destination square, where the sides alternately capture, and always
1089 // capture with the least valuable piece. After each capture, we look for
1090 // new X-ray attacks from behind the capturing piece.
1091 captured = type_of(piece_on(from));
1094 assert(slIndex < 32);
1096 // Add the new entry to the swap list
1097 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1099 // Locate and remove the next least valuable attacker
1100 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1102 // Stop before processing a king capture
1103 if (captured == KING)
1105 if (stmAttackers == attackers)
1112 stmAttackers = attackers & pieces(stm);
1115 } while (stmAttackers);
1117 // Having built the swap list, we negamax through it to find the best
1118 // achievable score from the point of view of the side to move.
1120 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1126 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1127 /// rule or repetition. It does not detect stalemates.
1129 bool Position::is_draw() const {
1131 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1134 StateInfo* stp = st;
1135 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1137 stp = stp->previous->previous;
1139 if (stp->key == st->key)
1140 return true; // Draw at first repetition
1147 /// Position::flip() flips position with the white and black sides reversed. This
1148 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1150 void Position::flip() {
1153 std::stringstream ss(fen());
1155 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1157 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1158 f.insert(0, token + (f.empty() ? " " : "/"));
1161 ss >> token; // Active color
1162 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1164 ss >> token; // Castling availability
1167 std::transform(f.begin(), f.end(), f.begin(),
1168 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1170 ss >> token; // En passant square
1171 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1173 std::getline(ss, token); // Half and full moves
1176 set(f, is_chess960(), this_thread());
1178 assert(pos_is_ok());
1182 /// Position::pos_is_ok() performs some consistency checks for the position object.
1183 /// This is meant to be helpful when debugging.
1185 bool Position::pos_is_ok(int* step) const {
1187 // Which parts of the position should be verified?
1188 const bool all = false;
1190 const bool testBitboards = all || false;
1191 const bool testState = all || false;
1192 const bool testKingCount = all || false;
1193 const bool testKingCapture = all || false;
1194 const bool testPieceCounts = all || false;
1195 const bool testPieceList = all || false;
1196 const bool testCastlingSquares = all || false;
1201 if ( (sideToMove != WHITE && sideToMove != BLACK)
1202 || piece_on(king_square(WHITE)) != W_KING
1203 || piece_on(king_square(BLACK)) != B_KING
1204 || ( ep_square() != SQ_NONE
1205 && relative_rank(sideToMove, ep_square()) != RANK_6))
1208 if (step && ++*step, testBitboards)
1210 // The intersection of the white and black pieces must be empty
1211 if (pieces(WHITE) & pieces(BLACK))
1214 // The union of the white and black pieces must be equal to all
1216 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1219 // Separate piece type bitboards must have empty intersections
1220 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1221 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1222 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1226 if (step && ++*step, testState)
1230 if ( st->key != si.key
1231 || st->pawnKey != si.pawnKey
1232 || st->materialKey != si.materialKey
1233 || st->nonPawnMaterial[WHITE] != si.nonPawnMaterial[WHITE]
1234 || st->nonPawnMaterial[BLACK] != si.nonPawnMaterial[BLACK]
1235 || st->psq != si.psq
1236 || st->checkersBB != si.checkersBB)
1240 if (step && ++*step, testKingCount)
1241 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1242 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1245 if (step && ++*step, testKingCapture)
1246 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1249 if (step && ++*step, testPieceCounts)
1250 for (Color c = WHITE; c <= BLACK; ++c)
1251 for (PieceType pt = PAWN; pt <= KING; ++pt)
1252 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1255 if (step && ++*step, testPieceList)
1256 for (Color c = WHITE; c <= BLACK; ++c)
1257 for (PieceType pt = PAWN; pt <= KING; ++pt)
1258 for (int i = 0; i < pieceCount[c][pt]; ++i)
1259 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1260 || index[pieceList[c][pt][i]] != i)
1263 if (step && ++*step, testCastlingSquares)
1264 for (Color c = WHITE; c <= BLACK; ++c)
1265 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1267 if (!can_castle(c | s))
1270 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1271 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1272 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))