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 (Piece pc : Pieces)
113 for (Square s = SQ_A1; s <= SQ_H8; ++s)
114 Zobrist::psq[pc][s] = rng.rand<Key>();
116 for (File f = FILE_A; f <= FILE_H; ++f)
117 Zobrist::enpassant[f] = rng.rand<Key>();
119 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
121 Zobrist::castling[cr] = 0;
125 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
126 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
130 Zobrist::side = rng.rand<Key>();
134 /// Position::set() initializes the position object with the given FEN string.
135 /// This function is not very robust - make sure that input FENs are correct,
136 /// this is assumed to be the responsibility of the GUI.
138 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
140 A FEN string defines a particular position using only the ASCII character set.
142 A FEN string contains six fields separated by a space. The fields are:
144 1) Piece placement (from white's perspective). Each rank is described, starting
145 with rank 8 and ending with rank 1. Within each rank, the contents of each
146 square are described from file A through file H. Following the Standard
147 Algebraic Notation (SAN), each piece is identified by a single letter taken
148 from the standard English names. White pieces are designated using upper-case
149 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
150 noted using digits 1 through 8 (the number of blank squares), and "/"
153 2) Active color. "w" means white moves next, "b" means black.
155 3) Castling availability. If neither side can castle, this is "-". Otherwise,
156 this has one or more letters: "K" (White can castle kingside), "Q" (White
157 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
158 can castle queenside).
160 4) En passant target square (in algebraic notation). If there's no en passant
161 target square, this is "-". If a pawn has just made a 2-square move, this
162 is the position "behind" the pawn. This is recorded regardless of whether
163 there is a pawn in position to make an en passant capture.
165 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
166 or capture. This is used to determine if a draw can be claimed under the
169 6) Fullmove number. The number of the full move. It starts at 1, and is
170 incremented after Black's move.
173 unsigned char col, row, token;
176 std::istringstream ss(fenStr);
178 std::memset(this, 0, sizeof(Position));
179 std::memset(si, 0, sizeof(StateInfo));
180 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
185 // 1. Piece placement
186 while ((ss >> token) && !isspace(token))
189 sq += Square(token - '0'); // Advance the given number of files
191 else if (token == '/')
194 else if ((idx = PieceToChar.find(token)) != string::npos)
196 put_piece(Piece(idx), sq);
203 sideToMove = (token == 'w' ? WHITE : BLACK);
206 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
207 // Shredder-FEN that uses the letters of the columns on which the rooks began
208 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
209 // if an inner rook is associated with the castling right, the castling tag is
210 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
211 while ((ss >> token) && !isspace(token))
214 Color c = islower(token) ? BLACK : WHITE;
215 Piece rook = make_piece(c, ROOK);
217 token = char(toupper(token));
220 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
222 else if (token == 'Q')
223 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
225 else if (token >= 'A' && token <= 'H')
226 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
231 set_castling_right(c, rsq);
234 // 4. En passant square. Ignore if no pawn capture is possible
235 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
236 && ((ss >> row) && (row == '3' || row == '6')))
238 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
240 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
241 st->epSquare = SQ_NONE;
244 st->epSquare = SQ_NONE;
246 // 5-6. Halfmove clock and fullmove number
247 ss >> std::skipws >> st->rule50 >> gamePly;
249 // Convert from fullmove starting from 1 to ply starting from 0,
250 // handle also common incorrect FEN with fullmove = 0.
251 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
253 chess960 = isChess960;
263 /// Position::set_castling_right() is a helper function used to set castling
264 /// rights given the corresponding color and the rook starting square.
266 void Position::set_castling_right(Color c, Square rfrom) {
268 Square kfrom = square<KING>(c);
269 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
270 CastlingRight cr = (c | cs);
272 st->castlingRights |= cr;
273 castlingRightsMask[kfrom] |= cr;
274 castlingRightsMask[rfrom] |= cr;
275 castlingRookSquare[cr] = rfrom;
277 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
278 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
280 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
281 if (s != kfrom && s != rfrom)
282 castlingPath[cr] |= s;
284 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
285 if (s != kfrom && s != rfrom)
286 castlingPath[cr] |= s;
290 /// Position::set_check_info() sets king attacks to detect if a move gives check
292 void Position::set_check_info(StateInfo* si) const {
294 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE));
295 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK));
297 Square ksq = square<KING>(~sideToMove);
299 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
300 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
301 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
302 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
303 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
304 si->checkSquares[KING] = 0;
308 /// Position::set_state() computes the hash keys of the position, and other
309 /// data that once computed is updated incrementally as moves are made.
310 /// The function is only used when a new position is set up, and to verify
311 /// the correctness of the StateInfo data when running in debug mode.
313 void Position::set_state(StateInfo* si) const {
315 si->key = si->pawnKey = si->materialKey = 0;
316 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
317 si->psq = SCORE_ZERO;
318 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
322 for (Bitboard b = pieces(); b; )
324 Square s = pop_lsb(&b);
325 Piece pc = piece_on(s);
326 si->key ^= Zobrist::psq[pc][s];
327 si->psq += PSQT::psq[pc][s];
330 if (si->epSquare != SQ_NONE)
331 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
333 if (sideToMove == BLACK)
334 si->key ^= Zobrist::side;
336 si->key ^= Zobrist::castling[si->castlingRights];
338 for (Bitboard b = pieces(PAWN); b; )
340 Square s = pop_lsb(&b);
341 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
344 for (Piece pc : Pieces)
346 if (type_of(pc) != PAWN && type_of(pc) != KING)
347 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
349 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
350 si->materialKey ^= Zobrist::psq[pc][cnt];
355 /// Position::fen() returns a FEN representation of the position. In case of
356 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
358 const string Position::fen() const {
361 std::ostringstream ss;
363 for (Rank r = RANK_8; r >= RANK_1; --r)
365 for (File f = FILE_A; f <= FILE_H; ++f)
367 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
374 ss << PieceToChar[piece_on(make_square(f, r))];
381 ss << (sideToMove == WHITE ? " w " : " b ");
383 if (can_castle(WHITE_OO))
384 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
386 if (can_castle(WHITE_OOO))
387 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
389 if (can_castle(BLACK_OO))
390 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
392 if (can_castle(BLACK_OOO))
393 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
395 if (!can_castle(WHITE) && !can_castle(BLACK))
398 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
399 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
405 /// Position::game_phase() calculates the game phase interpolating total non-pawn
406 /// material between endgame and midgame limits.
408 Phase Position::game_phase() const {
410 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
412 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
414 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
418 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors) that
419 /// are blocking attacks on the square 's' from 'sliders'. A piece blocks a slider
420 /// if removing that piece from the board would result in a position where square 's'
421 /// is attacked. For example, a king-attack blocking piece can be either a pinned or
422 /// a discovered check piece, according if its color is the opposite or the same of
423 /// the color of the slider.
425 Bitboard Position::slider_blockers(Bitboard sliders, Square s) const {
427 Bitboard b, pinners, result = 0;
429 // Pinners are sliders that attack 's' when a pinned piece is removed
430 pinners = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
431 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
435 b = between_bb(s, pop_lsb(&pinners)) & pieces();
437 if (!more_than_one(b))
444 /// Position::attackers_to() computes a bitboard of all pieces which attack a
445 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
447 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
449 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
450 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
451 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
452 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
453 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
454 | (attacks_from<KING>(s) & pieces(KING));
458 /// Position::legal() tests whether a pseudo-legal move is legal
460 bool Position::legal(Move m) const {
464 Color us = sideToMove;
465 Square from = from_sq(m);
467 assert(color_of(moved_piece(m)) == us);
468 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
470 // En passant captures are a tricky special case. Because they are rather
471 // uncommon, we do it simply by testing whether the king is attacked after
473 if (type_of(m) == ENPASSANT)
475 Square ksq = square<KING>(us);
476 Square to = to_sq(m);
477 Square capsq = to - pawn_push(us);
478 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
480 assert(to == ep_square());
481 assert(moved_piece(m) == make_piece(us, PAWN));
482 assert(piece_on(capsq) == make_piece(~us, PAWN));
483 assert(piece_on(to) == NO_PIECE);
485 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
486 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
489 // If the moving piece is a king, check whether the destination
490 // square is attacked by the opponent. Castling moves are checked
491 // for legality during move generation.
492 if (type_of(piece_on(from)) == KING)
493 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
495 // A non-king move is legal if and only if it is not pinned or it
496 // is moving along the ray towards or away from the king.
497 return !(pinned_pieces(us) & from)
498 || aligned(from, to_sq(m), square<KING>(us));
502 /// Position::pseudo_legal() takes a random move and tests whether the move is
503 /// pseudo legal. It is used to validate moves from TT that can be corrupted
504 /// due to SMP concurrent access or hash position key aliasing.
506 bool Position::pseudo_legal(const Move m) const {
508 Color us = sideToMove;
509 Square from = from_sq(m);
510 Square to = to_sq(m);
511 Piece pc = moved_piece(m);
513 // Use a slower but simpler function for uncommon cases
514 if (type_of(m) != NORMAL)
515 return MoveList<LEGAL>(*this).contains(m);
517 // Is not a promotion, so promotion piece must be empty
518 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
521 // If the 'from' square is not occupied by a piece belonging to the side to
522 // move, the move is obviously not legal.
523 if (pc == NO_PIECE || color_of(pc) != us)
526 // The destination square cannot be occupied by a friendly piece
530 // Handle the special case of a pawn move
531 if (type_of(pc) == PAWN)
533 // We have already handled promotion moves, so destination
534 // cannot be on the 8th/1st rank.
535 if (rank_of(to) == relative_rank(us, RANK_8))
538 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
539 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
540 && !( (from + 2 * pawn_push(us) == to) // Not a double push
541 && (rank_of(from) == relative_rank(us, RANK_2))
543 && empty(to - pawn_push(us))))
546 else if (!(attacks_from(pc, from) & to))
549 // Evasions generator already takes care to avoid some kind of illegal moves
550 // and legal() relies on this. We therefore have to take care that the same
551 // kind of moves are filtered out here.
554 if (type_of(pc) != KING)
556 // Double check? In this case a king move is required
557 if (more_than_one(checkers()))
560 // Our move must be a blocking evasion or a capture of the checking piece
561 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
564 // In case of king moves under check we have to remove king so as to catch
565 // invalid moves like b1a1 when opposite queen is on c1.
566 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
574 /// Position::gives_check() tests whether a pseudo-legal move gives a check
576 bool Position::gives_check(Move m) const {
579 assert(color_of(moved_piece(m)) == sideToMove);
581 Square from = from_sq(m);
582 Square to = to_sq(m);
584 // Is there a direct check?
585 if (st->checkSquares[type_of(piece_on(from))] & to)
588 // Is there a discovered check?
589 if ( (discovered_check_candidates() & from)
590 && !aligned(from, to, square<KING>(~sideToMove)))
599 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
601 // En passant capture with check? We have already handled the case
602 // of direct checks and ordinary discovered check, so the only case we
603 // need to handle is the unusual case of a discovered check through
604 // the captured pawn.
607 Square capsq = make_square(file_of(to), rank_of(from));
608 Bitboard b = (pieces() ^ from ^ capsq) | to;
610 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
611 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
616 Square rfrom = to; // Castling is encoded as 'King captures the rook'
617 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
618 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
620 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
621 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
630 /// Position::do_move() makes a move, and saves all information necessary
631 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
632 /// moves should be filtered out before this function is called.
634 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
637 assert(&newSt != st);
640 Key k = st->key ^ Zobrist::side;
642 // Copy some fields of the old state to our new StateInfo object except the
643 // ones which are going to be recalculated from scratch anyway and then switch
644 // our state pointer to point to the new (ready to be updated) state.
645 std::memcpy(&newSt, st, offsetof(StateInfo, key));
649 // Increment ply counters. In particular, rule50 will be reset to zero later on
650 // in case of a capture or a pawn move.
655 Color us = sideToMove;
657 Square from = from_sq(m);
658 Square to = to_sq(m);
659 Piece pc = piece_on(from);
660 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
662 assert(color_of(pc) == us);
663 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
664 assert(type_of(captured) != KING);
666 if (type_of(m) == CASTLING)
668 assert(pc == make_piece(us, KING));
669 assert(captured == make_piece(us, ROOK));
672 do_castling<true>(us, from, to, rfrom, rto);
674 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
675 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
683 // If the captured piece is a pawn, update pawn hash key, otherwise
684 // update non-pawn material.
685 if (type_of(captured) == PAWN)
687 if (type_of(m) == ENPASSANT)
689 capsq -= pawn_push(us);
691 assert(pc == make_piece(us, PAWN));
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[captured][capsq];
703 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
705 // Update board and piece lists
706 remove_piece(captured, capsq);
708 // Update material hash key and prefetch access to materialTable
709 k ^= Zobrist::psq[captured][capsq];
710 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
711 prefetch(thisThread->materialTable[st->materialKey]);
713 // Update incremental scores
714 st->psq -= PSQT::psq[captured][capsq];
716 // Reset rule 50 counter
721 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][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(pc, from, to);
742 // If the moving piece is a pawn do some special extra work
743 if (type_of(pc) == PAWN)
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 Piece promotion = make_piece(us, promotion_type(m));
757 assert(relative_rank(us, to) == RANK_8);
758 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
760 remove_piece(pc, to);
761 put_piece(promotion, to);
764 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
765 st->pawnKey ^= Zobrist::psq[pc][to];
766 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
767 ^ Zobrist::psq[pc][pieceCount[pc]];
769 // Update incremental score
770 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
773 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
776 // Update pawn hash key and prefetch access to pawnsTable
777 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
778 prefetch(thisThread->pawnsTable[st->pawnKey]);
780 // Reset rule 50 draw counter
784 // Update incremental scores
785 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
788 st->capturedPiece = 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 Piece pc = piece_on(to);
819 assert(empty(from) || type_of(m) == CASTLING);
820 assert(type_of(st->capturedPiece) != KING);
822 if (type_of(m) == PROMOTION)
824 assert(relative_rank(us, to) == RANK_8);
825 assert(type_of(pc) == promotion_type(m));
826 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
828 remove_piece(pc, to);
829 pc = make_piece(us, PAWN);
833 if (type_of(m) == CASTLING)
836 do_castling<false>(us, from, to, rfrom, rto);
840 move_piece(pc, to, from); // Put the piece back at the source square
842 if (st->capturedPiece)
846 if (type_of(m) == ENPASSANT)
848 capsq -= pawn_push(us);
850 assert(type_of(pc) == PAWN);
851 assert(to == st->previous->epSquare);
852 assert(relative_rank(us, to) == RANK_6);
853 assert(piece_on(capsq) == NO_PIECE);
854 assert(st->capturedPiece == make_piece(~us, PAWN));
857 put_piece(st->capturedPiece, 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 in Chess960 where from/to squares can overlap.
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(make_piece(us, KING), Do ? from : to);
881 remove_piece(make_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(make_piece(us, KING), Do ? to : from);
884 put_piece(make_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 Square from = from_sq(m);
935 Square to = to_sq(m);
936 Piece pc = piece_on(from);
937 Piece captured = piece_on(to);
938 Key k = st->key ^ Zobrist::side;
941 k ^= Zobrist::psq[captured][to];
943 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
947 /// Position::see() is a static exchange evaluator: It tries to estimate the
948 /// material gain or loss resulting from a move.
950 Value Position::see_sign(Move m) const {
954 // Early return if SEE cannot be negative because captured piece value
955 // is not less then capturing one. Note that king moves always return
956 // here because king midgame value is set to 0.
957 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
958 return VALUE_KNOWN_WIN;
963 Value Position::see(Move m) const {
966 Bitboard occupied, attackers, stmAttackers;
976 swapList[0] = PieceValue[MG][piece_on(to)];
977 stm = color_of(piece_on(from));
978 occupied = pieces() ^ from;
980 // Castling moves are implemented as king capturing the rook so cannot
981 // be handled correctly. Simply return VALUE_ZERO that is always correct
982 // unless in the rare case the rook ends up under attack.
983 if (type_of(m) == CASTLING)
986 if (type_of(m) == ENPASSANT)
988 occupied ^= to - pawn_push(stm); // Remove the captured pawn
989 swapList[0] = PieceValue[MG][PAWN];
992 // Find all attackers to the destination square, with the moving piece
993 // removed, but possibly an X-ray attacker added behind it.
994 attackers = attackers_to(to, occupied) & occupied;
996 // If the opponent has no attackers we are finished
998 stmAttackers = attackers & pieces(stm);
1002 // The destination square is defended, which makes things rather more
1003 // difficult to compute. We proceed by building up a "swap list" containing
1004 // the material gain or loss at each stop in a sequence of captures to the
1005 // destination square, where the sides alternately capture, and always
1006 // capture with the least valuable piece. After each capture, we look for
1007 // new X-ray attacks from behind the capturing piece.
1008 captured = type_of(piece_on(from));
1011 assert(slIndex < 32);
1013 // Add the new entry to the swap list
1014 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1016 // Locate and remove the next least valuable attacker
1017 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1019 stmAttackers = attackers & pieces(stm);
1022 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1024 // Having built the swap list, we negamax through it to find the best
1025 // achievable score from the point of view of the side to move.
1027 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1033 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1034 /// or by repetition. It does not detect stalemates.
1036 bool Position::is_draw() const {
1038 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1041 StateInfo* stp = st;
1042 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1044 stp = stp->previous->previous;
1046 if (stp->key == st->key)
1047 return true; // Draw at first repetition
1054 /// Position::flip() flips position with the white and black sides reversed. This
1055 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1057 void Position::flip() {
1060 std::stringstream ss(fen());
1062 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1064 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1065 f.insert(0, token + (f.empty() ? " " : "/"));
1068 ss >> token; // Active color
1069 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1071 ss >> token; // Castling availability
1074 std::transform(f.begin(), f.end(), f.begin(),
1075 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1077 ss >> token; // En passant square
1078 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1080 std::getline(ss, token); // Half and full moves
1083 set(f, is_chess960(), st, this_thread());
1085 assert(pos_is_ok());
1089 /// Position::pos_is_ok() performs some consistency checks for the position object.
1090 /// This is meant to be helpful when debugging.
1092 bool Position::pos_is_ok(int* failedStep) const {
1094 const bool Fast = true; // Quick (default) or full check?
1096 enum { Default, King, Bitboards, State, Lists, Castling };
1098 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1103 if (step == Default)
1104 if ( (sideToMove != WHITE && sideToMove != BLACK)
1105 || piece_on(square<KING>(WHITE)) != W_KING
1106 || piece_on(square<KING>(BLACK)) != B_KING
1107 || ( ep_square() != SQ_NONE
1108 && relative_rank(sideToMove, ep_square()) != RANK_6))
1112 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1113 || std::count(board, board + SQUARE_NB, B_KING) != 1
1114 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1117 if (step == Bitboards)
1119 if ( (pieces(WHITE) & pieces(BLACK))
1120 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1123 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1124 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1125 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1133 if (std::memcmp(&si, st, sizeof(StateInfo)))
1138 for (Piece pc : Pieces)
1140 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1143 for (int i = 0; i < pieceCount[pc]; ++i)
1144 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1148 if (step == Castling)
1149 for (Color c = WHITE; c <= BLACK; ++c)
1150 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1152 if (!can_castle(c | s))
1155 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1156 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1157 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))