2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
7 Stockfish is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 #include <cstring> // For std::memset, std::memcmp
39 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
46 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
50 const string PieceToChar(" PNBRQK pnbrqk");
52 // min_attacker() is a helper function used by see() to locate the least
53 // valuable attacker for the side to move, remove the attacker we just found
54 // from the bitboards and scan for new X-ray attacks behind it.
57 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
58 Bitboard& occupied, Bitboard& attackers) {
60 Bitboard b = stmAttackers & bb[Pt];
62 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
64 occupied ^= b & ~(b - 1);
66 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
67 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
69 if (Pt == ROOK || Pt == QUEEN)
70 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
72 attackers &= occupied; // After X-ray that may add already processed pieces
77 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
78 return KING; // No need to update bitboards: it is the last cycle
84 /// CheckInfo constructor
86 CheckInfo::CheckInfo(const Position& pos) {
88 Color them = ~pos.side_to_move();
89 ksq = pos.square<KING>(them);
91 pinned = pos.pinned_pieces(pos.side_to_move());
92 dcCandidates = pos.discovered_check_candidates();
94 checkSquares[PAWN] = pos.attacks_from<PAWN>(ksq, them);
95 checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
96 checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);
97 checkSquares[ROOK] = pos.attacks_from<ROOK>(ksq);
98 checkSquares[QUEEN] = checkSquares[BISHOP] | checkSquares[ROOK];
99 checkSquares[KING] = 0;
103 /// operator<<(Position) returns an ASCII representation of the position
105 std::ostream& operator<<(std::ostream& os, const Position& pos) {
107 os << "\n +---+---+---+---+---+---+---+---+\n";
109 for (Rank r = RANK_8; r >= RANK_1; --r)
111 for (File f = FILE_A; f <= FILE_H; ++f)
112 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
114 os << " |\n +---+---+---+---+---+---+---+---+\n";
117 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
118 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
120 for (Bitboard b = pos.checkers(); b; )
121 os << UCI::square(pop_lsb(&b)) << " ";
127 /// Position::init() initializes at startup the various arrays used to compute
130 void Position::init() {
134 for (Color c = WHITE; c <= BLACK; ++c)
135 for (PieceType pt = PAWN; pt <= KING; ++pt)
136 for (Square s = SQ_A1; s <= SQ_H8; ++s)
137 Zobrist::psq[c][pt][s] = rng.rand<Key>();
139 for (File f = FILE_A; f <= FILE_H; ++f)
140 Zobrist::enpassant[f] = rng.rand<Key>();
142 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
144 Zobrist::castling[cr] = 0;
148 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
149 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
153 Zobrist::side = rng.rand<Key>();
154 Zobrist::exclusion = rng.rand<Key>();
158 /// Position::operator=() creates a copy of 'pos' but detaching the state pointer
159 /// from the source to be self-consistent and not depending on any external data.
161 Position& Position::operator=(const Position& pos) {
163 std::memcpy(this, &pos, sizeof(Position));
164 std::memcpy(&startState, st, sizeof(StateInfo));
174 /// Position::clear() erases the position object to a pristine state, with an
175 /// empty board, white to move, and no castling rights.
177 void Position::clear() {
179 std::memset(this, 0, sizeof(Position));
180 startState.epSquare = SQ_NONE;
183 for (int i = 0; i < PIECE_TYPE_NB; ++i)
184 for (int j = 0; j < 16; ++j)
185 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
189 /// Position::set() initializes the position object with the given FEN string.
190 /// This function is not very robust - make sure that input FENs are correct,
191 /// this is assumed to be the responsibility of the GUI.
193 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
195 A FEN string defines a particular position using only the ASCII character set.
197 A FEN string contains six fields separated by a space. The fields are:
199 1) Piece placement (from white's perspective). Each rank is described, starting
200 with rank 8 and ending with rank 1. Within each rank, the contents of each
201 square are described from file A through file H. Following the Standard
202 Algebraic Notation (SAN), each piece is identified by a single letter taken
203 from the standard English names. White pieces are designated using upper-case
204 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
205 noted using digits 1 through 8 (the number of blank squares), and "/"
208 2) Active color. "w" means white moves next, "b" means black.
210 3) Castling availability. If neither side can castle, this is "-". Otherwise,
211 this has one or more letters: "K" (White can castle kingside), "Q" (White
212 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
213 can castle queenside).
215 4) En passant target square (in algebraic notation). If there's no en passant
216 target square, this is "-". If a pawn has just made a 2-square move, this
217 is the position "behind" the pawn. This is recorded regardless of whether
218 there is a pawn in position to make an en passant capture.
220 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
221 or capture. This is used to determine if a draw can be claimed under the
224 6) Fullmove number. The number of the full move. It starts at 1, and is
225 incremented after Black's move.
228 unsigned char col, row, token;
231 std::istringstream ss(fenStr);
236 // 1. Piece placement
237 while ((ss >> token) && !isspace(token))
240 sq += Square(token - '0'); // Advance the given number of files
242 else if (token == '/')
245 else if ((idx = PieceToChar.find(token)) != string::npos)
247 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
254 sideToMove = (token == 'w' ? WHITE : BLACK);
257 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
258 // Shredder-FEN that uses the letters of the columns on which the rooks began
259 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
260 // if an inner rook is associated with the castling right, the castling tag is
261 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
262 while ((ss >> token) && !isspace(token))
265 Color c = islower(token) ? BLACK : WHITE;
266 Piece rook = make_piece(c, ROOK);
268 token = char(toupper(token));
271 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
273 else if (token == 'Q')
274 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
276 else if (token >= 'A' && token <= 'H')
277 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
282 set_castling_right(c, rsq);
285 // 4. En passant square. Ignore if no pawn capture is possible
286 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
287 && ((ss >> row) && (row == '3' || row == '6')))
289 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
291 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
292 st->epSquare = SQ_NONE;
295 // 5-6. Halfmove clock and fullmove number
296 ss >> std::skipws >> st->rule50 >> gamePly;
298 // Convert from fullmove starting from 1 to ply starting from 0,
299 // handle also common incorrect FEN with fullmove = 0.
300 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
302 chess960 = isChess960;
310 /// Position::set_castling_right() is a helper function used to set castling
311 /// rights given the corresponding color and the rook starting square.
313 void Position::set_castling_right(Color c, Square rfrom) {
315 Square kfrom = square<KING>(c);
316 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
317 CastlingRight cr = (c | cs);
319 st->castlingRights |= cr;
320 castlingRightsMask[kfrom] |= cr;
321 castlingRightsMask[rfrom] |= cr;
322 castlingRookSquare[cr] = rfrom;
324 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
325 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
327 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
328 if (s != kfrom && s != rfrom)
329 castlingPath[cr] |= s;
331 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
332 if (s != kfrom && s != rfrom)
333 castlingPath[cr] |= s;
337 /// Position::set_state() computes the hash keys of the position, and other
338 /// data that once computed is updated incrementally as moves are made.
339 /// The function is only used when a new position is set up, and to verify
340 /// the correctness of the StateInfo data when running in debug mode.
342 void Position::set_state(StateInfo* si) const {
344 si->key = si->pawnKey = si->materialKey = 0;
345 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
346 si->psq = SCORE_ZERO;
348 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
350 for (Bitboard b = pieces(); b; )
352 Square s = pop_lsb(&b);
353 Piece pc = piece_on(s);
354 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
355 si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];
358 if (si->epSquare != SQ_NONE)
359 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
361 if (sideToMove == BLACK)
362 si->key ^= Zobrist::side;
364 si->key ^= Zobrist::castling[si->castlingRights];
366 for (Bitboard b = pieces(PAWN); b; )
368 Square s = pop_lsb(&b);
369 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
372 for (Color c = WHITE; c <= BLACK; ++c)
373 for (PieceType pt = PAWN; pt <= KING; ++pt)
374 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
375 si->materialKey ^= Zobrist::psq[c][pt][cnt];
377 for (Color c = WHITE; c <= BLACK; ++c)
378 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
379 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
383 /// Position::fen() returns a FEN representation of the position. In case of
384 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
386 const string Position::fen() const {
389 std::ostringstream ss;
391 for (Rank r = RANK_8; r >= RANK_1; --r)
393 for (File f = FILE_A; f <= FILE_H; ++f)
395 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
402 ss << PieceToChar[piece_on(make_square(f, r))];
409 ss << (sideToMove == WHITE ? " w " : " b ");
411 if (can_castle(WHITE_OO))
412 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
414 if (can_castle(WHITE_OOO))
415 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
417 if (can_castle(BLACK_OO))
418 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
420 if (can_castle(BLACK_OOO))
421 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
423 if (!can_castle(WHITE) && !can_castle(BLACK))
426 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
427 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
433 /// Position::game_phase() calculates the game phase interpolating total non-pawn
434 /// material between endgame and midgame limits.
436 Phase Position::game_phase() const {
438 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
440 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
442 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
446 /// Position::check_blockers() returns a bitboard of all the pieces with color
447 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
448 /// blocks a check if removing that piece from the board would result in a
449 /// position where the king is in check. A check blocking piece can be either a
450 /// pinned or a discovered check piece, according if its color 'c' is the same
451 /// or the opposite of 'kingColor'.
453 Bitboard Position::check_blockers(Color c, Color kingColor) const {
455 Bitboard b, pinners, result = 0;
456 Square ksq = square<KING>(kingColor);
458 // Pinners are sliders that give check when a pinned piece is removed
459 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
460 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
464 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
466 if (!more_than_one(b))
467 result |= b & pieces(c);
473 /// Position::attackers_to() computes a bitboard of all pieces which attack a
474 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
476 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
478 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
479 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
480 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
481 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
482 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
483 | (attacks_from<KING>(s) & pieces(KING));
487 /// Position::legal() tests whether a pseudo-legal move is legal
489 bool Position::legal(Move m, Bitboard pinned) const {
492 assert(pinned == pinned_pieces(sideToMove));
494 Color us = sideToMove;
495 Square from = from_sq(m);
497 assert(color_of(moved_piece(m)) == us);
498 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
500 // En passant captures are a tricky special case. Because they are rather
501 // uncommon, we do it simply by testing whether the king is attacked after
503 if (type_of(m) == ENPASSANT)
505 Square ksq = square<KING>(us);
506 Square to = to_sq(m);
507 Square capsq = to - pawn_push(us);
508 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
510 assert(to == ep_square());
511 assert(moved_piece(m) == make_piece(us, PAWN));
512 assert(piece_on(capsq) == make_piece(~us, PAWN));
513 assert(piece_on(to) == NO_PIECE);
515 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
516 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
519 // If the moving piece is a king, check whether the destination
520 // square is attacked by the opponent. Castling moves are checked
521 // for legality during move generation.
522 if (type_of(piece_on(from)) == KING)
523 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
525 // A non-king move is legal if and only if it is not pinned or it
526 // is moving along the ray towards or away from the king.
529 || aligned(from, to_sq(m), square<KING>(us));
533 /// Position::pseudo_legal() takes a random move and tests whether the move is
534 /// pseudo legal. It is used to validate moves from TT that can be corrupted
535 /// due to SMP concurrent access or hash position key aliasing.
537 bool Position::pseudo_legal(const Move m) const {
539 Color us = sideToMove;
540 Square from = from_sq(m);
541 Square to = to_sq(m);
542 Piece pc = moved_piece(m);
544 // Use a slower but simpler function for uncommon cases
545 if (type_of(m) != NORMAL)
546 return MoveList<LEGAL>(*this).contains(m);
548 // Is not a promotion, so promotion piece must be empty
549 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
552 // If the 'from' square is not occupied by a piece belonging to the side to
553 // move, the move is obviously not legal.
554 if (pc == NO_PIECE || color_of(pc) != us)
557 // The destination square cannot be occupied by a friendly piece
561 // Handle the special case of a pawn move
562 if (type_of(pc) == PAWN)
564 // We have already handled promotion moves, so destination
565 // cannot be on the 8th/1st rank.
566 if (rank_of(to) == relative_rank(us, RANK_8))
569 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
570 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
571 && !( (from + 2 * pawn_push(us) == to) // Not a double push
572 && (rank_of(from) == relative_rank(us, RANK_2))
574 && empty(to - pawn_push(us))))
577 else if (!(attacks_from(pc, from) & to))
580 // Evasions generator already takes care to avoid some kind of illegal moves
581 // and legal() relies on this. We therefore have to take care that the same
582 // kind of moves are filtered out here.
585 if (type_of(pc) != KING)
587 // Double check? In this case a king move is required
588 if (more_than_one(checkers()))
591 // Our move must be a blocking evasion or a capture of the checking piece
592 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
595 // In case of king moves under check we have to remove king so as to catch
596 // invalid moves like b1a1 when opposite queen is on c1.
597 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
605 /// Position::gives_check() tests whether a pseudo-legal move gives a check
607 bool Position::gives_check(Move m, const CheckInfo& ci) const {
610 assert(ci.dcCandidates == discovered_check_candidates());
611 assert(color_of(moved_piece(m)) == sideToMove);
613 Square from = from_sq(m);
614 Square to = to_sq(m);
616 // Is there a direct check?
617 if (ci.checkSquares[type_of(piece_on(from))] & to)
620 // Is there a discovered check?
622 && (ci.dcCandidates & from)
623 && !aligned(from, to, ci.ksq))
632 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
634 // En passant capture with check? We have already handled the case
635 // of direct checks and ordinary discovered check, so the only case we
636 // need to handle is the unusual case of a discovered check through
637 // the captured pawn.
640 Square capsq = make_square(file_of(to), rank_of(from));
641 Bitboard b = (pieces() ^ from ^ capsq) | to;
643 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
644 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
649 Square rfrom = to; // Castling is encoded as 'King captures the rook'
650 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
651 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
653 return (PseudoAttacks[ROOK][rto] & ci.ksq)
654 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
663 /// Position::do_move() makes a move, and saves all information necessary
664 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
665 /// moves should be filtered out before this function is called.
667 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
670 assert(&newSt != st);
673 Key k = st->key ^ Zobrist::side;
675 // Copy some fields of the old state to our new StateInfo object except the
676 // ones which are going to be recalculated from scratch anyway and then switch
677 // our state pointer to point to the new (ready to be updated) state.
678 std::memcpy(&newSt, st, offsetof(StateInfo, key));
682 // Increment ply counters. In particular, rule50 will be reset to zero later on
683 // in case of a capture or a pawn move.
688 Color us = sideToMove;
690 Square from = from_sq(m);
691 Square to = to_sq(m);
692 PieceType pt = type_of(piece_on(from));
693 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
695 assert(color_of(piece_on(from)) == us);
696 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
697 assert(captured != KING);
699 if (type_of(m) == CASTLING)
704 do_castling<true>(us, from, to, rfrom, rto);
706 captured = NO_PIECE_TYPE;
707 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
708 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
715 // If the captured piece is a pawn, update pawn hash key, otherwise
716 // update non-pawn material.
717 if (captured == PAWN)
719 if (type_of(m) == ENPASSANT)
721 capsq -= pawn_push(us);
724 assert(to == st->epSquare);
725 assert(relative_rank(us, to) == RANK_6);
726 assert(piece_on(to) == NO_PIECE);
727 assert(piece_on(capsq) == make_piece(them, PAWN));
729 board[capsq] = NO_PIECE; // Not done by remove_piece()
732 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
735 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
737 // Update board and piece lists
738 remove_piece(them, captured, capsq);
740 // Update material hash key and prefetch access to materialTable
741 k ^= Zobrist::psq[them][captured][capsq];
742 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
743 prefetch(thisThread->materialTable[st->materialKey]);
745 // Update incremental scores
746 st->psq -= PSQT::psq[them][captured][capsq];
748 // Reset rule 50 counter
753 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
755 // Reset en passant square
756 if (st->epSquare != SQ_NONE)
758 k ^= Zobrist::enpassant[file_of(st->epSquare)];
759 st->epSquare = SQ_NONE;
762 // Update castling rights if needed
763 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
765 int cr = castlingRightsMask[from] | castlingRightsMask[to];
766 k ^= Zobrist::castling[st->castlingRights & cr];
767 st->castlingRights &= ~cr;
770 // Move the piece. The tricky Chess960 castling is handled earlier
771 if (type_of(m) != CASTLING)
772 move_piece(us, pt, from, to);
774 // If the moving piece is a pawn do some special extra work
777 // Set en-passant square if the moved pawn can be captured
778 if ( (int(to) ^ int(from)) == 16
779 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
781 st->epSquare = (from + to) / 2;
782 k ^= Zobrist::enpassant[file_of(st->epSquare)];
785 else if (type_of(m) == PROMOTION)
787 PieceType promotion = promotion_type(m);
789 assert(relative_rank(us, to) == RANK_8);
790 assert(promotion >= KNIGHT && promotion <= QUEEN);
792 remove_piece(us, PAWN, to);
793 put_piece(us, promotion, to);
796 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
797 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
798 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
799 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
801 // Update incremental score
802 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
805 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
808 // Update pawn hash key and prefetch access to pawnsTable
809 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
810 prefetch(thisThread->pawnsTable[st->pawnKey]);
812 // Reset rule 50 draw counter
816 // Update incremental scores
817 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
820 st->capturedType = captured;
822 // Update the key with the final value
825 // Calculate checkers bitboard (if move gives check)
826 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
828 sideToMove = ~sideToMove;
834 /// Position::undo_move() unmakes a move. When it returns, the position should
835 /// be restored to exactly the same state as before the move was made.
837 void Position::undo_move(Move m) {
841 sideToMove = ~sideToMove;
843 Color us = sideToMove;
844 Square from = from_sq(m);
845 Square to = to_sq(m);
846 PieceType pt = type_of(piece_on(to));
848 assert(empty(from) || type_of(m) == CASTLING);
849 assert(st->capturedType != KING);
851 if (type_of(m) == PROMOTION)
853 assert(relative_rank(us, to) == RANK_8);
854 assert(pt == promotion_type(m));
855 assert(pt >= KNIGHT && pt <= QUEEN);
857 remove_piece(us, pt, to);
858 put_piece(us, PAWN, to);
862 if (type_of(m) == CASTLING)
865 do_castling<false>(us, from, to, rfrom, rto);
869 move_piece(us, pt, to, from); // Put the piece back at the source square
871 if (st->capturedType)
875 if (type_of(m) == ENPASSANT)
877 capsq -= pawn_push(us);
880 assert(to == st->previous->epSquare);
881 assert(relative_rank(us, to) == RANK_6);
882 assert(piece_on(capsq) == NO_PIECE);
883 assert(st->capturedType == PAWN);
886 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
890 // Finally point our state pointer back to the previous state
898 /// Position::do_castling() is a helper used to do/undo a castling move. This
899 /// is a bit tricky, especially in Chess960.
901 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
903 bool kingSide = to > from;
904 rfrom = to; // Castling is encoded as "king captures friendly rook"
905 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
906 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
908 // Remove both pieces first since squares could overlap in Chess960
909 remove_piece(us, KING, Do ? from : to);
910 remove_piece(us, ROOK, Do ? rfrom : rto);
911 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
912 put_piece(us, KING, Do ? to : from);
913 put_piece(us, ROOK, Do ? rto : rfrom);
917 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
918 /// the side to move without executing any move on the board.
920 void Position::do_null_move(StateInfo& newSt) {
923 assert(&newSt != st);
925 std::memcpy(&newSt, st, sizeof(StateInfo));
929 if (st->epSquare != SQ_NONE)
931 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
932 st->epSquare = SQ_NONE;
935 st->key ^= Zobrist::side;
936 prefetch(TT.first_entry(st->key));
939 st->pliesFromNull = 0;
941 sideToMove = ~sideToMove;
946 void Position::undo_null_move() {
951 sideToMove = ~sideToMove;
955 /// Position::key_after() computes the new hash key after the given move. Needed
956 /// for speculative prefetch. It doesn't recognize special moves like castling,
957 /// en-passant and promotions.
959 Key Position::key_after(Move m) const {
961 Color us = sideToMove;
962 Square from = from_sq(m);
963 Square to = to_sq(m);
964 PieceType pt = type_of(piece_on(from));
965 PieceType captured = type_of(piece_on(to));
966 Key k = st->key ^ Zobrist::side;
969 k ^= Zobrist::psq[~us][captured][to];
971 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
975 /// Position::see() is a static exchange evaluator: It tries to estimate the
976 /// material gain or loss resulting from a move.
978 Value Position::see_sign(Move m) const {
982 // Early return if SEE cannot be negative because captured piece value
983 // is not less then capturing one. Note that king moves always return
984 // here because king midgame value is set to 0.
985 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
986 return VALUE_KNOWN_WIN;
991 Value Position::see(Move m) const {
994 Bitboard occupied, attackers, stmAttackers;
1004 swapList[0] = PieceValue[MG][piece_on(to)];
1005 stm = color_of(piece_on(from));
1006 occupied = pieces() ^ from;
1008 // Castling moves are implemented as king capturing the rook so cannot
1009 // be handled correctly. Simply return VALUE_ZERO that is always correct
1010 // unless in the rare case the rook ends up under attack.
1011 if (type_of(m) == CASTLING)
1014 if (type_of(m) == ENPASSANT)
1016 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1017 swapList[0] = PieceValue[MG][PAWN];
1020 // Find all attackers to the destination square, with the moving piece
1021 // removed, but possibly an X-ray attacker added behind it.
1022 attackers = attackers_to(to, occupied) & occupied;
1024 // If the opponent has no attackers we are finished
1026 stmAttackers = attackers & pieces(stm);
1030 // The destination square is defended, which makes things rather more
1031 // difficult to compute. We proceed by building up a "swap list" containing
1032 // the material gain or loss at each stop in a sequence of captures to the
1033 // destination square, where the sides alternately capture, and always
1034 // capture with the least valuable piece. After each capture, we look for
1035 // new X-ray attacks from behind the capturing piece.
1036 captured = type_of(piece_on(from));
1039 assert(slIndex < 32);
1041 // Add the new entry to the swap list
1042 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1044 // Locate and remove the next least valuable attacker
1045 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1047 stmAttackers = attackers & pieces(stm);
1050 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1052 // Having built the swap list, we negamax through it to find the best
1053 // achievable score from the point of view of the side to move.
1055 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1061 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1062 /// or by repetition. It does not detect stalemates.
1064 bool Position::is_draw() const {
1066 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1069 StateInfo* stp = st;
1070 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1072 stp = stp->previous->previous;
1074 if (stp->key == st->key)
1075 return true; // Draw at first repetition
1082 /// Position::flip() flips position with the white and black sides reversed. This
1083 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1085 void Position::flip() {
1088 std::stringstream ss(fen());
1090 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1092 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1093 f.insert(0, token + (f.empty() ? " " : "/"));
1096 ss >> token; // Active color
1097 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1099 ss >> token; // Castling availability
1102 std::transform(f.begin(), f.end(), f.begin(),
1103 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1105 ss >> token; // En passant square
1106 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1108 std::getline(ss, token); // Half and full moves
1111 set(f, is_chess960(), this_thread());
1113 assert(pos_is_ok());
1117 /// Position::pos_is_ok() performs some consistency checks for the position object.
1118 /// This is meant to be helpful when debugging.
1120 bool Position::pos_is_ok(int* failedStep) const {
1122 const bool Fast = true; // Quick (default) or full check?
1124 enum { Default, King, Bitboards, State, Lists, Castling };
1126 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1131 if (step == Default)
1132 if ( (sideToMove != WHITE && sideToMove != BLACK)
1133 || piece_on(square<KING>(WHITE)) != W_KING
1134 || piece_on(square<KING>(BLACK)) != B_KING
1135 || ( ep_square() != SQ_NONE
1136 && relative_rank(sideToMove, ep_square()) != RANK_6))
1140 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1141 || std::count(board, board + SQUARE_NB, B_KING) != 1
1142 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1145 if (step == Bitboards)
1147 if ( (pieces(WHITE) & pieces(BLACK))
1148 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1151 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1152 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1153 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1161 if (std::memcmp(&si, st, sizeof(StateInfo)))
1166 for (Color c = WHITE; c <= BLACK; ++c)
1167 for (PieceType pt = PAWN; pt <= KING; ++pt)
1169 if (pieceCount[c][pt] != popcount(pieces(c, pt)))
1172 for (int i = 0; i < pieceCount[c][pt]; ++i)
1173 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1174 || index[pieceList[c][pt][i]] != i)
1178 if (step == Castling)
1179 for (Color c = WHITE; c <= BLACK; ++c)
1180 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1182 if (!can_castle(c | s))
1185 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1186 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1187 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))