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/>.
37 static const string PieceToChar(" PNBRQK pnbrqk");
41 Value PieceValue[PHASE_NB][PIECE_NB] = {
42 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
43 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
45 static Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
49 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
50 Key enpassant[FILE_NB];
51 Key castling[CASTLING_RIGHT_NB];
56 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
60 // min_attacker() is a helper function used by see() to locate the least
61 // valuable attacker for the side to move, remove the attacker we just found
62 // from the bitboards and scan for new X-ray attacks behind it.
64 template<int Pt> FORCE_INLINE
65 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
66 Bitboard& occupied, Bitboard& attackers) {
68 Bitboard b = stmAttackers & bb[Pt];
70 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
72 occupied ^= b & ~(b - 1);
74 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
75 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
77 if (Pt == ROOK || Pt == QUEEN)
78 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
80 attackers &= occupied; // After X-ray that may add already processed pieces
84 template<> FORCE_INLINE
85 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
86 return KING; // No need to update bitboards: it is the last cycle
94 CheckInfo::CheckInfo(const Position& pos) {
96 Color them = ~pos.side_to_move();
97 ksq = pos.king_square(them);
99 pinned = pos.pinned_pieces(pos.side_to_move());
100 dcCandidates = pos.discovered_check_candidates();
102 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
103 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
104 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
105 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
106 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
111 /// operator<<(Position) returns an ASCII representation of the position
113 std::ostream& operator<<(std::ostream& os, const Position& pos) {
115 os << "\n +---+---+---+---+---+---+---+---+\n";
117 for (Rank r = RANK_8; r >= RANK_1; --r)
119 for (File f = FILE_A; f <= FILE_H; ++f)
120 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
122 os << " |\n +---+---+---+---+---+---+---+---+\n";
125 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
126 << std::setfill('0') << std::setw(16) << pos.st->key << "\nCheckers: ";
128 for (Bitboard b = pos.checkers(); b; )
129 os << UCI::format_square(pop_lsb(&b)) << " ";
135 /// Position::init() initializes at startup the various arrays used to compute
136 /// hash keys and the piece square tables. The latter is a two-step operation:
137 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
138 /// Secondly, the black halves of the tables are initialized by flipping and
139 /// changing the sign of the white scores.
141 void Position::init() {
145 for (Color c = WHITE; c <= BLACK; ++c)
146 for (PieceType pt = PAWN; pt <= KING; ++pt)
147 for (Square s = SQ_A1; s <= SQ_H8; ++s)
148 Zobrist::psq[c][pt][s] = rk.rand<Key>();
150 for (File f = FILE_A; f <= FILE_H; ++f)
151 Zobrist::enpassant[f] = rk.rand<Key>();
153 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
158 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
159 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
163 Zobrist::side = rk.rand<Key>();
164 Zobrist::exclusion = rk.rand<Key>();
166 for (PieceType pt = PAWN; pt <= KING; ++pt)
168 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
169 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
171 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
173 for (Square s = SQ_A1; s <= SQ_H8; ++s)
175 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
176 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
182 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
183 /// object to not depend on any external data so we detach state pointer from
186 Position& Position::operator=(const Position& pos) {
188 std::memcpy(this, &pos, sizeof(Position));
199 /// Position::clear() erases the position object to a pristine state, with an
200 /// empty board, white to move, and no castling rights.
202 void Position::clear() {
204 std::memset(this, 0, sizeof(Position));
205 startState.epSquare = SQ_NONE;
208 for (int i = 0; i < PIECE_TYPE_NB; ++i)
209 for (int j = 0; j < 16; ++j)
210 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
214 /// Position::set() initializes the position object with the given FEN string.
215 /// This function is not very robust - make sure that input FENs are correct,
216 /// this is assumed to be the responsibility of the GUI.
218 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
220 A FEN string defines a particular position using only the ASCII character set.
222 A FEN string contains six fields separated by a space. The fields are:
224 1) Piece placement (from white's perspective). Each rank is described, starting
225 with rank 8 and ending with rank 1. Within each rank, the contents of each
226 square are described from file A through file H. Following the Standard
227 Algebraic Notation (SAN), each piece is identified by a single letter taken
228 from the standard English names. White pieces are designated using upper-case
229 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
230 noted using digits 1 through 8 (the number of blank squares), and "/"
233 2) Active color. "w" means white moves next, "b" means black.
235 3) Castling availability. If neither side can castle, this is "-". Otherwise,
236 this has one or more letters: "K" (White can castle kingside), "Q" (White
237 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
238 can castle queenside).
240 4) En passant target square (in algebraic notation). If there's no en passant
241 target square, this is "-". If a pawn has just made a 2-square move, this
242 is the position "behind" the pawn. This is recorded regardless of whether
243 there is a pawn in position to make an en passant capture.
245 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
246 or capture. This is used to determine if a draw can be claimed under the
249 6) Fullmove number. The number of the full move. It starts at 1, and is
250 incremented after Black's move.
253 unsigned char col, row, token;
256 std::istringstream ss(fenStr);
261 // 1. Piece placement
262 while ((ss >> token) && !isspace(token))
265 sq += Square(token - '0'); // Advance the given number of files
267 else if (token == '/')
270 else if ((idx = PieceToChar.find(token)) != string::npos)
272 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
279 sideToMove = (token == 'w' ? WHITE : BLACK);
282 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
283 // Shredder-FEN that uses the letters of the columns on which the rooks began
284 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
285 // if an inner rook is associated with the castling right, the castling tag is
286 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
287 while ((ss >> token) && !isspace(token))
290 Color c = islower(token) ? BLACK : WHITE;
292 token = char(toupper(token));
295 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
297 else if (token == 'Q')
298 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
300 else if (token >= 'A' && token <= 'H')
301 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
306 set_castling_right(c, rsq);
309 // 4. En passant square. Ignore if no pawn capture is possible
310 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
311 && ((ss >> row) && (row == '3' || row == '6')))
313 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
315 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
316 st->epSquare = SQ_NONE;
319 // 5-6. Halfmove clock and fullmove number
320 ss >> std::skipws >> st->rule50 >> gamePly;
322 // Convert from fullmove starting from 1 to ply starting from 0,
323 // handle also common incorrect FEN with fullmove = 0.
324 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
326 chess960 = isChess960;
334 /// Position::set_castling_right() is a helper function used to set castling
335 /// rights given the corresponding color and the rook starting square.
337 void Position::set_castling_right(Color c, Square rfrom) {
339 Square kfrom = king_square(c);
340 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
341 CastlingRight cr = (c | cs);
343 st->castlingRights |= cr;
344 castlingRightsMask[kfrom] |= cr;
345 castlingRightsMask[rfrom] |= cr;
346 castlingRookSquare[cr] = rfrom;
348 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
349 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
351 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
352 if (s != kfrom && s != rfrom)
353 castlingPath[cr] |= s;
355 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
356 if (s != kfrom && s != rfrom)
357 castlingPath[cr] |= s;
361 /// Position::set_state() computes the hash keys of the position, and other
362 /// data that once computed is updated incrementally as moves are made.
363 /// The function is only used when a new position is set up, and to verify
364 /// the correctness of the StateInfo data when running in debug mode.
366 void Position::set_state(StateInfo* si) const {
368 si->key = si->pawnKey = si->materialKey = 0;
369 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
370 si->psq = SCORE_ZERO;
372 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
374 for (Bitboard b = pieces(); b; )
376 Square s = pop_lsb(&b);
377 Piece pc = piece_on(s);
378 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
379 si->psq += psq[color_of(pc)][type_of(pc)][s];
382 if (ep_square() != SQ_NONE)
383 si->key ^= Zobrist::enpassant[file_of(ep_square())];
385 if (sideToMove == BLACK)
386 si->key ^= Zobrist::side;
388 si->key ^= Zobrist::castling[st->castlingRights];
390 for (Bitboard b = pieces(PAWN); b; )
392 Square s = pop_lsb(&b);
393 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
396 for (Color c = WHITE; c <= BLACK; ++c)
397 for (PieceType pt = PAWN; pt <= KING; ++pt)
398 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
399 si->materialKey ^= Zobrist::psq[c][pt][cnt];
401 for (Color c = WHITE; c <= BLACK; ++c)
402 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
403 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
407 /// Position::fen() returns a FEN representation of the position. In case of
408 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
410 const string Position::fen() const {
413 std::ostringstream ss;
415 for (Rank r = RANK_8; r >= RANK_1; --r)
417 for (File f = FILE_A; f <= FILE_H; ++f)
419 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
426 ss << PieceToChar[piece_on(make_square(f, r))];
433 ss << (sideToMove == WHITE ? " w " : " b ");
435 if (can_castle(WHITE_OO))
436 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | KING_SIDE)) : 'K');
438 if (can_castle(WHITE_OOO))
439 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE)) : 'Q');
441 if (can_castle(BLACK_OO))
442 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | KING_SIDE)) : 'k');
444 if (can_castle(BLACK_OOO))
445 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE)) : 'q');
447 if (!can_castle(WHITE) && !can_castle(BLACK))
450 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::format_square(ep_square()) + " ")
451 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
457 /// Position::game_phase() calculates the game phase interpolating total non-pawn
458 /// material between endgame and midgame limits.
460 Phase Position::game_phase() const {
462 Value npm = st->npMaterial[WHITE] + st->npMaterial[BLACK];
464 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
466 return Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));
470 /// Position::check_blockers() returns a bitboard of all the pieces with color
471 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
472 /// blocks a check if removing that piece from the board would result in a
473 /// position where the king is in check. A check blocking piece can be either a
474 /// pinned or a discovered check piece, according if its color 'c' is the same
475 /// or the opposite of 'kingColor'.
477 Bitboard Position::check_blockers(Color c, Color kingColor) const {
479 Bitboard b, pinners, result = 0;
480 Square ksq = king_square(kingColor);
482 // Pinners are sliders that give check when a pinned piece is removed
483 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
484 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
488 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
490 if (!more_than_one(b))
491 result |= b & pieces(c);
497 /// Position::attackers_to() computes a bitboard of all pieces which attack a
498 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
500 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
502 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
503 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
504 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
505 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
506 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
507 | (attacks_from<KING>(s) & pieces(KING));
511 /// Position::legal() tests whether a pseudo-legal move is legal
513 bool Position::legal(Move m, Bitboard pinned) const {
516 assert(pinned == pinned_pieces(sideToMove));
518 Color us = sideToMove;
519 Square from = from_sq(m);
521 assert(color_of(moved_piece(m)) == us);
522 assert(piece_on(king_square(us)) == make_piece(us, KING));
524 // En passant captures are a tricky special case. Because they are rather
525 // uncommon, we do it simply by testing whether the king is attacked after
527 if (type_of(m) == ENPASSANT)
529 Square ksq = king_square(us);
530 Square to = to_sq(m);
531 Square capsq = to - pawn_push(us);
532 Bitboard occ = (pieces() ^ from ^ capsq) | to;
534 assert(to == ep_square());
535 assert(moved_piece(m) == make_piece(us, PAWN));
536 assert(piece_on(capsq) == make_piece(~us, PAWN));
537 assert(piece_on(to) == NO_PIECE);
539 return !(attacks_bb< ROOK>(ksq, occ) & pieces(~us, QUEEN, ROOK))
540 && !(attacks_bb<BISHOP>(ksq, occ) & pieces(~us, QUEEN, BISHOP));
543 // If the moving piece is a king, check whether the destination
544 // square is attacked by the opponent. Castling moves are checked
545 // for legality during move generation.
546 if (type_of(piece_on(from)) == KING)
547 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
549 // A non-king move is legal if and only if it is not pinned or it
550 // is moving along the ray towards or away from the king.
553 || aligned(from, to_sq(m), king_square(us));
557 /// Position::pseudo_legal() takes a random move and tests whether the move is
558 /// pseudo legal. It is used to validate moves from TT that can be corrupted
559 /// due to SMP concurrent access or hash position key aliasing.
561 bool Position::pseudo_legal(const Move m) const {
563 Color us = sideToMove;
564 Square from = from_sq(m);
565 Square to = to_sq(m);
566 Piece pc = moved_piece(m);
568 // Use a slower but simpler function for uncommon cases
569 if (type_of(m) != NORMAL)
570 return MoveList<LEGAL>(*this).contains(m);
572 // Is not a promotion, so promotion piece must be empty
573 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
576 // If the 'from' square is not occupied by a piece belonging to the side to
577 // move, the move is obviously not legal.
578 if (pc == NO_PIECE || color_of(pc) != us)
581 // The destination square cannot be occupied by a friendly piece
585 // Handle the special case of a pawn move
586 if (type_of(pc) == PAWN)
588 // We have already handled promotion moves, so destination
589 // cannot be on the 8th/1st rank.
590 if (rank_of(to) == relative_rank(us, RANK_8))
593 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
595 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
597 && !( (from + 2 * pawn_push(us) == to) // Not a double push
598 && (rank_of(from) == relative_rank(us, RANK_2))
600 && empty(to - pawn_push(us))))
603 else if (!(attacks_from(pc, from) & to))
606 // Evasions generator already takes care to avoid some kind of illegal moves
607 // and legal() relies on this. We therefore have to take care that the same
608 // kind of moves are filtered out here.
611 if (type_of(pc) != KING)
613 // Double check? In this case a king move is required
614 if (more_than_one(checkers()))
617 // Our move must be a blocking evasion or a capture of the checking piece
618 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
621 // In case of king moves under check we have to remove king so as to catch
622 // invalid moves like b1a1 when opposite queen is on c1.
623 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
631 /// Position::gives_check() tests whether a pseudo-legal move gives a check
633 bool Position::gives_check(Move m, const CheckInfo& ci) const {
636 assert(ci.dcCandidates == discovered_check_candidates());
637 assert(color_of(moved_piece(m)) == sideToMove);
639 Square from = from_sq(m);
640 Square to = to_sq(m);
641 PieceType pt = type_of(piece_on(from));
643 // Is there a direct check?
644 if (ci.checkSq[pt] & to)
647 // Is there a discovered check?
648 if ( unlikely(ci.dcCandidates)
649 && (ci.dcCandidates & from)
650 && !aligned(from, to, ci.ksq))
659 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
661 // En passant capture with check? We have already handled the case
662 // of direct checks and ordinary discovered check, so the only case we
663 // need to handle is the unusual case of a discovered check through
664 // the captured pawn.
667 Square capsq = make_square(file_of(to), rank_of(from));
668 Bitboard b = (pieces() ^ from ^ capsq) | to;
670 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
671 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
676 Square rfrom = to; // Castling is encoded as 'King captures the rook'
677 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
678 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
680 return (PseudoAttacks[ROOK][rto] & ci.ksq)
681 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
690 /// Position::do_move() makes a move, and saves all information necessary
691 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
692 /// moves should be filtered out before this function is called.
694 void Position::do_move(Move m, StateInfo& newSt) {
697 do_move(m, newSt, ci, gives_check(m, ci));
700 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
703 assert(&newSt != st);
708 // Copy some fields of the old state to our new StateInfo object except the
709 // ones which are going to be recalculated from scratch anyway and then switch
710 // our state pointer to point to the new (ready to be updated) state.
711 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
716 // Update side to move
719 // Increment ply counters. In particular, rule50 will be reset to zero later on
720 // in case of a capture or a pawn move.
725 Color us = sideToMove;
727 Square from = from_sq(m);
728 Square to = to_sq(m);
729 Piece pc = piece_on(from);
730 PieceType pt = type_of(pc);
731 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
733 assert(color_of(pc) == us);
734 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
735 assert(captured != KING);
737 if (type_of(m) == CASTLING)
739 assert(pc == make_piece(us, KING));
742 do_castling<true>(from, to, rfrom, rto);
744 captured = NO_PIECE_TYPE;
745 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
746 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
753 // If the captured piece is a pawn, update pawn hash key, otherwise
754 // update non-pawn material.
755 if (captured == PAWN)
757 if (type_of(m) == ENPASSANT)
759 capsq += pawn_push(them);
762 assert(to == st->epSquare);
763 assert(relative_rank(us, to) == RANK_6);
764 assert(piece_on(to) == NO_PIECE);
765 assert(piece_on(capsq) == make_piece(them, PAWN));
767 board[capsq] = NO_PIECE;
770 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
773 st->npMaterial[them] -= PieceValue[MG][captured];
775 // Update board and piece lists
776 remove_piece(capsq, them, captured);
778 // Update material hash key and prefetch access to materialTable
779 k ^= Zobrist::psq[them][captured][capsq];
780 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
781 prefetch((char*)thisThread->materialTable[st->materialKey]);
783 // Update incremental scores
784 st->psq -= psq[them][captured][capsq];
786 // Reset rule 50 counter
791 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
793 // Reset en passant square
794 if (st->epSquare != SQ_NONE)
796 k ^= Zobrist::enpassant[file_of(st->epSquare)];
797 st->epSquare = SQ_NONE;
800 // Update castling rights if needed
801 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
803 int cr = castlingRightsMask[from] | castlingRightsMask[to];
804 k ^= Zobrist::castling[st->castlingRights & cr];
805 st->castlingRights &= ~cr;
808 // Move the piece. The tricky Chess960 castling is handled earlier
809 if (type_of(m) != CASTLING)
810 move_piece(from, to, us, pt);
812 // If the moving piece is a pawn do some special extra work
815 // Set en-passant square if the moved pawn can be captured
816 if ( (int(to) ^ int(from)) == 16
817 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
819 st->epSquare = Square((from + to) / 2);
820 k ^= Zobrist::enpassant[file_of(st->epSquare)];
823 else if (type_of(m) == PROMOTION)
825 PieceType promotion = promotion_type(m);
827 assert(relative_rank(us, to) == RANK_8);
828 assert(promotion >= KNIGHT && promotion <= QUEEN);
830 remove_piece(to, us, PAWN);
831 put_piece(to, us, promotion);
834 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
835 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
836 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
837 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
839 // Update incremental score
840 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
843 st->npMaterial[us] += PieceValue[MG][promotion];
846 // Update pawn hash key and prefetch access to pawnsTable
847 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
848 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
850 // Reset rule 50 draw counter
854 // Update incremental scores
855 st->psq += psq[us][pt][to] - psq[us][pt][from];
858 st->capturedType = captured;
860 // Update the key with the final value
863 // Update checkers bitboard: piece must be already moved due to attacks_from()
868 if (type_of(m) != NORMAL)
869 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
873 if (ci.checkSq[pt] & to)
874 st->checkersBB |= to;
877 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
880 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
883 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
888 sideToMove = ~sideToMove;
894 /// Position::undo_move() unmakes a move. When it returns, the position should
895 /// be restored to exactly the same state as before the move was made.
897 void Position::undo_move(Move m) {
901 sideToMove = ~sideToMove;
903 Color us = sideToMove;
904 Square from = from_sq(m);
905 Square to = to_sq(m);
906 PieceType pt = type_of(piece_on(to));
908 assert(empty(from) || type_of(m) == CASTLING);
909 assert(st->capturedType != KING);
911 if (type_of(m) == PROMOTION)
913 assert(pt == promotion_type(m));
914 assert(relative_rank(us, to) == RANK_8);
915 assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
917 remove_piece(to, us, promotion_type(m));
918 put_piece(to, us, PAWN);
922 if (type_of(m) == CASTLING)
925 do_castling<false>(from, to, rfrom, rto);
929 move_piece(to, from, us, pt); // Put the piece back at the source square
931 if (st->capturedType)
935 if (type_of(m) == ENPASSANT)
937 capsq -= pawn_push(us);
940 assert(to == st->previous->epSquare);
941 assert(relative_rank(us, to) == RANK_6);
942 assert(piece_on(capsq) == NO_PIECE);
945 put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
949 // Finally point our state pointer back to the previous state
957 /// Position::do_castling() is a helper used to do/undo a castling move. This
958 /// is a bit tricky, especially in Chess960.
960 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
962 bool kingSide = to > from;
963 rfrom = to; // Castling is encoded as "king captures friendly rook"
964 rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
965 to = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
967 // Remove both pieces first since squares could overlap in Chess960
968 remove_piece(Do ? from : to, sideToMove, KING);
969 remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
970 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
971 put_piece(Do ? to : from, sideToMove, KING);
972 put_piece(Do ? rto : rfrom, sideToMove, ROOK);
976 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
977 /// the side to move without executing any move on the board.
979 void Position::do_null_move(StateInfo& newSt) {
983 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
988 if (st->epSquare != SQ_NONE)
990 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
991 st->epSquare = SQ_NONE;
994 st->key ^= Zobrist::side;
995 prefetch((char*)TT.first_entry(st->key));
998 st->pliesFromNull = 0;
1000 sideToMove = ~sideToMove;
1002 assert(pos_is_ok());
1005 void Position::undo_null_move() {
1007 assert(!checkers());
1010 sideToMove = ~sideToMove;
1014 /// Position::key_after() computes the new hash key after the given moven. Needed
1015 /// for speculative prefetch. It doesn't recognize special moves like castling,
1016 /// en-passant and promotions.
1018 Key Position::key_after(Move m) const {
1020 Color us = sideToMove;
1021 Square from = from_sq(m);
1022 Square to = to_sq(m);
1023 PieceType pt = type_of(piece_on(from));
1024 PieceType captured = type_of(piece_on(to));
1025 Key k = st->key ^ Zobrist::side;
1028 k ^= Zobrist::psq[~us][captured][to];
1030 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1034 /// Position::see() is a static exchange evaluator: It tries to estimate the
1035 /// material gain or loss resulting from a move.
1037 Value Position::see_sign(Move m) const {
1041 // Early return if SEE cannot be negative because captured piece value
1042 // is not less then capturing one. Note that king moves always return
1043 // here because king midgame value is set to 0.
1044 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1045 return VALUE_KNOWN_WIN;
1050 Value Position::see(Move m) const {
1053 Bitboard occupied, attackers, stmAttackers;
1063 swapList[0] = PieceValue[MG][piece_on(to)];
1064 stm = color_of(piece_on(from));
1065 occupied = pieces() ^ from;
1067 // Castling moves are implemented as king capturing the rook so cannot be
1068 // handled correctly. Simply return 0 that is always the correct value
1069 // unless in the rare case the rook ends up under attack.
1070 if (type_of(m) == CASTLING)
1073 if (type_of(m) == ENPASSANT)
1075 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1076 swapList[0] = PieceValue[MG][PAWN];
1079 // Find all attackers to the destination square, with the moving piece
1080 // removed, but possibly an X-ray attacker added behind it.
1081 attackers = attackers_to(to, occupied) & occupied;
1083 // If the opponent has no attackers we are finished
1085 stmAttackers = attackers & pieces(stm);
1089 // The destination square is defended, which makes things rather more
1090 // difficult to compute. We proceed by building up a "swap list" containing
1091 // the material gain or loss at each stop in a sequence of captures to the
1092 // destination square, where the sides alternately capture, and always
1093 // capture with the least valuable piece. After each capture, we look for
1094 // new X-ray attacks from behind the capturing piece.
1095 captured = type_of(piece_on(from));
1098 assert(slIndex < 32);
1100 // Add the new entry to the swap list
1101 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1103 // Locate and remove the next least valuable attacker
1104 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1106 // Stop before processing a king capture
1107 if (captured == KING)
1109 if (stmAttackers == attackers)
1116 stmAttackers = attackers & pieces(stm);
1119 } while (stmAttackers);
1121 // Having built the swap list, we negamax through it to find the best
1122 // achievable score from the point of view of the side to move.
1124 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1130 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1131 /// rule or repetition. It does not detect stalemates.
1133 bool Position::is_draw() const {
1135 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1138 StateInfo* stp = st;
1139 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1141 stp = stp->previous->previous;
1143 if (stp->key == st->key)
1144 return true; // Draw at first repetition
1151 /// Position::flip() flips position with the white and black sides reversed. This
1152 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1154 static char toggle_case(char c) {
1155 return char(islower(c) ? toupper(c) : tolower(c));
1158 void Position::flip() {
1161 std::stringstream ss(fen());
1163 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1165 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1166 f.insert(0, token + (f.empty() ? " " : "/"));
1169 ss >> token; // Active color
1170 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1172 ss >> token; // Castling availability
1175 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1177 ss >> token; // En passant square
1178 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1180 std::getline(ss, token); // Half and full moves
1183 set(f, is_chess960(), this_thread());
1185 assert(pos_is_ok());
1189 /// Position::pos_is_ok() performs some consistency checks for the position object.
1190 /// This is meant to be helpful when debugging.
1192 bool Position::pos_is_ok(int* step) const {
1194 // Which parts of the position should be verified?
1195 const bool all = false;
1197 const bool testBitboards = all || false;
1198 const bool testState = all || false;
1199 const bool testKingCount = all || false;
1200 const bool testKingCapture = all || false;
1201 const bool testPieceCounts = all || false;
1202 const bool testPieceList = all || false;
1203 const bool testCastlingSquares = all || false;
1208 if ( (sideToMove != WHITE && sideToMove != BLACK)
1209 || piece_on(king_square(WHITE)) != W_KING
1210 || piece_on(king_square(BLACK)) != B_KING
1211 || ( ep_square() != SQ_NONE
1212 && relative_rank(sideToMove, ep_square()) != RANK_6))
1215 if (step && ++*step, testBitboards)
1217 // The intersection of the white and black pieces must be empty
1218 if (pieces(WHITE) & pieces(BLACK))
1221 // The union of the white and black pieces must be equal to all
1223 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1226 // Separate piece type bitboards must have empty intersections
1227 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1228 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1229 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1233 if (step && ++*step, testState)
1237 if ( st->key != si.key
1238 || st->pawnKey != si.pawnKey
1239 || st->materialKey != si.materialKey
1240 || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1241 || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1242 || st->psq != si.psq
1243 || st->checkersBB != si.checkersBB)
1247 if (step && ++*step, testKingCount)
1248 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1249 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1252 if (step && ++*step, testKingCapture)
1253 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1256 if (step && ++*step, testPieceCounts)
1257 for (Color c = WHITE; c <= BLACK; ++c)
1258 for (PieceType pt = PAWN; pt <= KING; ++pt)
1259 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1262 if (step && ++*step, testPieceList)
1263 for (Color c = WHITE; c <= BLACK; ++c)
1264 for (PieceType pt = PAWN; pt <= KING; ++pt)
1265 for (int i = 0; i < pieceCount[c][pt]; ++i)
1266 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1267 || index[pieceList[c][pt][i]] != i)
1270 if (step && ++*step, testCastlingSquares)
1271 for (Color c = WHITE; c <= BLACK; ++c)
1272 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1274 if (!can_castle(c | s))
1277 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1278 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1279 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))