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::set() initializes the position object with the given FEN string.
176 /// This function is not very robust - make sure that input FENs are correct,
177 /// this is assumed to be the responsibility of the GUI.
179 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
181 A FEN string defines a particular position using only the ASCII character set.
183 A FEN string contains six fields separated by a space. The fields are:
185 1) Piece placement (from white's perspective). Each rank is described, starting
186 with rank 8 and ending with rank 1. Within each rank, the contents of each
187 square are described from file A through file H. Following the Standard
188 Algebraic Notation (SAN), each piece is identified by a single letter taken
189 from the standard English names. White pieces are designated using upper-case
190 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
191 noted using digits 1 through 8 (the number of blank squares), and "/"
194 2) Active color. "w" means white moves next, "b" means black.
196 3) Castling availability. If neither side can castle, this is "-". Otherwise,
197 this has one or more letters: "K" (White can castle kingside), "Q" (White
198 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
199 can castle queenside).
201 4) En passant target square (in algebraic notation). If there's no en passant
202 target square, this is "-". If a pawn has just made a 2-square move, this
203 is the position "behind" the pawn. This is recorded regardless of whether
204 there is a pawn in position to make an en passant capture.
206 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
207 or capture. This is used to determine if a draw can be claimed under the
210 6) Fullmove number. The number of the full move. It starts at 1, and is
211 incremented after Black's move.
214 char col, row, token;
217 std::istringstream ss(fenStr);
222 // 1. Piece placement
223 while ((ss >> token) && !isspace(token))
226 sq += Square(token - '0'); // Advance the given number of files
228 else if (token == '/')
231 else if ((idx = PieceToChar.find(token)) != string::npos)
233 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
240 sideToMove = (token == 'w' ? WHITE : BLACK);
243 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
244 // Shredder-FEN that uses the letters of the columns on which the rooks began
245 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
246 // if an inner rook is associated with the castling right, the castling tag is
247 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
248 while ((ss >> token) && !isspace(token))
251 Color c = islower(token) ? BLACK : WHITE;
253 token = char(toupper(token));
256 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
258 else if (token == 'Q')
259 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
261 else if (token >= 'A' && token <= 'H')
262 rsq = File(token - 'A') | relative_rank(c, RANK_1);
267 set_castling_right(c, rsq);
270 // 4. En passant square. Ignore if no pawn capture is possible
271 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
272 && ((ss >> row) && (row == '3' || row == '6')))
274 st->epSquare = File(col - 'a') | Rank(row - '1');
276 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
277 st->epSquare = SQ_NONE;
280 // 5-6. Halfmove clock and fullmove number
281 ss >> std::skipws >> st->rule50 >> gamePly;
283 // Convert from fullmove starting from 1 to ply starting from 0,
284 // handle also common incorrect FEN with fullmove = 0.
285 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
287 st->key = compute_key();
288 st->pawnKey = compute_pawn_key();
289 st->materialKey = compute_material_key();
290 st->psq = compute_psq_score();
291 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
292 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
293 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
294 chess960 = isChess960;
301 /// Position::set_castling_right() is a helper function used to set castling
302 /// rights given the corresponding color and the rook starting square.
304 void Position::set_castling_right(Color c, Square rfrom) {
306 Square kfrom = king_square(c);
307 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
308 CastlingRight cr = (c | cs);
310 st->castlingRights |= cr;
311 castlingRightsMask[kfrom] |= cr;
312 castlingRightsMask[rfrom] |= cr;
313 castlingRookSquare[cr] = rfrom;
315 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
316 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
318 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
319 if (s != kfrom && s != rfrom)
320 castlingPath[cr] |= s;
322 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
323 if (s != kfrom && s != rfrom)
324 castlingPath[cr] |= s;
328 /// Position::fen() returns a FEN representation of the position. In case of
329 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
331 const string Position::fen() const {
334 std::ostringstream ss;
336 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
338 for (File file = FILE_A; file <= FILE_H; ++file)
340 for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file)
347 ss << PieceToChar[piece_on(file | rank)];
354 ss << (sideToMove == WHITE ? " w " : " b ");
356 if (can_castle(WHITE_OO))
357 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | KING_SIDE)), false) : 'K');
359 if (can_castle(WHITE_OOO))
360 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | QUEEN_SIDE)), false) : 'Q');
362 if (can_castle(BLACK_OO))
363 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | KING_SIDE)), true) : 'k');
365 if (can_castle(BLACK_OOO))
366 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | QUEEN_SIDE)), true) : 'q');
368 if (!can_castle(WHITE) && !can_castle(BLACK))
371 ss << (ep_square() == SQ_NONE ? " - " : " " + to_string(ep_square()) + " ")
372 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
378 /// Position::pretty() returns an ASCII representation of the position to be
379 /// printed to the standard output together with the move's san notation.
381 const string Position::pretty(Move move) const {
383 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
384 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
385 + dottedLine + "\n| . | | . | | . | | . | |";
387 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
389 for (Bitboard b = pieces(); b; )
391 Square s = pop_lsb(&b);
392 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
395 std::ostringstream ss;
398 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
399 << move_to_san(*const_cast<Position*>(this), move);
401 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
402 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
404 for (Bitboard b = checkers(); b; )
405 ss << to_string(pop_lsb(&b)) << " ";
407 ss << "\nLegal moves: ";
408 for (MoveList<LEGAL> it(*this); *it; ++it)
409 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
415 /// Position::check_blockers() returns a bitboard of all the pieces with color
416 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
417 /// blocks a check if removing that piece from the board would result in a
418 /// position where the king is in check. A check blocking piece can be either a
419 /// pinned or a discovered check piece, according if its color 'c' is the same
420 /// or the opposite of 'kingColor'.
422 Bitboard Position::check_blockers(Color c, Color kingColor) const {
424 Bitboard b, pinners, result = 0;
425 Square ksq = king_square(kingColor);
427 // Pinners are sliders that give check when a pinned piece is removed
428 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
429 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
433 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
435 if (!more_than_one(b))
436 result |= b & pieces(c);
442 /// Position::attackers_to() computes a bitboard of all pieces which attack a
443 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
445 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
447 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
448 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
449 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
450 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
451 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
452 | (attacks_from<KING>(s) & pieces(KING));
456 /// Position::legal() tests whether a pseudo-legal move is legal
458 bool Position::legal(Move m, Bitboard pinned) const {
461 assert(pinned == pinned_pieces(sideToMove));
463 Color us = sideToMove;
464 Square from = from_sq(m);
466 assert(color_of(moved_piece(m)) == us);
467 assert(piece_on(king_square(us)) == make_piece(us, KING));
469 // En passant captures are a tricky special case. Because they are rather
470 // uncommon, we do it simply by testing whether the king is attacked after
472 if (type_of(m) == ENPASSANT)
475 Square to = to_sq(m);
476 Square capsq = to + pawn_push(them);
477 Square ksq = king_square(us);
478 Bitboard b = (pieces() ^ from ^ capsq) | to;
480 assert(to == ep_square());
481 assert(moved_piece(m) == make_piece(us, PAWN));
482 assert(piece_on(capsq) == make_piece(them, PAWN));
483 assert(piece_on(to) == NO_PIECE);
485 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
486 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
489 // If the moving piece is a king, check whether the destination
490 // square is attacked by the opponent. Castling moves are checked
491 // for legality during move generation.
492 if (type_of(piece_on(from)) == KING)
493 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
495 // A non-king move is legal if and only if it is not pinned or it
496 // is moving along the ray towards or away from the king.
499 || aligned(from, to_sq(m), king_square(us));
503 /// Position::pseudo_legal() takes a random move and tests whether the move is
504 /// pseudo legal. It is used to validate moves from TT that can be corrupted
505 /// due to SMP concurrent access or hash position key aliasing.
507 bool Position::pseudo_legal(const Move m) const {
509 Color us = sideToMove;
510 Square from = from_sq(m);
511 Square to = to_sq(m);
512 Piece pc = moved_piece(m);
514 // Use a slower but simpler function for uncommon cases
515 if (type_of(m) != NORMAL)
516 return MoveList<LEGAL>(*this).contains(m);
518 // Is not a promotion, so promotion piece must be empty
519 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
522 // If the 'from' square is not occupied by a piece belonging to the side to
523 // move, the move is obviously not legal.
524 if (pc == NO_PIECE || color_of(pc) != us)
527 // The destination square cannot be occupied by a friendly piece
531 // Handle the special case of a pawn move
532 if (type_of(pc) == PAWN)
534 // We have already handled promotion moves, so destination
535 // cannot be on the 8th/1st rank.
536 if (rank_of(to) == relative_rank(us, RANK_8))
539 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
541 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
543 && !( (from + 2 * pawn_push(us) == to) // Not a double push
544 && (rank_of(from) == relative_rank(us, RANK_2))
546 && empty(to - pawn_push(us))))
549 else if (!(attacks_from(pc, from) & to))
552 // Evasions generator already takes care to avoid some kind of illegal moves
553 // and legal() relies on this. We therefore have to take care that the same
554 // kind of moves are filtered out here.
557 if (type_of(pc) != KING)
559 // Double check? In this case a king move is required
560 if (more_than_one(checkers()))
563 // Our move must be a blocking evasion or a capture of the checking piece
564 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
567 // In case of king moves under check we have to remove king so as to catch
568 // invalid moves like b1a1 when opposite queen is on c1.
569 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
577 /// Position::gives_check() tests whether a pseudo-legal move gives a check
579 bool Position::gives_check(Move m, const CheckInfo& ci) const {
582 assert(ci.dcCandidates == discovered_check_candidates());
583 assert(color_of(moved_piece(m)) == sideToMove);
585 Square from = from_sq(m);
586 Square to = to_sq(m);
587 PieceType pt = type_of(piece_on(from));
589 // Is there a direct check?
590 if (ci.checkSq[pt] & to)
593 // Is there a discovered check?
594 if ( unlikely(ci.dcCandidates)
595 && (ci.dcCandidates & from)
596 && !aligned(from, to, ci.ksq))
605 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
607 // En passant capture with check? We have already handled the case
608 // of direct checks and ordinary discovered check, so the only case we
609 // need to handle is the unusual case of a discovered check through
610 // the captured pawn.
613 Square capsq = file_of(to) | rank_of(from);
614 Bitboard b = (pieces() ^ from ^ capsq) | to;
616 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
617 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
622 Square rfrom = to; // Castling is encoded as 'King captures the rook'
623 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
624 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
626 return (PseudoAttacks[ROOK][rto] & ci.ksq)
627 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
636 /// Position::do_move() makes a move, and saves all information necessary
637 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
638 /// moves should be filtered out before this function is called.
640 void Position::do_move(Move m, StateInfo& newSt) {
643 do_move(m, newSt, ci, gives_check(m, ci));
646 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
649 assert(&newSt != st);
654 // Copy some fields of the old state to our new StateInfo object except the
655 // ones which are going to be recalculated from scratch anyway and then switch
656 // our state pointer to point to the new (ready to be updated) state.
657 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
662 // Update side to move
665 // Increment ply counters. In particular, rule50 will be reset to zero later on
666 // in case of a capture or a pawn move.
671 Color us = sideToMove;
673 Square from = from_sq(m);
674 Square to = to_sq(m);
675 Piece pc = piece_on(from);
676 PieceType pt = type_of(pc);
677 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
679 assert(color_of(pc) == us);
680 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
681 assert(captured != KING);
683 if (type_of(m) == CASTLING)
685 assert(pc == make_piece(us, KING));
687 bool kingSide = to > from;
688 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
689 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
690 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
691 captured = NO_PIECE_TYPE;
693 do_castling(from, to, rfrom, rto);
695 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
696 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
703 // If the captured piece is a pawn, update pawn hash key, otherwise
704 // update non-pawn material.
705 if (captured == PAWN)
707 if (type_of(m) == ENPASSANT)
709 capsq += pawn_push(them);
712 assert(to == st->epSquare);
713 assert(relative_rank(us, to) == RANK_6);
714 assert(piece_on(to) == NO_PIECE);
715 assert(piece_on(capsq) == make_piece(them, PAWN));
717 board[capsq] = NO_PIECE;
720 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
723 st->npMaterial[them] -= PieceValue[MG][captured];
725 // Update board and piece lists
726 remove_piece(capsq, them, captured);
728 // Update material hash key and prefetch access to materialTable
729 k ^= Zobrist::psq[them][captured][capsq];
730 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
731 prefetch((char*)thisThread->materialTable[st->materialKey]);
733 // Update incremental scores
734 st->psq -= psq[them][captured][capsq];
736 // Reset rule 50 counter
741 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
743 // Reset en passant square
744 if (st->epSquare != SQ_NONE)
746 k ^= Zobrist::enpassant[file_of(st->epSquare)];
747 st->epSquare = SQ_NONE;
750 // Update castling rights if needed
751 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
753 int cr = castlingRightsMask[from] | castlingRightsMask[to];
754 k ^= Zobrist::castling[st->castlingRights & cr];
755 st->castlingRights &= ~cr;
758 // Prefetch TT access as soon as we know the new hash key
759 prefetch((char*)TT.first_entry(k));
761 // Move the piece. The tricky Chess960 castling is handled earlier
762 if (type_of(m) != CASTLING)
763 move_piece(from, to, us, pt);
765 // If the moving piece is a pawn do some special extra work
768 // Set en-passant square if the moved pawn can be captured
769 if ( (int(to) ^ int(from)) == 16
770 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
772 st->epSquare = Square((from + to) / 2);
773 k ^= Zobrist::enpassant[file_of(st->epSquare)];
776 if (type_of(m) == PROMOTION)
778 PieceType promotion = promotion_type(m);
780 assert(relative_rank(us, to) == RANK_8);
781 assert(promotion >= KNIGHT && promotion <= QUEEN);
783 remove_piece(to, us, PAWN);
784 put_piece(to, us, promotion);
787 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
788 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
789 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
790 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
792 // Update incremental score
793 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
796 st->npMaterial[us] += PieceValue[MG][promotion];
799 // Update pawn hash key and prefetch access to pawnsTable
800 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
801 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
803 // Reset rule 50 draw counter
807 // Update incremental scores
808 st->psq += psq[us][pt][to] - psq[us][pt][from];
811 st->capturedType = captured;
813 // Update the key with the final value
816 // Update checkers bitboard: piece must be already moved
821 if (type_of(m) != NORMAL)
822 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
826 if (ci.checkSq[pt] & to)
827 st->checkersBB |= to;
830 if (ci.dcCandidates && (ci.dcCandidates & from))
833 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
836 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
841 sideToMove = ~sideToMove;
847 /// Position::undo_move() unmakes a move. When it returns, the position should
848 /// be restored to exactly the same state as before the move was made.
850 void Position::undo_move(Move m) {
854 sideToMove = ~sideToMove;
856 Color us = sideToMove;
858 Square from = from_sq(m);
859 Square to = to_sq(m);
860 PieceType pt = type_of(piece_on(to));
861 PieceType captured = st->capturedType;
863 assert(empty(from) || type_of(m) == CASTLING);
864 assert(captured != KING);
866 if (type_of(m) == PROMOTION)
868 PieceType promotion = promotion_type(m);
870 assert(promotion == pt);
871 assert(relative_rank(us, to) == RANK_8);
872 assert(promotion >= KNIGHT && promotion <= QUEEN);
874 remove_piece(to, us, promotion);
875 put_piece(to, us, PAWN);
879 if (type_of(m) == CASTLING)
881 bool kingSide = to > from;
882 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
883 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
884 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
885 captured = NO_PIECE_TYPE;
887 do_castling(to, from, rto, rfrom);
890 move_piece(to, from, us, pt); // Put the piece back at the source square
896 if (type_of(m) == ENPASSANT)
898 capsq -= pawn_push(us);
901 assert(to == st->previous->epSquare);
902 assert(relative_rank(us, to) == RANK_6);
903 assert(piece_on(capsq) == NO_PIECE);
906 put_piece(capsq, them, captured); // Restore the captured piece
909 // Finally point our state pointer back to the previous state
917 /// Position::do_castling() is a helper used to do/undo a castling move. This
918 /// is a bit tricky, especially in Chess960.
920 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
922 // Remove both pieces first since squares could overlap in Chess960
923 remove_piece(kfrom, sideToMove, KING);
924 remove_piece(rfrom, sideToMove, ROOK);
925 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
926 put_piece(kto, sideToMove, KING);
927 put_piece(rto, sideToMove, ROOK);
931 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
932 /// the side to move without executing any move on the board.
934 void Position::do_null_move(StateInfo& newSt) {
938 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
943 if (st->epSquare != SQ_NONE)
945 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
946 st->epSquare = SQ_NONE;
949 st->key ^= Zobrist::side;
950 prefetch((char*)TT.first_entry(st->key));
953 st->pliesFromNull = 0;
955 sideToMove = ~sideToMove;
960 void Position::undo_null_move() {
965 sideToMove = ~sideToMove;
969 /// Position::see() is a static exchange evaluator: It tries to estimate the
970 /// material gain or loss resulting from a move.
972 Value Position::see_sign(Move m) const {
976 // Early return if SEE cannot be negative because captured piece value
977 // is not less then capturing one. Note that king moves always return
978 // here because king midgame value is set to 0.
979 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
980 return VALUE_KNOWN_WIN;
985 Value Position::see(Move m) const {
988 Bitboard occupied, attackers, stmAttackers;
998 swapList[0] = PieceValue[MG][piece_on(to)];
999 stm = color_of(piece_on(from));
1000 occupied = pieces() ^ from;
1002 // Castling moves are implemented as king capturing the rook so cannot be
1003 // handled correctly. Simply return 0 that is always the correct value
1004 // unless in the rare case the rook ends up under attack.
1005 if (type_of(m) == CASTLING)
1008 if (type_of(m) == ENPASSANT)
1010 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1011 swapList[0] = PieceValue[MG][PAWN];
1014 // Find all attackers to the destination square, with the moving piece
1015 // removed, but possibly an X-ray attacker added behind it.
1016 attackers = attackers_to(to, occupied) & occupied;
1018 // If the opponent has no attackers we are finished
1020 stmAttackers = attackers & pieces(stm);
1024 // The destination square is defended, which makes things rather more
1025 // difficult to compute. We proceed by building up a "swap list" containing
1026 // the material gain or loss at each stop in a sequence of captures to the
1027 // destination square, where the sides alternately capture, and always
1028 // capture with the least valuable piece. After each capture, we look for
1029 // new X-ray attacks from behind the capturing piece.
1030 captured = type_of(piece_on(from));
1033 assert(slIndex < 32);
1035 // Add the new entry to the swap list
1036 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1038 // Locate and remove the next least valuable attacker
1039 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1041 // Stop before processing a king capture
1042 if (captured == KING)
1044 if (stmAttackers == attackers)
1051 stmAttackers = attackers & pieces(stm);
1054 } while (stmAttackers);
1056 // Having built the swap list, we negamax through it to find the best
1057 // achievable score from the point of view of the side to move.
1059 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1065 /// Position::clear() erases the position object to a pristine state, with an
1066 /// empty board, white to move, and no castling rights.
1068 void Position::clear() {
1070 std::memset(this, 0, sizeof(Position));
1071 startState.epSquare = SQ_NONE;
1074 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1075 for (int j = 0; j < 16; ++j)
1076 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1080 /// Position::compute_key() computes the hash key of the position. The hash
1081 /// key is usually updated incrementally as moves are made and unmade. The
1082 /// compute_key() function is only used when a new position is set up, and
1083 /// to verify the correctness of the hash key when running in debug mode.
1085 Key Position::compute_key() const {
1087 Key k = Zobrist::castling[st->castlingRights];
1089 for (Bitboard b = pieces(); b; )
1091 Square s = pop_lsb(&b);
1092 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1095 if (ep_square() != SQ_NONE)
1096 k ^= Zobrist::enpassant[file_of(ep_square())];
1098 if (sideToMove == BLACK)
1105 /// Position::compute_pawn_key() computes the hash key of the position. The
1106 /// hash key is usually updated incrementally as moves are made and unmade.
1107 /// The compute_pawn_key() function is only used when a new position is set
1108 /// up, and to verify the correctness of the pawn hash key when running in
1111 Key Position::compute_pawn_key() const {
1115 for (Bitboard b = pieces(PAWN); b; )
1117 Square s = pop_lsb(&b);
1118 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1125 /// Position::compute_material_key() computes the hash key of the position.
1126 /// The hash key is usually updated incrementally as moves are made and unmade.
1127 /// The compute_material_key() function is only used when a new position is set
1128 /// up, and to verify the correctness of the material hash key when running in
1131 Key Position::compute_material_key() const {
1135 for (Color c = WHITE; c <= BLACK; ++c)
1136 for (PieceType pt = PAWN; pt <= KING; ++pt)
1137 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1138 k ^= Zobrist::psq[c][pt][cnt];
1144 /// Position::compute_psq_score() computes the incremental scores for the middlegame
1145 /// and the endgame. These functions are used to initialize the incremental scores
1146 /// when a new position is set up, and to verify that the scores are correctly
1147 /// updated by do_move and undo_move when the program is running in debug mode.
1149 Score Position::compute_psq_score() const {
1151 Score score = SCORE_ZERO;
1153 for (Bitboard b = pieces(); b; )
1155 Square s = pop_lsb(&b);
1156 Piece pc = piece_on(s);
1157 score += psq[color_of(pc)][type_of(pc)][s];
1164 /// Position::compute_non_pawn_material() computes the total non-pawn middlegame
1165 /// material value for the given side. Material values are updated incrementally
1166 /// during the search. This function is only used when initializing a new Position
1169 Value Position::compute_non_pawn_material(Color c) const {
1171 Value value = VALUE_ZERO;
1173 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1174 value += pieceCount[c][pt] * PieceValue[MG][pt];
1180 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1181 /// rule or repetition. It does not detect stalemates.
1183 bool Position::is_draw() const {
1186 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1189 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1192 StateInfo* stp = st;
1193 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1195 stp = stp->previous->previous;
1197 if (stp->key == st->key)
1198 return true; // Draw at first repetition
1205 /// Position::flip() flips position with the white and black sides reversed. This
1206 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1208 static char toggle_case(char c) {
1209 return char(islower(c) ? toupper(c) : tolower(c));
1212 void Position::flip() {
1215 std::stringstream ss(fen());
1217 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1219 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1220 f.insert(0, token + (f.empty() ? " " : "/"));
1223 ss >> token; // Active color
1224 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1226 ss >> token; // Castling availability
1229 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1231 ss >> token; // En passant square
1232 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1234 std::getline(ss, token); // Half and full moves
1237 set(f, is_chess960(), this_thread());
1239 assert(pos_is_ok());
1243 /// Position::pos_is_ok() performs some consistency checks for the position object.
1244 /// This is meant to be helpful when debugging.
1246 bool Position::pos_is_ok(int* failedStep) const {
1248 int dummy, *step = failedStep ? failedStep : &dummy;
1250 // What features of the position should be verified?
1251 const bool all = false;
1253 const bool debugBitboards = all || false;
1254 const bool debugKingCount = all || false;
1255 const bool debugKingCapture = all || false;
1256 const bool debugCheckerCount = all || false;
1257 const bool debugKey = all || false;
1258 const bool debugMaterialKey = all || false;
1259 const bool debugPawnKey = all || false;
1260 const bool debugIncrementalEval = all || false;
1261 const bool debugNonPawnMaterial = all || false;
1262 const bool debugPieceCounts = all || false;
1263 const bool debugPieceList = all || false;
1264 const bool debugCastlingSquares = all || false;
1268 if (sideToMove != WHITE && sideToMove != BLACK)
1271 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1274 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1277 if ((*step)++, debugKingCount)
1279 int kingCount[COLOR_NB] = {};
1281 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1282 if (type_of(piece_on(s)) == KING)
1283 ++kingCount[color_of(piece_on(s))];
1285 if (kingCount[0] != 1 || kingCount[1] != 1)
1289 if ((*step)++, debugKingCapture)
1290 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1293 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1296 if ((*step)++, debugBitboards)
1298 // The intersection of the white and black pieces must be empty
1299 if (pieces(WHITE) & pieces(BLACK))
1302 // The union of the white and black pieces must be equal to all
1304 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1307 // Separate piece type bitboards must have empty intersections
1308 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1309 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1310 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1314 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1317 if ((*step)++, debugKey && st->key != compute_key())
1320 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1323 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1326 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1329 if ((*step)++, debugNonPawnMaterial)
1330 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1331 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1334 if ((*step)++, debugPieceCounts)
1335 for (Color c = WHITE; c <= BLACK; ++c)
1336 for (PieceType pt = PAWN; pt <= KING; ++pt)
1337 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1340 if ((*step)++, debugPieceList)
1341 for (Color c = WHITE; c <= BLACK; ++c)
1342 for (PieceType pt = PAWN; pt <= KING; ++pt)
1343 for (int i = 0; i < pieceCount[c][pt]; ++i)
1344 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1345 || index[pieceList[c][pt][i]] != i)
1348 if ((*step)++, debugCastlingSquares)
1349 for (Color c = WHITE; c <= BLACK; ++c)
1350 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1352 if (!can_castle(c | s))
1355 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1356 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1357 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))