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 static const string PieceToChar(" PNBRQK pnbrqk");
41 Value PieceValue[PHASE_NB][PIECE_NB] = {
42 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
43 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
45 static Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
49 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
50 Key enpassant[FILE_NB];
51 Key castling[CASTLING_RIGHT_NB];
56 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
60 // min_attacker() is a helper function used by see() to locate the least
61 // valuable attacker for the side to move, remove the attacker we just found
62 // from the bitboards and scan for new X-ray attacks behind it.
64 template<int Pt> FORCE_INLINE
65 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
66 Bitboard& occupied, Bitboard& attackers) {
68 Bitboard b = stmAttackers & bb[Pt];
70 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
72 occupied ^= b & ~(b - 1);
74 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
75 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
77 if (Pt == ROOK || Pt == QUEEN)
78 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
80 attackers &= occupied; // After X-ray that may add already processed pieces
84 template<> FORCE_INLINE
85 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
86 return KING; // No need to update bitboards: it is the last cycle
94 CheckInfo::CheckInfo(const Position& pos) {
96 Color them = ~pos.side_to_move();
97 ksq = pos.king_square(them);
99 pinned = pos.pinned_pieces(pos.side_to_move());
100 dcCandidates = pos.discovered_check_candidates();
102 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
103 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
104 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
105 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
106 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
111 /// Position::init() initializes at startup the various arrays used to compute
112 /// hash keys and the piece square tables. The latter is a two-step operation:
113 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
114 /// Secondly, the black halves of the tables are initialized by flipping and
115 /// changing the sign of the white scores.
117 void Position::init() {
121 for (Color c = WHITE; c <= BLACK; ++c)
122 for (PieceType pt = PAWN; pt <= KING; ++pt)
123 for (Square s = SQ_A1; s <= SQ_H8; ++s)
124 Zobrist::psq[c][pt][s] = rk.rand<Key>();
126 for (File f = FILE_A; f <= FILE_H; ++f)
127 Zobrist::enpassant[f] = rk.rand<Key>();
129 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
134 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
135 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
139 Zobrist::side = rk.rand<Key>();
140 Zobrist::exclusion = rk.rand<Key>();
142 for (PieceType pt = PAWN; pt <= KING; ++pt)
144 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
145 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
147 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
149 for (Square s = SQ_A1; s <= SQ_H8; ++s)
151 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
152 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
158 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
159 /// object to not depend on any external data so we detach state pointer from
162 Position& Position::operator=(const Position& pos) {
164 std::memcpy(this, &pos, sizeof(Position));
175 /// Position::clear() erases the position object to a pristine state, with an
176 /// empty board, white to move, and no castling rights.
178 void Position::clear() {
180 std::memset(this, 0, sizeof(Position));
181 startState.epSquare = SQ_NONE;
184 for (int i = 0; i < PIECE_TYPE_NB; ++i)
185 for (int j = 0; j < 16; ++j)
186 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
190 /// Position::set() initializes the position object with the given FEN string.
191 /// This function is not very robust - make sure that input FENs are correct,
192 /// this is assumed to be the responsibility of the GUI.
194 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
196 A FEN string defines a particular position using only the ASCII character set.
198 A FEN string contains six fields separated by a space. The fields are:
200 1) Piece placement (from white's perspective). Each rank is described, starting
201 with rank 8 and ending with rank 1. Within each rank, the contents of each
202 square are described from file A through file H. Following the Standard
203 Algebraic Notation (SAN), each piece is identified by a single letter taken
204 from the standard English names. White pieces are designated using upper-case
205 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
206 noted using digits 1 through 8 (the number of blank squares), and "/"
209 2) Active color. "w" means white moves next, "b" means black.
211 3) Castling availability. If neither side can castle, this is "-". Otherwise,
212 this has one or more letters: "K" (White can castle kingside), "Q" (White
213 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
214 can castle queenside).
216 4) En passant target square (in algebraic notation). If there's no en passant
217 target square, this is "-". If a pawn has just made a 2-square move, this
218 is the position "behind" the pawn. This is recorded regardless of whether
219 there is a pawn in position to make an en passant capture.
221 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
222 or capture. This is used to determine if a draw can be claimed under the
225 6) Fullmove number. The number of the full move. It starts at 1, and is
226 incremented after Black's move.
229 char col, row, token;
232 std::istringstream ss(fenStr);
237 // 1. Piece placement
238 while ((ss >> token) && !isspace(token))
241 sq += Square(token - '0'); // Advance the given number of files
243 else if (token == '/')
246 else if ((idx = PieceToChar.find(token)) != string::npos)
248 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
255 sideToMove = (token == 'w' ? WHITE : BLACK);
258 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
259 // Shredder-FEN that uses the letters of the columns on which the rooks began
260 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
261 // if an inner rook is associated with the castling right, the castling tag is
262 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
263 while ((ss >> token) && !isspace(token))
266 Color c = islower(token) ? BLACK : WHITE;
268 token = char(toupper(token));
271 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
273 else if (token == 'Q')
274 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
276 else if (token >= 'A' && token <= 'H')
277 rsq = File(token - 'A') | relative_rank(c, RANK_1);
282 set_castling_right(c, rsq);
285 // 4. En passant square. Ignore if no pawn capture is possible
286 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
287 && ((ss >> row) && (row == '3' || row == '6')))
289 st->epSquare = File(col - 'a') | Rank(row - '1');
291 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
292 st->epSquare = SQ_NONE;
295 // 5-6. Halfmove clock and fullmove number
296 ss >> std::skipws >> st->rule50 >> gamePly;
298 // Convert from fullmove starting from 1 to ply starting from 0,
299 // handle also common incorrect FEN with fullmove = 0.
300 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
302 chess960 = isChess960;
310 /// Position::set_castling_right() is a helper function used to set castling
311 /// rights given the corresponding color and the rook starting square.
313 void Position::set_castling_right(Color c, Square rfrom) {
315 Square kfrom = king_square(c);
316 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
317 CastlingRight cr = (c | cs);
319 st->castlingRights |= cr;
320 castlingRightsMask[kfrom] |= cr;
321 castlingRightsMask[rfrom] |= cr;
322 castlingRookSquare[cr] = rfrom;
324 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
325 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
327 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
328 if (s != kfrom && s != rfrom)
329 castlingPath[cr] |= s;
331 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
332 if (s != kfrom && s != rfrom)
333 castlingPath[cr] |= s;
337 /// Position::set_state() computes the hash keys of the position, and other
338 /// data that once computed is updated incrementally as moves are made.
339 /// The function is only used when a new position is set up, and to verify
340 /// the correctness of the StateInfo data when running in debug mode.
342 void Position::set_state(StateInfo* si) const {
344 si->key = si->pawnKey = si->materialKey = 0;
345 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
346 si->psq = SCORE_ZERO;
348 si->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
350 for (Bitboard b = pieces(); b; )
352 Square s = pop_lsb(&b);
353 Piece pc = piece_on(s);
354 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
355 si->psq += psq[color_of(pc)][type_of(pc)][s];
358 if (ep_square() != SQ_NONE)
359 si->key ^= Zobrist::enpassant[file_of(ep_square())];
361 if (sideToMove == BLACK)
362 si->key ^= Zobrist::side;
364 si->key ^= Zobrist::castling[st->castlingRights];
366 for (Bitboard b = pieces(PAWN); b; )
368 Square s = pop_lsb(&b);
369 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
372 for (Color c = WHITE; c <= BLACK; ++c)
373 for (PieceType pt = PAWN; pt <= KING; ++pt)
374 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
375 si->materialKey ^= Zobrist::psq[c][pt][cnt];
377 for (Color c = WHITE; c <= BLACK; ++c)
378 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
379 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
383 /// Position::fen() returns a FEN representation of the position. In case of
384 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
386 const string Position::fen() const {
389 std::ostringstream ss;
391 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
393 for (File file = FILE_A; file <= FILE_H; ++file)
395 for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file)
402 ss << PieceToChar[piece_on(file | rank)];
409 ss << (sideToMove == WHITE ? " w " : " b ");
411 if (can_castle(WHITE_OO))
412 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | KING_SIDE)), false) : 'K');
414 if (can_castle(WHITE_OOO))
415 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | QUEEN_SIDE)), false) : 'Q');
417 if (can_castle(BLACK_OO))
418 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | KING_SIDE)), true) : 'k');
420 if (can_castle(BLACK_OOO))
421 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | QUEEN_SIDE)), true) : 'q');
423 if (!can_castle(WHITE) && !can_castle(BLACK))
426 ss << (ep_square() == SQ_NONE ? " - " : " " + to_string(ep_square()) + " ")
427 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
433 /// Position::pretty() returns an ASCII representation of the position to be
434 /// printed to the standard output together with the move's san notation.
436 const string Position::pretty(Move move) const {
438 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
439 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
440 + dottedLine + "\n| . | | . | | . | | . | |";
442 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
444 for (Bitboard b = pieces(); b; )
446 Square s = pop_lsb(&b);
447 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
450 std::ostringstream ss;
453 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
454 << move_to_san(*const_cast<Position*>(this), move);
456 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
457 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
459 for (Bitboard b = checkers(); b; )
460 ss << to_string(pop_lsb(&b)) << " ";
462 ss << "\nLegal moves: ";
463 for (MoveList<LEGAL> it(*this); *it; ++it)
464 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
470 /// Position::check_blockers() returns a bitboard of all the pieces with color
471 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
472 /// blocks a check if removing that piece from the board would result in a
473 /// position where the king is in check. A check blocking piece can be either a
474 /// pinned or a discovered check piece, according if its color 'c' is the same
475 /// or the opposite of 'kingColor'.
477 Bitboard Position::check_blockers(Color c, Color kingColor) const {
479 Bitboard b, pinners, result = 0;
480 Square ksq = king_square(kingColor);
482 // Pinners are sliders that give check when a pinned piece is removed
483 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
484 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
488 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
490 if (!more_than_one(b))
491 result |= b & pieces(c);
497 /// Position::attackers_to() computes a bitboard of all pieces which attack a
498 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
500 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
502 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
503 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
504 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
505 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
506 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
507 | (attacks_from<KING>(s) & pieces(KING));
511 /// Position::legal() tests whether a pseudo-legal move is legal
513 bool Position::legal(Move m, Bitboard pinned) const {
516 assert(pinned == pinned_pieces(sideToMove));
518 Color us = sideToMove;
519 Square from = from_sq(m);
521 assert(color_of(moved_piece(m)) == us);
522 assert(piece_on(king_square(us)) == make_piece(us, KING));
524 // En passant captures are a tricky special case. Because they are rather
525 // uncommon, we do it simply by testing whether the king is attacked after
527 if (type_of(m) == ENPASSANT)
530 Square to = to_sq(m);
531 Square capsq = to + pawn_push(them);
532 Square ksq = king_square(us);
533 Bitboard b = (pieces() ^ from ^ capsq) | to;
535 assert(to == ep_square());
536 assert(moved_piece(m) == make_piece(us, PAWN));
537 assert(piece_on(capsq) == make_piece(them, PAWN));
538 assert(piece_on(to) == NO_PIECE);
540 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
541 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
544 // If the moving piece is a king, check whether the destination
545 // square is attacked by the opponent. Castling moves are checked
546 // for legality during move generation.
547 if (type_of(piece_on(from)) == KING)
548 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
550 // A non-king move is legal if and only if it is not pinned or it
551 // is moving along the ray towards or away from the king.
554 || aligned(from, to_sq(m), king_square(us));
558 /// Position::pseudo_legal() takes a random move and tests whether the move is
559 /// pseudo legal. It is used to validate moves from TT that can be corrupted
560 /// due to SMP concurrent access or hash position key aliasing.
562 bool Position::pseudo_legal(const Move m) const {
564 Color us = sideToMove;
565 Square from = from_sq(m);
566 Square to = to_sq(m);
567 Piece pc = moved_piece(m);
569 // Use a slower but simpler function for uncommon cases
570 if (type_of(m) != NORMAL)
571 return MoveList<LEGAL>(*this).contains(m);
573 // Is not a promotion, so promotion piece must be empty
574 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
577 // If the 'from' square is not occupied by a piece belonging to the side to
578 // move, the move is obviously not legal.
579 if (pc == NO_PIECE || color_of(pc) != us)
582 // The destination square cannot be occupied by a friendly piece
586 // Handle the special case of a pawn move
587 if (type_of(pc) == PAWN)
589 // We have already handled promotion moves, so destination
590 // cannot be on the 8th/1st rank.
591 if (rank_of(to) == relative_rank(us, RANK_8))
594 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
596 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
598 && !( (from + 2 * pawn_push(us) == to) // Not a double push
599 && (rank_of(from) == relative_rank(us, RANK_2))
601 && empty(to - pawn_push(us))))
604 else if (!(attacks_from(pc, from) & to))
607 // Evasions generator already takes care to avoid some kind of illegal moves
608 // and legal() relies on this. We therefore have to take care that the same
609 // kind of moves are filtered out here.
612 if (type_of(pc) != KING)
614 // Double check? In this case a king move is required
615 if (more_than_one(checkers()))
618 // Our move must be a blocking evasion or a capture of the checking piece
619 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
622 // In case of king moves under check we have to remove king so as to catch
623 // invalid moves like b1a1 when opposite queen is on c1.
624 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
632 /// Position::gives_check() tests whether a pseudo-legal move gives a check
634 bool Position::gives_check(Move m, const CheckInfo& ci) const {
637 assert(ci.dcCandidates == discovered_check_candidates());
638 assert(color_of(moved_piece(m)) == sideToMove);
640 Square from = from_sq(m);
641 Square to = to_sq(m);
642 PieceType pt = type_of(piece_on(from));
644 // Is there a direct check?
645 if (ci.checkSq[pt] & to)
648 // Is there a discovered check?
649 if ( unlikely(ci.dcCandidates)
650 && (ci.dcCandidates & from)
651 && !aligned(from, to, ci.ksq))
660 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
662 // En passant capture with check? We have already handled the case
663 // of direct checks and ordinary discovered check, so the only case we
664 // need to handle is the unusual case of a discovered check through
665 // the captured pawn.
668 Square capsq = file_of(to) | rank_of(from);
669 Bitboard b = (pieces() ^ from ^ capsq) | to;
671 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
672 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
677 Square rfrom = to; // Castling is encoded as 'King captures the rook'
678 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
679 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
681 return (PseudoAttacks[ROOK][rto] & ci.ksq)
682 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
691 /// Position::do_move() makes a move, and saves all information necessary
692 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
693 /// moves should be filtered out before this function is called.
695 void Position::do_move(Move m, StateInfo& newSt) {
698 do_move(m, newSt, ci, gives_check(m, ci));
701 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
704 assert(&newSt != st);
709 // Copy some fields of the old state to our new StateInfo object except the
710 // ones which are going to be recalculated from scratch anyway and then switch
711 // our state pointer to point to the new (ready to be updated) state.
712 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
717 // Update side to move
720 // Increment ply counters. In particular, rule50 will be reset to zero later on
721 // in case of a capture or a pawn move.
726 Color us = sideToMove;
728 Square from = from_sq(m);
729 Square to = to_sq(m);
730 Piece pc = piece_on(from);
731 PieceType pt = type_of(pc);
732 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
734 assert(color_of(pc) == us);
735 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
736 assert(captured != KING);
738 if (type_of(m) == CASTLING)
740 assert(pc == make_piece(us, KING));
742 bool kingSide = to > from;
743 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
744 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
745 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
746 captured = NO_PIECE_TYPE;
748 do_castling(from, to, rfrom, rto);
750 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
751 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
758 // If the captured piece is a pawn, update pawn hash key, otherwise
759 // update non-pawn material.
760 if (captured == PAWN)
762 if (type_of(m) == ENPASSANT)
764 capsq += pawn_push(them);
767 assert(to == st->epSquare);
768 assert(relative_rank(us, to) == RANK_6);
769 assert(piece_on(to) == NO_PIECE);
770 assert(piece_on(capsq) == make_piece(them, PAWN));
772 board[capsq] = NO_PIECE;
775 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
778 st->npMaterial[them] -= PieceValue[MG][captured];
780 // Update board and piece lists
781 remove_piece(capsq, them, captured);
783 // Update material hash key and prefetch access to materialTable
784 k ^= Zobrist::psq[them][captured][capsq];
785 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
786 prefetch((char*)thisThread->materialTable[st->materialKey]);
788 // Update incremental scores
789 st->psq -= psq[them][captured][capsq];
791 // Reset rule 50 counter
796 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
798 // Reset en passant square
799 if (st->epSquare != SQ_NONE)
801 k ^= Zobrist::enpassant[file_of(st->epSquare)];
802 st->epSquare = SQ_NONE;
805 // Update castling rights if needed
806 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
808 int cr = castlingRightsMask[from] | castlingRightsMask[to];
809 k ^= Zobrist::castling[st->castlingRights & cr];
810 st->castlingRights &= ~cr;
813 // Prefetch TT access as soon as we know the new hash key
814 prefetch((char*)TT.first_entry(k));
816 // Move the piece. The tricky Chess960 castling is handled earlier
817 if (type_of(m) != CASTLING)
818 move_piece(from, to, us, pt);
820 // If the moving piece is a pawn do some special extra work
823 // Set en-passant square if the moved pawn can be captured
824 if ( (int(to) ^ int(from)) == 16
825 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
827 st->epSquare = Square((from + to) / 2);
828 k ^= Zobrist::enpassant[file_of(st->epSquare)];
831 if (type_of(m) == PROMOTION)
833 PieceType promotion = promotion_type(m);
835 assert(relative_rank(us, to) == RANK_8);
836 assert(promotion >= KNIGHT && promotion <= QUEEN);
838 remove_piece(to, us, PAWN);
839 put_piece(to, us, promotion);
842 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
843 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
844 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
845 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
847 // Update incremental score
848 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
851 st->npMaterial[us] += PieceValue[MG][promotion];
854 // Update pawn hash key and prefetch access to pawnsTable
855 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
856 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
858 // Reset rule 50 draw counter
862 // Update incremental scores
863 st->psq += psq[us][pt][to] - psq[us][pt][from];
866 st->capturedType = captured;
868 // Update the key with the final value
871 // Update checkers bitboard: piece must be already moved
876 if (type_of(m) != NORMAL)
877 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
881 if (ci.checkSq[pt] & to)
882 st->checkersBB |= to;
885 if (ci.dcCandidates && (ci.dcCandidates & from))
888 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
891 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
896 sideToMove = ~sideToMove;
902 /// Position::undo_move() unmakes a move. When it returns, the position should
903 /// be restored to exactly the same state as before the move was made.
905 void Position::undo_move(Move m) {
909 sideToMove = ~sideToMove;
911 Color us = sideToMove;
913 Square from = from_sq(m);
914 Square to = to_sq(m);
915 PieceType pt = type_of(piece_on(to));
916 PieceType captured = st->capturedType;
918 assert(empty(from) || type_of(m) == CASTLING);
919 assert(captured != KING);
921 if (type_of(m) == PROMOTION)
923 PieceType promotion = promotion_type(m);
925 assert(promotion == pt);
926 assert(relative_rank(us, to) == RANK_8);
927 assert(promotion >= KNIGHT && promotion <= QUEEN);
929 remove_piece(to, us, promotion);
930 put_piece(to, us, PAWN);
934 if (type_of(m) == CASTLING)
936 bool kingSide = to > from;
937 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
938 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
939 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
940 captured = NO_PIECE_TYPE;
942 do_castling(to, from, rto, rfrom);
945 move_piece(to, from, us, pt); // Put the piece back at the source square
951 if (type_of(m) == ENPASSANT)
953 capsq -= pawn_push(us);
956 assert(to == st->previous->epSquare);
957 assert(relative_rank(us, to) == RANK_6);
958 assert(piece_on(capsq) == NO_PIECE);
961 put_piece(capsq, them, captured); // Restore the captured piece
964 // Finally point our state pointer back to the previous state
972 /// Position::do_castling() is a helper used to do/undo a castling move. This
973 /// is a bit tricky, especially in Chess960.
975 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
977 // Remove both pieces first since squares could overlap in Chess960
978 remove_piece(kfrom, sideToMove, KING);
979 remove_piece(rfrom, sideToMove, ROOK);
980 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
981 put_piece(kto, sideToMove, KING);
982 put_piece(rto, sideToMove, ROOK);
986 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
987 /// the side to move without executing any move on the board.
989 void Position::do_null_move(StateInfo& newSt) {
993 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
998 if (st->epSquare != SQ_NONE)
1000 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1001 st->epSquare = SQ_NONE;
1004 st->key ^= Zobrist::side;
1005 prefetch((char*)TT.first_entry(st->key));
1008 st->pliesFromNull = 0;
1010 sideToMove = ~sideToMove;
1012 assert(pos_is_ok());
1015 void Position::undo_null_move() {
1017 assert(!checkers());
1020 sideToMove = ~sideToMove;
1024 /// Position::see() is a static exchange evaluator: It tries to estimate the
1025 /// material gain or loss resulting from a move.
1027 Value Position::see_sign(Move m) const {
1031 // Early return if SEE cannot be negative because captured piece value
1032 // is not less then capturing one. Note that king moves always return
1033 // here because king midgame value is set to 0.
1034 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1035 return VALUE_KNOWN_WIN;
1040 Value Position::see(Move m) const {
1043 Bitboard occupied, attackers, stmAttackers;
1053 swapList[0] = PieceValue[MG][piece_on(to)];
1054 stm = color_of(piece_on(from));
1055 occupied = pieces() ^ from;
1057 // Castling moves are implemented as king capturing the rook so cannot be
1058 // handled correctly. Simply return 0 that is always the correct value
1059 // unless in the rare case the rook ends up under attack.
1060 if (type_of(m) == CASTLING)
1063 if (type_of(m) == ENPASSANT)
1065 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1066 swapList[0] = PieceValue[MG][PAWN];
1069 // Find all attackers to the destination square, with the moving piece
1070 // removed, but possibly an X-ray attacker added behind it.
1071 attackers = attackers_to(to, occupied) & occupied;
1073 // If the opponent has no attackers we are finished
1075 stmAttackers = attackers & pieces(stm);
1079 // The destination square is defended, which makes things rather more
1080 // difficult to compute. We proceed by building up a "swap list" containing
1081 // the material gain or loss at each stop in a sequence of captures to the
1082 // destination square, where the sides alternately capture, and always
1083 // capture with the least valuable piece. After each capture, we look for
1084 // new X-ray attacks from behind the capturing piece.
1085 captured = type_of(piece_on(from));
1088 assert(slIndex < 32);
1090 // Add the new entry to the swap list
1091 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1093 // Locate and remove the next least valuable attacker
1094 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1096 // Stop before processing a king capture
1097 if (captured == KING)
1099 if (stmAttackers == attackers)
1106 stmAttackers = attackers & pieces(stm);
1109 } while (stmAttackers);
1111 // Having built the swap list, we negamax through it to find the best
1112 // achievable score from the point of view of the side to move.
1114 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1120 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1121 /// rule or repetition. It does not detect stalemates.
1123 bool Position::is_draw() const {
1126 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1129 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1132 StateInfo* stp = st;
1133 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1135 stp = stp->previous->previous;
1137 if (stp->key == st->key)
1138 return true; // Draw at first repetition
1145 /// Position::flip() flips position with the white and black sides reversed. This
1146 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1148 static char toggle_case(char c) {
1149 return char(islower(c) ? toupper(c) : tolower(c));
1152 void Position::flip() {
1155 std::stringstream ss(fen());
1157 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1159 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1160 f.insert(0, token + (f.empty() ? " " : "/"));
1163 ss >> token; // Active color
1164 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1166 ss >> token; // Castling availability
1169 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1171 ss >> token; // En passant square
1172 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1174 std::getline(ss, token); // Half and full moves
1177 set(f, is_chess960(), this_thread());
1179 assert(pos_is_ok());
1183 /// Position::pos_is_ok() performs some consistency checks for the position object.
1184 /// This is meant to be helpful when debugging.
1186 bool Position::pos_is_ok(int* failedStep) const {
1188 int dummy, *step = failedStep ? failedStep : &dummy;
1190 // What features of the position should be verified?
1191 const bool all = false;
1193 const bool testBitboards = all || false;
1194 const bool testKingCount = all || false;
1195 const bool testKingCapture = all || false;
1196 const bool testState = all || false;
1197 const bool testCheckerCount = all || false;
1198 const bool testPieceCounts = all || false;
1199 const bool testPieceList = all || false;
1200 const bool testCastlingSquares = all || false;
1202 if (*step = 1, sideToMove != WHITE && sideToMove != BLACK)
1205 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1208 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1211 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1214 if ((*step)++, testKingCount)
1215 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1216 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1219 if ((*step)++, testKingCapture)
1220 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1223 if ((*step)++, testBitboards)
1225 // The intersection of the white and black pieces must be empty
1226 if (pieces(WHITE) & pieces(BLACK))
1229 // The union of the white and black pieces must be equal to all
1231 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1234 // Separate piece type bitboards must have empty intersections
1235 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1236 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1237 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1241 if ((*step)++, testState)
1245 if ( st->key != si.key
1246 || st->pawnKey != si.pawnKey
1247 || st->materialKey != si.materialKey
1248 || st->npMaterial[WHITE] != si.npMaterial[WHITE]
1249 || st->npMaterial[BLACK] != si.npMaterial[BLACK]
1250 || st->psq != si.psq)
1254 if ((*step)++, testCheckerCount && popcount<Full>(st->checkersBB) > 2)
1257 if ((*step)++, testPieceCounts)
1258 for (Color c = WHITE; c <= BLACK; ++c)
1259 for (PieceType pt = PAWN; pt <= KING; ++pt)
1260 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1263 if ((*step)++, testPieceList)
1264 for (Color c = WHITE; c <= BLACK; ++c)
1265 for (PieceType pt = PAWN; pt <= KING; ++pt)
1266 for (int i = 0; i < pieceCount[c][pt]; ++i)
1267 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1268 || index[pieceList[c][pt][i]] != i)
1271 if ((*step)++, testCastlingSquares)
1272 for (Color c = WHITE; c <= BLACK; ++c)
1273 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1275 if (!can_castle(c | s))
1278 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1279 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1280 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))