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, std::memcmp
36 Value PieceValue[PHASE_NB][PIECE_NB] = {
37 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
38 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
42 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
43 Key enpassant[FILE_NB];
44 Key castling[CASTLING_RIGHT_NB];
49 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
53 const string PieceToChar(" PNBRQK pnbrqk");
55 // min_attacker() is a helper function used by see() to locate the least
56 // valuable attacker for the side to move, remove the attacker we just found
57 // from the bitboards and scan for new X-ray attacks behind it.
60 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
61 Bitboard& occupied, Bitboard& attackers) {
63 Bitboard b = stmAttackers & bb[Pt];
65 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
67 occupied ^= b & ~(b - 1);
69 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
70 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
72 if (Pt == ROOK || Pt == QUEEN)
73 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
75 attackers &= occupied; // After X-ray that may add already processed pieces
80 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
81 return KING; // No need to update bitboards: it is the last cycle
89 CheckInfo::CheckInfo(const Position& pos) {
91 Color them = ~pos.side_to_move();
92 ksq = pos.king_square(them);
94 pinned = pos.pinned_pieces(pos.side_to_move());
95 dcCandidates = pos.discovered_check_candidates();
97 checkSquares[PAWN] = pos.attacks_from<PAWN>(ksq, them);
98 checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
99 checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);
100 checkSquares[ROOK] = pos.attacks_from<ROOK>(ksq);
101 checkSquares[QUEEN] = checkSquares[BISHOP] | checkSquares[ROOK];
102 checkSquares[KING] = 0;
106 /// operator<<(Position) returns an ASCII representation of the position
108 std::ostream& operator<<(std::ostream& os, const Position& pos) {
110 os << "\n +---+---+---+---+---+---+---+---+\n";
112 for (Rank r = RANK_8; r >= RANK_1; --r)
114 for (File f = FILE_A; f <= FILE_H; ++f)
115 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
117 os << " |\n +---+---+---+---+---+---+---+---+\n";
120 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
121 << std::setfill('0') << std::setw(16) << pos.st->key << std::dec << "\nCheckers: ";
123 for (Bitboard b = pos.checkers(); b; )
124 os << UCI::square(pop_lsb(&b)) << " ";
130 /// Position::init() initializes at startup the various arrays used to compute
133 void Position::init() {
137 for (Color c = WHITE; c <= BLACK; ++c)
138 for (PieceType pt = PAWN; pt <= KING; ++pt)
139 for (Square s = SQ_A1; s <= SQ_H8; ++s)
140 Zobrist::psq[c][pt][s] = rng.rand<Key>();
142 for (File f = FILE_A; f <= FILE_H; ++f)
143 Zobrist::enpassant[f] = rng.rand<Key>();
145 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
147 Zobrist::castling[cr] = 0;
151 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
152 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
156 Zobrist::side = rng.rand<Key>();
157 Zobrist::exclusion = rng.rand<Key>();
161 /// Position::operator=() creates a copy of 'pos' but detaching the state pointer
162 /// from the source to be self-consistent and not depending on any external data.
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
167 std::memcpy(&startState, st, sizeof(StateInfo));
177 /// Position::clear() erases the position object to a pristine state, with an
178 /// empty board, white to move, and no castling rights.
180 void Position::clear() {
182 std::memset(this, 0, sizeof(Position));
183 startState.epSquare = SQ_NONE;
186 for (int i = 0; i < PIECE_TYPE_NB; ++i)
187 for (int j = 0; j < 16; ++j)
188 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
192 /// Position::set() initializes the position object with the given FEN string.
193 /// This function is not very robust - make sure that input FENs are correct,
194 /// this is assumed to be the responsibility of the GUI.
196 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
198 A FEN string defines a particular position using only the ASCII character set.
200 A FEN string contains six fields separated by a space. The fields are:
202 1) Piece placement (from white's perspective). Each rank is described, starting
203 with rank 8 and ending with rank 1. Within each rank, the contents of each
204 square are described from file A through file H. Following the Standard
205 Algebraic Notation (SAN), each piece is identified by a single letter taken
206 from the standard English names. White pieces are designated using upper-case
207 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
208 noted using digits 1 through 8 (the number of blank squares), and "/"
211 2) Active color. "w" means white moves next, "b" means black.
213 3) Castling availability. If neither side can castle, this is "-". Otherwise,
214 this has one or more letters: "K" (White can castle kingside), "Q" (White
215 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
216 can castle queenside).
218 4) En passant target square (in algebraic notation). If there's no en passant
219 target square, this is "-". If a pawn has just made a 2-square move, this
220 is the position "behind" the pawn. This is recorded regardless of whether
221 there is a pawn in position to make an en passant capture.
223 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
224 or capture. This is used to determine if a draw can be claimed under the
227 6) Fullmove number. The number of the full move. It starts at 1, and is
228 incremented after Black's move.
231 unsigned char col, row, token;
234 std::istringstream ss(fenStr);
239 // 1. Piece placement
240 while ((ss >> token) && !isspace(token))
243 sq += Square(token - '0'); // Advance the given number of files
245 else if (token == '/')
248 else if ((idx = PieceToChar.find(token)) != string::npos)
250 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
257 sideToMove = (token == 'w' ? WHITE : BLACK);
260 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
261 // Shredder-FEN that uses the letters of the columns on which the rooks began
262 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
263 // if an inner rook is associated with the castling right, the castling tag is
264 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
265 while ((ss >> token) && !isspace(token))
268 Color c = islower(token) ? BLACK : WHITE;
270 token = char(toupper(token));
273 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
275 else if (token == 'Q')
276 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
278 else if (token >= 'A' && token <= 'H')
279 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
284 set_castling_right(c, rsq);
287 // 4. En passant square. Ignore if no pawn capture is possible
288 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
289 && ((ss >> row) && (row == '3' || row == '6')))
291 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
293 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
294 st->epSquare = SQ_NONE;
297 // 5-6. Halfmove clock and fullmove number
298 ss >> std::skipws >> st->rule50 >> gamePly;
300 // Convert from fullmove starting from 1 to ply starting from 0,
301 // handle also common incorrect FEN with fullmove = 0.
302 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
304 chess960 = isChess960;
312 /// Position::set_castling_right() is a helper function used to set castling
313 /// rights given the corresponding color and the rook starting square.
315 void Position::set_castling_right(Color c, Square rfrom) {
317 Square kfrom = king_square(c);
318 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
319 CastlingRight cr = (c | cs);
321 st->castlingRights |= cr;
322 castlingRightsMask[kfrom] |= cr;
323 castlingRightsMask[rfrom] |= cr;
324 castlingRookSquare[cr] = rfrom;
326 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
327 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
329 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
330 if (s != kfrom && s != rfrom)
331 castlingPath[cr] |= s;
333 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
334 if (s != kfrom && s != rfrom)
335 castlingPath[cr] |= s;
339 /// Position::set_state() computes the hash keys of the position, and other
340 /// data that once computed is updated incrementally as moves are made.
341 /// The function is only used when a new position is set up, and to verify
342 /// the correctness of the StateInfo data when running in debug mode.
344 void Position::set_state(StateInfo* si) const {
346 si->key = si->pawnKey = si->materialKey = 0;
347 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
348 si->psq = SCORE_ZERO;
350 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
352 for (Bitboard b = pieces(); b; )
354 Square s = pop_lsb(&b);
355 Piece pc = piece_on(s);
356 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
357 si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];
360 if (si->epSquare != SQ_NONE)
361 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
363 if (sideToMove == BLACK)
364 si->key ^= Zobrist::side;
366 si->key ^= Zobrist::castling[si->castlingRights];
368 for (Bitboard b = pieces(PAWN); b; )
370 Square s = pop_lsb(&b);
371 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
374 for (Color c = WHITE; c <= BLACK; ++c)
375 for (PieceType pt = PAWN; pt <= KING; ++pt)
376 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
377 si->materialKey ^= Zobrist::psq[c][pt][cnt];
379 for (Color c = WHITE; c <= BLACK; ++c)
380 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
381 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
385 /// Position::fen() returns a FEN representation of the position. In case of
386 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
388 const string Position::fen() const {
391 std::ostringstream ss;
393 for (Rank r = RANK_8; r >= RANK_1; --r)
395 for (File f = FILE_A; f <= FILE_H; ++f)
397 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
404 ss << PieceToChar[piece_on(make_square(f, r))];
411 ss << (sideToMove == WHITE ? " w " : " b ");
413 if (can_castle(WHITE_OO))
414 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
416 if (can_castle(WHITE_OOO))
417 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
419 if (can_castle(BLACK_OO))
420 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
422 if (can_castle(BLACK_OOO))
423 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
425 if (!can_castle(WHITE) && !can_castle(BLACK))
428 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
429 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
435 /// Position::game_phase() calculates the game phase interpolating total non-pawn
436 /// material between endgame and midgame limits.
438 Phase Position::game_phase() const {
440 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
442 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
444 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
448 /// Position::check_blockers() returns a bitboard of all the pieces with color
449 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
450 /// blocks a check if removing that piece from the board would result in a
451 /// position where the king is in check. A check blocking piece can be either a
452 /// pinned or a discovered check piece, according if its color 'c' is the same
453 /// or the opposite of 'kingColor'.
455 Bitboard Position::check_blockers(Color c, Color kingColor) const {
457 Bitboard b, pinners, result = 0;
458 Square ksq = king_square(kingColor);
460 // Pinners are sliders that give check when a pinned piece is removed
461 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
462 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
466 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
468 if (!more_than_one(b))
469 result |= b & pieces(c);
475 /// Position::attackers_to() computes a bitboard of all pieces which attack a
476 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
478 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
480 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
481 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
482 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
483 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
484 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
485 | (attacks_from<KING>(s) & pieces(KING));
489 /// Position::legal() tests whether a pseudo-legal move is legal
491 bool Position::legal(Move m, Bitboard pinned) const {
494 assert(pinned == pinned_pieces(sideToMove));
496 Color us = sideToMove;
497 Square from = from_sq(m);
499 assert(color_of(moved_piece(m)) == us);
500 assert(piece_on(king_square(us)) == make_piece(us, KING));
502 // En passant captures are a tricky special case. Because they are rather
503 // uncommon, we do it simply by testing whether the king is attacked after
505 if (type_of(m) == ENPASSANT)
507 Square ksq = king_square(us);
508 Square to = to_sq(m);
509 Square capsq = to - pawn_push(us);
510 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
512 assert(to == ep_square());
513 assert(moved_piece(m) == make_piece(us, PAWN));
514 assert(piece_on(capsq) == make_piece(~us, PAWN));
515 assert(piece_on(to) == NO_PIECE);
517 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
518 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
521 // If the moving piece is a king, check whether the destination
522 // square is attacked by the opponent. Castling moves are checked
523 // for legality during move generation.
524 if (type_of(piece_on(from)) == KING)
525 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
527 // A non-king move is legal if and only if it is not pinned or it
528 // is moving along the ray towards or away from the king.
531 || aligned(from, to_sq(m), king_square(us));
535 /// Position::pseudo_legal() takes a random move and tests whether the move is
536 /// pseudo legal. It is used to validate moves from TT that can be corrupted
537 /// due to SMP concurrent access or hash position key aliasing.
539 bool Position::pseudo_legal(const Move m) const {
541 Color us = sideToMove;
542 Square from = from_sq(m);
543 Square to = to_sq(m);
544 Piece pc = moved_piece(m);
546 // Use a slower but simpler function for uncommon cases
547 if (type_of(m) != NORMAL)
548 return MoveList<LEGAL>(*this).contains(m);
550 // Is not a promotion, so promotion piece must be empty
551 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
554 // If the 'from' square is not occupied by a piece belonging to the side to
555 // move, the move is obviously not legal.
556 if (pc == NO_PIECE || color_of(pc) != us)
559 // The destination square cannot be occupied by a friendly piece
563 // Handle the special case of a pawn move
564 if (type_of(pc) == PAWN)
566 // We have already handled promotion moves, so destination
567 // cannot be on the 8th/1st rank.
568 if (rank_of(to) == relative_rank(us, RANK_8))
571 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
572 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
573 && !( (from + 2 * pawn_push(us) == to) // Not a double push
574 && (rank_of(from) == relative_rank(us, RANK_2))
576 && empty(to - pawn_push(us))))
579 else if (!(attacks_from(pc, from) & to))
582 // Evasions generator already takes care to avoid some kind of illegal moves
583 // and legal() relies on this. We therefore have to take care that the same
584 // kind of moves are filtered out here.
587 if (type_of(pc) != KING)
589 // Double check? In this case a king move is required
590 if (more_than_one(checkers()))
593 // Our move must be a blocking evasion or a capture of the checking piece
594 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
597 // In case of king moves under check we have to remove king so as to catch
598 // invalid moves like b1a1 when opposite queen is on c1.
599 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
607 /// Position::gives_check() tests whether a pseudo-legal move gives a check
609 bool Position::gives_check(Move m, const CheckInfo& ci) const {
612 assert(ci.dcCandidates == discovered_check_candidates());
613 assert(color_of(moved_piece(m)) == sideToMove);
615 Square from = from_sq(m);
616 Square to = to_sq(m);
618 // Is there a direct check?
619 if (ci.checkSquares[type_of(piece_on(from))] & to)
622 // Is there a discovered check?
624 && (ci.dcCandidates & from)
625 && !aligned(from, to, ci.ksq))
634 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
636 // En passant capture with check? We have already handled the case
637 // of direct checks and ordinary discovered check, so the only case we
638 // need to handle is the unusual case of a discovered check through
639 // the captured pawn.
642 Square capsq = make_square(file_of(to), rank_of(from));
643 Bitboard b = (pieces() ^ from ^ capsq) | to;
645 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
646 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
651 Square rfrom = to; // Castling is encoded as 'King captures the rook'
652 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
653 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
655 return (PseudoAttacks[ROOK][rto] & ci.ksq)
656 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
665 /// Position::do_move() makes a move, and saves all information necessary
666 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
667 /// moves should be filtered out before this function is called.
669 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
672 assert(&newSt != st);
675 Key k = st->key ^ Zobrist::side;
677 // Copy some fields of the old state to our new StateInfo object except the
678 // ones which are going to be recalculated from scratch anyway and then switch
679 // our state pointer to point to the new (ready to be updated) state.
680 std::memcpy(&newSt, st, offsetof(StateInfo, key));
684 // Increment ply counters. In particular, rule50 will be reset to zero later on
685 // in case of a capture or a pawn move.
690 Color us = sideToMove;
692 Square from = from_sq(m);
693 Square to = to_sq(m);
694 PieceType pt = type_of(piece_on(from));
695 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
697 assert(color_of(piece_on(from)) == us);
698 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
699 assert(captured != KING);
701 if (type_of(m) == CASTLING)
706 do_castling<true>(us, from, to, rfrom, rto);
708 captured = NO_PIECE_TYPE;
709 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
710 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
717 // If the captured piece is a pawn, update pawn hash key, otherwise
718 // update non-pawn material.
719 if (captured == PAWN)
721 if (type_of(m) == ENPASSANT)
723 capsq -= pawn_push(us);
726 assert(to == st->epSquare);
727 assert(relative_rank(us, to) == RANK_6);
728 assert(piece_on(to) == NO_PIECE);
729 assert(piece_on(capsq) == make_piece(them, PAWN));
731 board[capsq] = NO_PIECE; // Not done by remove_piece()
734 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
737 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
739 // Update board and piece lists
740 remove_piece(them, captured, capsq);
742 // Update material hash key and prefetch access to materialTable
743 k ^= Zobrist::psq[them][captured][capsq];
744 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
745 prefetch(thisThread->materialTable[st->materialKey]);
747 // Update incremental scores
748 st->psq -= PSQT::psq[them][captured][capsq];
750 // Reset rule 50 counter
755 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
757 // Reset en passant square
758 if (st->epSquare != SQ_NONE)
760 k ^= Zobrist::enpassant[file_of(st->epSquare)];
761 st->epSquare = SQ_NONE;
764 // Update castling rights if needed
765 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
767 int cr = castlingRightsMask[from] | castlingRightsMask[to];
768 k ^= Zobrist::castling[st->castlingRights & cr];
769 st->castlingRights &= ~cr;
772 // Move the piece. The tricky Chess960 castling is handled earlier
773 if (type_of(m) != CASTLING)
774 move_piece(us, pt, from, to);
776 // If the moving piece is a pawn do some special extra work
779 // Set en-passant square if the moved pawn can be captured
780 if ( (int(to) ^ int(from)) == 16
781 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
783 st->epSquare = (from + to) / 2;
784 k ^= Zobrist::enpassant[file_of(st->epSquare)];
787 else if (type_of(m) == PROMOTION)
789 PieceType promotion = promotion_type(m);
791 assert(relative_rank(us, to) == RANK_8);
792 assert(promotion >= KNIGHT && promotion <= QUEEN);
794 remove_piece(us, PAWN, to);
795 put_piece(us, promotion, to);
798 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
799 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
800 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
801 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
803 // Update incremental score
804 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
807 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
810 // Update pawn hash key and prefetch access to pawnsTable
811 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
812 prefetch(thisThread->pawnsTable[st->pawnKey]);
814 // Reset rule 50 draw counter
818 // Update incremental scores
819 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
822 st->capturedType = captured;
824 // Update the key with the final value
827 // Calculate checkers bitboard (if move gives check)
828 st->checkersBB = givesCheck ? attackers_to(king_square(them)) & pieces(us) : 0;
830 sideToMove = ~sideToMove;
836 /// Position::undo_move() unmakes a move. When it returns, the position should
837 /// be restored to exactly the same state as before the move was made.
839 void Position::undo_move(Move m) {
843 sideToMove = ~sideToMove;
845 Color us = sideToMove;
846 Square from = from_sq(m);
847 Square to = to_sq(m);
848 PieceType pt = type_of(piece_on(to));
850 assert(empty(from) || type_of(m) == CASTLING);
851 assert(st->capturedType != KING);
853 if (type_of(m) == PROMOTION)
855 assert(relative_rank(us, to) == RANK_8);
856 assert(pt == promotion_type(m));
857 assert(pt >= KNIGHT && pt <= QUEEN);
859 remove_piece(us, pt, to);
860 put_piece(us, PAWN, to);
864 if (type_of(m) == CASTLING)
867 do_castling<false>(us, from, to, rfrom, rto);
871 move_piece(us, pt, to, from); // Put the piece back at the source square
873 if (st->capturedType)
877 if (type_of(m) == ENPASSANT)
879 capsq -= pawn_push(us);
882 assert(to == st->previous->epSquare);
883 assert(relative_rank(us, to) == RANK_6);
884 assert(piece_on(capsq) == NO_PIECE);
885 assert(st->capturedType == PAWN);
888 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
892 // Finally point our state pointer back to the previous state
900 /// Position::do_castling() is a helper used to do/undo a castling move. This
901 /// is a bit tricky, especially in Chess960.
903 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
905 bool kingSide = to > from;
906 rfrom = to; // Castling is encoded as "king captures friendly rook"
907 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
908 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
910 // Remove both pieces first since squares could overlap in Chess960
911 remove_piece(us, KING, Do ? from : to);
912 remove_piece(us, ROOK, Do ? rfrom : rto);
913 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
914 put_piece(us, KING, Do ? to : from);
915 put_piece(us, ROOK, Do ? rto : rfrom);
919 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
920 /// the side to move without executing any move on the board.
922 void Position::do_null_move(StateInfo& newSt) {
925 assert(&newSt != st);
927 std::memcpy(&newSt, st, sizeof(StateInfo));
931 if (st->epSquare != SQ_NONE)
933 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
934 st->epSquare = SQ_NONE;
937 st->key ^= Zobrist::side;
938 prefetch(TT.first_entry(st->key));
941 st->pliesFromNull = 0;
943 sideToMove = ~sideToMove;
948 void Position::undo_null_move() {
953 sideToMove = ~sideToMove;
957 /// Position::key_after() computes the new hash key after the given move. Needed
958 /// for speculative prefetch. It doesn't recognize special moves like castling,
959 /// en-passant and promotions.
961 Key Position::key_after(Move m) const {
963 Color us = sideToMove;
964 Square from = from_sq(m);
965 Square to = to_sq(m);
966 PieceType pt = type_of(piece_on(from));
967 PieceType captured = type_of(piece_on(to));
968 Key k = st->key ^ Zobrist::side;
971 k ^= Zobrist::psq[~us][captured][to];
973 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
977 /// Position::see() is a static exchange evaluator: It tries to estimate the
978 /// material gain or loss resulting from a move.
980 Value Position::see_sign(Move m) const {
984 // Early return if SEE cannot be negative because captured piece value
985 // is not less then capturing one. Note that king moves always return
986 // here because king midgame value is set to 0.
987 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
988 return VALUE_KNOWN_WIN;
993 Value Position::see(Move m) const {
996 Bitboard occupied, attackers, stmAttackers;
1006 swapList[0] = PieceValue[MG][piece_on(to)];
1007 stm = color_of(piece_on(from));
1008 occupied = pieces() ^ from;
1010 // Castling moves are implemented as king capturing the rook so cannot
1011 // be handled correctly. Simply return VALUE_ZERO that is always correct
1012 // unless in the rare case the rook ends up under attack.
1013 if (type_of(m) == CASTLING)
1016 if (type_of(m) == ENPASSANT)
1018 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1019 swapList[0] = PieceValue[MG][PAWN];
1022 // Find all attackers to the destination square, with the moving piece
1023 // removed, but possibly an X-ray attacker added behind it.
1024 attackers = attackers_to(to, occupied) & occupied;
1026 // If the opponent has no attackers we are finished
1028 stmAttackers = attackers & pieces(stm);
1032 // The destination square is defended, which makes things rather more
1033 // difficult to compute. We proceed by building up a "swap list" containing
1034 // the material gain or loss at each stop in a sequence of captures to the
1035 // destination square, where the sides alternately capture, and always
1036 // capture with the least valuable piece. After each capture, we look for
1037 // new X-ray attacks from behind the capturing piece.
1038 captured = type_of(piece_on(from));
1041 assert(slIndex < 32);
1043 // Add the new entry to the swap list
1044 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1046 // Locate and remove the next least valuable attacker
1047 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1049 stmAttackers = attackers & pieces(stm);
1052 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1054 // Having built the swap list, we negamax through it to find the best
1055 // achievable score from the point of view of the side to move.
1057 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1063 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1064 /// or by repetition. It does not detect stalemates.
1066 bool Position::is_draw() const {
1068 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1071 StateInfo* stp = st;
1072 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1074 stp = stp->previous->previous;
1076 if (stp->key == st->key)
1077 return true; // Draw at first repetition
1084 /// Position::flip() flips position with the white and black sides reversed. This
1085 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1087 void Position::flip() {
1090 std::stringstream ss(fen());
1092 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1094 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1095 f.insert(0, token + (f.empty() ? " " : "/"));
1098 ss >> token; // Active color
1099 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1101 ss >> token; // Castling availability
1104 std::transform(f.begin(), f.end(), f.begin(),
1105 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1107 ss >> token; // En passant square
1108 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1110 std::getline(ss, token); // Half and full moves
1113 set(f, is_chess960(), this_thread());
1115 assert(pos_is_ok());
1119 /// Position::pos_is_ok() performs some consistency checks for the position object.
1120 /// This is meant to be helpful when debugging.
1122 bool Position::pos_is_ok(int* failedStep) const {
1124 const bool Fast = true; // Quick (default) or full check?
1126 enum { Default, King, Bitboards, State, Lists, Castling };
1128 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1133 if (step == Default)
1134 if ( (sideToMove != WHITE && sideToMove != BLACK)
1135 || piece_on(king_square(WHITE)) != W_KING
1136 || piece_on(king_square(BLACK)) != B_KING
1137 || ( ep_square() != SQ_NONE
1138 && relative_rank(sideToMove, ep_square()) != RANK_6))
1142 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1143 || std::count(board, board + SQUARE_NB, B_KING) != 1
1144 || attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1147 if (step == Bitboards)
1149 if ( (pieces(WHITE) & pieces(BLACK))
1150 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1153 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1154 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1155 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1163 if (std::memcmp(&si, st, sizeof(StateInfo)))
1168 for (Color c = WHITE; c <= BLACK; ++c)
1169 for (PieceType pt = PAWN; pt <= KING; ++pt)
1171 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1174 for (int i = 0; i < pieceCount[c][pt]; ++i)
1175 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1176 || index[pieceList[c][pt][i]] != i)
1180 if (step == Castling)
1181 for (Color c = WHITE; c <= BLACK; ++c)
1182 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1184 if (!can_castle(c | s))
1187 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1188 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1189 ||(castlingRightsMask[king_square(c)] & (c | s)) != (c | s))