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-2013 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/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // min_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the bitboards and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 Bitboard b = stmAttackers & bb[Pt];
72 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
74 occupied ^= b & ~(b - 1);
76 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
77 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
79 if (Pt == ROOK || Pt == QUEEN)
80 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
82 attackers &= occupied; // After X-ray that may add already processed pieces
86 template<> FORCE_INLINE
87 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
88 return KING; // No need to update bitboards, it is the last cycle
96 CheckInfo::CheckInfo(const Position& pos) {
98 Color them = ~pos.side_to_move();
99 ksq = pos.king_square(them);
101 pinned = pos.pinned_pieces(pos.side_to_move());
102 dcCandidates = pos.discovered_check_candidates();
104 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
105 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
106 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
107 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
108 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
113 /// Position::init() initializes at startup the various arrays used to compute
114 /// hash keys and the piece square tables. The latter is a two-step operation:
115 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
116 /// the black halves of the tables are initialized by flipping and changing the
117 /// sign of the white scores.
119 void Position::init() {
123 for (Color c = WHITE; c <= BLACK; ++c)
124 for (PieceType pt = PAWN; pt <= KING; ++pt)
125 for (Square s = SQ_A1; s <= SQ_H8; ++s)
126 Zobrist::psq[c][pt][s] = rk.rand<Key>();
128 for (File f = FILE_A; f <= FILE_H; ++f)
129 Zobrist::enpassant[f] = rk.rand<Key>();
131 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; ++cr)
136 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
137 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
141 Zobrist::side = rk.rand<Key>();
142 Zobrist::exclusion = rk.rand<Key>();
144 for (PieceType pt = PAWN; pt <= KING; ++pt)
146 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
147 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
149 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
151 for (Square s = SQ_A1; s <= SQ_H8; ++s)
153 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
154 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
160 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
161 /// object do not depend on any external data so we detach state pointer from
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
177 /// Position::set() initializes the position object with the given FEN string.
178 /// This function is not very robust - make sure that input FENs are correct,
179 /// this is assumed to be the responsibility of the GUI.
181 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
183 A FEN string defines a particular position using only the ASCII character set.
185 A FEN string contains six fields separated by a space. The fields are:
187 1) Piece placement (from white's perspective). Each rank is described, starting
188 with rank 8 and ending with rank 1; within each rank, the contents of each
189 square are described from file A through file H. Following the Standard
190 Algebraic Notation (SAN), each piece is identified by a single letter taken
191 from the standard English names. White pieces are designated using upper-case
192 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
193 noted using digits 1 through 8 (the number of blank squares), and "/"
196 2) Active color. "w" means white moves next, "b" means black.
198 3) Castling availability. If neither side can castle, this is "-". Otherwise,
199 this has one or more letters: "K" (White can castle kingside), "Q" (White
200 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
201 can castle queenside).
203 4) En passant target square (in algebraic notation). If there's no en passant
204 target square, this is "-". If a pawn has just made a 2-square move, this
205 is the position "behind" the pawn. This is recorded regardless of whether
206 there is a pawn in position to make an en passant capture.
208 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
209 or capture. This is used to determine if a draw can be claimed under the
212 6) Fullmove number. The number of the full move. It starts at 1, and is
213 incremented after Black's move.
216 char col, row, token;
219 std::istringstream ss(fenStr);
224 // 1. Piece placement
225 while ((ss >> token) && !isspace(token))
228 sq += Square(token - '0'); // Advance the given number of files
230 else if (token == '/')
233 else if ((p = PieceToChar.find(token)) != string::npos)
235 put_piece(sq, color_of(Piece(p)), type_of(Piece(p)));
242 sideToMove = (token == 'w' ? WHITE : BLACK);
245 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
246 // Shredder-FEN that uses the letters of the columns on which the rooks began
247 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
248 // if an inner rook is associated with the castling right, the castling tag is
249 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
250 while ((ss >> token) && !isspace(token))
253 Color c = islower(token) ? BLACK : WHITE;
255 token = char(toupper(token));
258 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
260 else if (token == 'Q')
261 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
263 else if (token >= 'A' && token <= 'H')
264 rsq = File(token - 'A') | relative_rank(c, RANK_1);
269 set_castle_right(c, rsq);
272 // 4. En passant square. Ignore if no pawn capture is possible
273 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
274 && ((ss >> row) && (row == '3' || row == '6')))
276 st->epSquare = File(col - 'a') | Rank(row - '1');
278 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
279 st->epSquare = SQ_NONE;
282 // 5-6. Halfmove clock and fullmove number
283 ss >> std::skipws >> st->rule50 >> gamePly;
285 // Convert from fullmove starting from 1 to ply starting from 0,
286 // handle also common incorrect FEN with fullmove = 0.
287 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
289 st->key = compute_key();
290 st->pawnKey = compute_pawn_key();
291 st->materialKey = compute_material_key();
292 st->psq = compute_psq_score();
293 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
294 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
295 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
296 chess960 = isChess960;
303 /// Position::set_castle_right() is an helper function used to set castling
304 /// rights given the corresponding color and the rook starting square.
306 void Position::set_castle_right(Color c, Square rfrom) {
308 Square kfrom = king_square(c);
309 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
310 CastleRight cr = make_castle_right(c, cs);
312 st->castleRights |= cr;
313 castleRightsMask[kfrom] |= cr;
314 castleRightsMask[rfrom] |= cr;
315 castleRookSquare[c][cs] = rfrom;
317 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
318 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
320 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
321 if (s != kfrom && s != rfrom)
322 castlePath[c][cs] |= s;
324 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
325 if (s != kfrom && s != rfrom)
326 castlePath[c][cs] |= s;
330 /// Position::fen() returns a FEN representation of the position. In case
331 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
333 const string Position::fen() const {
335 std::ostringstream ss;
337 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
339 for (File file = FILE_A; file <= FILE_H; ++file)
341 Square sq = file | rank;
347 for ( ; file < FILE_H && empty(++sq); ++file)
353 ss << PieceToChar[piece_on(sq)];
360 ss << (sideToMove == WHITE ? " w " : " b ");
362 if (can_castle(WHITE_OO))
363 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
365 if (can_castle(WHITE_OOO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
368 if (can_castle(BLACK_OO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
371 if (can_castle(BLACK_OOO))
372 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
374 if (st->castleRights == CASTLES_NONE)
377 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
378 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
384 /// Position::pretty() returns an ASCII representation of the position to be
385 /// printed to the standard output together with the move's san notation.
387 const string Position::pretty(Move move) const {
389 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
390 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
391 + dottedLine + "\n| . | | . | | . | | . | |";
393 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
395 for (Bitboard b = pieces(); b; )
397 Square s = pop_lsb(&b);
398 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
401 std::ostringstream ss;
404 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
405 << move_to_san(*const_cast<Position*>(this), move);
407 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
408 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
410 for (Bitboard b = checkers(); b; )
411 ss << square_to_string(pop_lsb(&b)) << " ";
413 ss << "\nLegal moves: ";
414 for (MoveList<LEGAL> it(*this); *it; ++it)
415 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
421 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
422 /// pieces, according to the call parameters. Pinned pieces protect our king,
423 /// discovery check pieces attack the enemy king.
425 Bitboard Position::hidden_checkers(Square ksq, Color c, Color toMove) const {
427 Bitboard b, pinners, result = 0;
429 // Pinners are sliders that give check when pinned piece is removed
430 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
431 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
435 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
437 if (!more_than_one(b))
438 result |= b & pieces(toMove);
444 /// Position::attackers_to() computes a bitboard of all pieces which attack a
445 /// given square. Slider attacks use occ bitboard as occupancy.
447 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
449 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
450 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
451 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
452 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
453 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
454 | (attacks_from<KING>(s) & pieces(KING));
458 /// Position::legal() tests whether a pseudo-legal move is legal
460 bool Position::legal(Move m, Bitboard pinned) const {
463 assert(pinned == pinned_pieces(sideToMove));
465 Color us = sideToMove;
466 Square from = from_sq(m);
468 assert(color_of(moved_piece(m)) == us);
469 assert(piece_on(king_square(us)) == make_piece(us, KING));
471 // En passant captures are a tricky special case. Because they are rather
472 // uncommon, we do it simply by testing whether the king is attacked after
474 if (type_of(m) == ENPASSANT)
477 Square to = to_sq(m);
478 Square capsq = to + pawn_push(them);
479 Square ksq = king_square(us);
480 Bitboard b = (pieces() ^ from ^ capsq) | to;
482 assert(to == ep_square());
483 assert(moved_piece(m) == make_piece(us, PAWN));
484 assert(piece_on(capsq) == make_piece(them, PAWN));
485 assert(piece_on(to) == NO_PIECE);
487 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
488 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
491 // If the moving piece is a king, check whether the destination
492 // square is attacked by the opponent. Castling moves are checked
493 // for legality during move generation.
494 if (type_of(piece_on(from)) == KING)
495 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
497 // A non-king move is legal if and only if it is not pinned or it
498 // is moving along the ray towards or away from the king.
501 || aligned(from, to_sq(m), king_square(us));
505 /// Position::pseudo_legal() takes a random move and tests whether the move is
506 /// pseudo legal. It is used to validate moves from TT that can be corrupted
507 /// due to SMP concurrent access or hash position key aliasing.
509 bool Position::pseudo_legal(const Move m) const {
511 Color us = sideToMove;
512 Square from = from_sq(m);
513 Square to = to_sq(m);
514 Piece pc = moved_piece(m);
516 // Use a slower but simpler function for uncommon cases
517 if (type_of(m) != NORMAL)
518 return MoveList<LEGAL>(*this).contains(m);
520 // Is not a promotion, so promotion piece must be empty
521 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
524 // If the from square is not occupied by a piece belonging to the side to
525 // move, the move is obviously not legal.
526 if (pc == NO_PIECE || color_of(pc) != us)
529 // The destination square cannot be occupied by a friendly piece
533 // Handle the special case of a pawn move
534 if (type_of(pc) == PAWN)
536 // Move direction must be compatible with pawn color
537 int direction = to - from;
538 if ((us == WHITE) != (direction > 0))
541 // We have already handled promotion moves, so destination
542 // cannot be on the 8/1th rank.
543 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
546 // Proceed according to the square delta between the origin and
547 // destination squares.
554 // Capture. The destination square must be occupied by an enemy
555 // piece (en passant captures was handled earlier).
556 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
559 // From and to files must be one file apart, avoids a7h5
560 if (abs(file_of(from) - file_of(to)) != 1)
566 // Pawn push. The destination square must be empty.
572 // Double white pawn push. The destination square must be on the fourth
573 // rank, and both the destination square and the square between the
574 // source and destination squares must be empty.
575 if ( rank_of(to) != RANK_4
577 || !empty(from + DELTA_N))
582 // Double black pawn push. The destination square must be on the fifth
583 // rank, and both the destination square and the square between the
584 // source and destination squares must be empty.
585 if ( rank_of(to) != RANK_5
587 || !empty(from + DELTA_S))
595 else if (!(attacks_from(pc, from) & to))
598 // Evasions generator already takes care to avoid some kind of illegal moves
599 // and pl_move_is_legal() relies on this. So we have to take care that the
600 // same kind of moves are filtered out here.
603 if (type_of(pc) != KING)
605 // Double check? In this case a king move is required
606 if (more_than_one(checkers()))
609 // Our move must be a blocking evasion or a capture of the checking piece
610 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
613 // In case of king moves under check we have to remove king so to catch
614 // as invalid moves like b1a1 when opposite queen is on c1.
615 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
623 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
625 bool Position::gives_check(Move m, const CheckInfo& ci) const {
628 assert(ci.dcCandidates == discovered_check_candidates());
629 assert(color_of(moved_piece(m)) == sideToMove);
631 Square from = from_sq(m);
632 Square to = to_sq(m);
633 PieceType pt = type_of(piece_on(from));
636 if (ci.checkSq[pt] & to)
640 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
642 // For pawn and king moves we need to verify also direction
643 if ( (pt != PAWN && pt != KING)
644 || !aligned(from, to, king_square(~sideToMove)))
648 // Can we skip the ugly special cases ?
649 if (type_of(m) == NORMAL)
652 Color us = sideToMove;
653 Square ksq = king_square(~us);
658 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
660 // En passant capture with check ? We have already handled the case
661 // of direct checks and ordinary discovered check, the only case we
662 // need to handle is the unusual case of a discovered check through
663 // the captured pawn.
666 Square capsq = file_of(to) | rank_of(from);
667 Bitboard b = (pieces() ^ from ^ capsq) | to;
669 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
670 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
675 Square rfrom = to; // 'King captures the rook' notation
676 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
677 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
679 return (PseudoAttacks[ROOK][rto] & ksq)
680 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & 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 old state to our new StateInfo object except the ones
708 // which are going to be recalculated from scratch anyway, then switch our state
709 // 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 later reset it to zero
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) == CASTLE);
734 assert(captured != KING);
736 if (type_of(m) == CASTLE)
738 assert(pc == make_piece(us, KING));
740 bool kingSide = to > from;
741 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
742 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
743 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
744 captured = NO_PIECE_TYPE;
746 do_castle(from, to, rfrom, rto);
748 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
749 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
756 // If the captured piece is a pawn, update pawn hash key, otherwise
757 // update non-pawn material.
758 if (captured == PAWN)
760 if (type_of(m) == ENPASSANT)
762 capsq += pawn_push(them);
765 assert(to == st->epSquare);
766 assert(relative_rank(us, to) == RANK_6);
767 assert(piece_on(to) == NO_PIECE);
768 assert(piece_on(capsq) == make_piece(them, PAWN));
770 board[capsq] = NO_PIECE;
773 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
776 st->npMaterial[them] -= PieceValue[MG][captured];
778 // Update board and piece lists
779 remove_piece(capsq, them, captured);
781 // Update material hash key and prefetch access to materialTable
782 k ^= Zobrist::psq[them][captured][capsq];
783 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
784 prefetch((char*)thisThread->materialTable[st->materialKey]);
786 // Update incremental scores
787 st->psq -= psq[them][captured][capsq];
789 // Reset rule 50 counter
794 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
796 // Reset en passant square
797 if (st->epSquare != SQ_NONE)
799 k ^= Zobrist::enpassant[file_of(st->epSquare)];
800 st->epSquare = SQ_NONE;
803 // Update castle rights if needed
804 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
806 int cr = castleRightsMask[from] | castleRightsMask[to];
807 k ^= Zobrist::castle[st->castleRights & cr];
808 st->castleRights &= ~cr;
811 // Prefetch TT access as soon as we know the new hash key
812 prefetch((char*)TT.first_entry(k));
814 // Move the piece. The tricky Chess960 castle is handled earlier
815 if (type_of(m) != CASTLE)
816 move_piece(from, to, us, pt);
818 // If the moving piece is a pawn do some special extra work
821 // Set en-passant square, only if moved pawn can be captured
822 if ( (int(to) ^ int(from)) == 16
823 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
825 st->epSquare = Square((from + to) / 2);
826 k ^= Zobrist::enpassant[file_of(st->epSquare)];
829 if (type_of(m) == PROMOTION)
831 PieceType promotion = promotion_type(m);
833 assert(relative_rank(us, to) == RANK_8);
834 assert(promotion >= KNIGHT && promotion <= QUEEN);
836 remove_piece(to, us, PAWN);
837 put_piece(to, us, promotion);
840 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
841 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
842 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
843 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
845 // Update incremental score
846 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
849 st->npMaterial[us] += PieceValue[MG][promotion];
852 // Update pawn hash key and prefetch access to pawnsTable
853 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
854 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
856 // Reset rule 50 draw counter
860 // Update incremental scores
861 st->psq += psq[us][pt][to] - psq[us][pt][from];
864 st->capturedType = captured;
866 // Update the key with the final value
869 // Update checkers bitboard, piece must be already moved
874 if (type_of(m) != NORMAL)
875 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
879 if (ci.checkSq[pt] & to)
880 st->checkersBB |= to;
883 if (ci.dcCandidates && (ci.dcCandidates & from))
886 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
889 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
894 sideToMove = ~sideToMove;
900 /// Position::undo_move() unmakes a move. When it returns, the position should
901 /// be restored to exactly the same state as before the move was made.
903 void Position::undo_move(Move m) {
907 sideToMove = ~sideToMove;
909 Color us = sideToMove;
911 Square from = from_sq(m);
912 Square to = to_sq(m);
913 PieceType pt = type_of(piece_on(to));
914 PieceType captured = st->capturedType;
916 assert(empty(from) || type_of(m) == CASTLE);
917 assert(captured != KING);
919 if (type_of(m) == PROMOTION)
921 PieceType promotion = promotion_type(m);
923 assert(promotion == pt);
924 assert(relative_rank(us, to) == RANK_8);
925 assert(promotion >= KNIGHT && promotion <= QUEEN);
927 remove_piece(to, us, promotion);
928 put_piece(to, us, PAWN);
932 if (type_of(m) == CASTLE)
934 bool kingSide = to > from;
935 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
936 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
937 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
938 captured = NO_PIECE_TYPE;
940 do_castle(to, from, rto, rfrom);
943 move_piece(to, from, us, pt); // Put the piece back at the source square
949 if (type_of(m) == ENPASSANT)
951 capsq -= pawn_push(us);
954 assert(to == st->previous->epSquare);
955 assert(relative_rank(us, to) == RANK_6);
956 assert(piece_on(capsq) == NO_PIECE);
959 put_piece(capsq, them, captured); // Restore the captured piece
962 // Finally point our state pointer back to the previous state
970 /// Position::do_castle() is a helper used to do/undo a castling move. This
971 /// is a bit tricky, especially in Chess960.
973 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
975 // Remove both pieces first since squares could overlap in Chess960
976 remove_piece(kfrom, sideToMove, KING);
977 remove_piece(rfrom, sideToMove, ROOK);
978 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
979 put_piece(kto, sideToMove, KING);
980 put_piece(rto, sideToMove, ROOK);
984 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
985 /// the side to move without executing any move on the board.
987 void Position::do_null_move(StateInfo& newSt) {
991 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
996 if (st->epSquare != SQ_NONE)
998 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
999 st->epSquare = SQ_NONE;
1002 st->key ^= Zobrist::side;
1003 prefetch((char*)TT.first_entry(st->key));
1006 st->pliesFromNull = 0;
1008 sideToMove = ~sideToMove;
1010 assert(pos_is_ok());
1013 void Position::undo_null_move() {
1015 assert(!checkers());
1018 sideToMove = ~sideToMove;
1022 /// Position::see() is a static exchange evaluator: It tries to estimate the
1023 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1024 /// tempi into account. If the side who initiated the capturing sequence does the
1025 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1026 /// the capturing sequence is considered bad.
1028 int Position::see_sign(Move m) const {
1032 // Early return if SEE cannot be negative because captured piece value
1033 // is not less then capturing one. Note that king moves always return
1034 // here because king midgame value is set to 0.
1035 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1041 int Position::see(Move m, int asymmThreshold) const {
1044 Bitboard occupied, attackers, stmAttackers;
1045 int swapList[32], slIndex = 1;
1053 swapList[0] = PieceValue[MG][piece_on(to)];
1054 stm = color_of(piece_on(from));
1055 occupied = pieces() ^ from;
1057 // Castle 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) == CASTLE)
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];
1094 // Locate and remove the next least valuable attacker
1095 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1097 stmAttackers = attackers & pieces(stm);
1099 // Stop before processing a king capture
1100 if (captured == KING && stmAttackers)
1102 swapList[slIndex++] = QueenValueMg * 16;
1106 } while (stmAttackers);
1108 // If we are doing asymmetric SEE evaluation and the same side does the first
1109 // and the last capture, he loses a tempo and gain must be at least worth
1110 // 'asymmThreshold', otherwise we replace the score with a very low value,
1111 // before negamaxing.
1113 for (int i = 0; i < slIndex; i += 2)
1114 if (swapList[i] < asymmThreshold)
1115 swapList[i] = - QueenValueMg * 16;
1117 // Having built the swap list, we negamax through it to find the best
1118 // achievable score from the point of view of the side to move.
1120 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1126 /// Position::clear() erases the position object to a pristine state, with an
1127 /// empty board, white to move, and no castling rights.
1129 void Position::clear() {
1131 std::memset(this, 0, sizeof(Position));
1132 startState.epSquare = SQ_NONE;
1135 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1136 for (int j = 0; j < 16; ++j)
1137 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1141 /// Position::compute_key() computes the hash key of the position. The hash
1142 /// key is usually updated incrementally as moves are made and unmade, the
1143 /// compute_key() function is only used when a new position is set up, and
1144 /// to verify the correctness of the hash key when running in debug mode.
1146 Key Position::compute_key() const {
1148 Key k = Zobrist::castle[st->castleRights];
1150 for (Bitboard b = pieces(); b; )
1152 Square s = pop_lsb(&b);
1153 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1156 if (ep_square() != SQ_NONE)
1157 k ^= Zobrist::enpassant[file_of(ep_square())];
1159 if (sideToMove == BLACK)
1166 /// Position::compute_pawn_key() computes the hash key of the position. The
1167 /// hash key is usually updated incrementally as moves are made and unmade,
1168 /// the compute_pawn_key() function is only used when a new position is set
1169 /// up, and to verify the correctness of the pawn hash key when running in
1172 Key Position::compute_pawn_key() const {
1176 for (Bitboard b = pieces(PAWN); b; )
1178 Square s = pop_lsb(&b);
1179 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1186 /// Position::compute_material_key() computes the hash key of the position.
1187 /// The hash key is usually updated incrementally as moves are made and unmade,
1188 /// the compute_material_key() function is only used when a new position is set
1189 /// up, and to verify the correctness of the material hash key when running in
1192 Key Position::compute_material_key() const {
1196 for (Color c = WHITE; c <= BLACK; ++c)
1197 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1198 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1199 k ^= Zobrist::psq[c][pt][cnt];
1205 /// Position::compute_psq_score() computes the incremental scores for the middle
1206 /// game and the endgame. These functions are used to initialize the incremental
1207 /// scores when a new position is set up, and to verify that the scores are correctly
1208 /// updated by do_move and undo_move when the program is running in debug mode.
1210 Score Position::compute_psq_score() const {
1212 Score score = SCORE_ZERO;
1214 for (Bitboard b = pieces(); b; )
1216 Square s = pop_lsb(&b);
1217 Piece pc = piece_on(s);
1218 score += psq[color_of(pc)][type_of(pc)][s];
1225 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1226 /// game material value for the given side. Material values are updated
1227 /// incrementally during the search, this function is only used while
1228 /// initializing a new Position object.
1230 Value Position::compute_non_pawn_material(Color c) const {
1232 Value value = VALUE_ZERO;
1234 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1235 value += pieceCount[c][pt] * PieceValue[MG][pt];
1241 /// Position::is_draw() tests whether the position is drawn by material,
1242 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1243 /// must be done by the search.
1244 bool Position::is_draw() const {
1246 // Draw by material?
1248 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1251 // Draw by the 50 moves rule?
1252 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1255 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1259 StateInfo* stp = st->previous->previous;
1262 stp = stp->previous->previous;
1264 if (stp->key == st->key)
1265 return true; // Draw after first repetition
1276 /// Position::flip() flips position with the white and black sides reversed. This
1277 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1279 static char toggle_case(char c) {
1280 return char(islower(c) ? toupper(c) : tolower(c));
1283 void Position::flip() {
1286 std::stringstream ss(fen());
1288 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1290 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1291 f.insert(0, token + (f.empty() ? " " : "/"));
1294 ss >> token; // Active color
1295 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1297 ss >> token; // Castling availability
1300 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1302 ss >> token; // En passant square
1303 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1305 std::getline(ss, token); // Half and full moves
1308 set(f, is_chess960(), this_thread());
1310 assert(pos_is_ok());
1314 /// Position::pos_is_ok() performs some consitency checks for the position object.
1315 /// This is meant to be helpful when debugging.
1317 bool Position::pos_is_ok(int* failedStep) const {
1319 int dummy, *step = failedStep ? failedStep : &dummy;
1321 // What features of the position should be verified?
1322 const bool all = false;
1324 const bool debugBitboards = all || false;
1325 const bool debugKingCount = all || false;
1326 const bool debugKingCapture = all || false;
1327 const bool debugCheckerCount = all || false;
1328 const bool debugKey = all || false;
1329 const bool debugMaterialKey = all || false;
1330 const bool debugPawnKey = all || false;
1331 const bool debugIncrementalEval = all || false;
1332 const bool debugNonPawnMaterial = all || false;
1333 const bool debugPieceCounts = all || false;
1334 const bool debugPieceList = all || false;
1335 const bool debugCastleSquares = all || false;
1339 if (sideToMove != WHITE && sideToMove != BLACK)
1342 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1345 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1348 if ((*step)++, debugKingCount)
1350 int kingCount[COLOR_NB] = {};
1352 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1353 if (type_of(piece_on(s)) == KING)
1354 ++kingCount[color_of(piece_on(s))];
1356 if (kingCount[0] != 1 || kingCount[1] != 1)
1360 if ((*step)++, debugKingCapture)
1361 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1364 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1367 if ((*step)++, debugBitboards)
1369 // The intersection of the white and black pieces must be empty
1370 if (pieces(WHITE) & pieces(BLACK))
1373 // The union of the white and black pieces must be equal to all
1375 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1378 // Separate piece type bitboards must have empty intersections
1379 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1380 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1381 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1385 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1388 if ((*step)++, debugKey && st->key != compute_key())
1391 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1394 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1397 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1400 if ((*step)++, debugNonPawnMaterial)
1401 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1402 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1405 if ((*step)++, debugPieceCounts)
1406 for (Color c = WHITE; c <= BLACK; ++c)
1407 for (PieceType pt = PAWN; pt <= KING; ++pt)
1408 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1411 if ((*step)++, debugPieceList)
1412 for (Color c = WHITE; c <= BLACK; ++c)
1413 for (PieceType pt = PAWN; pt <= KING; ++pt)
1414 for (int i = 0; i < pieceCount[c][pt]; ++i)
1415 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1416 || index[pieceList[c][pt][i]] != i)
1419 if ((*step)++, debugCastleSquares)
1420 for (Color c = WHITE; c <= BLACK; ++c)
1421 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1423 CastleRight cr = make_castle_right(c, s);
1425 if (!can_castle(cr))
1428 if ( (castleRightsMask[king_square(c)] & cr) != cr
1429 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1430 || castleRightsMask[castleRookSquare[c][s]] != cr)