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-2014 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/>.
39 Value PieceValue[PHASE_NB][PIECE_NB] = {
40 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
41 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
45 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
46 Key enpassant[FILE_NB];
47 Key castling[CASTLING_RIGHT_NB];
52 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
56 const string PieceToChar(" PNBRQK pnbrqk");
57 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
59 // min_attacker() is a helper function used by see() to locate the least
60 // valuable attacker for the side to move, remove the attacker we just found
61 // from the bitboards and scan for new X-ray attacks behind it.
63 template<int Pt> FORCE_INLINE
64 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
65 Bitboard& occupied, Bitboard& attackers) {
67 Bitboard b = stmAttackers & bb[Pt];
69 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
71 occupied ^= b & ~(b - 1);
73 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
74 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
76 if (Pt == ROOK || Pt == QUEEN)
77 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
79 attackers &= occupied; // After X-ray that may add already processed pieces
83 template<> FORCE_INLINE
84 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
85 return KING; // No need to update bitboards: it is the last cycle
93 CheckInfo::CheckInfo(const Position& pos) {
95 Color them = ~pos.side_to_move();
96 ksq = pos.king_square(them);
98 pinned = pos.pinned_pieces(pos.side_to_move());
99 dcCandidates = pos.discovered_check_candidates();
101 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
102 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
103 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
104 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
105 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
110 /// Position::init() initializes at startup the various arrays used to compute
111 /// hash keys and the piece square tables. The latter is a two-step operation:
112 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
113 /// Secondly, the black halves of the tables are initialized by flipping and
114 /// changing the sign of the white scores.
116 void Position::init() {
120 for (Color c = WHITE; c <= BLACK; ++c)
121 for (PieceType pt = PAWN; pt <= KING; ++pt)
122 for (Square s = SQ_A1; s <= SQ_H8; ++s)
123 Zobrist::psq[c][pt][s] = rk.rand<Key>();
125 for (File f = FILE_A; f <= FILE_H; ++f)
126 Zobrist::enpassant[f] = rk.rand<Key>();
128 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
133 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
134 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
138 Zobrist::side = rk.rand<Key>();
139 Zobrist::exclusion = rk.rand<Key>();
141 for (PieceType pt = PAWN; pt <= KING; ++pt)
143 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
144 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
146 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
148 for (Square s = SQ_A1; s <= SQ_H8; ++s)
150 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
151 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
157 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
158 /// object to not depend on any external data so we detach state pointer from
161 Position& Position::operator=(const Position& pos) {
163 std::memcpy(this, &pos, sizeof(Position));
174 /// Position::clear() erases the position object to a pristine state, with an
175 /// empty board, white to move, and no castling rights.
177 void Position::clear() {
179 std::memset(this, 0, sizeof(Position));
180 startState.epSquare = SQ_NONE;
183 for (int i = 0; i < PIECE_TYPE_NB; ++i)
184 for (int j = 0; j < 16; ++j)
185 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
189 /// Position::set() initializes the position object with the given FEN string.
190 /// This function is not very robust - make sure that input FENs are correct,
191 /// this is assumed to be the responsibility of the GUI.
193 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
195 A FEN string defines a particular position using only the ASCII character set.
197 A FEN string contains six fields separated by a space. The fields are:
199 1) Piece placement (from white's perspective). Each rank is described, starting
200 with rank 8 and ending with rank 1. Within each rank, the contents of each
201 square are described from file A through file H. Following the Standard
202 Algebraic Notation (SAN), each piece is identified by a single letter taken
203 from the standard English names. White pieces are designated using upper-case
204 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
205 noted using digits 1 through 8 (the number of blank squares), and "/"
208 2) Active color. "w" means white moves next, "b" means black.
210 3) Castling availability. If neither side can castle, this is "-". Otherwise,
211 this has one or more letters: "K" (White can castle kingside), "Q" (White
212 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
213 can castle queenside).
215 4) En passant target square (in algebraic notation). If there's no en passant
216 target square, this is "-". If a pawn has just made a 2-square move, this
217 is the position "behind" the pawn. This is recorded regardless of whether
218 there is a pawn in position to make an en passant capture.
220 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
221 or capture. This is used to determine if a draw can be claimed under the
224 6) Fullmove number. The number of the full move. It starts at 1, and is
225 incremented after Black's move.
228 unsigned char col, row, token;
231 std::istringstream ss(fenStr);
236 // 1. Piece placement
237 while ((ss >> token) && !isspace(token))
240 sq += Square(token - '0'); // Advance the given number of files
242 else if (token == '/')
245 else if ((idx = PieceToChar.find(token)) != string::npos)
247 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
254 sideToMove = (token == 'w' ? WHITE : BLACK);
257 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
258 // Shredder-FEN that uses the letters of the columns on which the rooks began
259 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
260 // if an inner rook is associated with the castling right, the castling tag is
261 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
262 while ((ss >> token) && !isspace(token))
265 Color c = islower(token) ? BLACK : WHITE;
267 token = char(toupper(token));
270 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
272 else if (token == 'Q')
273 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
275 else if (token >= 'A' && token <= 'H')
276 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
281 set_castling_right(c, rsq);
284 // 4. En passant square. Ignore if no pawn capture is possible
285 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
286 && ((ss >> row) && (row == '3' || row == '6')))
288 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
290 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
291 st->epSquare = SQ_NONE;
294 // 5-6. Halfmove clock and fullmove number
295 ss >> std::skipws >> st->rule50 >> gamePly;
297 // Convert from fullmove starting from 1 to ply starting from 0,
298 // handle also common incorrect FEN with fullmove = 0.
299 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
301 chess960 = isChess960;
309 /// Position::set_castling_right() is a helper function used to set castling
310 /// rights given the corresponding color and the rook starting square.
312 void Position::set_castling_right(Color c, Square rfrom) {
314 Square kfrom = king_square(c);
315 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
316 CastlingRight cr = (c | cs);
318 st->castlingRights |= cr;
319 castlingRightsMask[kfrom] |= cr;
320 castlingRightsMask[rfrom] |= cr;
321 castlingRookSquare[cr] = rfrom;
323 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
324 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
326 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
327 if (s != kfrom && s != rfrom)
328 castlingPath[cr] |= s;
330 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
331 if (s != kfrom && s != rfrom)
332 castlingPath[cr] |= s;
336 /// Position::set_state() computes the hash keys of the position, and other
337 /// data that once computed is updated incrementally as moves are made.
338 /// The function is only used when a new position is set up, and to verify
339 /// the correctness of the StateInfo data when running in debug mode.
341 void Position::set_state(StateInfo* si) const {
343 si->key = si->pawnKey = si->materialKey = 0;
344 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
345 si->psq = SCORE_ZERO;
347 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
349 for (Bitboard b = pieces(); b; )
351 Square s = pop_lsb(&b);
352 Piece pc = piece_on(s);
353 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
354 si->psq += psq[color_of(pc)][type_of(pc)][s];
357 if (ep_square() != SQ_NONE)
358 si->key ^= Zobrist::enpassant[file_of(ep_square())];
360 if (sideToMove == BLACK)
361 si->key ^= Zobrist::side;
363 si->key ^= Zobrist::castling[st->castlingRights];
365 for (Bitboard b = pieces(PAWN); b; )
367 Square s = pop_lsb(&b);
368 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
371 for (Color c = WHITE; c <= BLACK; ++c)
372 for (PieceType pt = PAWN; pt <= KING; ++pt)
373 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
374 si->materialKey ^= Zobrist::psq[c][pt][cnt];
376 for (Color c = WHITE; c <= BLACK; ++c)
377 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
378 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
382 /// Position::fen() returns a FEN representation of the position. In case of
383 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
385 const string Position::fen() const {
388 std::ostringstream ss;
390 for (Rank r = RANK_8; r >= RANK_1; --r)
392 for (File f = FILE_A; f <= FILE_H; ++f)
394 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
401 ss << PieceToChar[piece_on(make_square(f, r))];
408 ss << (sideToMove == WHITE ? " w " : " b ");
410 if (can_castle(WHITE_OO))
411 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | KING_SIDE)) : 'K');
413 if (can_castle(WHITE_OOO))
414 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE)) : 'Q');
416 if (can_castle(BLACK_OO))
417 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | KING_SIDE)) : 'k');
419 if (can_castle(BLACK_OOO))
420 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE)) : 'q');
422 if (!can_castle(WHITE) && !can_castle(BLACK))
425 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::format_square(ep_square()) + " ")
426 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
432 /// Position::pretty() returns an ASCII representation of the position
434 const string Position::pretty() const {
436 std::ostringstream ss;
438 ss << "\n +---+---+---+---+---+---+---+---+\n";
440 for (Rank r = RANK_8; r >= RANK_1; --r)
442 for (File f = FILE_A; f <= FILE_H; ++f)
443 ss << " | " << PieceToChar[piece_on(make_square(f, r))];
445 ss << " |\n +---+---+---+---+---+---+---+---+\n";
448 ss << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
449 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
451 for (Bitboard b = checkers(); b; )
452 ss << UCI::format_square(pop_lsb(&b)) << " ";
458 /// Position::game_phase() calculates the game phase interpolating total non-pawn
459 /// material between endgame and midgame limits.
461 Phase Position::game_phase() const {
463 Value npm = st->npMaterial[WHITE] + st->npMaterial[BLACK];
465 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
467 return Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));
471 /// Position::check_blockers() returns a bitboard of all the pieces with color
472 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
473 /// blocks a check if removing that piece from the board would result in a
474 /// position where the king is in check. A check blocking piece can be either a
475 /// pinned or a discovered check piece, according if its color 'c' is the same
476 /// or the opposite of 'kingColor'.
478 Bitboard Position::check_blockers(Color c, Color kingColor) const {
480 Bitboard b, pinners, result = 0;
481 Square ksq = king_square(kingColor);
483 // Pinners are sliders that give check when a pinned piece is removed
484 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
485 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
489 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
491 if (!more_than_one(b))
492 result |= b & pieces(c);
498 /// Position::attackers_to() computes a bitboard of all pieces which attack a
499 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
501 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
503 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
504 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
505 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
506 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
507 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
508 | (attacks_from<KING>(s) & pieces(KING));
512 /// Position::legal() tests whether a pseudo-legal move is legal
514 bool Position::legal(Move m, Bitboard pinned) const {
517 assert(pinned == pinned_pieces(sideToMove));
519 Color us = sideToMove;
520 Square from = from_sq(m);
522 assert(color_of(moved_piece(m)) == us);
523 assert(piece_on(king_square(us)) == make_piece(us, KING));
525 // En passant captures are a tricky special case. Because they are rather
526 // uncommon, we do it simply by testing whether the king is attacked after
528 if (type_of(m) == ENPASSANT)
530 Square ksq = king_square(us);
531 Square to = to_sq(m);
532 Square capsq = to - pawn_push(us);
533 Bitboard occ = (pieces() ^ from ^ capsq) | to;
535 assert(to == ep_square());
536 assert(moved_piece(m) == make_piece(us, PAWN));
537 assert(piece_on(capsq) == make_piece(~us, PAWN));
538 assert(piece_on(to) == NO_PIECE);
540 return !(attacks_bb< ROOK>(ksq, occ) & pieces(~us, QUEEN, ROOK))
541 && !(attacks_bb<BISHOP>(ksq, occ) & pieces(~us, QUEEN, BISHOP));
544 // If the moving piece is a king, check whether the destination
545 // square is attacked by the opponent. Castling moves are checked
546 // for legality during move generation.
547 if (type_of(piece_on(from)) == KING)
548 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
550 // A non-king move is legal if and only if it is not pinned or it
551 // is moving along the ray towards or away from the king.
554 || aligned(from, to_sq(m), king_square(us));
558 /// Position::pseudo_legal() takes a random move and tests whether the move is
559 /// pseudo legal. It is used to validate moves from TT that can be corrupted
560 /// due to SMP concurrent access or hash position key aliasing.
562 bool Position::pseudo_legal(const Move m) const {
564 Color us = sideToMove;
565 Square from = from_sq(m);
566 Square to = to_sq(m);
567 Piece pc = moved_piece(m);
569 // Use a slower but simpler function for uncommon cases
570 if (type_of(m) != NORMAL)
571 return MoveList<LEGAL>(*this).contains(m);
573 // Is not a promotion, so promotion piece must be empty
574 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
577 // If the 'from' square is not occupied by a piece belonging to the side to
578 // move, the move is obviously not legal.
579 if (pc == NO_PIECE || color_of(pc) != us)
582 // The destination square cannot be occupied by a friendly piece
586 // Handle the special case of a pawn move
587 if (type_of(pc) == PAWN)
589 // We have already handled promotion moves, so destination
590 // cannot be on the 8th/1st rank.
591 if (rank_of(to) == relative_rank(us, RANK_8))
594 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
596 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
598 && !( (from + 2 * pawn_push(us) == to) // Not a double push
599 && (rank_of(from) == relative_rank(us, RANK_2))
601 && empty(to - pawn_push(us))))
604 else if (!(attacks_from(pc, from) & to))
607 // Evasions generator already takes care to avoid some kind of illegal moves
608 // and legal() relies on this. We therefore have to take care that the same
609 // kind of moves are filtered out here.
612 if (type_of(pc) != KING)
614 // Double check? In this case a king move is required
615 if (more_than_one(checkers()))
618 // Our move must be a blocking evasion or a capture of the checking piece
619 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
622 // In case of king moves under check we have to remove king so as to catch
623 // invalid moves like b1a1 when opposite queen is on c1.
624 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
632 /// Position::gives_check() tests whether a pseudo-legal move gives a check
634 bool Position::gives_check(Move m, const CheckInfo& ci) const {
637 assert(ci.dcCandidates == discovered_check_candidates());
638 assert(color_of(moved_piece(m)) == sideToMove);
640 Square from = from_sq(m);
641 Square to = to_sq(m);
642 PieceType pt = type_of(piece_on(from));
644 // Is there a direct check?
645 if (ci.checkSq[pt] & to)
648 // Is there a discovered check?
649 if ( unlikely(ci.dcCandidates)
650 && (ci.dcCandidates & from)
651 && !aligned(from, to, ci.ksq))
660 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
662 // En passant capture with check? We have already handled the case
663 // of direct checks and ordinary discovered check, so the only case we
664 // need to handle is the unusual case of a discovered check through
665 // the captured pawn.
668 Square capsq = make_square(file_of(to), rank_of(from));
669 Bitboard b = (pieces() ^ from ^ capsq) | to;
671 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
672 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
677 Square rfrom = to; // Castling is encoded as 'King captures the rook'
678 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
679 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
681 return (PseudoAttacks[ROOK][rto] & ci.ksq)
682 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
691 /// Position::do_move() makes a move, and saves all information necessary
692 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
693 /// moves should be filtered out before this function is called.
695 void Position::do_move(Move m, StateInfo& newSt) {
698 do_move(m, newSt, ci, gives_check(m, ci));
701 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
704 assert(&newSt != st);
709 // Copy some fields of the old state to our new StateInfo object except the
710 // ones which are going to be recalculated from scratch anyway and then switch
711 // our state pointer to point to the new (ready to be updated) state.
712 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
717 // Update side to move
720 // Increment ply counters. In particular, rule50 will be reset to zero later on
721 // in case of a capture or a pawn move.
726 Color us = sideToMove;
728 Square from = from_sq(m);
729 Square to = to_sq(m);
730 Piece pc = piece_on(from);
731 PieceType pt = type_of(pc);
732 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
734 assert(color_of(pc) == us);
735 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
736 assert(captured != KING);
738 if (type_of(m) == CASTLING)
740 assert(pc == make_piece(us, KING));
743 do_castling<true>(from, to, rfrom, rto);
745 captured = NO_PIECE_TYPE;
746 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
747 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
754 // If the captured piece is a pawn, update pawn hash key, otherwise
755 // update non-pawn material.
756 if (captured == PAWN)
758 if (type_of(m) == ENPASSANT)
760 capsq += pawn_push(them);
763 assert(to == st->epSquare);
764 assert(relative_rank(us, to) == RANK_6);
765 assert(piece_on(to) == NO_PIECE);
766 assert(piece_on(capsq) == make_piece(them, PAWN));
768 board[capsq] = NO_PIECE;
771 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
774 st->npMaterial[them] -= PieceValue[MG][captured];
776 // Update board and piece lists
777 remove_piece(capsq, them, captured);
779 // Update material hash key and prefetch access to materialTable
780 k ^= Zobrist::psq[them][captured][capsq];
781 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
782 prefetch((char*)thisThread->materialTable[st->materialKey]);
784 // Update incremental scores
785 st->psq -= psq[them][captured][capsq];
787 // Reset rule 50 counter
792 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
794 // Reset en passant square
795 if (st->epSquare != SQ_NONE)
797 k ^= Zobrist::enpassant[file_of(st->epSquare)];
798 st->epSquare = SQ_NONE;
801 // Update castling rights if needed
802 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
804 int cr = castlingRightsMask[from] | castlingRightsMask[to];
805 k ^= Zobrist::castling[st->castlingRights & cr];
806 st->castlingRights &= ~cr;
809 // Move the piece. The tricky Chess960 castling is handled earlier
810 if (type_of(m) != CASTLING)
811 move_piece(from, to, us, pt);
813 // If the moving piece is a pawn do some special extra work
816 // Set en-passant square if the moved pawn can be captured
817 if ( (int(to) ^ int(from)) == 16
818 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
820 st->epSquare = Square((from + to) / 2);
821 k ^= Zobrist::enpassant[file_of(st->epSquare)];
824 else if (type_of(m) == PROMOTION)
826 PieceType promotion = promotion_type(m);
828 assert(relative_rank(us, to) == RANK_8);
829 assert(promotion >= KNIGHT && promotion <= QUEEN);
831 remove_piece(to, us, PAWN);
832 put_piece(to, us, promotion);
835 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
836 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
837 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
838 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
840 // Update incremental score
841 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
844 st->npMaterial[us] += PieceValue[MG][promotion];
847 // Update pawn hash key and prefetch access to pawnsTable
848 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
849 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
851 // Reset rule 50 draw counter
855 // Update incremental scores
856 st->psq += psq[us][pt][to] - psq[us][pt][from];
859 st->capturedType = captured;
861 // Update the key with the final value
864 // Update checkers bitboard: piece must be already moved due to attacks_from()
869 if (type_of(m) != NORMAL)
870 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
874 if (ci.checkSq[pt] & to)
875 st->checkersBB |= to;
878 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
881 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
884 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
889 sideToMove = ~sideToMove;
895 /// Position::undo_move() unmakes a move. When it returns, the position should
896 /// be restored to exactly the same state as before the move was made.
898 void Position::undo_move(Move m) {
902 sideToMove = ~sideToMove;
904 Color us = sideToMove;
905 Square from = from_sq(m);
906 Square to = to_sq(m);
907 PieceType pt = type_of(piece_on(to));
909 assert(empty(from) || type_of(m) == CASTLING);
910 assert(st->capturedType != KING);
912 if (type_of(m) == PROMOTION)
914 assert(pt == promotion_type(m));
915 assert(relative_rank(us, to) == RANK_8);
916 assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
918 remove_piece(to, us, promotion_type(m));
919 put_piece(to, us, PAWN);
923 if (type_of(m) == CASTLING)
926 do_castling<false>(from, to, rfrom, rto);
930 move_piece(to, from, us, pt); // Put the piece back at the source square
932 if (st->capturedType)
936 if (type_of(m) == ENPASSANT)
938 capsq -= pawn_push(us);
941 assert(to == st->previous->epSquare);
942 assert(relative_rank(us, to) == RANK_6);
943 assert(piece_on(capsq) == NO_PIECE);
946 put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
950 // Finally point our state pointer back to the previous state
958 /// Position::do_castling() is a helper used to do/undo a castling move. This
959 /// is a bit tricky, especially in Chess960.
961 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
963 bool kingSide = to > from;
964 rfrom = to; // Castling is encoded as "king captures friendly rook"
965 rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
966 to = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
968 // Remove both pieces first since squares could overlap in Chess960
969 remove_piece(Do ? from : to, sideToMove, KING);
970 remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
971 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
972 put_piece(Do ? to : from, sideToMove, KING);
973 put_piece(Do ? rto : rfrom, sideToMove, ROOK);
977 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
978 /// the side to move without executing any move on the board.
980 void Position::do_null_move(StateInfo& newSt) {
984 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
989 if (st->epSquare != SQ_NONE)
991 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
992 st->epSquare = SQ_NONE;
995 st->key ^= Zobrist::side;
996 prefetch((char*)TT.first_entry(st->key));
999 st->pliesFromNull = 0;
1001 sideToMove = ~sideToMove;
1003 assert(pos_is_ok());
1006 void Position::undo_null_move() {
1008 assert(!checkers());
1011 sideToMove = ~sideToMove;
1015 /// Position::key_after() computes the new hash key after the given moven. Needed
1016 /// for speculative prefetch. It doesn't recognize special moves like castling,
1017 /// en-passant and promotions.
1019 Key Position::key_after(Move m) const {
1021 Color us = sideToMove;
1022 Square from = from_sq(m);
1023 Square to = to_sq(m);
1024 PieceType pt = type_of(piece_on(from));
1025 PieceType captured = type_of(piece_on(to));
1026 Key k = st->key ^ Zobrist::side;
1029 k ^= Zobrist::psq[~us][captured][to];
1031 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1035 /// Position::see() is a static exchange evaluator: It tries to estimate the
1036 /// material gain or loss resulting from a move.
1038 Value Position::see_sign(Move m) const {
1042 // Early return if SEE cannot be negative because captured piece value
1043 // is not less then capturing one. Note that king moves always return
1044 // here because king midgame value is set to 0.
1045 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1046 return VALUE_KNOWN_WIN;
1051 Value Position::see(Move m) const {
1054 Bitboard occupied, attackers, stmAttackers;
1064 swapList[0] = PieceValue[MG][piece_on(to)];
1065 stm = color_of(piece_on(from));
1066 occupied = pieces() ^ from;
1068 // Castling moves are implemented as king capturing the rook so cannot be
1069 // handled correctly. Simply return 0 that is always the correct value
1070 // unless in the rare case the rook ends up under attack.
1071 if (type_of(m) == CASTLING)
1074 if (type_of(m) == ENPASSANT)
1076 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1077 swapList[0] = PieceValue[MG][PAWN];
1080 // Find all attackers to the destination square, with the moving piece
1081 // removed, but possibly an X-ray attacker added behind it.
1082 attackers = attackers_to(to, occupied) & occupied;
1084 // If the opponent has no attackers we are finished
1086 stmAttackers = attackers & pieces(stm);
1090 // The destination square is defended, which makes things rather more
1091 // difficult to compute. We proceed by building up a "swap list" containing
1092 // the material gain or loss at each stop in a sequence of captures to the
1093 // destination square, where the sides alternately capture, and always
1094 // capture with the least valuable piece. After each capture, we look for
1095 // new X-ray attacks from behind the capturing piece.
1096 captured = type_of(piece_on(from));
1099 assert(slIndex < 32);
1101 // Add the new entry to the swap list
1102 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1104 // Locate and remove the next least valuable attacker
1105 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1107 // Stop before processing a king capture
1108 if (captured == KING)
1110 if (stmAttackers == attackers)
1117 stmAttackers = attackers & pieces(stm);
1120 } while (stmAttackers);
1122 // Having built the swap list, we negamax through it to find the best
1123 // achievable score from the point of view of the side to move.
1125 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1131 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1132 /// rule or repetition. It does not detect stalemates.
1134 bool Position::is_draw() const {
1136 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1139 StateInfo* stp = st;
1140 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1142 stp = stp->previous->previous;
1144 if (stp->key == st->key)
1145 return true; // Draw at first repetition
1152 /// Position::flip() flips position with the white and black sides reversed. This
1153 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1155 static char toggle_case(char c) {
1156 return char(islower(c) ? toupper(c) : tolower(c));
1159 void Position::flip() {
1162 std::stringstream ss(fen());
1164 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1166 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1167 f.insert(0, token + (f.empty() ? " " : "/"));
1170 ss >> token; // Active color
1171 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1173 ss >> token; // Castling availability
1176 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1178 ss >> token; // En passant square
1179 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1181 std::getline(ss, token); // Half and full moves
1184 set(f, is_chess960(), this_thread());
1186 assert(pos_is_ok());
1190 /// Position::pos_is_ok() performs some consistency checks for the position object.
1191 /// This is meant to be helpful when debugging.
1193 bool Position::pos_is_ok(int* step) const {
1195 // Which parts of the position should be verified?
1196 const bool all = false;
1198 const bool testBitboards = all || false;
1199 const bool testState = all || false;
1200 const bool testKingCount = all || false;
1201 const bool testKingCapture = all || false;
1202 const bool testPieceCounts = all || false;
1203 const bool testPieceList = all || false;
1204 const bool testCastlingSquares = all || false;
1209 if ( (sideToMove != WHITE && sideToMove != BLACK)
1210 || piece_on(king_square(WHITE)) != W_KING
1211 || piece_on(king_square(BLACK)) != B_KING
1212 || ( ep_square() != SQ_NONE
1213 && relative_rank(sideToMove, ep_square()) != RANK_6))
1216 if (step && ++*step, testBitboards)
1218 // The intersection of the white and black pieces must be empty
1219 if (pieces(WHITE) & pieces(BLACK))
1222 // The union of the white and black pieces must be equal to all
1224 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1227 // Separate piece type bitboards must have empty intersections
1228 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1229 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1230 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1234 if (step && ++*step, testState)
1238 if ( st->key != si.key
1239 || st->pawnKey != si.pawnKey
1240 || st->materialKey != si.materialKey
1241 || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1242 || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1243 || st->psq != si.psq
1244 || st->checkersBB != si.checkersBB)
1248 if (step && ++*step, testKingCount)
1249 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1250 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1253 if (step && ++*step, testKingCapture)
1254 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1257 if (step && ++*step, testPieceCounts)
1258 for (Color c = WHITE; c <= BLACK; ++c)
1259 for (PieceType pt = PAWN; pt <= KING; ++pt)
1260 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1263 if (step && ++*step, testPieceList)
1264 for (Color c = WHITE; c <= BLACK; ++c)
1265 for (PieceType pt = PAWN; pt <= KING; ++pt)
1266 for (int i = 0; i < pieceCount[c][pt]; ++i)
1267 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1268 || index[pieceList[c][pt][i]] != i)
1271 if (step && ++*step, testCastlingSquares)
1272 for (Color c = WHITE; c <= BLACK; ++c)
1273 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1275 if (!can_castle(c | s))
1278 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1279 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1280 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))