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
37 Value PieceValue[PHASE_NB][PIECE_NB] = {
38 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
39 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
43 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
44 Key enpassant[FILE_NB];
45 Key castling[CASTLING_RIGHT_NB];
50 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
54 const string PieceToChar(" PNBRQK pnbrqk");
56 // min_attacker() is a helper function used by see() to locate the least
57 // valuable attacker for the side to move, remove the attacker we just found
58 // from the bitboards and scan for new X-ray attacks behind it.
61 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
62 Bitboard& occupied, Bitboard& attackers) {
64 Bitboard b = stmAttackers & bb[Pt];
66 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
68 occupied ^= b & ~(b - 1);
70 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
71 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
73 if (Pt == ROOK || Pt == QUEEN)
74 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
76 attackers &= occupied; // After X-ray that may add already processed pieces
81 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
82 return KING; // No need to update bitboards: it is the last cycle
88 /// CheckInfo constructor
90 CheckInfo::CheckInfo(const Position& pos) {
92 Color them = ~pos.side_to_move();
93 ksq = pos.square<KING>(them);
95 pinned = pos.pinned_pieces(pos.side_to_move());
96 dcCandidates = pos.discovered_check_candidates();
98 checkSquares[PAWN] = pos.attacks_from<PAWN>(ksq, them);
99 checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
100 checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);
101 checkSquares[ROOK] = pos.attacks_from<ROOK>(ksq);
102 checkSquares[QUEEN] = checkSquares[BISHOP] | checkSquares[ROOK];
103 checkSquares[KING] = 0;
107 /// operator<<(Position) returns an ASCII representation of the position
109 std::ostream& operator<<(std::ostream& os, const Position& pos) {
111 os << "\n +---+---+---+---+---+---+---+---+\n";
113 for (Rank r = RANK_8; r >= RANK_1; --r)
115 for (File f = FILE_A; f <= FILE_H; ++f)
116 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
118 os << " |\n +---+---+---+---+---+---+---+---+\n";
121 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
122 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
124 for (Bitboard b = pos.checkers(); b; )
125 os << UCI::square(pop_lsb(&b)) << " ";
131 /// Position::init() initializes at startup the various arrays used to compute
134 void Position::init() {
138 for (Color c = WHITE; c <= BLACK; ++c)
139 for (PieceType pt = PAWN; pt <= KING; ++pt)
140 for (Square s = SQ_A1; s <= SQ_H8; ++s)
141 Zobrist::psq[c][pt][s] = rng.rand<Key>();
143 for (File f = FILE_A; f <= FILE_H; ++f)
144 Zobrist::enpassant[f] = rng.rand<Key>();
146 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
148 Zobrist::castling[cr] = 0;
152 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
153 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
157 Zobrist::side = rng.rand<Key>();
158 Zobrist::exclusion = rng.rand<Key>();
162 /// Position::operator=() creates a copy of 'pos' but detaching the state pointer
163 /// from the source to be self-consistent and not depending on any external data.
165 Position& Position::operator=(const Position& pos) {
167 std::memcpy(this, &pos, sizeof(Position));
168 std::memcpy(&startState, st, sizeof(StateInfo));
178 /// Position::clear() erases the position object to a pristine state, with an
179 /// empty board, white to move, and no castling rights.
181 void Position::clear() {
183 std::memset(this, 0, sizeof(Position));
184 startState.epSquare = SQ_NONE;
187 for (int i = 0; i < PIECE_TYPE_NB; ++i)
188 for (int j = 0; j < 16; ++j)
189 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
193 /// Position::set() initializes the position object with the given FEN string.
194 /// This function is not very robust - make sure that input FENs are correct,
195 /// this is assumed to be the responsibility of the GUI.
197 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
199 A FEN string defines a particular position using only the ASCII character set.
201 A FEN string contains six fields separated by a space. The fields are:
203 1) Piece placement (from white's perspective). Each rank is described, starting
204 with rank 8 and ending with rank 1. Within each rank, the contents of each
205 square are described from file A through file H. Following the Standard
206 Algebraic Notation (SAN), each piece is identified by a single letter taken
207 from the standard English names. White pieces are designated using upper-case
208 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
209 noted using digits 1 through 8 (the number of blank squares), and "/"
212 2) Active color. "w" means white moves next, "b" means black.
214 3) Castling availability. If neither side can castle, this is "-". Otherwise,
215 this has one or more letters: "K" (White can castle kingside), "Q" (White
216 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
217 can castle queenside).
219 4) En passant target square (in algebraic notation). If there's no en passant
220 target square, this is "-". If a pawn has just made a 2-square move, this
221 is the position "behind" the pawn. This is recorded regardless of whether
222 there is a pawn in position to make an en passant capture.
224 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
225 or capture. This is used to determine if a draw can be claimed under the
228 6) Fullmove number. The number of the full move. It starts at 1, and is
229 incremented after Black's move.
232 unsigned char col, row, token;
235 std::istringstream ss(fenStr);
240 // 1. Piece placement
241 while ((ss >> token) && !isspace(token))
244 sq += Square(token - '0'); // Advance the given number of files
246 else if (token == '/')
249 else if ((idx = PieceToChar.find(token)) != string::npos)
251 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
258 sideToMove = (token == 'w' ? WHITE : BLACK);
261 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
262 // Shredder-FEN that uses the letters of the columns on which the rooks began
263 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
264 // if an inner rook is associated with the castling right, the castling tag is
265 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
266 while ((ss >> token) && !isspace(token))
269 Color c = islower(token) ? BLACK : WHITE;
270 Piece rook = make_piece(c, ROOK);
272 token = char(toupper(token));
275 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
277 else if (token == 'Q')
278 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
280 else if (token >= 'A' && token <= 'H')
281 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
286 set_castling_right(c, rsq);
289 // 4. En passant square. Ignore if no pawn capture is possible
290 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
291 && ((ss >> row) && (row == '3' || row == '6')))
293 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
295 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
296 st->epSquare = SQ_NONE;
299 // 5-6. Halfmove clock and fullmove number
300 ss >> std::skipws >> st->rule50 >> gamePly;
302 // Convert from fullmove starting from 1 to ply starting from 0,
303 // handle also common incorrect FEN with fullmove = 0.
304 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
306 chess960 = isChess960;
314 /// Position::set_castling_right() is a helper function used to set castling
315 /// rights given the corresponding color and the rook starting square.
317 void Position::set_castling_right(Color c, Square rfrom) {
319 Square kfrom = square<KING>(c);
320 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
321 CastlingRight cr = (c | cs);
323 st->castlingRights |= cr;
324 castlingRightsMask[kfrom] |= cr;
325 castlingRightsMask[rfrom] |= cr;
326 castlingRookSquare[cr] = rfrom;
328 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
329 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
331 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
332 if (s != kfrom && s != rfrom)
333 castlingPath[cr] |= s;
335 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
336 if (s != kfrom && s != rfrom)
337 castlingPath[cr] |= s;
341 /// Position::set_state() computes the hash keys of the position, and other
342 /// data that once computed is updated incrementally as moves are made.
343 /// The function is only used when a new position is set up, and to verify
344 /// the correctness of the StateInfo data when running in debug mode.
346 void Position::set_state(StateInfo* si) const {
348 si->key = si->pawnKey = si->materialKey = 0;
349 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
350 si->psq = SCORE_ZERO;
352 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
354 for (Bitboard b = pieces(); b; )
356 Square s = pop_lsb(&b);
357 Piece pc = piece_on(s);
358 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
359 si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];
362 if (si->epSquare != SQ_NONE)
363 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
365 if (sideToMove == BLACK)
366 si->key ^= Zobrist::side;
368 si->key ^= Zobrist::castling[si->castlingRights];
370 for (Bitboard b = pieces(PAWN); b; )
372 Square s = pop_lsb(&b);
373 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
376 for (Color c = WHITE; c <= BLACK; ++c)
377 for (PieceType pt = PAWN; pt <= KING; ++pt)
378 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
379 si->materialKey ^= Zobrist::psq[c][pt][cnt];
381 for (Color c = WHITE; c <= BLACK; ++c)
382 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
383 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
387 /// Position::fen() returns a FEN representation of the position. In case of
388 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
390 const string Position::fen() const {
393 std::ostringstream ss;
395 for (Rank r = RANK_8; r >= RANK_1; --r)
397 for (File f = FILE_A; f <= FILE_H; ++f)
399 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
406 ss << PieceToChar[piece_on(make_square(f, r))];
413 ss << (sideToMove == WHITE ? " w " : " b ");
415 if (can_castle(WHITE_OO))
416 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
418 if (can_castle(WHITE_OOO))
419 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
421 if (can_castle(BLACK_OO))
422 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
424 if (can_castle(BLACK_OOO))
425 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
427 if (!can_castle(WHITE) && !can_castle(BLACK))
430 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
431 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
437 /// Position::game_phase() calculates the game phase interpolating total non-pawn
438 /// material between endgame and midgame limits.
440 Phase Position::game_phase() const {
442 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
444 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
446 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
450 /// Position::check_blockers() returns a bitboard of all the pieces with color
451 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
452 /// blocks a check if removing that piece from the board would result in a
453 /// position where the king is in check. A check blocking piece can be either a
454 /// pinned or a discovered check piece, according if its color 'c' is the same
455 /// or the opposite of 'kingColor'.
457 Bitboard Position::check_blockers(Color c, Color kingColor) const {
459 Bitboard b, pinners, result = 0;
460 Square ksq = square<KING>(kingColor);
462 // Pinners are sliders that give check when a pinned piece is removed
463 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
464 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
468 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
470 if (!more_than_one(b))
471 result |= b & pieces(c);
477 /// Position::attackers_to() computes a bitboard of all pieces which attack a
478 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
480 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
482 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
483 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
484 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
485 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
486 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
487 | (attacks_from<KING>(s) & pieces(KING));
491 /// Position::legal() tests whether a pseudo-legal move is legal
493 bool Position::legal(Move m, Bitboard pinned) const {
496 assert(pinned == pinned_pieces(sideToMove));
498 Color us = sideToMove;
499 Square from = from_sq(m);
501 assert(color_of(moved_piece(m)) == us);
502 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
504 // En passant captures are a tricky special case. Because they are rather
505 // uncommon, we do it simply by testing whether the king is attacked after
507 if (type_of(m) == ENPASSANT)
509 Square ksq = square<KING>(us);
510 Square to = to_sq(m);
511 Square capsq = to - pawn_push(us);
512 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
514 assert(to == ep_square());
515 assert(moved_piece(m) == make_piece(us, PAWN));
516 assert(piece_on(capsq) == make_piece(~us, PAWN));
517 assert(piece_on(to) == NO_PIECE);
519 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
520 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
523 // If the moving piece is a king, check whether the destination
524 // square is attacked by the opponent. Castling moves are checked
525 // for legality during move generation.
526 if (type_of(piece_on(from)) == KING)
527 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
529 // A non-king move is legal if and only if it is not pinned or it
530 // is moving along the ray towards or away from the king.
533 || aligned(from, to_sq(m), square<KING>(us));
537 /// Position::pseudo_legal() takes a random move and tests whether the move is
538 /// pseudo legal. It is used to validate moves from TT that can be corrupted
539 /// due to SMP concurrent access or hash position key aliasing.
541 bool Position::pseudo_legal(const Move m) const {
543 Color us = sideToMove;
544 Square from = from_sq(m);
545 Square to = to_sq(m);
546 Piece pc = moved_piece(m);
548 // Use a slower but simpler function for uncommon cases
549 if (type_of(m) != NORMAL)
550 return MoveList<LEGAL>(*this).contains(m);
552 // Is not a promotion, so promotion piece must be empty
553 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
556 // If the 'from' square is not occupied by a piece belonging to the side to
557 // move, the move is obviously not legal.
558 if (pc == NO_PIECE || color_of(pc) != us)
561 // The destination square cannot be occupied by a friendly piece
565 // Handle the special case of a pawn move
566 if (type_of(pc) == PAWN)
568 // We have already handled promotion moves, so destination
569 // cannot be on the 8th/1st rank.
570 if (rank_of(to) == relative_rank(us, RANK_8))
573 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
574 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
575 && !( (from + 2 * pawn_push(us) == to) // Not a double push
576 && (rank_of(from) == relative_rank(us, RANK_2))
578 && empty(to - pawn_push(us))))
581 else if (!(attacks_from(pc, from) & to))
584 // Evasions generator already takes care to avoid some kind of illegal moves
585 // and legal() relies on this. We therefore have to take care that the same
586 // kind of moves are filtered out here.
589 if (type_of(pc) != KING)
591 // Double check? In this case a king move is required
592 if (more_than_one(checkers()))
595 // Our move must be a blocking evasion or a capture of the checking piece
596 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
599 // In case of king moves under check we have to remove king so as to catch
600 // invalid moves like b1a1 when opposite queen is on c1.
601 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
609 /// Position::gives_check() tests whether a pseudo-legal move gives a check
611 bool Position::gives_check(Move m, const CheckInfo& ci) const {
614 assert(ci.dcCandidates == discovered_check_candidates());
615 assert(color_of(moved_piece(m)) == sideToMove);
617 Square from = from_sq(m);
618 Square to = to_sq(m);
620 // Is there a direct check?
621 if (ci.checkSquares[type_of(piece_on(from))] & to)
624 // Is there a discovered check?
626 && (ci.dcCandidates & from)
627 && !aligned(from, to, ci.ksq))
636 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
638 // En passant capture with check? We have already handled the case
639 // of direct checks and ordinary discovered check, so the only case we
640 // need to handle is the unusual case of a discovered check through
641 // the captured pawn.
644 Square capsq = make_square(file_of(to), rank_of(from));
645 Bitboard b = (pieces() ^ from ^ capsq) | to;
647 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
648 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
653 Square rfrom = to; // Castling is encoded as 'King captures the rook'
654 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
655 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
657 return (PseudoAttacks[ROOK][rto] & ci.ksq)
658 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
667 /// Position::do_move() makes a move, and saves all information necessary
668 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
669 /// moves should be filtered out before this function is called.
671 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
674 assert(&newSt != st);
677 Key k = st->key ^ Zobrist::side;
679 // Copy some fields of the old state to our new StateInfo object except the
680 // ones which are going to be recalculated from scratch anyway and then switch
681 // our state pointer to point to the new (ready to be updated) state.
682 std::memcpy(&newSt, st, offsetof(StateInfo, key));
686 // Increment ply counters. In particular, rule50 will be reset to zero later on
687 // in case of a capture or a pawn move.
692 Color us = sideToMove;
694 Square from = from_sq(m);
695 Square to = to_sq(m);
696 PieceType pt = type_of(piece_on(from));
697 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
699 assert(color_of(piece_on(from)) == us);
700 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
701 assert(captured != KING);
703 if (type_of(m) == CASTLING)
708 do_castling<true>(us, from, to, rfrom, rto);
710 captured = NO_PIECE_TYPE;
711 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
712 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
719 // If the captured piece is a pawn, update pawn hash key, otherwise
720 // update non-pawn material.
721 if (captured == PAWN)
723 if (type_of(m) == ENPASSANT)
725 capsq -= pawn_push(us);
728 assert(to == st->epSquare);
729 assert(relative_rank(us, to) == RANK_6);
730 assert(piece_on(to) == NO_PIECE);
731 assert(piece_on(capsq) == make_piece(them, PAWN));
733 board[capsq] = NO_PIECE; // Not done by remove_piece()
736 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
739 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
741 // Update board and piece lists
742 remove_piece(them, captured, capsq);
744 // Update material hash key and prefetch access to materialTable
745 k ^= Zobrist::psq[them][captured][capsq];
746 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
747 prefetch(thisThread->materialTable[st->materialKey]);
749 // Update incremental scores
750 st->psq -= PSQT::psq[them][captured][capsq];
752 // Reset rule 50 counter
757 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
759 // Reset en passant square
760 if (st->epSquare != SQ_NONE)
762 k ^= Zobrist::enpassant[file_of(st->epSquare)];
763 st->epSquare = SQ_NONE;
766 // Update castling rights if needed
767 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
769 int cr = castlingRightsMask[from] | castlingRightsMask[to];
770 k ^= Zobrist::castling[st->castlingRights & cr];
771 st->castlingRights &= ~cr;
774 // Move the piece. The tricky Chess960 castling is handled earlier
775 if (type_of(m) != CASTLING)
776 move_piece(us, pt, from, to);
778 // If the moving piece is a pawn do some special extra work
781 // Set en-passant square if the moved pawn can be captured
782 if ( (int(to) ^ int(from)) == 16
783 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
785 st->epSquare = (from + to) / 2;
786 k ^= Zobrist::enpassant[file_of(st->epSquare)];
789 else if (type_of(m) == PROMOTION)
791 PieceType promotion = promotion_type(m);
793 assert(relative_rank(us, to) == RANK_8);
794 assert(promotion >= KNIGHT && promotion <= QUEEN);
796 remove_piece(us, PAWN, to);
797 put_piece(us, promotion, to);
800 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
801 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
802 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
803 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
805 // Update incremental score
806 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
809 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
812 // Update pawn hash key and prefetch access to pawnsTable
813 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
814 prefetch(thisThread->pawnsTable[st->pawnKey]);
816 // Reset rule 50 draw counter
820 // Update incremental scores
821 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
824 st->capturedType = captured;
826 // Update the key with the final value
829 // Calculate checkers bitboard (if move gives check)
830 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
832 sideToMove = ~sideToMove;
838 /// Position::undo_move() unmakes a move. When it returns, the position should
839 /// be restored to exactly the same state as before the move was made.
841 void Position::undo_move(Move m) {
845 sideToMove = ~sideToMove;
847 Color us = sideToMove;
848 Square from = from_sq(m);
849 Square to = to_sq(m);
850 PieceType pt = type_of(piece_on(to));
852 assert(empty(from) || type_of(m) == CASTLING);
853 assert(st->capturedType != KING);
855 if (type_of(m) == PROMOTION)
857 assert(relative_rank(us, to) == RANK_8);
858 assert(pt == promotion_type(m));
859 assert(pt >= KNIGHT && pt <= QUEEN);
861 remove_piece(us, pt, to);
862 put_piece(us, PAWN, to);
866 if (type_of(m) == CASTLING)
869 do_castling<false>(us, from, to, rfrom, rto);
873 move_piece(us, pt, to, from); // Put the piece back at the source square
875 if (st->capturedType)
879 if (type_of(m) == ENPASSANT)
881 capsq -= pawn_push(us);
884 assert(to == st->previous->epSquare);
885 assert(relative_rank(us, to) == RANK_6);
886 assert(piece_on(capsq) == NO_PIECE);
887 assert(st->capturedType == PAWN);
890 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
894 // Finally point our state pointer back to the previous state
902 /// Position::do_castling() is a helper used to do/undo a castling move. This
903 /// is a bit tricky, especially in Chess960.
905 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
907 bool kingSide = to > from;
908 rfrom = to; // Castling is encoded as "king captures friendly rook"
909 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
910 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
912 // Remove both pieces first since squares could overlap in Chess960
913 remove_piece(us, KING, Do ? from : to);
914 remove_piece(us, ROOK, Do ? rfrom : rto);
915 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
916 put_piece(us, KING, Do ? to : from);
917 put_piece(us, ROOK, Do ? rto : rfrom);
921 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
922 /// the side to move without executing any move on the board.
924 void Position::do_null_move(StateInfo& newSt) {
927 assert(&newSt != st);
929 std::memcpy(&newSt, st, sizeof(StateInfo));
933 if (st->epSquare != SQ_NONE)
935 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
936 st->epSquare = SQ_NONE;
939 st->key ^= Zobrist::side;
940 prefetch(TT.first_entry(st->key));
943 st->pliesFromNull = 0;
945 sideToMove = ~sideToMove;
950 void Position::undo_null_move() {
955 sideToMove = ~sideToMove;
959 /// Position::key_after() computes the new hash key after the given move. Needed
960 /// for speculative prefetch. It doesn't recognize special moves like castling,
961 /// en-passant and promotions.
963 Key Position::key_after(Move m) const {
965 Color us = sideToMove;
966 Square from = from_sq(m);
967 Square to = to_sq(m);
968 PieceType pt = type_of(piece_on(from));
969 PieceType captured = type_of(piece_on(to));
970 Key k = st->key ^ Zobrist::side;
973 k ^= Zobrist::psq[~us][captured][to];
975 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
979 /// Position::see() is a static exchange evaluator: It tries to estimate the
980 /// material gain or loss resulting from a move.
982 Value Position::see_sign(Move m) const {
986 // Early return if SEE cannot be negative because captured piece value
987 // is not less then capturing one. Note that king moves always return
988 // here because king midgame value is set to 0.
989 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
990 return VALUE_KNOWN_WIN;
995 Value Position::see(Move m) const {
998 Bitboard occupied, attackers, stmAttackers;
1008 swapList[0] = PieceValue[MG][piece_on(to)];
1009 stm = color_of(piece_on(from));
1010 occupied = pieces() ^ from;
1012 // Castling moves are implemented as king capturing the rook so cannot
1013 // be handled correctly. Simply return VALUE_ZERO that is always correct
1014 // unless in the rare case the rook ends up under attack.
1015 if (type_of(m) == CASTLING)
1018 if (type_of(m) == ENPASSANT)
1020 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1021 swapList[0] = PieceValue[MG][PAWN];
1024 // Find all attackers to the destination square, with the moving piece
1025 // removed, but possibly an X-ray attacker added behind it.
1026 attackers = attackers_to(to, occupied) & occupied;
1028 // If the opponent has no attackers we are finished
1030 stmAttackers = attackers & pieces(stm);
1034 // The destination square is defended, which makes things rather more
1035 // difficult to compute. We proceed by building up a "swap list" containing
1036 // the material gain or loss at each stop in a sequence of captures to the
1037 // destination square, where the sides alternately capture, and always
1038 // capture with the least valuable piece. After each capture, we look for
1039 // new X-ray attacks from behind the capturing piece.
1040 captured = type_of(piece_on(from));
1043 assert(slIndex < 32);
1045 // Add the new entry to the swap list
1046 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1048 // Locate and remove the next least valuable attacker
1049 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1051 stmAttackers = attackers & pieces(stm);
1054 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1056 // Having built the swap list, we negamax through it to find the best
1057 // achievable score from the point of view of the side to move.
1059 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1065 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1066 /// or by repetition. It does not detect stalemates.
1068 bool Position::is_draw() const {
1070 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1073 StateInfo* stp = st;
1074 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1076 stp = stp->previous->previous;
1078 if (stp->key == st->key)
1079 return true; // Draw at first repetition
1086 /// Position::flip() flips position with the white and black sides reversed. This
1087 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1089 void Position::flip() {
1092 std::stringstream ss(fen());
1094 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1096 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1097 f.insert(0, token + (f.empty() ? " " : "/"));
1100 ss >> token; // Active color
1101 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1103 ss >> token; // Castling availability
1106 std::transform(f.begin(), f.end(), f.begin(),
1107 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1109 ss >> token; // En passant square
1110 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1112 std::getline(ss, token); // Half and full moves
1115 set(f, is_chess960(), this_thread());
1117 assert(pos_is_ok());
1121 /// Position::pos_is_ok() performs some consistency checks for the position object.
1122 /// This is meant to be helpful when debugging.
1124 bool Position::pos_is_ok(int* failedStep) const {
1126 const bool Fast = true; // Quick (default) or full check?
1128 enum { Default, King, Bitboards, State, Lists, Castling };
1130 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1135 if (step == Default)
1136 if ( (sideToMove != WHITE && sideToMove != BLACK)
1137 || piece_on(square<KING>(WHITE)) != W_KING
1138 || piece_on(square<KING>(BLACK)) != B_KING
1139 || ( ep_square() != SQ_NONE
1140 && relative_rank(sideToMove, ep_square()) != RANK_6))
1144 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1145 || std::count(board, board + SQUARE_NB, B_KING) != 1
1146 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1149 if (step == Bitboards)
1151 if ( (pieces(WHITE) & pieces(BLACK))
1152 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1155 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1156 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1157 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1165 if (std::memcmp(&si, st, sizeof(StateInfo)))
1170 for (Color c = WHITE; c <= BLACK; ++c)
1171 for (PieceType pt = PAWN; pt <= KING; ++pt)
1173 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1176 for (int i = 0; i < pieceCount[c][pt]; ++i)
1177 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1178 || index[pieceList[c][pt][i]] != i)
1182 if (step == Castling)
1183 for (Color c = WHITE; c <= BLACK; ++c)
1184 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1186 if (!can_castle(c | s))
1189 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1190 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1191 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))