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/>.
39 Value PieceValue[PHASE_NB][PIECE_NB] = {
40 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
41 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
45 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
46 Key enpassant[FILE_NB];
47 Key castling[CASTLING_RIGHT_NB];
52 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
56 const string PieceToChar(" PNBRQK pnbrqk");
57 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
59 // min_attacker() is a helper function used by see() to locate the least
60 // valuable attacker for the side to move, remove the attacker we just found
61 // from the bitboards and scan for new X-ray attacks behind it.
63 template<int Pt> FORCE_INLINE
64 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
65 Bitboard& occupied, Bitboard& attackers) {
67 Bitboard b = stmAttackers & bb[Pt];
69 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
71 occupied ^= b & ~(b - 1);
73 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
74 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
76 if (Pt == ROOK || Pt == QUEEN)
77 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
79 attackers &= occupied; // After X-ray that may add already processed pieces
83 template<> FORCE_INLINE
84 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
85 return KING; // No need to update bitboards: it is the last cycle
93 CheckInfo::CheckInfo(const Position& pos) {
95 Color them = ~pos.side_to_move();
96 ksq = pos.king_square(them);
98 pinned = pos.pinned_pieces(pos.side_to_move());
99 dcCandidates = pos.discovered_check_candidates();
101 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
102 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
103 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
104 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
105 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
110 /// operator<<(Position) returns an ASCII representation of the position
112 std::ostream& operator<<(std::ostream& os, const Position& pos) {
114 os << "\n +---+---+---+---+---+---+---+---+\n";
116 for (Rank r = RANK_8; r >= RANK_1; --r)
118 for (File f = FILE_A; f <= FILE_H; ++f)
119 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
121 os << " |\n +---+---+---+---+---+---+---+---+\n";
124 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
125 << std::setfill('0') << std::setw(16) << pos.st->key << std::dec << "\nCheckers: ";
127 for (Bitboard b = pos.checkers(); b; )
128 os << UCI::format_square(pop_lsb(&b)) << " ";
134 /// Position::init() initializes at startup the various arrays used to compute
135 /// hash keys and the piece square tables. The latter is a two-step operation:
136 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
137 /// Secondly, the black halves of the tables are initialized by flipping and
138 /// changing the sign of the white scores.
140 void Position::init() {
144 for (Color c = WHITE; c <= BLACK; ++c)
145 for (PieceType pt = PAWN; pt <= KING; ++pt)
146 for (Square s = SQ_A1; s <= SQ_H8; ++s)
147 Zobrist::psq[c][pt][s] = rk.rand<Key>();
149 for (File f = FILE_A; f <= FILE_H; ++f)
150 Zobrist::enpassant[f] = rk.rand<Key>();
152 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
157 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
158 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
162 Zobrist::side = rk.rand<Key>();
163 Zobrist::exclusion = rk.rand<Key>();
165 for (PieceType pt = PAWN; pt <= KING; ++pt)
167 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
168 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
170 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
172 for (Square s = SQ_A1; s <= SQ_H8; ++s)
174 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
175 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
181 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
182 /// object to not depend on any external data so we detach state pointer from
185 Position& Position::operator=(const Position& pos) {
187 std::memcpy(this, &pos, sizeof(Position));
198 /// Position::clear() erases the position object to a pristine state, with an
199 /// empty board, white to move, and no castling rights.
201 void Position::clear() {
203 std::memset(this, 0, sizeof(Position));
204 startState.epSquare = SQ_NONE;
207 for (int i = 0; i < PIECE_TYPE_NB; ++i)
208 for (int j = 0; j < 16; ++j)
209 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
213 /// Position::set() initializes the position object with the given FEN string.
214 /// This function is not very robust - make sure that input FENs are correct,
215 /// this is assumed to be the responsibility of the GUI.
217 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
219 A FEN string defines a particular position using only the ASCII character set.
221 A FEN string contains six fields separated by a space. The fields are:
223 1) Piece placement (from white's perspective). Each rank is described, starting
224 with rank 8 and ending with rank 1. Within each rank, the contents of each
225 square are described from file A through file H. Following the Standard
226 Algebraic Notation (SAN), each piece is identified by a single letter taken
227 from the standard English names. White pieces are designated using upper-case
228 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
229 noted using digits 1 through 8 (the number of blank squares), and "/"
232 2) Active color. "w" means white moves next, "b" means black.
234 3) Castling availability. If neither side can castle, this is "-". Otherwise,
235 this has one or more letters: "K" (White can castle kingside), "Q" (White
236 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
237 can castle queenside).
239 4) En passant target square (in algebraic notation). If there's no en passant
240 target square, this is "-". If a pawn has just made a 2-square move, this
241 is the position "behind" the pawn. This is recorded regardless of whether
242 there is a pawn in position to make an en passant capture.
244 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
245 or capture. This is used to determine if a draw can be claimed under the
248 6) Fullmove number. The number of the full move. It starts at 1, and is
249 incremented after Black's move.
252 unsigned char col, row, token;
255 std::istringstream ss(fenStr);
260 // 1. Piece placement
261 while ((ss >> token) && !isspace(token))
264 sq += Square(token - '0'); // Advance the given number of files
266 else if (token == '/')
269 else if ((idx = PieceToChar.find(token)) != string::npos)
271 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
278 sideToMove = (token == 'w' ? WHITE : BLACK);
281 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
282 // Shredder-FEN that uses the letters of the columns on which the rooks began
283 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
284 // if an inner rook is associated with the castling right, the castling tag is
285 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
286 while ((ss >> token) && !isspace(token))
289 Color c = islower(token) ? BLACK : WHITE;
291 token = char(toupper(token));
294 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
296 else if (token == 'Q')
297 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
299 else if (token >= 'A' && token <= 'H')
300 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
305 set_castling_right(c, rsq);
308 // 4. En passant square. Ignore if no pawn capture is possible
309 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
310 && ((ss >> row) && (row == '3' || row == '6')))
312 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
314 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
315 st->epSquare = SQ_NONE;
318 // 5-6. Halfmove clock and fullmove number
319 ss >> std::skipws >> st->rule50 >> gamePly;
321 // Convert from fullmove starting from 1 to ply starting from 0,
322 // handle also common incorrect FEN with fullmove = 0.
323 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
325 chess960 = isChess960;
333 /// Position::set_castling_right() is a helper function used to set castling
334 /// rights given the corresponding color and the rook starting square.
336 void Position::set_castling_right(Color c, Square rfrom) {
338 Square kfrom = king_square(c);
339 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
340 CastlingRight cr = (c | cs);
342 st->castlingRights |= cr;
343 castlingRightsMask[kfrom] |= cr;
344 castlingRightsMask[rfrom] |= cr;
345 castlingRookSquare[cr] = rfrom;
347 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
348 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
350 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
351 if (s != kfrom && s != rfrom)
352 castlingPath[cr] |= s;
354 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
355 if (s != kfrom && s != rfrom)
356 castlingPath[cr] |= s;
360 /// Position::set_state() computes the hash keys of the position, and other
361 /// data that once computed is updated incrementally as moves are made.
362 /// The function is only used when a new position is set up, and to verify
363 /// the correctness of the StateInfo data when running in debug mode.
365 void Position::set_state(StateInfo* si) const {
367 si->key = si->pawnKey = si->materialKey = 0;
368 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
369 si->psq = SCORE_ZERO;
371 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
373 for (Bitboard b = pieces(); b; )
375 Square s = pop_lsb(&b);
376 Piece pc = piece_on(s);
377 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
378 si->psq += psq[color_of(pc)][type_of(pc)][s];
381 if (ep_square() != SQ_NONE)
382 si->key ^= Zobrist::enpassant[file_of(ep_square())];
384 if (sideToMove == BLACK)
385 si->key ^= Zobrist::side;
387 si->key ^= Zobrist::castling[st->castlingRights];
389 for (Bitboard b = pieces(PAWN); b; )
391 Square s = pop_lsb(&b);
392 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
395 for (Color c = WHITE; c <= BLACK; ++c)
396 for (PieceType pt = PAWN; pt <= KING; ++pt)
397 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
398 si->materialKey ^= Zobrist::psq[c][pt][cnt];
400 for (Color c = WHITE; c <= BLACK; ++c)
401 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
402 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
406 /// Position::fen() returns a FEN representation of the position. In case of
407 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
409 const string Position::fen() const {
412 std::ostringstream ss;
414 for (Rank r = RANK_8; r >= RANK_1; --r)
416 for (File f = FILE_A; f <= FILE_H; ++f)
418 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
425 ss << PieceToChar[piece_on(make_square(f, r))];
432 ss << (sideToMove == WHITE ? " w " : " b ");
434 if (can_castle(WHITE_OO))
435 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | KING_SIDE)) : 'K');
437 if (can_castle(WHITE_OOO))
438 ss << (chess960 ? 'A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE)) : 'Q');
440 if (can_castle(BLACK_OO))
441 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | KING_SIDE)) : 'k');
443 if (can_castle(BLACK_OOO))
444 ss << (chess960 ? 'a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE)) : 'q');
446 if (!can_castle(WHITE) && !can_castle(BLACK))
449 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::format_square(ep_square()) + " ")
450 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
456 /// Position::game_phase() calculates the game phase interpolating total non-pawn
457 /// material between endgame and midgame limits.
459 Phase Position::game_phase() const {
461 Value npm = st->npMaterial[WHITE] + st->npMaterial[BLACK];
463 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
465 return Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));
469 /// Position::check_blockers() returns a bitboard of all the pieces with color
470 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
471 /// blocks a check if removing that piece from the board would result in a
472 /// position where the king is in check. A check blocking piece can be either a
473 /// pinned or a discovered check piece, according if its color 'c' is the same
474 /// or the opposite of 'kingColor'.
476 Bitboard Position::check_blockers(Color c, Color kingColor) const {
478 Bitboard b, pinners, result = 0;
479 Square ksq = king_square(kingColor);
481 // Pinners are sliders that give check when a pinned piece is removed
482 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
483 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
487 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
489 if (!more_than_one(b))
490 result |= b & pieces(c);
496 /// Position::attackers_to() computes a bitboard of all pieces which attack a
497 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
499 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
501 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
502 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
503 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
504 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
505 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
506 | (attacks_from<KING>(s) & pieces(KING));
510 /// Position::legal() tests whether a pseudo-legal move is legal
512 bool Position::legal(Move m, Bitboard pinned) const {
515 assert(pinned == pinned_pieces(sideToMove));
517 Color us = sideToMove;
518 Square from = from_sq(m);
520 assert(color_of(moved_piece(m)) == us);
521 assert(piece_on(king_square(us)) == make_piece(us, KING));
523 // En passant captures are a tricky special case. Because they are rather
524 // uncommon, we do it simply by testing whether the king is attacked after
526 if (type_of(m) == ENPASSANT)
528 Square ksq = king_square(us);
529 Square to = to_sq(m);
530 Square capsq = to - pawn_push(us);
531 Bitboard occ = (pieces() ^ from ^ capsq) | to;
533 assert(to == ep_square());
534 assert(moved_piece(m) == make_piece(us, PAWN));
535 assert(piece_on(capsq) == make_piece(~us, PAWN));
536 assert(piece_on(to) == NO_PIECE);
538 return !(attacks_bb< ROOK>(ksq, occ) & pieces(~us, QUEEN, ROOK))
539 && !(attacks_bb<BISHOP>(ksq, occ) & pieces(~us, QUEEN, BISHOP));
542 // If the moving piece is a king, check whether the destination
543 // square is attacked by the opponent. Castling moves are checked
544 // for legality during move generation.
545 if (type_of(piece_on(from)) == KING)
546 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
548 // A non-king move is legal if and only if it is not pinned or it
549 // is moving along the ray towards or away from the king.
552 || aligned(from, to_sq(m), king_square(us));
556 /// Position::pseudo_legal() takes a random move and tests whether the move is
557 /// pseudo legal. It is used to validate moves from TT that can be corrupted
558 /// due to SMP concurrent access or hash position key aliasing.
560 bool Position::pseudo_legal(const Move m) const {
562 Color us = sideToMove;
563 Square from = from_sq(m);
564 Square to = to_sq(m);
565 Piece pc = moved_piece(m);
567 // Use a slower but simpler function for uncommon cases
568 if (type_of(m) != NORMAL)
569 return MoveList<LEGAL>(*this).contains(m);
571 // Is not a promotion, so promotion piece must be empty
572 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
575 // If the 'from' square is not occupied by a piece belonging to the side to
576 // move, the move is obviously not legal.
577 if (pc == NO_PIECE || color_of(pc) != us)
580 // The destination square cannot be occupied by a friendly piece
584 // Handle the special case of a pawn move
585 if (type_of(pc) == PAWN)
587 // We have already handled promotion moves, so destination
588 // cannot be on the 8th/1st rank.
589 if (rank_of(to) == relative_rank(us, RANK_8))
592 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
594 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
596 && !( (from + 2 * pawn_push(us) == to) // Not a double push
597 && (rank_of(from) == relative_rank(us, RANK_2))
599 && empty(to - pawn_push(us))))
602 else if (!(attacks_from(pc, from) & to))
605 // Evasions generator already takes care to avoid some kind of illegal moves
606 // and legal() relies on this. We therefore have to take care that the same
607 // kind of moves are filtered out here.
610 if (type_of(pc) != KING)
612 // Double check? In this case a king move is required
613 if (more_than_one(checkers()))
616 // Our move must be a blocking evasion or a capture of the checking piece
617 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
620 // In case of king moves under check we have to remove king so as to catch
621 // invalid moves like b1a1 when opposite queen is on c1.
622 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
630 /// Position::gives_check() tests whether a pseudo-legal move gives a check
632 bool Position::gives_check(Move m, const CheckInfo& ci) const {
635 assert(ci.dcCandidates == discovered_check_candidates());
636 assert(color_of(moved_piece(m)) == sideToMove);
638 Square from = from_sq(m);
639 Square to = to_sq(m);
640 PieceType pt = type_of(piece_on(from));
642 // Is there a direct check?
643 if (ci.checkSq[pt] & to)
646 // Is there a discovered check?
647 if ( unlikely(ci.dcCandidates)
648 && (ci.dcCandidates & from)
649 && !aligned(from, to, ci.ksq))
658 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
660 // En passant capture with check? We have already handled the case
661 // of direct checks and ordinary discovered check, so the only case we
662 // need to handle is the unusual case of a discovered check through
663 // the captured pawn.
666 Square capsq = make_square(file_of(to), rank_of(from));
667 Bitboard b = (pieces() ^ from ^ capsq) | to;
669 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
670 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
675 Square rfrom = to; // Castling is encoded as 'King captures the rook'
676 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
677 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
679 return (PseudoAttacks[ROOK][rto] & ci.ksq)
680 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
689 /// Position::do_move() makes a move, and saves all information necessary
690 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
691 /// moves should be filtered out before this function is called.
693 void Position::do_move(Move m, StateInfo& newSt) {
696 do_move(m, newSt, ci, gives_check(m, ci));
699 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
702 assert(&newSt != st);
707 // Copy some fields of the old state to our new StateInfo object except the
708 // ones which are going to be recalculated from scratch anyway and then switch
709 // our state pointer to point to the new (ready to be updated) state.
710 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
715 // Update side to move
718 // Increment ply counters. In particular, rule50 will be reset to zero later on
719 // in case of a capture or a pawn move.
724 Color us = sideToMove;
726 Square from = from_sq(m);
727 Square to = to_sq(m);
728 Piece pc = piece_on(from);
729 PieceType pt = type_of(pc);
730 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
732 assert(color_of(pc) == us);
733 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
734 assert(captured != KING);
736 if (type_of(m) == CASTLING)
738 assert(pc == make_piece(us, KING));
741 do_castling<true>(from, to, rfrom, rto);
743 captured = NO_PIECE_TYPE;
744 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
745 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
752 // If the captured piece is a pawn, update pawn hash key, otherwise
753 // update non-pawn material.
754 if (captured == PAWN)
756 if (type_of(m) == ENPASSANT)
758 capsq += pawn_push(them);
761 assert(to == st->epSquare);
762 assert(relative_rank(us, to) == RANK_6);
763 assert(piece_on(to) == NO_PIECE);
764 assert(piece_on(capsq) == make_piece(them, PAWN));
766 board[capsq] = NO_PIECE;
769 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
772 st->npMaterial[them] -= PieceValue[MG][captured];
774 // Update board and piece lists
775 remove_piece(capsq, them, captured);
777 // Update material hash key and prefetch access to materialTable
778 k ^= Zobrist::psq[them][captured][capsq];
779 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
780 prefetch((char*)thisThread->materialTable[st->materialKey]);
782 // Update incremental scores
783 st->psq -= psq[them][captured][capsq];
785 // Reset rule 50 counter
790 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
792 // Reset en passant square
793 if (st->epSquare != SQ_NONE)
795 k ^= Zobrist::enpassant[file_of(st->epSquare)];
796 st->epSquare = SQ_NONE;
799 // Update castling rights if needed
800 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
802 int cr = castlingRightsMask[from] | castlingRightsMask[to];
803 k ^= Zobrist::castling[st->castlingRights & cr];
804 st->castlingRights &= ~cr;
807 // Move the piece. The tricky Chess960 castling is handled earlier
808 if (type_of(m) != CASTLING)
809 move_piece(from, to, us, pt);
811 // If the moving piece is a pawn do some special extra work
814 // Set en-passant square if the moved pawn can be captured
815 if ( (int(to) ^ int(from)) == 16
816 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
818 st->epSquare = Square((from + to) / 2);
819 k ^= Zobrist::enpassant[file_of(st->epSquare)];
822 else if (type_of(m) == PROMOTION)
824 PieceType promotion = promotion_type(m);
826 assert(relative_rank(us, to) == RANK_8);
827 assert(promotion >= KNIGHT && promotion <= QUEEN);
829 remove_piece(to, us, PAWN);
830 put_piece(to, us, promotion);
833 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
834 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
835 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
836 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
838 // Update incremental score
839 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
842 st->npMaterial[us] += PieceValue[MG][promotion];
845 // Update pawn hash key and prefetch access to pawnsTable
846 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
847 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
849 // Reset rule 50 draw counter
853 // Update incremental scores
854 st->psq += psq[us][pt][to] - psq[us][pt][from];
857 st->capturedType = captured;
859 // Update the key with the final value
862 // Update checkers bitboard: piece must be already moved due to attacks_from()
867 if (type_of(m) != NORMAL)
868 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
872 if (ci.checkSq[pt] & to)
873 st->checkersBB |= to;
876 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
879 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
882 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
887 sideToMove = ~sideToMove;
893 /// Position::undo_move() unmakes a move. When it returns, the position should
894 /// be restored to exactly the same state as before the move was made.
896 void Position::undo_move(Move m) {
900 sideToMove = ~sideToMove;
902 Color us = sideToMove;
903 Square from = from_sq(m);
904 Square to = to_sq(m);
905 PieceType pt = type_of(piece_on(to));
907 assert(empty(from) || type_of(m) == CASTLING);
908 assert(st->capturedType != KING);
910 if (type_of(m) == PROMOTION)
912 assert(pt == promotion_type(m));
913 assert(relative_rank(us, to) == RANK_8);
914 assert(promotion_type(m) >= KNIGHT && promotion_type(m) <= QUEEN);
916 remove_piece(to, us, promotion_type(m));
917 put_piece(to, us, PAWN);
921 if (type_of(m) == CASTLING)
924 do_castling<false>(from, to, rfrom, rto);
928 move_piece(to, from, us, pt); // Put the piece back at the source square
930 if (st->capturedType)
934 if (type_of(m) == ENPASSANT)
936 capsq -= pawn_push(us);
939 assert(to == st->previous->epSquare);
940 assert(relative_rank(us, to) == RANK_6);
941 assert(piece_on(capsq) == NO_PIECE);
944 put_piece(capsq, ~us, st->capturedType); // Restore the captured piece
948 // Finally point our state pointer back to the previous state
956 /// Position::do_castling() is a helper used to do/undo a castling move. This
957 /// is a bit tricky, especially in Chess960.
959 void Position::do_castling(Square from, Square& to, Square& rfrom, Square& rto) {
961 bool kingSide = to > from;
962 rfrom = to; // Castling is encoded as "king captures friendly rook"
963 rto = relative_square(sideToMove, kingSide ? SQ_F1 : SQ_D1);
964 to = relative_square(sideToMove, kingSide ? SQ_G1 : SQ_C1);
966 // Remove both pieces first since squares could overlap in Chess960
967 remove_piece(Do ? from : to, sideToMove, KING);
968 remove_piece(Do ? rfrom : rto, sideToMove, ROOK);
969 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
970 put_piece(Do ? to : from, sideToMove, KING);
971 put_piece(Do ? rto : rfrom, sideToMove, ROOK);
975 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
976 /// the side to move without executing any move on the board.
978 void Position::do_null_move(StateInfo& newSt) {
982 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
987 if (st->epSquare != SQ_NONE)
989 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
990 st->epSquare = SQ_NONE;
993 st->key ^= Zobrist::side;
994 prefetch((char*)TT.first_entry(st->key));
997 st->pliesFromNull = 0;
999 sideToMove = ~sideToMove;
1001 assert(pos_is_ok());
1004 void Position::undo_null_move() {
1006 assert(!checkers());
1009 sideToMove = ~sideToMove;
1013 /// Position::key_after() computes the new hash key after the given moven. Needed
1014 /// for speculative prefetch. It doesn't recognize special moves like castling,
1015 /// en-passant and promotions.
1017 Key Position::key_after(Move m) const {
1019 Color us = sideToMove;
1020 Square from = from_sq(m);
1021 Square to = to_sq(m);
1022 PieceType pt = type_of(piece_on(from));
1023 PieceType captured = type_of(piece_on(to));
1024 Key k = st->key ^ Zobrist::side;
1027 k ^= Zobrist::psq[~us][captured][to];
1029 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
1033 /// Position::see() is a static exchange evaluator: It tries to estimate the
1034 /// material gain or loss resulting from a move.
1036 Value Position::see_sign(Move m) const {
1040 // Early return if SEE cannot be negative because captured piece value
1041 // is not less then capturing one. Note that king moves always return
1042 // here because king midgame value is set to 0.
1043 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1044 return VALUE_KNOWN_WIN;
1049 Value Position::see(Move m) const {
1052 Bitboard occupied, attackers, stmAttackers;
1062 swapList[0] = PieceValue[MG][piece_on(to)];
1063 stm = color_of(piece_on(from));
1064 occupied = pieces() ^ from;
1066 // Castling moves are implemented as king capturing the rook so cannot be
1067 // handled correctly. Simply return 0 that is always the correct value
1068 // unless in the rare case the rook ends up under attack.
1069 if (type_of(m) == CASTLING)
1072 if (type_of(m) == ENPASSANT)
1074 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1075 swapList[0] = PieceValue[MG][PAWN];
1078 // Find all attackers to the destination square, with the moving piece
1079 // removed, but possibly an X-ray attacker added behind it.
1080 attackers = attackers_to(to, occupied) & occupied;
1082 // If the opponent has no attackers we are finished
1084 stmAttackers = attackers & pieces(stm);
1088 // The destination square is defended, which makes things rather more
1089 // difficult to compute. We proceed by building up a "swap list" containing
1090 // the material gain or loss at each stop in a sequence of captures to the
1091 // destination square, where the sides alternately capture, and always
1092 // capture with the least valuable piece. After each capture, we look for
1093 // new X-ray attacks from behind the capturing piece.
1094 captured = type_of(piece_on(from));
1097 assert(slIndex < 32);
1099 // Add the new entry to the swap list
1100 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1102 // Locate and remove the next least valuable attacker
1103 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1105 // Stop before processing a king capture
1106 if (captured == KING)
1108 if (stmAttackers == attackers)
1115 stmAttackers = attackers & pieces(stm);
1118 } while (stmAttackers);
1120 // Having built the swap list, we negamax through it to find the best
1121 // achievable score from the point of view of the side to move.
1123 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1129 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1130 /// rule or repetition. It does not detect stalemates.
1132 bool Position::is_draw() const {
1134 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1137 StateInfo* stp = st;
1138 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1140 stp = stp->previous->previous;
1142 if (stp->key == st->key)
1143 return true; // Draw at first repetition
1150 /// Position::flip() flips position with the white and black sides reversed. This
1151 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1153 static char toggle_case(char c) {
1154 return char(islower(c) ? toupper(c) : tolower(c));
1157 void Position::flip() {
1160 std::stringstream ss(fen());
1162 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1164 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1165 f.insert(0, token + (f.empty() ? " " : "/"));
1168 ss >> token; // Active color
1169 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1171 ss >> token; // Castling availability
1174 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1176 ss >> token; // En passant square
1177 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1179 std::getline(ss, token); // Half and full moves
1182 set(f, is_chess960(), this_thread());
1184 assert(pos_is_ok());
1188 /// Position::pos_is_ok() performs some consistency checks for the position object.
1189 /// This is meant to be helpful when debugging.
1191 bool Position::pos_is_ok(int* step) const {
1193 // Which parts of the position should be verified?
1194 const bool all = false;
1196 const bool testBitboards = all || false;
1197 const bool testState = all || false;
1198 const bool testKingCount = all || false;
1199 const bool testKingCapture = all || false;
1200 const bool testPieceCounts = all || false;
1201 const bool testPieceList = all || false;
1202 const bool testCastlingSquares = all || false;
1207 if ( (sideToMove != WHITE && sideToMove != BLACK)
1208 || piece_on(king_square(WHITE)) != W_KING
1209 || piece_on(king_square(BLACK)) != B_KING
1210 || ( ep_square() != SQ_NONE
1211 && relative_rank(sideToMove, ep_square()) != RANK_6))
1214 if (step && ++*step, testBitboards)
1216 // The intersection of the white and black pieces must be empty
1217 if (pieces(WHITE) & pieces(BLACK))
1220 // The union of the white and black pieces must be equal to all
1222 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1225 // Separate piece type bitboards must have empty intersections
1226 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1227 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1228 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1232 if (step && ++*step, testState)
1236 if ( st->key != si.key
1237 || st->pawnKey != si.pawnKey
1238 || st->materialKey != si.materialKey
1239 || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1240 || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1241 || st->psq != si.psq
1242 || st->checkersBB != si.checkersBB)
1246 if (step && ++*step, testKingCount)
1247 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1248 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1251 if (step && ++*step, testKingCapture)
1252 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1255 if (step && ++*step, testPieceCounts)
1256 for (Color c = WHITE; c <= BLACK; ++c)
1257 for (PieceType pt = PAWN; pt <= KING; ++pt)
1258 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1261 if (step && ++*step, testPieceList)
1262 for (Color c = WHITE; c <= BLACK; ++c)
1263 for (PieceType pt = PAWN; pt <= KING; ++pt)
1264 for (int i = 0; i < pieceCount[c][pt]; ++i)
1265 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1266 || index[pieceList[c][pt][i]] != i)
1269 if (step && ++*step, testCastlingSquares)
1270 for (Color c = WHITE; c <= BLACK; ++c)
1271 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1273 if (!can_castle(c | s))
1276 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1277 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1278 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))