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
39 extern Score psq[PIECE_NB][SQUARE_NB];
44 Key psq[PIECE_NB][SQUARE_NB];
45 Key enpassant[FILE_NB];
46 Key castling[CASTLING_RIGHT_NB];
52 const string PieceToChar(" PNBRQK pnbrqk");
54 // min_attacker() is a helper function used by see() to locate the least
55 // valuable attacker for the side to move, remove the attacker we just found
56 // from the bitboards and scan for new X-ray attacks behind it.
59 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
60 Bitboard& occupied, Bitboard& attackers) {
62 Bitboard b = stmAttackers & bb[Pt];
64 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
66 occupied ^= b & ~(b - 1);
68 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
69 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
71 if (Pt == ROOK || Pt == QUEEN)
72 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
74 attackers &= occupied; // After X-ray that may add already processed pieces
79 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
80 return KING; // No need to update bitboards: it is the last cycle
86 /// operator<<(Position) returns an ASCII representation of the position
88 std::ostream& operator<<(std::ostream& os, const Position& pos) {
90 os << "\n +---+---+---+---+---+---+---+---+\n";
92 for (Rank r = RANK_8; r >= RANK_1; --r)
94 for (File f = FILE_A; f <= FILE_H; ++f)
95 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
97 os << " |\n +---+---+---+---+---+---+---+---+\n";
100 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
101 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
103 for (Bitboard b = pos.checkers(); b; )
104 os << UCI::square(pop_lsb(&b)) << " ";
110 /// Position::init() initializes at startup the various arrays used to compute
113 void Position::init() {
117 for (Piece pc : Pieces)
118 for (Square s = SQ_A1; s <= SQ_H8; ++s)
119 Zobrist::psq[pc][s] = rng.rand<Key>();
121 for (File f = FILE_A; f <= FILE_H; ++f)
122 Zobrist::enpassant[f] = rng.rand<Key>();
124 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
126 Zobrist::castling[cr] = 0;
130 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
131 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
135 Zobrist::side = rng.rand<Key>();
139 /// Position::set() initializes the position object with the given FEN string.
140 /// This function is not very robust - make sure that input FENs are correct,
141 /// this is assumed to be the responsibility of the GUI.
143 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
145 A FEN string defines a particular position using only the ASCII character set.
147 A FEN string contains six fields separated by a space. The fields are:
149 1) Piece placement (from white's perspective). Each rank is described, starting
150 with rank 8 and ending with rank 1. Within each rank, the contents of each
151 square are described from file A through file H. Following the Standard
152 Algebraic Notation (SAN), each piece is identified by a single letter taken
153 from the standard English names. White pieces are designated using upper-case
154 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
155 noted using digits 1 through 8 (the number of blank squares), and "/"
158 2) Active color. "w" means white moves next, "b" means black.
160 3) Castling availability. If neither side can castle, this is "-". Otherwise,
161 this has one or more letters: "K" (White can castle kingside), "Q" (White
162 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
163 can castle queenside).
165 4) En passant target square (in algebraic notation). If there's no en passant
166 target square, this is "-". If a pawn has just made a 2-square move, this
167 is the position "behind" the pawn. This is recorded regardless of whether
168 there is a pawn in position to make an en passant capture.
170 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
171 or capture. This is used to determine if a draw can be claimed under the
174 6) Fullmove number. The number of the full move. It starts at 1, and is
175 incremented after Black's move.
178 unsigned char col, row, token;
181 std::istringstream ss(fenStr);
183 std::memset(this, 0, sizeof(Position));
184 std::memset(si, 0, sizeof(StateInfo));
185 std::fill_n(&pieceList[0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
190 // 1. Piece placement
191 while ((ss >> token) && !isspace(token))
194 sq += Square(token - '0'); // Advance the given number of files
196 else if (token == '/')
199 else if ((idx = PieceToChar.find(token)) != string::npos)
201 put_piece(Piece(idx), sq);
208 sideToMove = (token == 'w' ? WHITE : BLACK);
211 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
212 // Shredder-FEN that uses the letters of the columns on which the rooks began
213 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
214 // if an inner rook is associated with the castling right, the castling tag is
215 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
216 while ((ss >> token) && !isspace(token))
219 Color c = islower(token) ? BLACK : WHITE;
220 Piece rook = make_piece(c, ROOK);
222 token = char(toupper(token));
225 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
227 else if (token == 'Q')
228 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
230 else if (token >= 'A' && token <= 'H')
231 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
236 set_castling_right(c, rsq);
239 // 4. En passant square. Ignore if no pawn capture is possible
240 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
241 && ((ss >> row) && (row == '3' || row == '6')))
243 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
245 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
246 st->epSquare = SQ_NONE;
249 st->epSquare = SQ_NONE;
251 // 5-6. Halfmove clock and fullmove number
252 ss >> std::skipws >> st->rule50 >> gamePly;
254 // Convert from fullmove starting from 1 to ply starting from 0,
255 // handle also common incorrect FEN with fullmove = 0.
256 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
258 chess960 = isChess960;
268 /// Position::set_castling_right() is a helper function used to set castling
269 /// rights given the corresponding color and the rook starting square.
271 void Position::set_castling_right(Color c, Square rfrom) {
273 Square kfrom = square<KING>(c);
274 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
275 CastlingRight cr = (c | cs);
277 st->castlingRights |= cr;
278 castlingRightsMask[kfrom] |= cr;
279 castlingRightsMask[rfrom] |= cr;
280 castlingRookSquare[cr] = rfrom;
282 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
283 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
285 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
286 if (s != kfrom && s != rfrom)
287 castlingPath[cr] |= s;
289 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
290 if (s != kfrom && s != rfrom)
291 castlingPath[cr] |= s;
295 /// Position::set_check_info() sets king attacks to detect if a move gives check
297 void Position::set_check_info(StateInfo* si) const {
299 si->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE), si->pinnersForKing[WHITE]);
300 si->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK), si->pinnersForKing[BLACK]);
302 Square ksq = square<KING>(~sideToMove);
304 si->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
305 si->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
306 si->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
307 si->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
308 si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK];
309 si->checkSquares[KING] = 0;
313 /// Position::set_state() computes the hash keys of the position, and other
314 /// data that once computed is updated incrementally as moves are made.
315 /// The function is only used when a new position is set up, and to verify
316 /// the correctness of the StateInfo data when running in debug mode.
318 void Position::set_state(StateInfo* si) const {
320 si->key = si->pawnKey = si->materialKey = 0;
321 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
322 si->psq = SCORE_ZERO;
323 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
327 for (Bitboard b = pieces(); b; )
329 Square s = pop_lsb(&b);
330 Piece pc = piece_on(s);
331 si->key ^= Zobrist::psq[pc][s];
332 si->psq += PSQT::psq[pc][s];
335 if (si->epSquare != SQ_NONE)
336 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
338 if (sideToMove == BLACK)
339 si->key ^= Zobrist::side;
341 si->key ^= Zobrist::castling[si->castlingRights];
343 for (Bitboard b = pieces(PAWN); b; )
345 Square s = pop_lsb(&b);
346 si->pawnKey ^= Zobrist::psq[piece_on(s)][s];
349 for (Piece pc : Pieces)
351 if (type_of(pc) != PAWN && type_of(pc) != KING)
352 si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc];
354 for (int cnt = 0; cnt < pieceCount[pc]; ++cnt)
355 si->materialKey ^= Zobrist::psq[pc][cnt];
360 /// Position::fen() returns a FEN representation of the position. In case of
361 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
363 const string Position::fen() const {
366 std::ostringstream ss;
368 for (Rank r = RANK_8; r >= RANK_1; --r)
370 for (File f = FILE_A; f <= FILE_H; ++f)
372 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
379 ss << PieceToChar[piece_on(make_square(f, r))];
386 ss << (sideToMove == WHITE ? " w " : " b ");
388 if (can_castle(WHITE_OO))
389 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
391 if (can_castle(WHITE_OOO))
392 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
394 if (can_castle(BLACK_OO))
395 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
397 if (can_castle(BLACK_OOO))
398 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
400 if (!can_castle(WHITE) && !can_castle(BLACK))
403 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
404 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
410 /// Position::game_phase() calculates the game phase interpolating total non-pawn
411 /// material between endgame and midgame limits.
413 Phase Position::game_phase() const {
415 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
417 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
419 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
423 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors)
424 /// that are blocking attacks on the square 's' from 'sliders'. A piece blocks a
425 /// slider if removing that piece from the board would result in a position where
426 /// square 's' is attacked. For example, a king-attack blocking piece can be either
427 /// a pinned or a discovered check piece, according if its color is the opposite
428 /// or the same of the color of the slider. The pinners bitboard get filled with
429 /// real and potential pinners.
431 Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const {
433 Bitboard b, p, result = 0;
435 // Pinners are sliders that attack 's' when a pinned piece is removed
436 pinners = p = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
437 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
441 b = between_bb(s, pop_lsb(&p)) & pieces();
443 if (!more_than_one(b))
450 /// Position::attackers_to() computes a bitboard of all pieces which attack a
451 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
453 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
455 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
456 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
457 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
458 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
459 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
460 | (attacks_from<KING>(s) & pieces(KING));
464 /// Position::legal() tests whether a pseudo-legal move is legal
466 bool Position::legal(Move m) const {
470 Color us = sideToMove;
471 Square from = from_sq(m);
473 assert(color_of(moved_piece(m)) == us);
474 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
476 // En passant captures are a tricky special case. Because they are rather
477 // uncommon, we do it simply by testing whether the king is attacked after
479 if (type_of(m) == ENPASSANT)
481 Square ksq = square<KING>(us);
482 Square to = to_sq(m);
483 Square capsq = to - pawn_push(us);
484 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
486 assert(to == ep_square());
487 assert(moved_piece(m) == make_piece(us, PAWN));
488 assert(piece_on(capsq) == make_piece(~us, PAWN));
489 assert(piece_on(to) == NO_PIECE);
491 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
492 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
495 // If the moving piece is a king, check whether the destination
496 // square is attacked by the opponent. Castling moves are checked
497 // for legality during move generation.
498 if (type_of(piece_on(from)) == KING)
499 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
501 // A non-king move is legal if and only if it is not pinned or it
502 // is moving along the ray towards or away from the king.
503 return !(pinned_pieces(us) & from)
504 || aligned(from, to_sq(m), square<KING>(us));
508 /// Position::pseudo_legal() takes a random move and tests whether the move is
509 /// pseudo legal. It is used to validate moves from TT that can be corrupted
510 /// due to SMP concurrent access or hash position key aliasing.
512 bool Position::pseudo_legal(const Move m) const {
514 Color us = sideToMove;
515 Square from = from_sq(m);
516 Square to = to_sq(m);
517 Piece pc = moved_piece(m);
519 // Use a slower but simpler function for uncommon cases
520 if (type_of(m) != NORMAL)
521 return MoveList<LEGAL>(*this).contains(m);
523 // Is not a promotion, so promotion piece must be empty
524 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
527 // If the 'from' square is not occupied by a piece belonging to the side to
528 // move, the move is obviously not legal.
529 if (pc == NO_PIECE || color_of(pc) != us)
532 // The destination square cannot be occupied by a friendly piece
536 // Handle the special case of a pawn move
537 if (type_of(pc) == PAWN)
539 // We have already handled promotion moves, so destination
540 // cannot be on the 8th/1st rank.
541 if (rank_of(to) == relative_rank(us, RANK_8))
544 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
545 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
546 && !( (from + 2 * pawn_push(us) == to) // Not a double push
547 && (rank_of(from) == relative_rank(us, RANK_2))
549 && empty(to - pawn_push(us))))
552 else if (!(attacks_from(pc, from) & to))
555 // Evasions generator already takes care to avoid some kind of illegal moves
556 // and legal() relies on this. We therefore have to take care that the same
557 // kind of moves are filtered out here.
560 if (type_of(pc) != KING)
562 // Double check? In this case a king move is required
563 if (more_than_one(checkers()))
566 // Our move must be a blocking evasion or a capture of the checking piece
567 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
570 // In case of king moves under check we have to remove king so as to catch
571 // invalid moves like b1a1 when opposite queen is on c1.
572 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
580 /// Position::gives_check() tests whether a pseudo-legal move gives a check
582 bool Position::gives_check(Move m) const {
585 assert(color_of(moved_piece(m)) == sideToMove);
587 Square from = from_sq(m);
588 Square to = to_sq(m);
590 // Is there a direct check?
591 if (st->checkSquares[type_of(piece_on(from))] & to)
594 // Is there a discovered check?
595 if ( (discovered_check_candidates() & from)
596 && !aligned(from, to, square<KING>(~sideToMove)))
605 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & square<KING>(~sideToMove);
607 // En passant capture with check? We have already handled the case
608 // of direct checks and ordinary discovered check, so the only case we
609 // need to handle is the unusual case of a discovered check through
610 // the captured pawn.
613 Square capsq = make_square(file_of(to), rank_of(from));
614 Bitboard b = (pieces() ^ from ^ capsq) | to;
616 return (attacks_bb< ROOK>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK))
617 | (attacks_bb<BISHOP>(square<KING>(~sideToMove), b) & pieces(sideToMove, QUEEN, BISHOP));
622 Square rfrom = to; // Castling is encoded as 'King captures the rook'
623 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
624 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
626 return (PseudoAttacks[ROOK][rto] & square<KING>(~sideToMove))
627 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square<KING>(~sideToMove));
636 /// Position::do_move() makes a move, and saves all information necessary
637 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
638 /// moves should be filtered out before this function is called.
640 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
643 assert(&newSt != st);
646 Key k = st->key ^ Zobrist::side;
648 // Copy some fields of the old state to our new StateInfo object except the
649 // ones which are going to be recalculated from scratch anyway and then switch
650 // our state pointer to point to the new (ready to be updated) state.
651 std::memcpy(&newSt, st, offsetof(StateInfo, key));
655 // Increment ply counters. In particular, rule50 will be reset to zero later on
656 // in case of a capture or a pawn move.
661 Color us = sideToMove;
663 Square from = from_sq(m);
664 Square to = to_sq(m);
665 Piece pc = piece_on(from);
666 Piece captured = type_of(m) == ENPASSANT ? make_piece(them, PAWN) : piece_on(to);
668 assert(color_of(pc) == us);
669 assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us));
670 assert(type_of(captured) != KING);
672 if (type_of(m) == CASTLING)
674 assert(pc == make_piece(us, KING));
675 assert(captured == make_piece(us, ROOK));
678 do_castling<true>(us, from, to, rfrom, rto);
680 st->psq += PSQT::psq[captured][rto] - PSQT::psq[captured][rfrom];
681 k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto];
689 // If the captured piece is a pawn, update pawn hash key, otherwise
690 // update non-pawn material.
691 if (type_of(captured) == PAWN)
693 if (type_of(m) == ENPASSANT)
695 capsq -= pawn_push(us);
697 assert(pc == make_piece(us, PAWN));
698 assert(to == st->epSquare);
699 assert(relative_rank(us, to) == RANK_6);
700 assert(piece_on(to) == NO_PIECE);
701 assert(piece_on(capsq) == make_piece(them, PAWN));
703 board[capsq] = NO_PIECE; // Not done by remove_piece()
706 st->pawnKey ^= Zobrist::psq[captured][capsq];
709 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
711 // Update board and piece lists
712 remove_piece(captured, capsq);
714 // Update material hash key and prefetch access to materialTable
715 k ^= Zobrist::psq[captured][capsq];
716 st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]];
717 prefetch(thisThread->materialTable[st->materialKey]);
719 // Update incremental scores
720 st->psq -= PSQT::psq[captured][capsq];
722 // Reset rule 50 counter
727 k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
729 // Reset en passant square
730 if (st->epSquare != SQ_NONE)
732 k ^= Zobrist::enpassant[file_of(st->epSquare)];
733 st->epSquare = SQ_NONE;
736 // Update castling rights if needed
737 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
739 int cr = castlingRightsMask[from] | castlingRightsMask[to];
740 k ^= Zobrist::castling[st->castlingRights & cr];
741 st->castlingRights &= ~cr;
744 // Move the piece. The tricky Chess960 castling is handled earlier
745 if (type_of(m) != CASTLING)
746 move_piece(pc, from, to);
748 // If the moving piece is a pawn do some special extra work
749 if (type_of(pc) == PAWN)
751 // Set en-passant square if the moved pawn can be captured
752 if ( (int(to) ^ int(from)) == 16
753 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
755 st->epSquare = (from + to) / 2;
756 k ^= Zobrist::enpassant[file_of(st->epSquare)];
759 else if (type_of(m) == PROMOTION)
761 Piece promotion = make_piece(us, promotion_type(m));
763 assert(relative_rank(us, to) == RANK_8);
764 assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN);
766 remove_piece(pc, to);
767 put_piece(promotion, to);
770 k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
771 st->pawnKey ^= Zobrist::psq[pc][to];
772 st->materialKey ^= Zobrist::psq[promotion][pieceCount[promotion]-1]
773 ^ Zobrist::psq[pc][pieceCount[pc]];
775 // Update incremental score
776 st->psq += PSQT::psq[promotion][to] - PSQT::psq[pc][to];
779 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
782 // Update pawn hash key and prefetch access to pawnsTable
783 st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
784 prefetch(thisThread->pawnsTable[st->pawnKey]);
786 // Reset rule 50 draw counter
790 // Update incremental scores
791 st->psq += PSQT::psq[pc][to] - PSQT::psq[pc][from];
794 st->capturedPiece = captured;
796 // Update the key with the final value
799 // Calculate checkers bitboard (if move gives check)
800 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
802 sideToMove = ~sideToMove;
804 // Update king attacks used for fast check detection
811 /// Position::undo_move() unmakes a move. When it returns, the position should
812 /// be restored to exactly the same state as before the move was made.
814 void Position::undo_move(Move m) {
818 sideToMove = ~sideToMove;
820 Color us = sideToMove;
821 Square from = from_sq(m);
822 Square to = to_sq(m);
823 Piece pc = piece_on(to);
825 assert(empty(from) || type_of(m) == CASTLING);
826 assert(type_of(st->capturedPiece) != KING);
828 if (type_of(m) == PROMOTION)
830 assert(relative_rank(us, to) == RANK_8);
831 assert(type_of(pc) == promotion_type(m));
832 assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN);
834 remove_piece(pc, to);
835 pc = make_piece(us, PAWN);
839 if (type_of(m) == CASTLING)
842 do_castling<false>(us, from, to, rfrom, rto);
846 move_piece(pc, to, from); // Put the piece back at the source square
848 if (st->capturedPiece)
852 if (type_of(m) == ENPASSANT)
854 capsq -= pawn_push(us);
856 assert(type_of(pc) == PAWN);
857 assert(to == st->previous->epSquare);
858 assert(relative_rank(us, to) == RANK_6);
859 assert(piece_on(capsq) == NO_PIECE);
860 assert(st->capturedPiece == make_piece(~us, PAWN));
863 put_piece(st->capturedPiece, capsq); // Restore the captured piece
867 // Finally point our state pointer back to the previous state
875 /// Position::do_castling() is a helper used to do/undo a castling move. This
876 /// is a bit tricky in Chess960 where from/to squares can overlap.
878 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
880 bool kingSide = to > from;
881 rfrom = to; // Castling is encoded as "king captures friendly rook"
882 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
883 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
885 // Remove both pieces first since squares could overlap in Chess960
886 remove_piece(make_piece(us, KING), Do ? from : to);
887 remove_piece(make_piece(us, ROOK), Do ? rfrom : rto);
888 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
889 put_piece(make_piece(us, KING), Do ? to : from);
890 put_piece(make_piece(us, ROOK), Do ? rto : rfrom);
894 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
895 /// the side to move without executing any move on the board.
897 void Position::do_null_move(StateInfo& newSt) {
900 assert(&newSt != st);
902 std::memcpy(&newSt, st, sizeof(StateInfo));
906 if (st->epSquare != SQ_NONE)
908 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
909 st->epSquare = SQ_NONE;
912 st->key ^= Zobrist::side;
913 prefetch(TT.first_entry(st->key));
916 st->pliesFromNull = 0;
918 sideToMove = ~sideToMove;
925 void Position::undo_null_move() {
930 sideToMove = ~sideToMove;
934 /// Position::key_after() computes the new hash key after the given move. Needed
935 /// for speculative prefetch. It doesn't recognize special moves like castling,
936 /// en-passant and promotions.
938 Key Position::key_after(Move m) const {
940 Square from = from_sq(m);
941 Square to = to_sq(m);
942 Piece pc = piece_on(from);
943 Piece captured = piece_on(to);
944 Key k = st->key ^ Zobrist::side;
947 k ^= Zobrist::psq[captured][to];
949 return k ^ Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from];
953 /// Position::see() is a static exchange evaluator: It tries to estimate the
954 /// material gain or loss resulting from a move.
956 Value Position::see_sign(Move m) const {
960 // Early return if SEE cannot be negative because captured piece value
961 // is not less then capturing one. Note that king moves always return
962 // here because king midgame value is set to 0.
963 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
964 return VALUE_KNOWN_WIN;
969 Value Position::see(Move m) const {
972 Bitboard occupied, attackers, stmAttackers;
982 swapList[0] = PieceValue[MG][piece_on(to)];
983 stm = color_of(piece_on(from));
984 occupied = pieces() ^ from;
986 // Castling moves are implemented as king capturing the rook so cannot
987 // be handled correctly. Simply return VALUE_ZERO that is always correct
988 // unless in the rare case the rook ends up under attack.
989 if (type_of(m) == CASTLING)
992 if (type_of(m) == ENPASSANT)
994 occupied ^= to - pawn_push(stm); // Remove the captured pawn
995 swapList[0] = PieceValue[MG][PAWN];
998 // Find all attackers to the destination square, with the moving piece
999 // removed, but possibly an X-ray attacker added behind it.
1000 attackers = attackers_to(to, occupied) & occupied;
1002 // If the opponent has no attackers we are finished
1004 stmAttackers = attackers & pieces(stm);
1005 occupied ^= to; // For the case when captured piece is a pinner
1007 // Don't allow pinned pieces to attack as long all pinners (this includes also
1008 // potential ones) are on their original square. When a pinner moves to the
1009 // exchange-square or get captured on it, we fall back to standard SEE behaviour.
1010 if ( (stmAttackers & pinned_pieces(stm))
1011 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1012 stmAttackers &= ~pinned_pieces(stm);
1017 // The destination square is defended, which makes things rather more
1018 // difficult to compute. We proceed by building up a "swap list" containing
1019 // the material gain or loss at each stop in a sequence of captures to the
1020 // destination square, where the sides alternately capture, and always
1021 // capture with the least valuable piece. After each capture, we look for
1022 // new X-ray attacks from behind the capturing piece.
1023 captured = type_of(piece_on(from));
1026 assert(slIndex < 32);
1028 // Add the new entry to the swap list
1029 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1031 // Locate and remove the next least valuable attacker
1032 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1034 stmAttackers = attackers & pieces(stm);
1035 if ( (stmAttackers & pinned_pieces(stm))
1036 && (st->pinnersForKing[stm] & occupied) == st->pinnersForKing[stm])
1037 stmAttackers &= ~pinned_pieces(stm);
1041 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1043 // Having built the swap list, we negamax through it to find the best
1044 // achievable score from the point of view of the side to move.
1046 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1052 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1053 /// or by repetition. It does not detect stalemates.
1055 bool Position::is_draw() const {
1057 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1060 StateInfo* stp = st;
1061 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1063 stp = stp->previous->previous;
1065 if (stp->key == st->key)
1066 return true; // Draw at first repetition
1073 /// Position::flip() flips position with the white and black sides reversed. This
1074 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1076 void Position::flip() {
1079 std::stringstream ss(fen());
1081 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1083 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1084 f.insert(0, token + (f.empty() ? " " : "/"));
1087 ss >> token; // Active color
1088 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1090 ss >> token; // Castling availability
1093 std::transform(f.begin(), f.end(), f.begin(),
1094 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1096 ss >> token; // En passant square
1097 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1099 std::getline(ss, token); // Half and full moves
1102 set(f, is_chess960(), st, this_thread());
1104 assert(pos_is_ok());
1108 /// Position::pos_is_ok() performs some consistency checks for the position object.
1109 /// This is meant to be helpful when debugging.
1111 bool Position::pos_is_ok(int* failedStep) const {
1113 const bool Fast = true; // Quick (default) or full check?
1115 enum { Default, King, Bitboards, State, Lists, Castling };
1117 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1122 if (step == Default)
1123 if ( (sideToMove != WHITE && sideToMove != BLACK)
1124 || piece_on(square<KING>(WHITE)) != W_KING
1125 || piece_on(square<KING>(BLACK)) != B_KING
1126 || ( ep_square() != SQ_NONE
1127 && relative_rank(sideToMove, ep_square()) != RANK_6))
1131 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1132 || std::count(board, board + SQUARE_NB, B_KING) != 1
1133 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1136 if (step == Bitboards)
1138 if ( (pieces(WHITE) & pieces(BLACK))
1139 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1142 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1143 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1144 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1152 if (std::memcmp(&si, st, sizeof(StateInfo)))
1157 for (Piece pc : Pieces)
1159 if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))))
1162 for (int i = 0; i < pieceCount[pc]; ++i)
1163 if (board[pieceList[pc][i]] != pc || index[pieceList[pc][i]] != i)
1167 if (step == Castling)
1168 for (Color c = WHITE; c <= BLACK; ++c)
1169 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1171 if (!can_castle(c | s))
1174 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1175 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1176 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))