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 <cstddef> // For offsetof()
24 #include <cstring> // For std::memset, std::memcmp
35 #include "syzygy/tbprobe.h"
40 extern Score psq[PIECE_NB][SQUARE_NB];
45 Key psq[PIECE_NB][SQUARE_NB];
46 Key enpassant[FILE_NB];
47 Key castling[CASTLING_RIGHT_NB];
53 const string PieceToChar(" PNBRQK pnbrqk");
55 // min_attacker() is a helper function used by see_ge() to locate the least
56 // valuable attacker for the side to move, remove the attacker we just found
57 // from the bitboards and scan for new X-ray attacks behind it.
60 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
61 Bitboard& occupied, Bitboard& attackers) {
63 Bitboard b = stmAttackers & bb[Pt];
65 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
67 occupied ^= b & ~(b - 1);
69 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
70 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
72 if (Pt == ROOK || Pt == QUEEN)
73 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
75 attackers &= occupied; // After X-ray that may add already processed pieces
80 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
81 return KING; // No need to update bitboards: it is the last cycle
87 /// operator<<(Position) returns an ASCII representation of the position
89 std::ostream& operator<<(std::ostream& os, const Position& pos) {
91 os << "\n +---+---+---+---+---+---+---+---+\n";
93 for (Rank r = RANK_8; r >= RANK_1; --r)
95 for (File f = FILE_A; f <= FILE_H; ++f)
96 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
98 os << " |\n +---+---+---+---+---+---+---+---+\n";
101 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
102 << std::setfill('0') << std::setw(16) << pos.key()
103 << std::setfill(' ') << std::dec << "\nCheckers: ";
105 for (Bitboard b = pos.checkers(); b; )
106 os << UCI::square(pop_lsb(&b)) << " ";
108 if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces())
109 && !pos.can_castle(ANY_CASTLING))
113 p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread());
114 Tablebases::ProbeState s1, s2;
115 Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1);
116 int dtz = Tablebases::probe_dtz(p, &s2);
117 os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")"
118 << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")";
125 /// Position::init() initializes at startup the various arrays used to compute
128 void Position::init() {
132 for (Piece pc : Pieces)
133 for (Square s = SQ_A1; s <= SQ_H8; ++s)
134 Zobrist::psq[pc][s] = rng.rand<Key>();
136 for (File f = FILE_A; f <= FILE_H; ++f)
137 Zobrist::enpassant[f] = rng.rand<Key>();
139 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
141 Zobrist::castling[cr] = 0;
145 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
146 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
150 Zobrist::side = rng.rand<Key>();
151 Zobrist::noPawns = rng.rand<Key>();
155 /// Position::set() initializes the position object with the given FEN string.
156 /// This function is not very robust - make sure that input FENs are correct,
157 /// this is assumed to be the responsibility of the GUI.
159 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
161 A FEN string defines a particular position using only the ASCII character set.
163 A FEN string contains six fields separated by a space. The fields are:
165 1) Piece placement (from white's perspective). Each rank is described, starting
166 with rank 8 and ending with rank 1. Within each rank, the contents of each
167 square are described from file A through file H. Following the Standard
168 Algebraic Notation (SAN), each piece is identified by a single letter taken
169 from the standard English names. White pieces are designated using upper-case
170 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
171 noted using digits 1 through 8 (the number of blank squares), and "/"
174 2) Active color. "w" means white moves next, "b" means black.
176 3) Castling availability. If neither side can castle, this is "-". Otherwise,
177 this has one or more letters: "K" (White can castle kingside), "Q" (White
178 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
179 can castle queenside).
181 4) En passant target square (in algebraic notation). If there's no en passant
182 target square, this is "-". If a pawn has just made a 2-square move, this
183 is the position "behind" the pawn. This is recorded only if there is a pawn
184 in position to make an en passant capture, and if there really is a pawn
185 that might have advanced two squares.
187 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
188 or capture. This is used to determine if a draw can be claimed under the
191 6) Fullmove number. The number of the full move. It starts at 1, and is
192 incremented after Black's move.
195 unsigned char col, row, token;
198 std::istringstream ss(fenStr);
200 std::memset(this, 0, sizeof(Position));
201 std::memset(si, 0, sizeof(StateInfo));
202 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
207 // 1. Piece placement
208 while ((ss >> token) && !isspace(token))
211 sq += Square(token - '0'); // Advance the given number of files
213 else if (token == '/')
216 else if ((idx = PieceToChar.find(token)) != string::npos)
218 put_piece(Piece(idx), sq);
225 sideToMove = (token == 'w' ? WHITE : BLACK);
228 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
229 // Shredder-FEN that uses the letters of the columns on which the rooks began
230 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
231 // if an inner rook is associated with the castling right, the castling tag is
232 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
233 while ((ss >> token) && !isspace(token))
236 Color c = islower(token) ? BLACK : WHITE;
237 Piece rook = make_piece(c, ROOK);
239 token = char(toupper(token));
242 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
244 else if (token == 'Q')
245 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
247 else if (token >= 'A' && token <= 'H')
248 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
253 set_castling_right(c, rsq);
256 // 4. En passant square. Ignore if no pawn capture is possible
257 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
258 && ((ss >> row) && (row == '3' || row == '6')))
260 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
262 if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))
263 || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))))
264 st->epSquare = SQ_NONE;
267 st->epSquare = SQ_NONE;
269 // 5-6. Halfmove clock and fullmove number
270 ss >> std::skipws >> st->rule50 >> gamePly;
272 // Convert from fullmove starting from 1 to ply starting from 0,
273 // handle also common incorrect FEN with fullmove = 0.
274 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
276 chess960 = isChess960;
286 /// Position::set_castling_right() is a helper function used to set castling
287 /// rights given the corresponding color and the rook starting square.
289 void Position::set_castling_right(Color c, Square rfrom) {
291 Square kfrom = square<KING>(c);
292 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
293 CastlingRight cr = (c | cs);
295 st->castlingRights |= cr;
296 castlingRightsMask[kfrom] |= cr;
297 castlingRightsMask[rfrom] |= cr;
298 castlingRookSquare[cr] = rfrom;
300 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
301 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
303 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
304 if (s != kfrom && s != rfrom)
305 castlingPath[cr] |= s;
307 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
308 if (s != kfrom && s != rfrom)
309 castlingPath[cr] |= s;
313 /// Position::set_check_info() sets king attacks to detect if a move gives check
315 void Position::set_check_info(StateInfo* si) const {
317 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
318 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
320 Square ksq = square<KING>(~sideToMove);
322 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
323 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
324 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
325 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
326 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
327 si->checkSquares[KING] = 0;
331 /// Position::set_state() computes the hash keys of the position, and other
332 /// data that once computed is updated incrementally as moves are made.
333 /// The function is only used when a new position is set up, and to verify
334 /// the correctness of the StateInfo data when running in debug mode.
336 void Position::set_state(StateInfo* si) const {
338 si->key = si->materialKey = 0;
339 si->pawnKey = Zobrist::noPawns;
340 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
341 si->psq = SCORE_ZERO;
342 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
346 for (Bitboard b = pieces(); b; )
348 Square s = pop_lsb(&b);
349 Piece pc = piece_on(s);
350 si->key ^= Zobrist::psq[pc][s];
351 si->psq += PSQT::psq[pc][s];
354 if (si->epSquare != SQ_NONE)
355 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
357 if (sideToMove == BLACK)
358 si->key ^= Zobrist::side;
360 si->key ^= Zobrist::castling[si->castlingRights];
362 for (Bitboard b = pieces(PAWN); b; )
364 Square s = pop_lsb(&b);
365 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
368 for (Piece pc : Pieces)
370 if (type_of(pc) != PAWN && type_of(pc) != KING)
371 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
373 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
374 si->materialKey ^= Zobrist::psq[pc][cnt];
379 /// Position::set() is an overload to initialize the position object with
380 /// the given endgame code string like "KBPKN". It is manily an helper to
381 /// get the material key out of an endgame code. Position is not playable,
382 /// indeed is even not guaranteed to be legal.
384 Position& Position::set(const string& code, Color c, StateInfo* si) {
386 assert(code.length() > 0 && code.length() < 8);
387 assert(code[0] == 'K');
389 string sides[] = { code.substr(code.find('K', 1)), // Weak
390 code.substr(0, code.find('K', 1)) }; // Strong
392 std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower);
394 string fenStr = sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/8/8/"
395 + sides[1] + char(8 - sides[1].length() + '0') + " w - - 0 10";
397 return set(fenStr, false, si, nullptr);
401 /// Position::fen() returns a FEN representation of the position. In case of
402 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
404 const string Position::fen() const {
407 std::ostringstream ss;
409 for (Rank r = RANK_8; r >= RANK_1; --r)
411 for (File f = FILE_A; f <= FILE_H; ++f)
413 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
420 ss << PieceToChar[piece_on(make_square(f, r))];
427 ss << (sideToMove == WHITE ? " w " : " b ");
429 if (can_castle(WHITE_OO))
430 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
432 if (can_castle(WHITE_OOO))
433 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
435 if (can_castle(BLACK_OO))
436 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
438 if (can_castle(BLACK_OOO))
439 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
441 if (!can_castle(WHITE) && !can_castle(BLACK))
444 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
445 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
451 /// Position::game_phase() calculates the game phase interpolating total non-pawn
452 /// material between endgame and midgame limits.
454 Phase Position::game_phase() const {
456 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
458 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
460 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
464 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
465 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
466 /// slider if removing that piece from the board would result in a position where
467 /// square 's' is attacked. For example, a king-attack blocking piece can be either
468 /// a pinned or a discovered check piece, according if its color is the opposite
469 /// or the same of the color of the slider.
471 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
476 // Snipers are sliders that attack 's' when a piece is removed
477 Bitboard snipers = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
478 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
482 Square sniperSq = pop_lsb(&snipers);
483 Bitboard b = between_bb(s, sniperSq) & pieces();
485 if (!more_than_one(b))
488 if (b & pieces(color_of(piece_on(s))))
496 /// Position::attackers_to() computes a bitboard of all pieces which attack a
497 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
499 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
501 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
502 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
503 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
504 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
505 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
506 | (attacks_from<KING>(s) & pieces(KING));
510 /// Position::legal() tests whether a pseudo-legal move is legal
512 bool Position::legal(Move m) const {
516 Color us = sideToMove;
517 Square from = from_sq(m);
519 assert(color_of(moved_piece(m)) == us);
520 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
522 // En passant captures are a tricky special case. Because they are rather
523 // uncommon, we do it simply by testing whether the king is attacked after
525 if (type_of(m) == ENPASSANT)
527 Square ksq = square<KING>(us);
528 Square to = to_sq(m);
529 Square capsq = to - pawn_push(us);
530 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
532 assert(to == ep_square());
533 assert(moved_piece(m) == make_piece(us, PAWN));
534 assert(piece_on(capsq) == make_piece(~us, PAWN));
535 assert(piece_on(to) == NO_PIECE);
537 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
538 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
541 // If the moving piece is a king, check whether the destination
542 // square is attacked by the opponent. Castling moves are checked
543 // for legality during move generation.
544 if (type_of(piece_on(from)) == KING)
545 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
547 // A non-king move is legal if and only if it is not pinned or it
548 // is moving along the ray towards or away from the king.
549 return !(pinned_pieces(us) & from)
550 || aligned(from, to_sq(m), square<KING>(us));
554 /// Position::pseudo_legal() takes a random move and tests whether the move is
555 /// pseudo legal. It is used to validate moves from TT that can be corrupted
556 /// due to SMP concurrent access or hash position key aliasing.
558 bool Position::pseudo_legal(const Move m) const {
560 Color us = sideToMove;
561 Square from = from_sq(m);
562 Square to = to_sq(m);
563 Piece pc = moved_piece(m);
565 // Use a slower but simpler function for uncommon cases
566 if (type_of(m) != NORMAL)
567 return MoveList<LEGAL>(*this).contains(m);
569 // Is not a promotion, so promotion piece must be empty
570 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
573 // If the 'from' square is not occupied by a piece belonging to the side to
574 // move, the move is obviously not legal.
575 if (pc == NO_PIECE || color_of(pc) != us)
578 // The destination square cannot be occupied by a friendly piece
582 // Handle the special case of a pawn move
583 if (type_of(pc) == PAWN)
585 // We have already handled promotion moves, so destination
586 // cannot be on the 8th/1st rank.
587 if (rank_of(to) == relative_rank(us, RANK_8))
590 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
591 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
592 && !( (from + 2 * pawn_push(us) == to) // Not a double push
593 && (rank_of(from) == relative_rank(us, RANK_2))
595 && empty(to - pawn_push(us))))
598 else if (!(attacks_from(pc, from) & to))
601 // Evasions generator already takes care to avoid some kind of illegal moves
602 // and legal() relies on this. We therefore have to take care that the same
603 // kind of moves are filtered out here.
606 if (type_of(pc) != KING)
608 // Double check? In this case a king move is required
609 if (more_than_one(checkers()))
612 // Our move must be a blocking evasion or a capture of the checking piece
613 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
616 // In case of king moves under check we have to remove king so as to catch
617 // invalid moves like b1a1 when opposite queen is on c1.
618 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
626 /// Position::gives_check() tests whether a pseudo-legal move gives a check
628 bool Position::gives_check(Move m) const {
631 assert(color_of(moved_piece(m)) == sideToMove);
633 Square from = from_sq(m);
634 Square to = to_sq(m);
636 // Is there a direct check?
637 if (st->checkSquares[type_of(piece_on(from))] & to)
640 // Is there a discovered check?
641 if ( (discovered_check_candidates() & from)
642 && !aligned(from, to, square<KING>(~sideToMove)))
651 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
653 // En passant capture with check? We have already handled the case
654 // of direct checks and ordinary discovered check, so the only case we
655 // need to handle is the unusual case of a discovered check through
656 // the captured pawn.
659 Square capsq = make_square(file_of(to), rank_of(from));
660 Bitboard b = (pieces() ^ from ^ capsq) | to;
662 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
663 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
668 Square rfrom = to; // Castling is encoded as 'King captures the rook'
669 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
670 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
672 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
673 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
682 /// Position::do_move() makes a move, and saves all information necessary
683 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
684 /// moves should be filtered out before this function is called.
686 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
689 assert(&newSt != st);
692 Key k = st->key ^ Zobrist::side;
694 // Copy some fields of the old state to our new StateInfo object except the
695 // ones which are going to be recalculated from scratch anyway and then switch
696 // our state pointer to point to the new (ready to be updated) state.
697 std::memcpy(&newSt, st, offsetof(StateInfo, key));
701 // Increment ply counters. In particular, rule50 will be reset to zero later on
702 // in case of a capture or a pawn move.
707 Color us = sideToMove;
709 Square from = from_sq(m);
710 Square to = to_sq(m);
711 Piece pc = piece_on(from);
712 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
714 assert(color_of(pc) == us);
715 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
716 assert(type_of(captured) != KING);
718 if (type_of(m) == CASTLING)
720 assert(pc == make_piece(us, KING));
721 assert(captured == make_piece(us, ROOK));
724 do_castling<true>(us, from, to, rfrom, rto);
726 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
727 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
735 // If the captured piece is a pawn, update pawn hash key, otherwise
736 // update non-pawn material.
737 if (type_of(captured) == PAWN)
739 if (type_of(m) == ENPASSANT)
741 capsq -= pawn_push(us);
743 assert(pc == make_piece(us, PAWN));
744 assert(to == st->epSquare);
745 assert(relative_rank(us, to) == RANK_6);
746 assert(piece_on(to) == NO_PIECE);
747 assert(piece_on(capsq) == make_piece(them, PAWN));
749 board[capsq] = NO_PIECE; // Not done by remove_piece()
752 st->pawnKey ^= Zobrist::psq[captured][capsq];
755 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
757 // Update board and piece lists
758 remove_piece(captured, capsq);
760 // Update material hash key and prefetch access to materialTable
761 k ^= Zobrist::psq[captured][capsq];
762 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
763 prefetch(thisThread->materialTable[st->materialKey]);
765 // Update incremental scores
766 st->psq -= PSQT::psq[captured][capsq];
768 // Reset rule 50 counter
773 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
775 // Reset en passant square
776 if (st->epSquare != SQ_NONE)
778 k ^= Zobrist::enpassant[file_of(st->epSquare)];
779 st->epSquare = SQ_NONE;
782 // Update castling rights if needed
783 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
785 int cr = castlingRightsMask[from] | castlingRightsMask[to];
786 k ^= Zobrist::castling[st->castlingRights & cr];
787 st->castlingRights &= ~cr;
790 // Move the piece. The tricky Chess960 castling is handled earlier
791 if (type_of(m) != CASTLING)
792 move_piece(pc, from, to);
794 // If the moving piece is a pawn do some special extra work
795 if (type_of(pc) == PAWN)
797 // Set en-passant square if the moved pawn can be captured
798 if ( (int(to) ^ int(from)) == 16
799 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
801 st->epSquare = (from + to) / 2;
802 k ^= Zobrist::enpassant[file_of(st->epSquare)];
805 else if (type_of(m) == PROMOTION)
807 Piece promotion = make_piece(us, promotion_type(m));
809 assert(relative_rank(us, to) == RANK_8);
810 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
812 remove_piece(pc, to);
813 put_piece(promotion, to);
816 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
817 st->pawnKey ^= Zobrist::psq[pc][to];
818 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
819 ^ Zobrist::psq[pc][pieceCount[pc]];
821 // Update incremental score
822 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
825 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
828 // Update pawn hash key and prefetch access to pawnsTable
829 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
830 prefetch(thisThread->pawnsTable[st->pawnKey]);
832 // Reset rule 50 draw counter
836 // Update incremental scores
837 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
840 st->capturedPiece = captured;
842 // Update the key with the final value
845 // Calculate checkers bitboard (if move gives check)
846 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
848 sideToMove = ~sideToMove;
850 // Update king attacks used for fast check detection
857 /// Position::undo_move() unmakes a move. When it returns, the position should
858 /// be restored to exactly the same state as before the move was made.
860 void Position::undo_move(Move m) {
864 sideToMove = ~sideToMove;
866 Color us = sideToMove;
867 Square from = from_sq(m);
868 Square to = to_sq(m);
869 Piece pc = piece_on(to);
871 assert(empty(from) || type_of(m) == CASTLING);
872 assert(type_of(st->capturedPiece) != KING);
874 if (type_of(m) == PROMOTION)
876 assert(relative_rank(us, to) == RANK_8);
877 assert(type_of(pc) == promotion_type(m));
878 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
880 remove_piece(pc, to);
881 pc = make_piece(us, PAWN);
885 if (type_of(m) == CASTLING)
888 do_castling<false>(us, from, to, rfrom, rto);
892 move_piece(pc, to, from); // Put the piece back at the source square
894 if (st->capturedPiece)
898 if (type_of(m) == ENPASSANT)
900 capsq -= pawn_push(us);
902 assert(type_of(pc) == PAWN);
903 assert(to == st->previous->epSquare);
904 assert(relative_rank(us, to) == RANK_6);
905 assert(piece_on(capsq) == NO_PIECE);
906 assert(st->capturedPiece == make_piece(~us, PAWN));
909 put_piece(st->capturedPiece, capsq); // Restore the captured piece
913 // Finally point our state pointer back to the previous state
921 /// Position::do_castling() is a helper used to do/undo a castling move. This
922 /// is a bit tricky in Chess960 where from/to squares can overlap.
924 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
926 bool kingSide = to > from;
927 rfrom = to; // Castling is encoded as "king captures friendly rook"
928 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
929 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
931 // Remove both pieces first since squares could overlap in Chess960
932 remove_piece(make_piece(us, KING), Do ? from : to);
933 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
934 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
935 put_piece(make_piece(us, KING), Do ? to : from);
936 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
940 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
941 /// the side to move without executing any move on the board.
943 void Position::do_null_move(StateInfo& newSt) {
946 assert(&newSt != st);
948 std::memcpy(&newSt, st, sizeof(StateInfo));
952 if (st->epSquare != SQ_NONE)
954 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
955 st->epSquare = SQ_NONE;
958 st->key ^= Zobrist::side;
959 prefetch(TT.first_entry(st->key));
962 st->pliesFromNull = 0;
964 sideToMove = ~sideToMove;
971 void Position::undo_null_move() {
976 sideToMove = ~sideToMove;
980 /// Position::key_after() computes the new hash key after the given move. Needed
981 /// for speculative prefetch. It doesn't recognize special moves like castling,
982 /// en-passant and promotions.
984 Key Position::key_after(Move m) const {
986 Square from = from_sq(m);
987 Square to = to_sq(m);
988 Piece pc = piece_on(from);
989 Piece captured = piece_on(to);
990 Key k = st->key ^ Zobrist::side;
993 k ^= Zobrist::psq[captured][to];
995 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
999 /// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
1000 /// SEE value of move is greater or equal to the given value. We'll use an
1001 /// algorithm similar to alpha-beta pruning with a null window.
1003 bool Position::see_ge(Move m, Value v) const {
1007 // Castling moves are implemented as king capturing the rook so cannot be
1008 // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
1009 // correct unless in the rare case the rook ends up under attack.
1010 if (type_of(m) == CASTLING)
1011 return VALUE_ZERO >= v;
1013 Square from = from_sq(m), to = to_sq(m);
1014 PieceType nextVictim = type_of(piece_on(from));
1015 Color stm = ~color_of(piece_on(from)); // First consider opponent's move
1016 Value balance; // Values of the pieces taken by us minus opponent's ones
1017 Bitboard occupied, stmAttackers;
1019 if (type_of(m) == ENPASSANT)
1021 occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
1022 balance = PieceValue[MG][PAWN];
1026 balance = PieceValue[MG][piece_on(to)];
1033 if (nextVictim == KING)
1036 balance -= PieceValue[MG][nextVictim];
1041 bool relativeStm = true; // True if the opponent is to move
1042 occupied ^= pieces() ^ from ^ to;
1044 // Find all attackers to the destination square, with the moving piece removed,
1045 // but possibly an X-ray attacker added behind it.
1046 Bitboard attackers = attackers_to(to, occupied) & occupied;
1050 stmAttackers = attackers & pieces(stm);
1052 // Don't allow pinned pieces to attack pieces except the king as long all
1053 // pinners are on their original square.
1054 if (!(st->pinnersForKing[stm] & ~occupied))
1055 stmAttackers &= ~st->blockersForKing[stm];
1060 // Locate and remove the next least valuable attacker
1061 nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1063 if (nextVictim == KING)
1064 return relativeStm == bool(attackers & pieces(~stm));
1066 balance += relativeStm ? PieceValue[MG][nextVictim]
1067 : -PieceValue[MG][nextVictim];
1069 relativeStm = !relativeStm;
1071 if (relativeStm == (balance >= v))
1079 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1080 /// or by repetition. It does not detect stalemates.
1082 bool Position::is_draw() const {
1084 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1087 int e = std::min(st->rule50, st->pliesFromNull);
1092 StateInfo* stp = st->previous->previous;
1095 stp = stp->previous->previous;
1097 if (stp->key == st->key)
1098 return true; // Draw at first repetition
1100 } while ((e -= 2) >= 4);
1106 /// Position::flip() flips position with the white and black sides reversed. This
1107 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1109 void Position::flip() {
1112 std::stringstream ss(fen());
1114 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1116 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1117 f.insert(0, token + (f.empty() ? " " : "/"));
1120 ss >> token; // Active color
1121 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1123 ss >> token; // Castling availability
1126 std::transform(f.begin(), f.end(), f.begin(),
1127 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1129 ss >> token; // En passant square
1130 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1132 std::getline(ss, token); // Half and full moves
1135 set(f, is_chess960(), st, this_thread());
1137 assert(pos_is_ok());
1141 /// Position::pos_is_ok() performs some consistency checks for the position object.
1142 /// This is meant to be helpful when debugging.
1144 bool Position::pos_is_ok(int* failedStep) const {
1146 const bool Fast = true; // Quick (default) or full check?
1148 enum { Default, King, Bitboards, State, Lists, Castling };
1150 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1155 if (step == Default)
1156 if ( (sideToMove != WHITE && sideToMove != BLACK)
1157 || piece_on(square<KING>(WHITE)) != W_KING
1158 || piece_on(square<KING>(BLACK)) != B_KING
1159 || ( ep_square() != SQ_NONE
1160 && relative_rank(sideToMove, ep_square()) != RANK_6))
1164 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1165 || std::count(board, board + SQUARE_NB, B_KING) != 1
1166 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1169 if (step == Bitboards)
1171 if ( (pieces(WHITE) & pieces(BLACK))
1172 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1175 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1176 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1177 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1185 if (std::memcmp(&si, st, sizeof(StateInfo)))
1190 for (Piece pc : Pieces)
1192 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1195 for (int i = 0; i < pieceCount[pc]; ++i)
1196 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1200 if (step == Castling)
1201 for (Color c = WHITE; c <= BLACK; ++c)
1202 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1204 if (!can_castle(c | s))
1207 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1208 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1209 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))