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
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 #include <cstring> // For std::memset, std::memcmp
36 Value PieceValue[PHASE_NB][PIECE_NB] = {
37 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
38 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
42 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
43 Key enpassant[FILE_NB];
44 Key castling[CASTLING_RIGHT_NB];
49 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
53 const string PieceToChar(" PNBRQK pnbrqk");
55 // min_attacker() is a helper function used by see() to locate the least
56 // valuable attacker for the side to move, remove the attacker we just found
57 // from the bitboards and scan for new X-ray attacks behind it.
60 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
61 Bitboard& occupied, Bitboard& attackers) {
63 Bitboard b = stmAttackers & bb[Pt];
65 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
67 occupied ^= b & ~(b - 1);
69 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
70 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
72 if (Pt == ROOK || Pt == QUEEN)
73 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
75 attackers &= occupied; // After X-ray that may add already processed pieces
80 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
81 return KING; // No need to update bitboards: it is the last cycle
89 CheckInfo::CheckInfo(const Position& pos) {
91 Color them = ~pos.side_to_move();
92 ksq = pos.king_square(them);
94 pinned = pos.pinned_pieces(pos.side_to_move());
95 dcCandidates = pos.discovered_check_candidates();
97 checkSquares[PAWN] = pos.attacks_from<PAWN>(ksq, them);
98 checkSquares[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
99 checkSquares[BISHOP] = pos.attacks_from<BISHOP>(ksq);
100 checkSquares[ROOK] = pos.attacks_from<ROOK>(ksq);
101 checkSquares[QUEEN] = checkSquares[BISHOP] | checkSquares[ROOK];
102 checkSquares[KING] = 0;
106 /// operator<<(Position) returns an ASCII representation of the position
108 std::ostream& operator<<(std::ostream& os, const Position& pos) {
110 os << "\n +---+---+---+---+---+---+---+---+\n";
112 for (Rank r = RANK_8; r >= RANK_1; --r)
114 for (File f = FILE_A; f <= FILE_H; ++f)
115 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
117 os << " |\n +---+---+---+---+---+---+---+---+\n";
120 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
121 << std::setfill('0') << std::setw(16) << pos.st->key << std::dec << "\nCheckers: ";
123 for (Bitboard b = pos.checkers(); b; )
124 os << UCI::square(pop_lsb(&b)) << " ";
130 /// Position::init() initializes at startup the various arrays used to compute
133 void Position::init() {
137 for (Color c = WHITE; c <= BLACK; ++c)
138 for (PieceType pt = PAWN; pt <= KING; ++pt)
139 for (Square s = SQ_A1; s <= SQ_H8; ++s)
140 Zobrist::psq[c][pt][s] = rng.rand<Key>();
142 for (File f = FILE_A; f <= FILE_H; ++f)
143 Zobrist::enpassant[f] = rng.rand<Key>();
145 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
147 Zobrist::castling[cr] = 0;
151 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
152 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
156 Zobrist::side = rng.rand<Key>();
157 Zobrist::exclusion = rng.rand<Key>();
161 /// Position::operator=() creates a copy of 'pos' but detaching the state pointer
162 /// from the source to be self-consistent and not depending on any external data.
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
167 std::memcpy(&startState, st, sizeof(StateInfo));
177 /// Position::clear() erases the position object to a pristine state, with an
178 /// empty board, white to move, and no castling rights.
180 void Position::clear() {
182 std::memset(this, 0, sizeof(Position));
183 startState.epSquare = SQ_NONE;
186 for (int i = 0; i < PIECE_TYPE_NB; ++i)
187 for (int j = 0; j < 16; ++j)
188 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
192 /// Position::set() initializes the position object with the given FEN string.
193 /// This function is not very robust - make sure that input FENs are correct,
194 /// this is assumed to be the responsibility of the GUI.
196 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
198 A FEN string defines a particular position using only the ASCII character set.
200 A FEN string contains six fields separated by a space. The fields are:
202 1) Piece placement (from white's perspective). Each rank is described, starting
203 with rank 8 and ending with rank 1. Within each rank, the contents of each
204 square are described from file A through file H. Following the Standard
205 Algebraic Notation (SAN), each piece is identified by a single letter taken
206 from the standard English names. White pieces are designated using upper-case
207 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
208 noted using digits 1 through 8 (the number of blank squares), and "/"
211 2) Active color. "w" means white moves next, "b" means black.
213 3) Castling availability. If neither side can castle, this is "-". Otherwise,
214 this has one or more letters: "K" (White can castle kingside), "Q" (White
215 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
216 can castle queenside).
218 4) En passant target square (in algebraic notation). If there's no en passant
219 target square, this is "-". If a pawn has just made a 2-square move, this
220 is the position "behind" the pawn. This is recorded regardless of whether
221 there is a pawn in position to make an en passant capture.
223 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
224 or capture. This is used to determine if a draw can be claimed under the
227 6) Fullmove number. The number of the full move. It starts at 1, and is
228 incremented after Black's move.
231 unsigned char col, row, token;
234 std::istringstream ss(fenStr);
239 // 1. Piece placement
240 while ((ss >> token) && !isspace(token))
243 sq += Square(token - '0'); // Advance the given number of files
245 else if (token == '/')
248 else if ((idx = PieceToChar.find(token)) != string::npos)
250 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
257 sideToMove = (token == 'w' ? WHITE : BLACK);
260 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
261 // Shredder-FEN that uses the letters of the columns on which the rooks began
262 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
263 // if an inner rook is associated with the castling right, the castling tag is
264 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
265 while ((ss >> token) && !isspace(token))
268 Color c = islower(token) ? BLACK : WHITE;
269 Piece rook = make_piece(c, ROOK);
271 token = char(toupper(token));
274 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
276 else if (token == 'Q')
277 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
279 else if (token >= 'A' && token <= 'H')
280 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
285 set_castling_right(c, rsq);
288 // 4. En passant square. Ignore if no pawn capture is possible
289 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
290 && ((ss >> row) && (row == '3' || row == '6')))
292 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
294 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
295 st->epSquare = SQ_NONE;
298 // 5-6. Halfmove clock and fullmove number
299 ss >> std::skipws >> st->rule50 >> gamePly;
301 // Convert from fullmove starting from 1 to ply starting from 0,
302 // handle also common incorrect FEN with fullmove = 0.
303 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
305 chess960 = isChess960;
313 /// Position::set_castling_right() is a helper function used to set castling
314 /// rights given the corresponding color and the rook starting square.
316 void Position::set_castling_right(Color c, Square rfrom) {
318 Square kfrom = king_square(c);
319 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
320 CastlingRight cr = (c | cs);
322 st->castlingRights |= cr;
323 castlingRightsMask[kfrom] |= cr;
324 castlingRightsMask[rfrom] |= cr;
325 castlingRookSquare[cr] = rfrom;
327 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
328 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
330 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
331 if (s != kfrom && s != rfrom)
332 castlingPath[cr] |= s;
334 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
335 if (s != kfrom && s != rfrom)
336 castlingPath[cr] |= s;
340 /// Position::set_state() computes the hash keys of the position, and other
341 /// data that once computed is updated incrementally as moves are made.
342 /// The function is only used when a new position is set up, and to verify
343 /// the correctness of the StateInfo data when running in debug mode.
345 void Position::set_state(StateInfo* si) const {
347 si->key = si->pawnKey = si->materialKey = 0;
348 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
349 si->psq = SCORE_ZERO;
351 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
353 for (Bitboard b = pieces(); b; )
355 Square s = pop_lsb(&b);
356 Piece pc = piece_on(s);
357 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
358 si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];
361 if (si->epSquare != SQ_NONE)
362 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
364 if (sideToMove == BLACK)
365 si->key ^= Zobrist::side;
367 si->key ^= Zobrist::castling[si->castlingRights];
369 for (Bitboard b = pieces(PAWN); b; )
371 Square s = pop_lsb(&b);
372 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
375 for (Color c = WHITE; c <= BLACK; ++c)
376 for (PieceType pt = PAWN; pt <= KING; ++pt)
377 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
378 si->materialKey ^= Zobrist::psq[c][pt][cnt];
380 for (Color c = WHITE; c <= BLACK; ++c)
381 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
382 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
386 /// Position::fen() returns a FEN representation of the position. In case of
387 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
389 const string Position::fen() const {
392 std::ostringstream ss;
394 for (Rank r = RANK_8; r >= RANK_1; --r)
396 for (File f = FILE_A; f <= FILE_H; ++f)
398 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
405 ss << PieceToChar[piece_on(make_square(f, r))];
412 ss << (sideToMove == WHITE ? " w " : " b ");
414 if (can_castle(WHITE_OO))
415 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
417 if (can_castle(WHITE_OOO))
418 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
420 if (can_castle(BLACK_OO))
421 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
423 if (can_castle(BLACK_OOO))
424 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
426 if (!can_castle(WHITE) && !can_castle(BLACK))
429 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
430 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
436 /// Position::game_phase() calculates the game phase interpolating total non-pawn
437 /// material between endgame and midgame limits.
439 Phase Position::game_phase() const {
441 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
443 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
445 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
449 /// Position::check_blockers() returns a bitboard of all the pieces with color
450 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
451 /// blocks a check if removing that piece from the board would result in a
452 /// position where the king is in check. A check blocking piece can be either a
453 /// pinned or a discovered check piece, according if its color 'c' is the same
454 /// or the opposite of 'kingColor'.
456 Bitboard Position::check_blockers(Color c, Color kingColor) const {
458 Bitboard b, pinners, result = 0;
459 Square ksq = king_square(kingColor);
461 // Pinners are sliders that give check when a pinned piece is removed
462 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
463 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
467 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
469 if (!more_than_one(b))
470 result |= b & pieces(c);
476 /// Position::attackers_to() computes a bitboard of all pieces which attack a
477 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
479 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
481 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
482 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
483 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
484 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
485 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
486 | (attacks_from<KING>(s) & pieces(KING));
490 /// Position::legal() tests whether a pseudo-legal move is legal
492 bool Position::legal(Move m, Bitboard pinned) const {
495 assert(pinned == pinned_pieces(sideToMove));
497 Color us = sideToMove;
498 Square from = from_sq(m);
500 assert(color_of(moved_piece(m)) == us);
501 assert(piece_on(king_square(us)) == make_piece(us, KING));
503 // En passant captures are a tricky special case. Because they are rather
504 // uncommon, we do it simply by testing whether the king is attacked after
506 if (type_of(m) == ENPASSANT)
508 Square ksq = king_square(us);
509 Square to = to_sq(m);
510 Square capsq = to - pawn_push(us);
511 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
513 assert(to == ep_square());
514 assert(moved_piece(m) == make_piece(us, PAWN));
515 assert(piece_on(capsq) == make_piece(~us, PAWN));
516 assert(piece_on(to) == NO_PIECE);
518 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
519 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
522 // If the moving piece is a king, check whether the destination
523 // square is attacked by the opponent. Castling moves are checked
524 // for legality during move generation.
525 if (type_of(piece_on(from)) == KING)
526 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
528 // A non-king move is legal if and only if it is not pinned or it
529 // is moving along the ray towards or away from the king.
532 || aligned(from, to_sq(m), king_square(us));
536 /// Position::pseudo_legal() takes a random move and tests whether the move is
537 /// pseudo legal. It is used to validate moves from TT that can be corrupted
538 /// due to SMP concurrent access or hash position key aliasing.
540 bool Position::pseudo_legal(const Move m) const {
542 Color us = sideToMove;
543 Square from = from_sq(m);
544 Square to = to_sq(m);
545 Piece pc = moved_piece(m);
547 // Use a slower but simpler function for uncommon cases
548 if (type_of(m) != NORMAL)
549 return MoveList<LEGAL>(*this).contains(m);
551 // Is not a promotion, so promotion piece must be empty
552 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
555 // If the 'from' square is not occupied by a piece belonging to the side to
556 // move, the move is obviously not legal.
557 if (pc == NO_PIECE || color_of(pc) != us)
560 // The destination square cannot be occupied by a friendly piece
564 // Handle the special case of a pawn move
565 if (type_of(pc) == PAWN)
567 // We have already handled promotion moves, so destination
568 // cannot be on the 8th/1st rank.
569 if (rank_of(to) == relative_rank(us, RANK_8))
572 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
573 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
574 && !( (from + 2 * pawn_push(us) == to) // Not a double push
575 && (rank_of(from) == relative_rank(us, RANK_2))
577 && empty(to - pawn_push(us))))
580 else if (!(attacks_from(pc, from) & to))
583 // Evasions generator already takes care to avoid some kind of illegal moves
584 // and legal() relies on this. We therefore have to take care that the same
585 // kind of moves are filtered out here.
588 if (type_of(pc) != KING)
590 // Double check? In this case a king move is required
591 if (more_than_one(checkers()))
594 // Our move must be a blocking evasion or a capture of the checking piece
595 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
598 // In case of king moves under check we have to remove king so as to catch
599 // invalid moves like b1a1 when opposite queen is on c1.
600 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
608 /// Position::gives_check() tests whether a pseudo-legal move gives a check
610 bool Position::gives_check(Move m, const CheckInfo& ci) const {
613 assert(ci.dcCandidates == discovered_check_candidates());
614 assert(color_of(moved_piece(m)) == sideToMove);
616 Square from = from_sq(m);
617 Square to = to_sq(m);
619 // Is there a direct check?
620 if (ci.checkSquares[type_of(piece_on(from))] & to)
623 // Is there a discovered check?
625 && (ci.dcCandidates & from)
626 && !aligned(from, to, ci.ksq))
635 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
637 // En passant capture with check? We have already handled the case
638 // of direct checks and ordinary discovered check, so the only case we
639 // need to handle is the unusual case of a discovered check through
640 // the captured pawn.
643 Square capsq = make_square(file_of(to), rank_of(from));
644 Bitboard b = (pieces() ^ from ^ capsq) | to;
646 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
647 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
652 Square rfrom = to; // Castling is encoded as 'King captures the rook'
653 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
654 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
656 return (PseudoAttacks[ROOK][rto] & ci.ksq)
657 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
666 /// Position::do_move() makes a move, and saves all information necessary
667 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
668 /// moves should be filtered out before this function is called.
670 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
673 assert(&newSt != st);
676 Key k = st->key ^ Zobrist::side;
678 // Copy some fields of the old state to our new StateInfo object except the
679 // ones which are going to be recalculated from scratch anyway and then switch
680 // our state pointer to point to the new (ready to be updated) state.
681 std::memcpy(&newSt, st, offsetof(StateInfo, key));
685 // Increment ply counters. In particular, rule50 will be reset to zero later on
686 // in case of a capture or a pawn move.
691 Color us = sideToMove;
693 Square from = from_sq(m);
694 Square to = to_sq(m);
695 PieceType pt = type_of(piece_on(from));
696 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
698 assert(color_of(piece_on(from)) == us);
699 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
700 assert(captured != KING);
702 if (type_of(m) == CASTLING)
707 do_castling<true>(us, from, to, rfrom, rto);
709 captured = NO_PIECE_TYPE;
710 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
711 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
718 // If the captured piece is a pawn, update pawn hash key, otherwise
719 // update non-pawn material.
720 if (captured == PAWN)
722 if (type_of(m) == ENPASSANT)
724 capsq -= pawn_push(us);
727 assert(to == st->epSquare);
728 assert(relative_rank(us, to) == RANK_6);
729 assert(piece_on(to) == NO_PIECE);
730 assert(piece_on(capsq) == make_piece(them, PAWN));
732 board[capsq] = NO_PIECE; // Not done by remove_piece()
735 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
738 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
740 // Update board and piece lists
741 remove_piece(them, captured, capsq);
743 // Update material hash key and prefetch access to materialTable
744 k ^= Zobrist::psq[them][captured][capsq];
745 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
746 prefetch(thisThread->materialTable[st->materialKey]);
748 // Update incremental scores
749 st->psq -= PSQT::psq[them][captured][capsq];
751 // Reset rule 50 counter
756 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
758 // Reset en passant square
759 if (st->epSquare != SQ_NONE)
761 k ^= Zobrist::enpassant[file_of(st->epSquare)];
762 st->epSquare = SQ_NONE;
765 // Update castling rights if needed
766 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
768 int cr = castlingRightsMask[from] | castlingRightsMask[to];
769 k ^= Zobrist::castling[st->castlingRights & cr];
770 st->castlingRights &= ~cr;
773 // Move the piece. The tricky Chess960 castling is handled earlier
774 if (type_of(m) != CASTLING)
775 move_piece(us, pt, from, to);
777 // If the moving piece is a pawn do some special extra work
780 // Set en-passant square if the moved pawn can be captured
781 if ( (int(to) ^ int(from)) == 16
782 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
784 st->epSquare = (from + to) / 2;
785 k ^= Zobrist::enpassant[file_of(st->epSquare)];
788 else if (type_of(m) == PROMOTION)
790 PieceType promotion = promotion_type(m);
792 assert(relative_rank(us, to) == RANK_8);
793 assert(promotion >= KNIGHT && promotion <= QUEEN);
795 remove_piece(us, PAWN, to);
796 put_piece(us, promotion, to);
799 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
800 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
801 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
802 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
804 // Update incremental score
805 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
808 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
811 // Update pawn hash key and prefetch access to pawnsTable
812 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
813 prefetch(thisThread->pawnsTable[st->pawnKey]);
815 // Reset rule 50 draw counter
819 // Update incremental scores
820 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
823 st->capturedType = captured;
825 // Update the key with the final value
828 // Calculate checkers bitboard (if move gives check)
829 st->checkersBB = givesCheck ? attackers_to(king_square(them)) & pieces(us) : 0;
831 sideToMove = ~sideToMove;
837 /// Position::undo_move() unmakes a move. When it returns, the position should
838 /// be restored to exactly the same state as before the move was made.
840 void Position::undo_move(Move m) {
844 sideToMove = ~sideToMove;
846 Color us = sideToMove;
847 Square from = from_sq(m);
848 Square to = to_sq(m);
849 PieceType pt = type_of(piece_on(to));
851 assert(empty(from) || type_of(m) == CASTLING);
852 assert(st->capturedType != KING);
854 if (type_of(m) == PROMOTION)
856 assert(relative_rank(us, to) == RANK_8);
857 assert(pt == promotion_type(m));
858 assert(pt >= KNIGHT && pt <= QUEEN);
860 remove_piece(us, pt, to);
861 put_piece(us, PAWN, to);
865 if (type_of(m) == CASTLING)
868 do_castling<false>(us, from, to, rfrom, rto);
872 move_piece(us, pt, to, from); // Put the piece back at the source square
874 if (st->capturedType)
878 if (type_of(m) == ENPASSANT)
880 capsq -= pawn_push(us);
883 assert(to == st->previous->epSquare);
884 assert(relative_rank(us, to) == RANK_6);
885 assert(piece_on(capsq) == NO_PIECE);
886 assert(st->capturedType == PAWN);
889 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
893 // Finally point our state pointer back to the previous state
901 /// Position::do_castling() is a helper used to do/undo a castling move. This
902 /// is a bit tricky, especially in Chess960.
904 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
906 bool kingSide = to > from;
907 rfrom = to; // Castling is encoded as "king captures friendly rook"
908 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
909 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
911 // Remove both pieces first since squares could overlap in Chess960
912 remove_piece(us, KING, Do ? from : to);
913 remove_piece(us, ROOK, Do ? rfrom : rto);
914 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
915 put_piece(us, KING, Do ? to : from);
916 put_piece(us, ROOK, Do ? rto : rfrom);
920 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
921 /// the side to move without executing any move on the board.
923 void Position::do_null_move(StateInfo& newSt) {
926 assert(&newSt != st);
928 std::memcpy(&newSt, st, sizeof(StateInfo));
932 if (st->epSquare != SQ_NONE)
934 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
935 st->epSquare = SQ_NONE;
938 st->key ^= Zobrist::side;
939 prefetch(TT.first_entry(st->key));
942 st->pliesFromNull = 0;
944 sideToMove = ~sideToMove;
949 void Position::undo_null_move() {
954 sideToMove = ~sideToMove;
958 /// Position::key_after() computes the new hash key after the given move. Needed
959 /// for speculative prefetch. It doesn't recognize special moves like castling,
960 /// en-passant and promotions.
962 Key Position::key_after(Move m) const {
964 Color us = sideToMove;
965 Square from = from_sq(m);
966 Square to = to_sq(m);
967 PieceType pt = type_of(piece_on(from));
968 PieceType captured = type_of(piece_on(to));
969 Key k = st->key ^ Zobrist::side;
972 k ^= Zobrist::psq[~us][captured][to];
974 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
978 /// Position::see() is a static exchange evaluator: It tries to estimate the
979 /// material gain or loss resulting from a move.
981 Value Position::see_sign(Move m) const {
985 // Early return if SEE cannot be negative because captured piece value
986 // is not less then capturing one. Note that king moves always return
987 // here because king midgame value is set to 0.
988 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
989 return VALUE_KNOWN_WIN;
994 Value Position::see(Move m) const {
997 Bitboard occupied, attackers, stmAttackers;
1007 swapList[0] = PieceValue[MG][piece_on(to)];
1008 stm = color_of(piece_on(from));
1009 occupied = pieces() ^ from;
1011 // Castling moves are implemented as king capturing the rook so cannot
1012 // be handled correctly. Simply return VALUE_ZERO that is always correct
1013 // unless in the rare case the rook ends up under attack.
1014 if (type_of(m) == CASTLING)
1017 if (type_of(m) == ENPASSANT)
1019 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1020 swapList[0] = PieceValue[MG][PAWN];
1023 // Find all attackers to the destination square, with the moving piece
1024 // removed, but possibly an X-ray attacker added behind it.
1025 attackers = attackers_to(to, occupied) & occupied;
1027 // If the opponent has no attackers we are finished
1029 stmAttackers = attackers & pieces(stm);
1033 // The destination square is defended, which makes things rather more
1034 // difficult to compute. We proceed by building up a "swap list" containing
1035 // the material gain or loss at each stop in a sequence of captures to the
1036 // destination square, where the sides alternately capture, and always
1037 // capture with the least valuable piece. After each capture, we look for
1038 // new X-ray attacks from behind the capturing piece.
1039 captured = type_of(piece_on(from));
1042 assert(slIndex < 32);
1044 // Add the new entry to the swap list
1045 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1047 // Locate and remove the next least valuable attacker
1048 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1050 stmAttackers = attackers & pieces(stm);
1053 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1055 // Having built the swap list, we negamax through it to find the best
1056 // achievable score from the point of view of the side to move.
1058 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1064 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1065 /// or by repetition. It does not detect stalemates.
1067 bool Position::is_draw() const {
1069 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1072 StateInfo* stp = st;
1073 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1075 stp = stp->previous->previous;
1077 if (stp->key == st->key)
1078 return true; // Draw at first repetition
1085 /// Position::flip() flips position with the white and black sides reversed. This
1086 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1088 void Position::flip() {
1091 std::stringstream ss(fen());
1093 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1095 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1096 f.insert(0, token + (f.empty() ? " " : "/"));
1099 ss >> token; // Active color
1100 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1102 ss >> token; // Castling availability
1105 std::transform(f.begin(), f.end(), f.begin(),
1106 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1108 ss >> token; // En passant square
1109 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1111 std::getline(ss, token); // Half and full moves
1114 set(f, is_chess960(), this_thread());
1116 assert(pos_is_ok());
1120 /// Position::pos_is_ok() performs some consistency checks for the position object.
1121 /// This is meant to be helpful when debugging.
1123 bool Position::pos_is_ok(int* failedStep) const {
1125 const bool Fast = true; // Quick (default) or full check?
1127 enum { Default, King, Bitboards, State, Lists, Castling };
1129 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1134 if (step == Default)
1135 if ( (sideToMove != WHITE && sideToMove != BLACK)
1136 || piece_on(king_square(WHITE)) != W_KING
1137 || piece_on(king_square(BLACK)) != B_KING
1138 || ( ep_square() != SQ_NONE
1139 && relative_rank(sideToMove, ep_square()) != RANK_6))
1143 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1144 || std::count(board, board + SQUARE_NB, B_KING) != 1
1145 || attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1148 if (step == Bitboards)
1150 if ( (pieces(WHITE) & pieces(BLACK))
1151 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1154 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1155 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1156 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1164 if (std::memcmp(&si, st, sizeof(StateInfo)))
1169 for (Color c = WHITE; c <= BLACK; ++c)
1170 for (PieceType pt = PAWN; pt <= KING; ++pt)
1172 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1175 for (int i = 0; i < pieceCount[c][pt]; ++i)
1176 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1177 || index[pieceList[c][pt][i]] != i)
1181 if (step == Castling)
1182 for (Color c = WHITE; c <= BLACK; ++c)
1183 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1185 if (!can_castle(c | s))
1188 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1189 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1190 ||(castlingRightsMask[king_square(c)] & (c | s)) != (c | s))