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-2014 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/>.
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");
55 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
57 // min_attacker() is a helper function used by see() to locate the least
58 // valuable attacker for the side to move, remove the attacker we just found
59 // from the bitboards and scan for new X-ray attacks behind it.
61 template<int Pt> FORCE_INLINE
62 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
63 Bitboard& occupied, Bitboard& attackers) {
65 Bitboard b = stmAttackers & bb[Pt];
67 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
69 occupied ^= b & ~(b - 1);
71 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
72 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
74 if (Pt == ROOK || Pt == QUEEN)
75 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
77 attackers &= occupied; // After X-ray that may add already processed pieces
81 template<> FORCE_INLINE
82 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
83 return KING; // No need to update bitboards: it is the last cycle
91 CheckInfo::CheckInfo(const Position& pos) {
93 Color them = ~pos.side_to_move();
94 ksq = pos.king_square(them);
96 pinned = pos.pinned_pieces(pos.side_to_move());
97 dcCandidates = pos.discovered_check_candidates();
99 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
100 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
101 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
102 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
103 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
108 /// operator<<(Position) returns an ASCII representation of the position
110 std::ostream& operator<<(std::ostream& os, const Position& pos) {
112 os << "\n +---+---+---+---+---+---+---+---+\n";
114 for (Rank r = RANK_8; r >= RANK_1; --r)
116 for (File f = FILE_A; f <= FILE_H; ++f)
117 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
119 os << " |\n +---+---+---+---+---+---+---+---+\n";
122 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
123 << std::setfill('0') << std::setw(16) << pos.st->key << std::dec << "\nCheckers: ";
125 for (Bitboard b = pos.checkers(); b; )
126 os << UCI::format_square(pop_lsb(&b)) << " ";
132 /// Position::init() initializes at startup the various arrays used to compute
133 /// hash keys and the piece square tables. The latter is a two-step operation:
134 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
135 /// Secondly, the black halves of the tables are initialized by flipping and
136 /// changing the sign of the white scores.
138 void Position::init() {
142 for (Color c = WHITE; c <= BLACK; ++c)
143 for (PieceType pt = PAWN; pt <= KING; ++pt)
144 for (Square s = SQ_A1; s <= SQ_H8; ++s)
145 Zobrist::psq[c][pt][s] = rk.rand<Key>();
147 for (File f = FILE_A; f <= FILE_H; ++f)
148 Zobrist::enpassant[f] = rk.rand<Key>();
150 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
155 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
156 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
160 Zobrist::side = rk.rand<Key>();
161 Zobrist::exclusion = rk.rand<Key>();
163 for (PieceType pt = PAWN; pt <= KING; ++pt)
165 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
166 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
168 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
170 for (Square s = SQ_A1; s <= SQ_H8; ++s)
172 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
173 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
179 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
180 /// object to not depend on any external data so we detach state pointer from
183 Position& Position::operator=(const Position& pos) {
185 std::memcpy(this, &pos, sizeof(Position));
196 /// Position::clear() erases the position object to a pristine state, with an
197 /// empty board, white to move, and no castling rights.
199 void Position::clear() {
201 std::memset(this, 0, sizeof(Position));
202 startState.epSquare = SQ_NONE;
205 for (int i = 0; i < PIECE_TYPE_NB; ++i)
206 for (int j = 0; j < 16; ++j)
207 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
211 /// Position::set() initializes the position object with the given FEN string.
212 /// This function is not very robust - make sure that input FENs are correct,
213 /// this is assumed to be the responsibility of the GUI.
215 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
217 A FEN string defines a particular position using only the ASCII character set.
219 A FEN string contains six fields separated by a space. The fields are:
221 1) Piece placement (from white's perspective). Each rank is described, starting
222 with rank 8 and ending with rank 1. Within each rank, the contents of each
223 square are described from file A through file H. Following the Standard
224 Algebraic Notation (SAN), each piece is identified by a single letter taken
225 from the standard English names. White pieces are designated using upper-case
226 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
227 noted using digits 1 through 8 (the number of blank squares), and "/"
230 2) Active color. "w" means white moves next, "b" means black.
232 3) Castling availability. If neither side can castle, this is "-". Otherwise,
233 this has one or more letters: "K" (White can castle kingside), "Q" (White
234 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
235 can castle queenside).
237 4) En passant target square (in algebraic notation). If there's no en passant
238 target square, this is "-". If a pawn has just made a 2-square move, this
239 is the position "behind" the pawn. This is recorded regardless of whether
240 there is a pawn in position to make an en passant capture.
242 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
243 or capture. This is used to determine if a draw can be claimed under the
246 6) Fullmove number. The number of the full move. It starts at 1, and is
247 incremented after Black's move.
250 unsigned char col, row, token;
253 std::istringstream ss(fenStr);
258 // 1. Piece placement
259 while ((ss >> token) && !isspace(token))
262 sq += Square(token - '0'); // Advance the given number of files
264 else if (token == '/')
267 else if ((idx = PieceToChar.find(token)) != string::npos)
269 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
276 sideToMove = (token == 'w' ? WHITE : BLACK);
279 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
280 // Shredder-FEN that uses the letters of the columns on which the rooks began
281 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
282 // if an inner rook is associated with the castling right, the castling tag is
283 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
284 while ((ss >> token) && !isspace(token))
287 Color c = islower(token) ? BLACK : WHITE;
289 token = char(toupper(token));
292 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
294 else if (token == 'Q')
295 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
297 else if (token >= 'A' && token <= 'H')
298 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
303 set_castling_right(c, rsq);
306 // 4. En passant square. Ignore if no pawn capture is possible
307 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
308 && ((ss >> row) && (row == '3' || row == '6')))
310 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
312 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
313 st->epSquare = SQ_NONE;
316 // 5-6. Halfmove clock and fullmove number
317 ss >> std::skipws >> st->rule50 >> gamePly;
319 // Convert from fullmove starting from 1 to ply starting from 0,
320 // handle also common incorrect FEN with fullmove = 0.
321 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
323 chess960 = isChess960;
331 /// Position::set_castling_right() is a helper function used to set castling
332 /// rights given the corresponding color and the rook starting square.
334 void Position::set_castling_right(Color c, Square rfrom) {
336 Square kfrom = king_square(c);
337 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
338 CastlingRight cr = (c | cs);
340 st->castlingRights |= cr;
341 castlingRightsMask[kfrom] |= cr;
342 castlingRightsMask[rfrom] |= cr;
343 castlingRookSquare[cr] = rfrom;
345 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
346 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
348 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
349 if (s != kfrom && s != rfrom)
350 castlingPath[cr] |= s;
352 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
353 if (s != kfrom && s != rfrom)
354 castlingPath[cr] |= s;
358 /// Position::set_state() computes the hash keys of the position, and other
359 /// data that once computed is updated incrementally as moves are made.
360 /// The function is only used when a new position is set up, and to verify
361 /// the correctness of the StateInfo data when running in debug mode.
363 void Position::set_state(StateInfo* si) const {
365 si->key = si->pawnKey = si->materialKey = 0;
366 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
367 si->psq = SCORE_ZERO;
369 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
371 for (Bitboard b = pieces(); b; )
373 Square s = pop_lsb(&b);
374 Piece pc = piece_on(s);
375 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
376 si->psq += psq[color_of(pc)][type_of(pc)][s];
379 if (ep_square() != SQ_NONE)
380 si->key ^= Zobrist::enpassant[file_of(ep_square())];
382 if (sideToMove == BLACK)
383 si->key ^= Zobrist::side;
385 si->key ^= Zobrist::castling[st->castlingRights];
387 for (Bitboard b = pieces(PAWN); b; )
389 Square s = pop_lsb(&b);
390 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
393 for (Color c = WHITE; c <= BLACK; ++c)
394 for (PieceType pt = PAWN; pt <= KING; ++pt)
395 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
396 si->materialKey ^= Zobrist::psq[c][pt][cnt];
398 for (Color c = WHITE; c <= BLACK; ++c)
399 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
400 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
404 /// Position::fen() returns a FEN representation of the position. In case of
405 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
407 const string Position::fen() const {
410 std::ostringstream ss;
412 for (Rank r = RANK_8; r >= RANK_1; --r)
414 for (File f = FILE_A; f <= FILE_H; ++f)
416 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
423 ss << PieceToChar[piece_on(make_square(f, r))];
430 ss << (sideToMove == WHITE ? " w " : " b ");
432 if (can_castle(WHITE_OO))
433 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | KING_SIDE)) : 'K');
435 if (can_castle(WHITE_OOO))
436 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE)) : 'Q');
438 if (can_castle(BLACK_OO))
439 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | KING_SIDE)) : 'k');
441 if (can_castle(BLACK_OOO))
442 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE)) : 'q');
444 if (!can_castle(WHITE) && !can_castle(BLACK))
447 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::format_square(ep_square()) + " ")
448 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
454 /// Position::game_phase() calculates the game phase interpolating total non-pawn
455 /// material between endgame and midgame limits.
457 Phase Position::game_phase() const {
459 Value npm = st->npMaterial[WHITE] + st->npMaterial[BLACK];
461 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
463 return Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));
467 /// Position::check_blockers() returns a bitboard of all the pieces with color
468 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
469 /// blocks a check if removing that piece from the board would result in a
470 /// position where the king is in check. A check blocking piece can be either a
471 /// pinned or a discovered check piece, according if its color 'c' is the same
472 /// or the opposite of 'kingColor'.
474 Bitboard Position::check_blockers(Color c, Color kingColor) const {
476 Bitboard b, pinners, result = 0;
477 Square ksq = king_square(kingColor);
479 // Pinners are sliders that give check when a pinned piece is removed
480 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
481 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
485 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
487 if (!more_than_one(b))
488 result |= b & pieces(c);
494 /// Position::attackers_to() computes a bitboard of all pieces which attack a
495 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
497 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
499 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
500 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
501 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
502 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
503 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
504 | (attacks_from<KING>(s) & pieces(KING));
508 /// Position::legal() tests whether a pseudo-legal move is legal
510 bool Position::legal(Move m, Bitboard pinned) const {
513 assert(pinned == pinned_pieces(sideToMove));
515 Color us = sideToMove;
516 Square from = from_sq(m);
518 assert(color_of(moved_piece(m)) == us);
519 assert(piece_on(king_square(us)) == make_piece(us, KING));
521 // En passant captures are a tricky special case. Because they are rather
522 // uncommon, we do it simply by testing whether the king is attacked after
524 if (type_of(m) == ENPASSANT)
526 Square ksq = king_square(us);
527 Square to = to_sq(m);
528 Square capsq = to - pawn_push(us);
529 Bitboard occ = (pieces() ^ from ^ capsq) | to;
531 assert(to == ep_square());
532 assert(moved_piece(m) == make_piece(us, PAWN));
533 assert(piece_on(capsq) == make_piece(~us, PAWN));
534 assert(piece_on(to) == NO_PIECE);
536 return !(attacks_bb< ROOK>(ksq, occ) & pieces(~us, QUEEN, ROOK))
537 && !(attacks_bb<BISHOP>(ksq, occ) & pieces(~us, QUEEN, BISHOP));
540 // If the moving piece is a king, check whether the destination
541 // square is attacked by the opponent. Castling moves are checked
542 // for legality during move generation.
543 if (type_of(piece_on(from)) == KING)
544 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
546 // A non-king move is legal if and only if it is not pinned or it
547 // is moving along the ray towards or away from the king.
550 || aligned(from, to_sq(m), king_square(us));
554 /// Position::pseudo_legal() takes a random move and tests whether the move is
555 /// pseudo legal. It is used to validate moves from TT that can be corrupted
556 /// due to SMP concurrent access or hash position key aliasing.
558 bool Position::pseudo_legal(const Move m) const {
560 Color us = sideToMove;
561 Square from = from_sq(m);
562 Square to = to_sq(m);
563 Piece pc = moved_piece(m);
565 // Use a slower but simpler function for uncommon cases
566 if (type_of(m) != NORMAL)
567 return MoveList<LEGAL>(*this).contains(m);
569 // Is not a promotion, so promotion piece must be empty
570 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
573 // If the 'from' square is not occupied by a piece belonging to the side to
574 // move, the move is obviously not legal.
575 if (pc == NO_PIECE || color_of(pc) != us)
578 // The destination square cannot be occupied by a friendly piece
582 // Handle the special case of a pawn move
583 if (type_of(pc) == PAWN)
585 // We have already handled promotion moves, so destination
586 // cannot be on the 8th/1st rank.
587 if (rank_of(to) == relative_rank(us, RANK_8))
590 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
592 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
594 && !( (from + 2 * pawn_push(us) == to) // Not a double push
595 && (rank_of(from) == relative_rank(us, RANK_2))
597 && empty(to - pawn_push(us))))
600 else if (!(attacks_from(pc, from) & to))
603 // Evasions generator already takes care to avoid some kind of illegal moves
604 // and legal() relies on this. We therefore have to take care that the same
605 // kind of moves are filtered out here.
608 if (type_of(pc) != KING)
610 // Double check? In this case a king move is required
611 if (more_than_one(checkers()))
614 // Our move must be a blocking evasion or a capture of the checking piece
615 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
618 // In case of king moves under check we have to remove king so as to catch
619 // invalid moves like b1a1 when opposite queen is on c1.
620 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
628 /// Position::gives_check() tests whether a pseudo-legal move gives a check
630 bool Position::gives_check(Move m, const CheckInfo& ci) const {
633 assert(ci.dcCandidates == discovered_check_candidates());
634 assert(color_of(moved_piece(m)) == sideToMove);
636 Square from = from_sq(m);
637 Square to = to_sq(m);
638 PieceType pt = type_of(piece_on(from));
640 // Is there a direct check?
641 if (ci.checkSq[pt] & to)
644 // Is there a discovered check?
645 if ( unlikely(ci.dcCandidates)
646 && (ci.dcCandidates & from)
647 && !aligned(from, to, ci.ksq))
656 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
658 // En passant capture with check? We have already handled the case
659 // of direct checks and ordinary discovered check, so the only case we
660 // need to handle is the unusual case of a discovered check through
661 // the captured pawn.
664 Square capsq = make_square(file_of(to), rank_of(from));
665 Bitboard b = (pieces() ^ from ^ capsq) | to;
667 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
668 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
673 Square rfrom = to; // Castling is encoded as 'King captures the rook'
674 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
675 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
677 return (PseudoAttacks[ROOK][rto] & ci.ksq)
678 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
687 /// Position::do_move() makes a move, and saves all information necessary
688 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
689 /// moves should be filtered out before this function is called.
691 void Position::do_move(Move m, StateInfo& newSt) {
694 do_move(m, newSt, ci, gives_check(m, ci));
697 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
700 assert(&newSt != st);
705 // Copy some fields of the old state to our new StateInfo object except the
706 // ones which are going to be recalculated from scratch anyway and then switch
707 // our state pointer to point to the new (ready to be updated) state.
708 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
713 // Update side to move
716 // Increment ply counters. In particular, rule50 will be reset to zero later on
717 // in case of a capture or a pawn move.
722 Color us = sideToMove;
724 Square from = from_sq(m);
725 Square to = to_sq(m);
726 Piece pc = piece_on(from);
727 PieceType pt = type_of(pc);
728 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
730 assert(color_of(pc) == us);
731 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
732 assert(captured != KING);
734 if (type_of(m) == CASTLING)
736 assert(pc == make_piece(us, KING));
739 do_castling<true>(from, to, rfrom, rto);
741 captured = NO_PIECE_TYPE;
742 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
743 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
750 // If the captured piece is a pawn, update pawn hash key, otherwise
751 // update non-pawn material.
752 if (captured == PAWN)
754 if (type_of(m) == ENPASSANT)
756 capsq += pawn_push(them);
759 assert(to == st->epSquare);
760 assert(relative_rank(us, to) == RANK_6);
761 assert(piece_on(to) == NO_PIECE);
762 assert(piece_on(capsq) == make_piece(them, PAWN));
764 board[capsq] = NO_PIECE;
767 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
770 st->npMaterial[them] -= PieceValue[MG][captured];
772 // Update board and piece lists
773 remove_piece(capsq, them, captured);
775 // Update material hash key and prefetch access to materialTable
776 k ^= Zobrist::psq[them][captured][capsq];
777 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
778 prefetch((char*)thisThread->materialTable[st->materialKey]);
780 // Update incremental scores
781 st->psq -= psq[them][captured][capsq];
783 // Reset rule 50 counter
788 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
790 // Reset en passant square
791 if (st->epSquare != SQ_NONE)
793 k ^= Zobrist::enpassant[file_of(st->epSquare)];
794 st->epSquare = SQ_NONE;
797 // Update castling rights if needed
798 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
800 int cr = castlingRightsMask[from] | castlingRightsMask[to];
801 k ^= Zobrist::castling[st->castlingRights & cr];
802 st->castlingRights &= ~cr;
805 // Move the piece. The tricky Chess960 castling is handled earlier
806 if (type_of(m) != CASTLING)
807 move_piece(from, to, us, pt);
809 // If the moving piece is a pawn do some special extra work
812 // Set en-passant square if the moved pawn can be captured
813 if ( (int(to) ^ int(from)) == 16
814 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
816 st->epSquare = Square((from + to) / 2);
817 k ^= Zobrist::enpassant[file_of(st->epSquare)];
820 else if (type_of(m) == PROMOTION)
822 PieceType promotion = promotion_type(m);
824 assert(relative_rank(us, to) == RANK_8);
825 assert(promotion >= KNIGHT && promotion <= QUEEN);
827 remove_piece(to, us, PAWN);
828 put_piece(to, us, promotion);
831 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
832 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
833 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
834 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
836 // Update incremental score
837 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
840 st->npMaterial[us] += PieceValue[MG][promotion];
843 // Update pawn hash key and prefetch access to pawnsTable
844 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
845 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
847 // Reset rule 50 draw counter
851 // Update incremental scores
852 st->psq += psq[us][pt][to] - psq[us][pt][from];
855 st->capturedType = captured;
857 // Update the key with the final value
860 // Update checkers bitboard: piece must be already moved due to attacks_from()
865 if (type_of(m) != NORMAL)
866 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
870 if (ci.checkSq[pt] & to)
871 st->checkersBB |= to;
874 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
877 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
880 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
885 sideToMove = ~sideToMove;
891 /// Position::undo_move() unmakes a move. When it returns, the position should
892 /// be restored to exactly the same state as before the move was made.
894 void Position::undo_move(Move m) {
898 sideToMove = ~sideToMove;
900 Color us = sideToMove;
901 Square from = from_sq(m);
902 Square to = to_sq(m);
903 PieceType pt = type_of(piece_on(to));
905 assert(empty(from) || type_of(m) == CASTLING);
906 assert(st->capturedType != KING);
908 if (type_of(m) == PROMOTION)
910 assert(pt == promotion_type(m));
911 assert(relative_rank(us, to) == RANK_8);
912 assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
914 remove_piece(to, us, promotion_type(m));
915 put_piece(to, us, PAWN);
919 if (type_of(m) == CASTLING)
922 do_castling<false>(from, to, rfrom, rto);
926 move_piece(to, from, us, pt); // Put the piece back at the source square
928 if (st->capturedType)
932 if (type_of(m) == ENPASSANT)
934 capsq -= pawn_push(us);
937 assert(to == st->previous->epSquare);
938 assert(relative_rank(us, to) == RANK_6);
939 assert(piece_on(capsq) == NO_PIECE);
942 put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
946 // Finally point our state pointer back to the previous state
954 /// Position::do_castling() is a helper used to do/undo a castling move. This
955 /// is a bit tricky, especially in Chess960.
957 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
959 bool kingSide = to > from;
960 rfrom = to; // Castling is encoded as "king captures friendly rook"
961 rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
962 to = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
964 // Remove both pieces first since squares could overlap in Chess960
965 remove_piece(Do ? from : to, sideToMove, KING);
966 remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
967 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
968 put_piece(Do ? to : from, sideToMove, KING);
969 put_piece(Do ? rto : rfrom, sideToMove, ROOK);
973 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
974 /// the side to move without executing any move on the board.
976 void Position::do_null_move(StateInfo& newSt) {
980 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
985 if (st->epSquare != SQ_NONE)
987 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
988 st->epSquare = SQ_NONE;
991 st->key ^= Zobrist::side;
992 prefetch((char*)TT.first_entry(st->key));
995 st->pliesFromNull = 0;
997 sideToMove = ~sideToMove;
1002 void Position::undo_null_move() {
1004 assert(!checkers());
1007 sideToMove = ~sideToMove;
1011 /// Position::key_after() computes the new hash key after the given moven. Needed
1012 /// for speculative prefetch. It doesn't recognize special moves like castling,
1013 /// en-passant and promotions.
1015 Key Position::key_after(Move m) const {
1017 Color us = sideToMove;
1018 Square from = from_sq(m);
1019 Square to = to_sq(m);
1020 PieceType pt = type_of(piece_on(from));
1021 PieceType captured = type_of(piece_on(to));
1022 Key k = st->key ^ Zobrist::side;
1025 k ^= Zobrist::psq[~us][captured][to];
1027 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1031 /// Position::see() is a static exchange evaluator: It tries to estimate the
1032 /// material gain or loss resulting from a move.
1034 Value Position::see_sign(Move m) const {
1038 // Early return if SEE cannot be negative because captured piece value
1039 // is not less then capturing one. Note that king moves always return
1040 // here because king midgame value is set to 0.
1041 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1042 return VALUE_KNOWN_WIN;
1047 Value Position::see(Move m) const {
1050 Bitboard occupied, attackers, stmAttackers;
1060 swapList[0] = PieceValue[MG][piece_on(to)];
1061 stm = color_of(piece_on(from));
1062 occupied = pieces() ^ from;
1064 // Castling moves are implemented as king capturing the rook so cannot be
1065 // handled correctly. Simply return 0 that is always the correct value
1066 // unless in the rare case the rook ends up under attack.
1067 if (type_of(m) == CASTLING)
1070 if (type_of(m) == ENPASSANT)
1072 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1073 swapList[0] = PieceValue[MG][PAWN];
1076 // Find all attackers to the destination square, with the moving piece
1077 // removed, but possibly an X-ray attacker added behind it.
1078 attackers = attackers_to(to, occupied) & occupied;
1080 // If the opponent has no attackers we are finished
1082 stmAttackers = attackers & pieces(stm);
1086 // The destination square is defended, which makes things rather more
1087 // difficult to compute. We proceed by building up a "swap list" containing
1088 // the material gain or loss at each stop in a sequence of captures to the
1089 // destination square, where the sides alternately capture, and always
1090 // capture with the least valuable piece. After each capture, we look for
1091 // new X-ray attacks from behind the capturing piece.
1092 captured = type_of(piece_on(from));
1095 assert(slIndex < 32);
1097 // Add the new entry to the swap list
1098 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1100 // Locate and remove the next least valuable attacker
1101 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1103 // Stop before processing a king capture
1104 if (captured == KING)
1106 if (stmAttackers == attackers)
1113 stmAttackers = attackers & pieces(stm);
1116 } while (stmAttackers);
1118 // Having built the swap list, we negamax through it to find the best
1119 // achievable score from the point of view of the side to move.
1121 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1127 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1128 /// rule or repetition. It does not detect stalemates.
1130 bool Position::is_draw() const {
1132 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1135 StateInfo* stp = st;
1136 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1138 stp = stp->previous->previous;
1140 if (stp->key == st->key)
1141 return true; // Draw at first repetition
1148 /// Position::flip() flips position with the white and black sides reversed. This
1149 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1151 static char toggle_case(char c) {
1152 return char(islower(c) ? toupper(c) : tolower(c));
1155 void Position::flip() {
1158 std::stringstream ss(fen());
1160 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1162 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1163 f.insert(0, token + (f.empty() ? " " : "/"));
1166 ss >> token; // Active color
1167 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1169 ss >> token; // Castling availability
1172 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1174 ss >> token; // En passant square
1175 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1177 std::getline(ss, token); // Half and full moves
1180 set(f, is_chess960(), this_thread());
1182 assert(pos_is_ok());
1186 /// Position::pos_is_ok() performs some consistency checks for the position object.
1187 /// This is meant to be helpful when debugging.
1189 bool Position::pos_is_ok(int* step) const {
1191 // Which parts of the position should be verified?
1192 const bool all = false;
1194 const bool testBitboards = all || false;
1195 const bool testState = all || false;
1196 const bool testKingCount = all || false;
1197 const bool testKingCapture = all || false;
1198 const bool testPieceCounts = all || false;
1199 const bool testPieceList = all || false;
1200 const bool testCastlingSquares = all || false;
1205 if ( (sideToMove != WHITE && sideToMove != BLACK)
1206 || piece_on(king_square(WHITE)) != W_KING
1207 || piece_on(king_square(BLACK)) != B_KING
1208 || ( ep_square() != SQ_NONE
1209 && relative_rank(sideToMove, ep_square()) != RANK_6))
1212 if (step && ++*step, testBitboards)
1214 // The intersection of the white and black pieces must be empty
1215 if (pieces(WHITE) & pieces(BLACK))
1218 // The union of the white and black pieces must be equal to all
1220 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1223 // Separate piece type bitboards must have empty intersections
1224 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1225 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1226 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1230 if (step && ++*step, testState)
1234 if ( st->key != si.key
1235 || st->pawnKey != si.pawnKey
1236 || st->materialKey != si.materialKey
1237 || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1238 || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1239 || st->psq != si.psq
1240 || st->checkersBB != si.checkersBB)
1244 if (step && ++*step, testKingCount)
1245 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1246 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1249 if (step && ++*step, testKingCapture)
1250 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1253 if (step && ++*step, testPieceCounts)
1254 for (Color c = WHITE; c <= BLACK; ++c)
1255 for (PieceType pt = PAWN; pt <= KING; ++pt)
1256 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1259 if (step && ++*step, testPieceList)
1260 for (Color c = WHITE; c <= BLACK; ++c)
1261 for (PieceType pt = PAWN; pt <= KING; ++pt)
1262 for (int i = 0; i < pieceCount[c][pt]; ++i)
1263 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1264 || index[pieceList[c][pt][i]] != i)
1267 if (step && ++*step, testCastlingSquares)
1268 for (Color c = WHITE; c <= BLACK; ++c)
1269 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1271 if (!can_castle(c | s))
1274 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1275 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1276 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))