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[COLOR_NB][PIECE_TYPE_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[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][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(color_of(Piece(idx)), type_of(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[color_of(pc)][type_of(pc)][s];
328 si->psq += PSQT::psq[color_of(pc)][type_of(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[color_of(piece_on(s))][PAWN][s];
345 for (Color c = WHITE; c <= BLACK; ++c)
346 for (PieceType pt = PAWN; pt <= KING; ++pt)
347 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
348 si->materialKey ^= Zobrist::psq[c][pt][cnt];
350 for (Color c = WHITE; c <= BLACK; ++c)
351 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
352 si->nonPawnMaterial[c] += pieceCount[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 PieceType pt = type_of(piece_on(from));
661 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
663 assert(color_of(piece_on(from)) == us);
664 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
665 assert(captured != KING);
667 if (type_of(m) == CASTLING)
672 do_castling<true>(us, from, to, rfrom, rto);
674 captured = NO_PIECE_TYPE;
675 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
676 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
683 // If the captured piece is a pawn, update pawn hash key, otherwise
684 // update non-pawn material.
685 if (captured == PAWN)
687 if (type_of(m) == ENPASSANT)
689 capsq -= pawn_push(us);
692 assert(to == st->epSquare);
693 assert(relative_rank(us, to) == RANK_6);
694 assert(piece_on(to) == NO_PIECE);
695 assert(piece_on(capsq) == make_piece(them, PAWN));
697 board[capsq] = NO_PIECE; // Not done by remove_piece()
700 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
703 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
705 // Update board and piece lists
706 remove_piece(them, captured, capsq);
708 // Update material hash key and prefetch access to materialTable
709 k ^= Zobrist::psq[them][captured][capsq];
710 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
711 prefetch(thisThread->materialTable[st->materialKey]);
713 // Update incremental scores
714 st->psq -= PSQT::psq[them][captured][capsq];
716 // Reset rule 50 counter
721 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
723 // Reset en passant square
724 if (st->epSquare != SQ_NONE)
726 k ^= Zobrist::enpassant[file_of(st->epSquare)];
727 st->epSquare = SQ_NONE;
730 // Update castling rights if needed
731 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
733 int cr = castlingRightsMask[from] | castlingRightsMask[to];
734 k ^= Zobrist::castling[st->castlingRights & cr];
735 st->castlingRights &= ~cr;
738 // Move the piece. The tricky Chess960 castling is handled earlier
739 if (type_of(m) != CASTLING)
740 move_piece(us, pt, from, to);
742 // If the moving piece is a pawn do some special extra work
745 // Set en-passant square if the moved pawn can be captured
746 if ( (int(to) ^ int(from)) == 16
747 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
749 st->epSquare = (from + to) / 2;
750 k ^= Zobrist::enpassant[file_of(st->epSquare)];
753 else if (type_of(m) == PROMOTION)
755 PieceType promotion = promotion_type(m);
757 assert(relative_rank(us, to) == RANK_8);
758 assert(promotion >= KNIGHT && promotion <= QUEEN);
760 remove_piece(us, PAWN, to);
761 put_piece(us, promotion, to);
764 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
765 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
766 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
767 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
769 // Update incremental score
770 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
773 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
776 // Update pawn hash key and prefetch access to pawnsTable
777 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
778 prefetch(thisThread->pawnsTable[st->pawnKey]);
780 // Reset rule 50 draw counter
784 // Update incremental scores
785 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
788 st->capturedType = captured;
790 // Update the key with the final value
793 // Calculate checkers bitboard (if move gives check)
794 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
796 sideToMove = ~sideToMove;
798 // Update king attacks used for fast check detection
805 /// Position::undo_move() unmakes a move. When it returns, the position should
806 /// be restored to exactly the same state as before the move was made.
808 void Position::undo_move(Move m) {
812 sideToMove = ~sideToMove;
814 Color us = sideToMove;
815 Square from = from_sq(m);
816 Square to = to_sq(m);
817 PieceType pt = type_of(piece_on(to));
819 assert(empty(from) || type_of(m) == CASTLING);
820 assert(st->capturedType != KING);
822 if (type_of(m) == PROMOTION)
824 assert(relative_rank(us, to) == RANK_8);
825 assert(pt == promotion_type(m));
826 assert(pt >= KNIGHT && pt <= QUEEN);
828 remove_piece(us, pt, to);
829 put_piece(us, PAWN, to);
833 if (type_of(m) == CASTLING)
836 do_castling<false>(us, from, to, rfrom, rto);
840 move_piece(us, pt, to, from); // Put the piece back at the source square
842 if (st->capturedType)
846 if (type_of(m) == ENPASSANT)
848 capsq -= pawn_push(us);
851 assert(to == st->previous->epSquare);
852 assert(relative_rank(us, to) == RANK_6);
853 assert(piece_on(capsq) == NO_PIECE);
854 assert(st->capturedType == PAWN);
857 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
861 // Finally point our state pointer back to the previous state
869 /// Position::do_castling() is a helper used to do/undo a castling move. This
870 /// is a bit tricky, especially in Chess960.
872 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
874 bool kingSide = to > from;
875 rfrom = to; // Castling is encoded as "king captures friendly rook"
876 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
877 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
879 // Remove both pieces first since squares could overlap in Chess960
880 remove_piece(us, KING, Do ? from : to);
881 remove_piece(us, ROOK, Do ? rfrom : rto);
882 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
883 put_piece(us, KING, Do ? to : from);
884 put_piece(us, ROOK, Do ? rto : rfrom);
888 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
889 /// the side to move without executing any move on the board.
891 void Position::do_null_move(StateInfo& newSt) {
894 assert(&newSt != st);
896 std::memcpy(&newSt, st, sizeof(StateInfo));
900 if (st->epSquare != SQ_NONE)
902 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
903 st->epSquare = SQ_NONE;
906 st->key ^= Zobrist::side;
907 prefetch(TT.first_entry(st->key));
910 st->pliesFromNull = 0;
912 sideToMove = ~sideToMove;
919 void Position::undo_null_move() {
924 sideToMove = ~sideToMove;
928 /// Position::key_after() computes the new hash key after the given move. Needed
929 /// for speculative prefetch. It doesn't recognize special moves like castling,
930 /// en-passant and promotions.
932 Key Position::key_after(Move m) const {
934 Color us = sideToMove;
935 Square from = from_sq(m);
936 Square to = to_sq(m);
937 PieceType pt = type_of(piece_on(from));
938 PieceType captured = type_of(piece_on(to));
939 Key k = st->key ^ Zobrist::side;
942 k ^= Zobrist::psq[~us][captured][to];
944 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][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 if (pieceCount[c][pt] != popcount(pieces(c, pt)))
1145 for (int i = 0; i < pieceCount[c][pt]; ++i)
1146 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1147 || index[pieceList[c][pt][i]] != i)
1151 if (step == Castling)
1152 for (Color c = WHITE; c <= BLACK; ++c)
1153 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1155 if (!can_castle(c | s))
1158 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1159 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1160 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))