2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
7 Stockfish is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 #include <cstring> // For std::memset, std::memcmp
39 Key psq[PIECE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
47 const string PieceToChar(" PNBRQK pnbrqk");
49 // min_attacker() is a helper function used by see() to locate the least
50 // valuable attacker for the side to move, remove the attacker we just found
51 // from the bitboards and scan for new X-ray attacks behind it.
54 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
55 Bitboard& occupied, Bitboard& attackers) {
57 Bitboard b = stmAttackers & bb[Pt];
59 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
61 occupied ^= b & ~(b - 1);
63 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
64 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
66 if (Pt == ROOK || Pt == QUEEN)
67 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
69 attackers &= occupied; // After X-ray that may add already processed pieces
74 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
75 return KING; // No need to update bitboards: it is the last cycle
81 /// operator<<(Position) returns an ASCII representation of the position
83 std::ostream& operator<<(std::ostream& os, const Position& pos) {
85 os << "\n +---+---+---+---+---+---+---+---+\n";
87 for (Rank r = RANK_8; r >= RANK_1; --r)
89 for (File f = FILE_A; f <= FILE_H; ++f)
90 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
92 os << " |\n +---+---+---+---+---+---+---+---+\n";
95 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
96 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
98 for (Bitboard b = pos.checkers(); b; )
99 os << UCI::square(pop_lsb(&b)) << " ";
105 /// Position::init() initializes at startup the various arrays used to compute
108 void Position::init() {
112 for (Color c = WHITE; c <= BLACK; ++c)
113 for (PieceType pt = PAWN; pt <= KING; ++pt)
114 for (Square s = SQ_A1; s <= SQ_H8; ++s)
115 Zobrist::psq[make_piece(c, pt)][s] = rng.rand<Key>();
117 for (File f = FILE_A; f <= FILE_H; ++f)
118 Zobrist::enpassant[f] = rng.rand<Key>();
120 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
122 Zobrist::castling[cr] = 0;
126 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
127 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
131 Zobrist::side = rng.rand<Key>();
135 /// Position::set() initializes the position object with the given FEN string.
136 /// This function is not very robust - make sure that input FENs are correct,
137 /// this is assumed to be the responsibility of the GUI.
139 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
141 A FEN string defines a particular position using only the ASCII character set.
143 A FEN string contains six fields separated by a space. The fields are:
145 1) Piece placement (from white's perspective). Each rank is described, starting
146 with rank 8 and ending with rank 1. Within each rank, the contents of each
147 square are described from file A through file H. Following the Standard
148 Algebraic Notation (SAN), each piece is identified by a single letter taken
149 from the standard English names. White pieces are designated using upper-case
150 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
151 noted using digits 1 through 8 (the number of blank squares), and "/"
154 2) Active color. "w" means white moves next, "b" means black.
156 3) Castling availability. If neither side can castle, this is "-". Otherwise,
157 this has one or more letters: "K" (White can castle kingside), "Q" (White
158 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
159 can castle queenside).
161 4) En passant target square (in algebraic notation). If there's no en passant
162 target square, this is "-". If a pawn has just made a 2-square move, this
163 is the position "behind" the pawn. This is recorded regardless of whether
164 there is a pawn in position to make an en passant capture.
166 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
167 or capture. This is used to determine if a draw can be claimed under the
170 6) Fullmove number. The number of the full move. It starts at 1, and is
171 incremented after Black's move.
174 unsigned char col, row, token;
177 std::istringstream ss(fenStr);
179 std::memset(this, 0, sizeof(Position));
180 std::memset(si, 0, sizeof(StateInfo));
181 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
186 // 1. Piece placement
187 while ((ss >> token) && !isspace(token))
190 sq += Square(token - '0'); // Advance the given number of files
192 else if (token == '/')
195 else if ((idx = PieceToChar.find(token)) != string::npos)
197 put_piece(Piece(idx), sq);
204 sideToMove = (token == 'w' ? WHITE : BLACK);
207 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
208 // Shredder-FEN that uses the letters of the columns on which the rooks began
209 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
210 // if an inner rook is associated with the castling right, the castling tag is
211 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
212 while ((ss >> token) && !isspace(token))
215 Color c = islower(token) ? BLACK : WHITE;
216 Piece rook = make_piece(c, ROOK);
218 token = char(toupper(token));
221 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
223 else if (token == 'Q')
224 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
226 else if (token >= 'A' && token <= 'H')
227 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
232 set_castling_right(c, rsq);
235 // 4. En passant square. Ignore if no pawn capture is possible
236 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
237 && ((ss >> row) && (row == '3' || row == '6')))
239 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
241 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
242 st->epSquare = SQ_NONE;
245 st->epSquare = SQ_NONE;
247 // 5-6. Halfmove clock and fullmove number
248 ss >> std::skipws >> st->rule50 >> gamePly;
250 // Convert from fullmove starting from 1 to ply starting from 0,
251 // handle also common incorrect FEN with fullmove = 0.
252 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
254 chess960 = isChess960;
264 /// Position::set_castling_right() is a helper function used to set castling
265 /// rights given the corresponding color and the rook starting square.
267 void Position::set_castling_right(Color c, Square rfrom) {
269 Square kfrom = square<KING>(c);
270 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
271 CastlingRight cr = (c | cs);
273 st->castlingRights |= cr;
274 castlingRightsMask[kfrom] |= cr;
275 castlingRightsMask[rfrom] |= cr;
276 castlingRookSquare[cr] = rfrom;
278 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
279 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
281 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
282 if (s != kfrom && s != rfrom)
283 castlingPath[cr] |= s;
285 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
286 if (s != kfrom && s != rfrom)
287 castlingPath[cr] |= s;
291 /// Position::set_check_info() sets king attacks to detect if a move gives check
293 void Position::set_check_info(StateInfo* si) const {
295 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE));
296 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK));
298 Square ksq = square<KING>(~sideToMove);
300 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
301 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
302 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
303 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
304 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
305 si->checkSquares[KING] = 0;
309 /// Position::set_state() computes the hash keys of the position, and other
310 /// data that once computed is updated incrementally as moves are made.
311 /// The function is only used when a new position is set up, and to verify
312 /// the correctness of the StateInfo data when running in debug mode.
314 void Position::set_state(StateInfo* si) const {
316 si->key = si->pawnKey = si->materialKey = 0;
317 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
318 si->psq = SCORE_ZERO;
319 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
323 for (Bitboard b = pieces(); b; )
325 Square s = pop_lsb(&b);
326 Piece pc = piece_on(s);
327 si->key ^= Zobrist::psq[pc][s];
328 si->psq += PSQT::psq[pc][s];
331 if (si->epSquare != SQ_NONE)
332 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
334 if (sideToMove == BLACK)
335 si->key ^= Zobrist::side;
337 si->key ^= Zobrist::castling[si->castlingRights];
339 for (Bitboard b = pieces(PAWN); b; )
341 Square s = pop_lsb(&b);
342 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
345 for (Color c = WHITE; c <= BLACK; ++c)
346 for (PieceType pt = PAWN; pt <= KING; ++pt)
347 for (int cnt = 0; cnt < pieceCount[make_piece(c, pt)]; ++cnt)
348 si->materialKey ^= Zobrist::psq[make_piece(c, pt)][cnt];
350 for (Color c = WHITE; c <= BLACK; ++c)
351 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
352 si->nonPawnMaterial[c] += pieceCount[make_piece(c, pt)] * PieceValue[MG][pt];
356 /// Position::fen() returns a FEN representation of the position. In case of
357 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
359 const string Position::fen() const {
362 std::ostringstream ss;
364 for (Rank r = RANK_8; r >= RANK_1; --r)
366 for (File f = FILE_A; f <= FILE_H; ++f)
368 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
375 ss << PieceToChar[piece_on(make_square(f, r))];
382 ss << (sideToMove == WHITE ? " w " : " b ");
384 if (can_castle(WHITE_OO))
385 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
387 if (can_castle(WHITE_OOO))
388 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
390 if (can_castle(BLACK_OO))
391 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
393 if (can_castle(BLACK_OOO))
394 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
396 if (!can_castle(WHITE) && !can_castle(BLACK))
399 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
400 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
406 /// Position::game_phase() calculates the game phase interpolating total non-pawn
407 /// material between endgame and midgame limits.
409 Phase Position::game_phase() const {
411 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
413 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
415 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
419 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors) that
420 /// are blocking attacks on the square 's' from 'sliders'. A piece blocks a slider
421 /// if removing that piece from the board would result in a position where square 's'
422 /// is attacked. For example, a king-attack blocking piece can be either a pinned or
423 /// a discovered check piece, according if its color is the opposite or the same of
424 /// the color of the slider.
426 Bitboard Position::slider_blockers(Bitboard sliders, Square s) const {
428 Bitboard b, pinners, result = 0;
430 // Pinners are sliders that attack 's' when a pinned piece is removed
431 pinners = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
432 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
436 b = between_bb(s, pop_lsb(&pinners)) & pieces();
438 if (!more_than_one(b))
445 /// Position::attackers_to() computes a bitboard of all pieces which attack a
446 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
448 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
450 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
451 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
452 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
453 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
454 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
455 | (attacks_from<KING>(s) & pieces(KING));
459 /// Position::legal() tests whether a pseudo-legal move is legal
461 bool Position::legal(Move m) const {
465 Color us = sideToMove;
466 Square from = from_sq(m);
468 assert(color_of(moved_piece(m)) == us);
469 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
471 // En passant captures are a tricky special case. Because they are rather
472 // uncommon, we do it simply by testing whether the king is attacked after
474 if (type_of(m) == ENPASSANT)
476 Square ksq = square<KING>(us);
477 Square to = to_sq(m);
478 Square capsq = to - pawn_push(us);
479 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
481 assert(to == ep_square());
482 assert(moved_piece(m) == make_piece(us, PAWN));
483 assert(piece_on(capsq) == make_piece(~us, PAWN));
484 assert(piece_on(to) == NO_PIECE);
486 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
487 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
490 // If the moving piece is a king, check whether the destination
491 // square is attacked by the opponent. Castling moves are checked
492 // for legality during move generation.
493 if (type_of(piece_on(from)) == KING)
494 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
496 // A non-king move is legal if and only if it is not pinned or it
497 // is moving along the ray towards or away from the king.
498 return !(pinned_pieces(us) & from)
499 || aligned(from, to_sq(m), square<KING>(us));
503 /// Position::pseudo_legal() takes a random move and tests whether the move is
504 /// pseudo legal. It is used to validate moves from TT that can be corrupted
505 /// due to SMP concurrent access or hash position key aliasing.
507 bool Position::pseudo_legal(const Move m) const {
509 Color us = sideToMove;
510 Square from = from_sq(m);
511 Square to = to_sq(m);
512 Piece pc = moved_piece(m);
514 // Use a slower but simpler function for uncommon cases
515 if (type_of(m) != NORMAL)
516 return MoveList<LEGAL>(*this).contains(m);
518 // Is not a promotion, so promotion piece must be empty
519 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
522 // If the 'from' square is not occupied by a piece belonging to the side to
523 // move, the move is obviously not legal.
524 if (pc == NO_PIECE || color_of(pc) != us)
527 // The destination square cannot be occupied by a friendly piece
531 // Handle the special case of a pawn move
532 if (type_of(pc) == PAWN)
534 // We have already handled promotion moves, so destination
535 // cannot be on the 8th/1st rank.
536 if (rank_of(to) == relative_rank(us, RANK_8))
539 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
540 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
541 && !( (from + 2 * pawn_push(us) == to) // Not a double push
542 && (rank_of(from) == relative_rank(us, RANK_2))
544 && empty(to - pawn_push(us))))
547 else if (!(attacks_from(pc, from) & to))
550 // Evasions generator already takes care to avoid some kind of illegal moves
551 // and legal() relies on this. We therefore have to take care that the same
552 // kind of moves are filtered out here.
555 if (type_of(pc) != KING)
557 // Double check? In this case a king move is required
558 if (more_than_one(checkers()))
561 // Our move must be a blocking evasion or a capture of the checking piece
562 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
565 // In case of king moves under check we have to remove king so as to catch
566 // invalid moves like b1a1 when opposite queen is on c1.
567 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
575 /// Position::gives_check() tests whether a pseudo-legal move gives a check
577 bool Position::gives_check(Move m) const {
580 assert(color_of(moved_piece(m)) == sideToMove);
582 Square from = from_sq(m);
583 Square to = to_sq(m);
585 // Is there a direct check?
586 if (st->checkSquares[type_of(piece_on(from))] & to)
589 // Is there a discovered check?
590 if ( (discovered_check_candidates() & from)
591 && !aligned(from, to, square<KING>(~sideToMove)))
600 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
602 // En passant capture with check? We have already handled the case
603 // of direct checks and ordinary discovered check, so the only case we
604 // need to handle is the unusual case of a discovered check through
605 // the captured pawn.
608 Square capsq = make_square(file_of(to), rank_of(from));
609 Bitboard b = (pieces() ^ from ^ capsq) | to;
611 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
612 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
617 Square rfrom = to; // Castling is encoded as 'King captures the rook'
618 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
619 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
621 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
622 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
631 /// Position::do_move() makes a move, and saves all information necessary
632 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
633 /// moves should be filtered out before this function is called.
635 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
638 assert(&newSt != st);
641 Key k = st->key ^ Zobrist::side;
643 // Copy some fields of the old state to our new StateInfo object except the
644 // ones which are going to be recalculated from scratch anyway and then switch
645 // our state pointer to point to the new (ready to be updated) state.
646 std::memcpy(&newSt, st, offsetof(StateInfo, key));
650 // Increment ply counters. In particular, rule50 will be reset to zero later on
651 // in case of a capture or a pawn move.
656 Color us = sideToMove;
658 Square from = from_sq(m);
659 Square to = to_sq(m);
660 Piece pc = piece_on(from);
661 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
663 assert(color_of(pc) == us);
664 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
665 assert(type_of(captured) != KING);
667 if (type_of(m) == CASTLING)
669 assert(pc == make_piece(us, KING));
670 assert(captured == make_piece(us, ROOK));
673 do_castling<true>(us, from, to, rfrom, rto);
675 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
676 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
684 // If the captured piece is a pawn, update pawn hash key, otherwise
685 // update non-pawn material.
686 if (type_of(captured) == PAWN)
688 if (type_of(m) == ENPASSANT)
690 capsq -= pawn_push(us);
692 assert(pc == make_piece(us, PAWN));
693 assert(to == st->epSquare);
694 assert(relative_rank(us, to) == RANK_6);
695 assert(piece_on(to) == NO_PIECE);
696 assert(piece_on(capsq) == make_piece(them, PAWN));
698 board[capsq] = NO_PIECE; // Not done by remove_piece()
701 st->pawnKey ^= Zobrist::psq[captured][capsq];
704 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
706 // Update board and piece lists
707 remove_piece(captured, capsq);
709 // Update material hash key and prefetch access to materialTable
710 k ^= Zobrist::psq[captured][capsq];
711 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
712 prefetch(thisThread->materialTable[st->materialKey]);
714 // Update incremental scores
715 st->psq -= PSQT::psq[captured][capsq];
717 // Reset rule 50 counter
722 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
724 // Reset en passant square
725 if (st->epSquare != SQ_NONE)
727 k ^= Zobrist::enpassant[file_of(st->epSquare)];
728 st->epSquare = SQ_NONE;
731 // Update castling rights if needed
732 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
734 int cr = castlingRightsMask[from] | castlingRightsMask[to];
735 k ^= Zobrist::castling[st->castlingRights & cr];
736 st->castlingRights &= ~cr;
739 // Move the piece. The tricky Chess960 castling is handled earlier
740 if (type_of(m) != CASTLING)
741 move_piece(pc, from, to);
743 // If the moving piece is a pawn do some special extra work
744 if (type_of(pc) == PAWN)
746 // Set en-passant square if the moved pawn can be captured
747 if ( (int(to) ^ int(from)) == 16
748 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
750 st->epSquare = (from + to) / 2;
751 k ^= Zobrist::enpassant[file_of(st->epSquare)];
754 else if (type_of(m) == PROMOTION)
756 Piece promotion = make_piece(us, promotion_type(m));
758 assert(relative_rank(us, to) == RANK_8);
759 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
761 remove_piece(pc, to);
762 put_piece(promotion, to);
765 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
766 st->pawnKey ^= Zobrist::psq[pc][to];
767 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
768 ^ Zobrist::psq[pc][pieceCount[pc]];
770 // Update incremental score
771 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
774 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
777 // Update pawn hash key and prefetch access to pawnsTable
778 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
779 prefetch(thisThread->pawnsTable[st->pawnKey]);
781 // Reset rule 50 draw counter
785 // Update incremental scores
786 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
789 st->capturedPiece = captured;
791 // Update the key with the final value
794 // Calculate checkers bitboard (if move gives check)
795 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
797 sideToMove = ~sideToMove;
799 // Update king attacks used for fast check detection
806 /// Position::undo_move() unmakes a move. When it returns, the position should
807 /// be restored to exactly the same state as before the move was made.
809 void Position::undo_move(Move m) {
813 sideToMove = ~sideToMove;
815 Color us = sideToMove;
816 Square from = from_sq(m);
817 Square to = to_sq(m);
818 Piece pc = piece_on(to);
820 assert(empty(from) || type_of(m) == CASTLING);
821 assert(type_of(st->capturedPiece) != KING);
823 if (type_of(m) == PROMOTION)
825 assert(relative_rank(us, to) == RANK_8);
826 assert(type_of(pc) == promotion_type(m));
827 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
829 remove_piece(pc, to);
830 pc = make_piece(us, PAWN);
834 if (type_of(m) == CASTLING)
837 do_castling<false>(us, from, to, rfrom, rto);
841 move_piece(pc, to, from); // Put the piece back at the source square
843 if (st->capturedPiece)
847 if (type_of(m) == ENPASSANT)
849 capsq -= pawn_push(us);
851 assert(type_of(pc) == PAWN);
852 assert(to == st->previous->epSquare);
853 assert(relative_rank(us, to) == RANK_6);
854 assert(piece_on(capsq) == NO_PIECE);
855 assert(st->capturedPiece == make_piece(~us, PAWN));
858 put_piece(st->capturedPiece, capsq); // Restore the captured piece
862 // Finally point our state pointer back to the previous state
870 /// Position::do_castling() is a helper used to do/undo a castling move. This
871 /// is a bit tricky in Chess960 where from/to squares can overlap.
873 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
875 bool kingSide = to > from;
876 rfrom = to; // Castling is encoded as "king captures friendly rook"
877 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
878 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
880 // Remove both pieces first since squares could overlap in Chess960
881 remove_piece(make_piece(us, KING), Do ? from : to);
882 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
883 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
884 put_piece(make_piece(us, KING), Do ? to : from);
885 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
889 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
890 /// the side to move without executing any move on the board.
892 void Position::do_null_move(StateInfo& newSt) {
895 assert(&newSt != st);
897 std::memcpy(&newSt, st, sizeof(StateInfo));
901 if (st->epSquare != SQ_NONE)
903 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
904 st->epSquare = SQ_NONE;
907 st->key ^= Zobrist::side;
908 prefetch(TT.first_entry(st->key));
911 st->pliesFromNull = 0;
913 sideToMove = ~sideToMove;
920 void Position::undo_null_move() {
925 sideToMove = ~sideToMove;
929 /// Position::key_after() computes the new hash key after the given move. Needed
930 /// for speculative prefetch. It doesn't recognize special moves like castling,
931 /// en-passant and promotions.
933 Key Position::key_after(Move m) const {
935 Square from = from_sq(m);
936 Square to = to_sq(m);
937 Piece pc = piece_on(from);
938 Piece captured = piece_on(to);
939 Key k = st->key ^ Zobrist::side;
942 k ^= Zobrist::psq[captured][to];
944 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
948 /// Position::see() is a static exchange evaluator: It tries to estimate the
949 /// material gain or loss resulting from a move.
951 Value Position::see_sign(Move m) const {
955 // Early return if SEE cannot be negative because captured piece value
956 // is not less then capturing one. Note that king moves always return
957 // here because king midgame value is set to 0.
958 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
959 return VALUE_KNOWN_WIN;
964 Value Position::see(Move m) const {
967 Bitboard occupied, attackers, stmAttackers;
977 swapList[0] = PieceValue[MG][piece_on(to)];
978 stm = color_of(piece_on(from));
979 occupied = pieces() ^ from;
981 // Castling moves are implemented as king capturing the rook so cannot
982 // be handled correctly. Simply return VALUE_ZERO that is always correct
983 // unless in the rare case the rook ends up under attack.
984 if (type_of(m) == CASTLING)
987 if (type_of(m) == ENPASSANT)
989 occupied ^= to - pawn_push(stm); // Remove the captured pawn
990 swapList[0] = PieceValue[MG][PAWN];
993 // Find all attackers to the destination square, with the moving piece
994 // removed, but possibly an X-ray attacker added behind it.
995 attackers = attackers_to(to, occupied) & occupied;
997 // If the opponent has no attackers we are finished
999 stmAttackers = attackers & pieces(stm);
1003 // The destination square is defended, which makes things rather more
1004 // difficult to compute. We proceed by building up a "swap list" containing
1005 // the material gain or loss at each stop in a sequence of captures to the
1006 // destination square, where the sides alternately capture, and always
1007 // capture with the least valuable piece. After each capture, we look for
1008 // new X-ray attacks from behind the capturing piece.
1009 captured = type_of(piece_on(from));
1012 assert(slIndex < 32);
1014 // Add the new entry to the swap list
1015 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1017 // Locate and remove the next least valuable attacker
1018 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1020 stmAttackers = attackers & pieces(stm);
1023 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1025 // Having built the swap list, we negamax through it to find the best
1026 // achievable score from the point of view of the side to move.
1028 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1034 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1035 /// or by repetition. It does not detect stalemates.
1037 bool Position::is_draw() const {
1039 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1042 StateInfo* stp = st;
1043 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1045 stp = stp->previous->previous;
1047 if (stp->key == st->key)
1048 return true; // Draw at first repetition
1055 /// Position::flip() flips position with the white and black sides reversed. This
1056 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1058 void Position::flip() {
1061 std::stringstream ss(fen());
1063 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1065 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1066 f.insert(0, token + (f.empty() ? " " : "/"));
1069 ss >> token; // Active color
1070 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1072 ss >> token; // Castling availability
1075 std::transform(f.begin(), f.end(), f.begin(),
1076 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1078 ss >> token; // En passant square
1079 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1081 std::getline(ss, token); // Half and full moves
1084 set(f, is_chess960(), st, this_thread());
1086 assert(pos_is_ok());
1090 /// Position::pos_is_ok() performs some consistency checks for the position object.
1091 /// This is meant to be helpful when debugging.
1093 bool Position::pos_is_ok(int* failedStep) const {
1095 const bool Fast = true; // Quick (default) or full check?
1097 enum { Default, King, Bitboards, State, Lists, Castling };
1099 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1104 if (step == Default)
1105 if ( (sideToMove != WHITE && sideToMove != BLACK)
1106 || piece_on(square<KING>(WHITE)) != W_KING
1107 || piece_on(square<KING>(BLACK)) != B_KING
1108 || ( ep_square() != SQ_NONE
1109 && relative_rank(sideToMove, ep_square()) != RANK_6))
1113 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1114 || std::count(board, board + SQUARE_NB, B_KING) != 1
1115 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1118 if (step == Bitboards)
1120 if ( (pieces(WHITE) & pieces(BLACK))
1121 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1124 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1125 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1126 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1134 if (std::memcmp(&si, st, sizeof(StateInfo)))
1139 for (Color c = WHITE; c <= BLACK; ++c)
1140 for (PieceType pt = PAWN; pt <= KING; ++pt)
1142 Piece pc = make_piece(c, pt);
1144 if (pieceCount[pc] != popcount(pieces(c, pt)))
1147 for (int i = 0; i < pieceCount[pc]; ++i)
1148 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1152 if (step == Castling)
1153 for (Color c = WHITE; c <= BLACK; ++c)
1154 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1156 if (!can_castle(c | s))
1159 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1160 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1161 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))