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 // next_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 'occupied' bitboard and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 if (stmAttackers & bb[Pt])
72 Bitboard b = stmAttackers & bb[Pt];
73 occupied ^= b & ~(b - 1);
75 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
76 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
78 if (Pt == ROOK || Pt == QUEEN)
79 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
83 return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
86 template<> FORCE_INLINE
87 PieceType next_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();
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 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(Piece(p), sq);
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 && is_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 std::ostringstream ss;
398 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
399 << move_to_san(*const_cast<Position*>(this), move);
401 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
402 if (piece_on(sq) != NO_PIECE)
403 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
405 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
406 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
408 for (Bitboard b = checkers(); b; )
409 ss << square_to_string(pop_lsb(&b)) << " ";
411 ss << "\nLegal moves: ";
412 for (MoveList<LEGAL> it(*this); *it; ++it)
413 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
419 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
420 /// king) pieces for the given color. Or, when template parameter FindPinned is
421 /// false, the function return the pieces of the given color candidate for a
422 /// discovery check against the enemy king.
423 template<bool FindPinned>
424 Bitboard Position::hidden_checkers() const {
426 // Pinned pieces protect our king, dicovery checks attack the enemy king
427 Bitboard b, result = 0;
428 Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
429 Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
431 // Pinners are sliders, that give check when candidate pinned is removed
432 pinners &= (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
433 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
437 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
439 if (b && !more_than_one(b) && (b & pieces(sideToMove)))
445 // Explicit template instantiations
446 template Bitboard Position::hidden_checkers<true>() const;
447 template Bitboard Position::hidden_checkers<false>() const;
450 /// Position::attackers_to() computes a bitboard of all pieces which attack a
451 /// given square. Slider attacks use occ bitboard as occupancy.
453 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
455 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
456 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
457 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
458 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
459 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
460 | (attacks_from<KING>(s) & pieces(KING));
464 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
465 /// put in a given square. Slider attacks use occ bitboard as occupancy.
467 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
473 case BISHOP: return attacks_bb<BISHOP>(s, occ);
474 case ROOK : return attacks_bb<ROOK>(s, occ);
475 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
476 default : return StepAttacksBB[p][s];
481 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
483 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
486 assert(pinned == pinned_pieces());
488 Color us = sideToMove;
489 Square from = from_sq(m);
491 assert(color_of(piece_moved(m)) == us);
492 assert(piece_on(king_square(us)) == make_piece(us, KING));
494 // En passant captures are a tricky special case. Because they are rather
495 // uncommon, we do it simply by testing whether the king is attacked after
497 if (type_of(m) == ENPASSANT)
500 Square to = to_sq(m);
501 Square capsq = to + pawn_push(them);
502 Square ksq = king_square(us);
503 Bitboard b = (pieces() ^ from ^ capsq) | to;
505 assert(to == ep_square());
506 assert(piece_moved(m) == make_piece(us, PAWN));
507 assert(piece_on(capsq) == make_piece(them, PAWN));
508 assert(piece_on(to) == NO_PIECE);
510 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
511 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
514 // If the moving piece is a king, check whether the destination
515 // square is attacked by the opponent. Castling moves are checked
516 // for legality during move generation.
517 if (type_of(piece_on(from)) == KING)
518 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
520 // A non-king move is legal if and only if it is not pinned or it
521 // is moving along the ray towards or away from the king.
524 || squares_aligned(from, to_sq(m), king_square(us));
528 /// Position::is_pseudo_legal() takes a random move and tests whether the move
529 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
530 /// due to SMP concurrent access or hash position key aliasing.
532 bool Position::is_pseudo_legal(const Move m) const {
534 Color us = sideToMove;
535 Square from = from_sq(m);
536 Square to = to_sq(m);
537 Piece pc = piece_moved(m);
539 // Use a slower but simpler function for uncommon cases
540 if (type_of(m) != NORMAL)
541 return MoveList<LEGAL>(*this).contains(m);
543 // Is not a promotion, so promotion piece must be empty
544 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
547 // If the from square is not occupied by a piece belonging to the side to
548 // move, the move is obviously not legal.
549 if (pc == NO_PIECE || color_of(pc) != us)
552 // The destination square cannot be occupied by a friendly piece
553 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
556 // Handle the special case of a pawn move
557 if (type_of(pc) == PAWN)
559 // Move direction must be compatible with pawn color
560 int direction = to - from;
561 if ((us == WHITE) != (direction > 0))
564 // We have already handled promotion moves, so destination
565 // cannot be on the 8/1th rank.
566 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
569 // Proceed according to the square delta between the origin and
570 // destination squares.
577 // Capture. The destination square must be occupied by an enemy
578 // piece (en passant captures was handled earlier).
579 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
582 // From and to files must be one file apart, avoids a7h5
583 if (abs(file_of(from) - file_of(to)) != 1)
589 // Pawn push. The destination square must be empty.
595 // Double white pawn push. The destination square must be on the fourth
596 // rank, and both the destination square and the square between the
597 // source and destination squares must be empty.
598 if ( rank_of(to) != RANK_4
600 || !is_empty(from + DELTA_N))
605 // Double black pawn push. The destination square must be on the fifth
606 // rank, and both the destination square and the square between the
607 // source and destination squares must be empty.
608 if ( rank_of(to) != RANK_5
610 || !is_empty(from + DELTA_S))
618 else if (!(attacks_from(pc, from) & to))
621 // Evasions generator already takes care to avoid some kind of illegal moves
622 // and pl_move_is_legal() relies on this. So we have to take care that the
623 // same kind of moves are filtered out here.
626 if (type_of(pc) != KING)
628 // Double check? In this case a king move is required
629 if (more_than_one(checkers()))
632 // Our move must be a blocking evasion or a capture of the checking piece
633 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
636 // In case of king moves under check we have to remove king so to catch
637 // as invalid moves like b1a1 when opposite queen is on c1.
638 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
646 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
648 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
651 assert(ci.dcCandidates == discovered_check_candidates());
652 assert(color_of(piece_moved(m)) == sideToMove);
654 Square from = from_sq(m);
655 Square to = to_sq(m);
656 PieceType pt = type_of(piece_on(from));
659 if (ci.checkSq[pt] & to)
663 if (ci.dcCandidates && (ci.dcCandidates & from))
665 // For pawn and king moves we need to verify also direction
666 if ( (pt != PAWN && pt != KING)
667 || !squares_aligned(from, to, king_square(~sideToMove)))
671 // Can we skip the ugly special cases ?
672 if (type_of(m) == NORMAL)
675 Color us = sideToMove;
676 Square ksq = king_square(~us);
681 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
683 // En passant capture with check ? We have already handled the case
684 // of direct checks and ordinary discovered check, the only case we
685 // need to handle is the unusual case of a discovered check through
686 // the captured pawn.
689 Square capsq = file_of(to) | rank_of(from);
690 Bitboard b = (pieces() ^ from ^ capsq) | to;
692 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
693 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
698 Square rfrom = to; // 'King captures the rook' notation
699 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
700 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
701 Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
703 return attacks_bb<ROOK>(rto, b) & ksq;
712 /// Position::do_move() makes a move, and saves all information necessary
713 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
714 /// moves should be filtered out before this function is called.
716 void Position::do_move(Move m, StateInfo& newSt) {
719 do_move(m, newSt, ci, move_gives_check(m, ci));
722 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
725 assert(&newSt != st);
730 // Copy some fields of old state to our new StateInfo object except the ones
731 // which are going to be recalculated from scratch anyway, then switch our state
732 // pointer to point to the new, ready to be updated, state.
733 memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
738 // Update side to move
741 // Increment ply counters.In particular rule50 will be later reset it to zero
742 // in case of a capture or a pawn move.
747 Color us = sideToMove;
749 Square from = from_sq(m);
750 Square to = to_sq(m);
751 Piece pc = piece_on(from);
752 PieceType pt = type_of(pc);
753 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
755 assert(color_of(pc) == us);
756 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
757 assert(capture != KING);
759 if (type_of(m) == CASTLE)
761 assert(pc == make_piece(us, KING));
763 bool kingSide = to > from;
764 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
765 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
766 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
767 capture = NO_PIECE_TYPE;
769 do_castle(from, to, rfrom, rto);
771 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
772 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
779 // If the captured piece is a pawn, update pawn hash key, otherwise
780 // update non-pawn material.
783 if (type_of(m) == ENPASSANT)
785 capsq += pawn_push(them);
788 assert(to == st->epSquare);
789 assert(relative_rank(us, to) == RANK_6);
790 assert(piece_on(to) == NO_PIECE);
791 assert(piece_on(capsq) == make_piece(them, PAWN));
793 board[capsq] = NO_PIECE;
796 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
799 st->npMaterial[them] -= PieceValue[MG][capture];
801 // Remove the captured piece
802 byTypeBB[ALL_PIECES] ^= capsq;
803 byTypeBB[capture] ^= capsq;
804 byColorBB[them] ^= capsq;
806 // Update piece list, move the last piece at index[capsq] position and
809 // WARNING: This is a not reversible operation. When we will reinsert the
810 // captured piece in undo_move() we will put it at the end of the list and
811 // not in its original place, it means index[] and pieceList[] are not
812 // guaranteed to be invariant to a do_move() + undo_move() sequence.
813 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
814 index[lastSquare] = index[capsq];
815 pieceList[them][capture][index[lastSquare]] = lastSquare;
816 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
818 // Update material hash key and prefetch access to materialTable
819 k ^= Zobrist::psq[them][capture][capsq];
820 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
821 prefetch((char*)thisThread->materialTable[st->materialKey]);
823 // Update incremental scores
824 st->psq -= psq[them][capture][capsq];
826 // Reset rule 50 counter
831 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
833 // Reset en passant square
834 if (st->epSquare != SQ_NONE)
836 k ^= Zobrist::enpassant[file_of(st->epSquare)];
837 st->epSquare = SQ_NONE;
840 // Update castle rights if needed
841 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
843 int cr = castleRightsMask[from] | castleRightsMask[to];
844 k ^= Zobrist::castle[st->castleRights & cr];
845 st->castleRights &= ~cr;
848 // Prefetch TT access as soon as we know the new hash key
849 prefetch((char*)TT.first_entry(k));
851 // Move the piece. The tricky Chess960 castle is handled earlier
852 if (type_of(m) != CASTLE)
854 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
855 byTypeBB[ALL_PIECES] ^= from_to_bb;
856 byTypeBB[pt] ^= from_to_bb;
857 byColorBB[us] ^= from_to_bb;
859 board[from] = NO_PIECE;
862 // Update piece lists, index[from] is not updated and becomes stale. This
863 // works as long as index[] is accessed just by known occupied squares.
864 index[to] = index[from];
865 pieceList[us][pt][index[to]] = to;
868 // If the moving piece is a pawn do some special extra work
871 // Set en-passant square, only if moved pawn can be captured
872 if ( (int(to) ^ int(from)) == 16
873 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
875 st->epSquare = Square((from + to) / 2);
876 k ^= Zobrist::enpassant[file_of(st->epSquare)];
879 if (type_of(m) == PROMOTION)
881 PieceType promotion = promotion_type(m);
883 assert(relative_rank(us, to) == RANK_8);
884 assert(promotion >= KNIGHT && promotion <= QUEEN);
886 // Replace the pawn with the promoted piece
887 byTypeBB[PAWN] ^= to;
888 byTypeBB[promotion] |= to;
889 board[to] = make_piece(us, promotion);
891 // Update piece lists, move the last pawn at index[to] position
892 // and shrink the list. Add a new promotion piece to the list.
893 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
894 index[lastSquare] = index[to];
895 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
896 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
897 index[to] = pieceCount[us][promotion];
898 pieceList[us][promotion][index[to]] = to;
901 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
902 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
903 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
904 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
906 // Update incremental score
907 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
910 st->npMaterial[us] += PieceValue[MG][promotion];
913 // Update pawn hash key and prefetch access to pawnsTable
914 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
915 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
917 // Reset rule 50 draw counter
921 // Update incremental scores
922 st->psq += psq[us][pt][to] - psq[us][pt][from];
925 st->capturedType = capture;
927 // Update the key with the final value
930 // Update checkers bitboard, piece must be already moved
935 if (type_of(m) != NORMAL)
936 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
940 if (ci.checkSq[pt] & to)
941 st->checkersBB |= to;
944 if (ci.dcCandidates && (ci.dcCandidates & from))
947 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
950 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
955 sideToMove = ~sideToMove;
961 /// Position::undo_move() unmakes a move. When it returns, the position should
962 /// be restored to exactly the same state as before the move was made.
964 void Position::undo_move(Move m) {
968 sideToMove = ~sideToMove;
970 Color us = sideToMove;
972 Square from = from_sq(m);
973 Square to = to_sq(m);
974 PieceType pt = type_of(piece_on(to));
975 PieceType capture = st->capturedType;
977 assert(is_empty(from) || type_of(m) == CASTLE);
978 assert(capture != KING);
980 if (type_of(m) == PROMOTION)
982 PieceType promotion = promotion_type(m);
984 assert(promotion == pt);
985 assert(relative_rank(us, to) == RANK_8);
986 assert(promotion >= KNIGHT && promotion <= QUEEN);
988 // Replace the promoted piece with the pawn
989 byTypeBB[promotion] ^= to;
990 byTypeBB[PAWN] |= to;
991 board[to] = make_piece(us, PAWN);
993 // Update piece lists, move the last promoted piece at index[to] position
994 // and shrink the list. Add a new pawn to the list.
995 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
996 index[lastSquare] = index[to];
997 pieceList[us][promotion][index[lastSquare]] = lastSquare;
998 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
999 index[to] = pieceCount[us][PAWN]++;
1000 pieceList[us][PAWN][index[to]] = to;
1005 if (type_of(m) == CASTLE)
1007 bool kingSide = to > from;
1008 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1009 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1010 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1011 capture = NO_PIECE_TYPE;
1013 do_castle(to, from, rto, rfrom);
1017 // Put the piece back at the source square
1018 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1019 byTypeBB[ALL_PIECES] ^= from_to_bb;
1020 byTypeBB[pt] ^= from_to_bb;
1021 byColorBB[us] ^= from_to_bb;
1023 board[to] = NO_PIECE;
1024 board[from] = make_piece(us, pt);
1026 // Update piece lists, index[to] is not updated and becomes stale. This
1027 // works as long as index[] is accessed just by known occupied squares.
1028 index[from] = index[to];
1029 pieceList[us][pt][index[from]] = from;
1036 if (type_of(m) == ENPASSANT)
1038 capsq -= pawn_push(us);
1041 assert(to == st->previous->epSquare);
1042 assert(relative_rank(us, to) == RANK_6);
1043 assert(piece_on(capsq) == NO_PIECE);
1046 // Restore the captured piece
1047 byTypeBB[ALL_PIECES] |= capsq;
1048 byTypeBB[capture] |= capsq;
1049 byColorBB[them] |= capsq;
1051 board[capsq] = make_piece(them, capture);
1053 // Update piece list, add a new captured piece in capsq square
1054 index[capsq] = pieceCount[them][capture]++;
1055 pieceList[them][capture][index[capsq]] = capsq;
1058 // Finally point our state pointer back to the previous state
1062 assert(pos_is_ok());
1066 /// Position::do_castle() is a helper used to do/undo a castling move. This
1067 /// is a bit tricky, especially in Chess960.
1069 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1071 Color us = sideToMove;
1072 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1073 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1074 byTypeBB[KING] ^= k_from_to_bb;
1075 byTypeBB[ROOK] ^= r_from_to_bb;
1076 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1077 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1079 // Could be from == to, so first set NO_PIECE then KING and ROOK
1080 board[kfrom] = board[rfrom] = NO_PIECE;
1081 board[kto] = make_piece(us, KING);
1082 board[rto] = make_piece(us, ROOK);
1084 // Could be kfrom == rto, so use a 'tmp' variable
1085 int tmp = index[kfrom];
1086 index[rto] = index[rfrom];
1088 pieceList[us][KING][index[kto]] = kto;
1089 pieceList[us][ROOK][index[rto]] = rto;
1093 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1094 /// the side to move without executing any move on the board.
1096 void Position::do_null_move(StateInfo& newSt) {
1098 assert(!checkers());
1100 memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1102 newSt.previous = st;
1105 if (st->epSquare != SQ_NONE)
1107 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1108 st->epSquare = SQ_NONE;
1111 st->key ^= Zobrist::side;
1112 prefetch((char*)TT.first_entry(st->key));
1115 st->pliesFromNull = 0;
1117 sideToMove = ~sideToMove;
1119 assert(pos_is_ok());
1122 void Position::undo_null_move() {
1124 assert(!checkers());
1127 sideToMove = ~sideToMove;
1131 /// Position::see() is a static exchange evaluator: It tries to estimate the
1132 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1133 /// tempi into account. If the side who initiated the capturing sequence does the
1134 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1135 /// the capturing sequence is considered bad.
1137 int Position::see_sign(Move m) const {
1141 // Early return if SEE cannot be negative because captured piece value
1142 // is not less then capturing one. Note that king moves always return
1143 // here because king midgame value is set to 0.
1144 if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1150 int Position::see(Move m, int asymmThreshold) const {
1153 Bitboard occupied, attackers, stmAttackers;
1154 int swapList[32], slIndex = 1;
1162 captured = type_of(piece_on(to));
1163 occupied = pieces() ^ from;
1165 // Handle en passant moves
1166 if (type_of(m) == ENPASSANT)
1168 Square capQq = to - pawn_push(sideToMove);
1171 assert(type_of(piece_on(capQq)) == PAWN);
1173 // Remove the captured pawn
1177 else if (type_of(m) == CASTLE)
1178 // Castle moves are implemented as king capturing the rook so cannot be
1179 // handled correctly. Simply return 0 that is always the correct value
1180 // unless the rook is ends up under attack.
1183 // Find all attackers to the destination square, with the moving piece
1184 // removed, but possibly an X-ray attacker added behind it.
1185 attackers = attackers_to(to, occupied);
1187 // If the opponent has no attackers we are finished
1188 stm = ~color_of(piece_on(from));
1189 stmAttackers = attackers & pieces(stm);
1191 return PieceValue[MG][captured];
1193 // The destination square is defended, which makes things rather more
1194 // difficult to compute. We proceed by building up a "swap list" containing
1195 // the material gain or loss at each stop in a sequence of captures to the
1196 // destination square, where the sides alternately capture, and always
1197 // capture with the least valuable piece. After each capture, we look for
1198 // new X-ray attacks from behind the capturing piece.
1199 swapList[0] = PieceValue[MG][captured];
1200 captured = type_of(piece_on(from));
1203 assert(slIndex < 32);
1205 // Add the new entry to the swap list
1206 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1209 // Locate and remove from 'occupied' the next least valuable attacker
1210 captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1212 attackers &= occupied; // Remove the just found attacker
1214 stmAttackers = attackers & pieces(stm);
1216 if (captured == KING)
1218 // Stop before processing a king capture
1220 swapList[slIndex++] = QueenValueMg * 16;
1225 } while (stmAttackers);
1227 // If we are doing asymmetric SEE evaluation and the same side does the first
1228 // and the last capture, he loses a tempo and gain must be at least worth
1229 // 'asymmThreshold', otherwise we replace the score with a very low value,
1230 // before negamaxing.
1232 for (int i = 0; i < slIndex; i += 2)
1233 if (swapList[i] < asymmThreshold)
1234 swapList[i] = - QueenValueMg * 16;
1236 // Having built the swap list, we negamax through it to find the best
1237 // achievable score from the point of view of the side to move.
1239 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1245 /// Position::clear() erases the position object to a pristine state, with an
1246 /// empty board, white to move, and no castling rights.
1248 void Position::clear() {
1250 memset(this, 0, sizeof(Position));
1251 startState.epSquare = SQ_NONE;
1254 for (int i = 0; i < 8; i++)
1255 for (int j = 0; j < 16; j++)
1256 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1260 /// Position::put_piece() puts a piece on the given square of the board,
1261 /// updating the board array, pieces list, bitboards, and piece counts.
1263 void Position::put_piece(Piece p, Square s) {
1265 Color c = color_of(p);
1266 PieceType pt = type_of(p);
1269 index[s] = pieceCount[c][pt]++;
1270 pieceList[c][pt][index[s]] = s;
1272 byTypeBB[ALL_PIECES] |= s;
1278 /// Position::compute_key() computes the hash key of the position. The hash
1279 /// key is usually updated incrementally as moves are made and unmade, the
1280 /// compute_key() function is only used when a new position is set up, and
1281 /// to verify the correctness of the hash key when running in debug mode.
1283 Key Position::compute_key() const {
1285 Key k = Zobrist::castle[st->castleRights];
1287 for (Bitboard b = pieces(); b; )
1289 Square s = pop_lsb(&b);
1290 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1293 if (ep_square() != SQ_NONE)
1294 k ^= Zobrist::enpassant[file_of(ep_square())];
1296 if (sideToMove == BLACK)
1303 /// Position::compute_pawn_key() computes the hash key of the position. The
1304 /// hash key is usually updated incrementally as moves are made and unmade,
1305 /// the compute_pawn_key() function is only used when a new position is set
1306 /// up, and to verify the correctness of the pawn hash key when running in
1309 Key Position::compute_pawn_key() const {
1313 for (Bitboard b = pieces(PAWN); b; )
1315 Square s = pop_lsb(&b);
1316 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1323 /// Position::compute_material_key() computes the hash key of the position.
1324 /// The hash key is usually updated incrementally as moves are made and unmade,
1325 /// the compute_material_key() function is only used when a new position is set
1326 /// up, and to verify the correctness of the material hash key when running in
1329 Key Position::compute_material_key() const {
1333 for (Color c = WHITE; c <= BLACK; c++)
1334 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1335 for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1336 k ^= Zobrist::psq[c][pt][cnt];
1342 /// Position::compute_psq_score() computes the incremental scores for the middle
1343 /// game and the endgame. These functions are used to initialize the incremental
1344 /// scores when a new position is set up, and to verify that the scores are correctly
1345 /// updated by do_move and undo_move when the program is running in debug mode.
1346 Score Position::compute_psq_score() const {
1348 Score score = SCORE_ZERO;
1350 for (Bitboard b = pieces(); b; )
1352 Square s = pop_lsb(&b);
1353 Piece pc = piece_on(s);
1354 score += psq[color_of(pc)][type_of(pc)][s];
1361 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1362 /// game material value for the given side. Material values are updated
1363 /// incrementally during the search, this function is only used while
1364 /// initializing a new Position object.
1366 Value Position::compute_non_pawn_material(Color c) const {
1368 Value value = VALUE_ZERO;
1370 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1371 value += piece_count(c, pt) * PieceValue[MG][pt];
1377 /// Position::is_draw() tests whether the position is drawn by material,
1378 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1379 /// must be done by the search.
1380 bool Position::is_draw() const {
1382 // Draw by material?
1384 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1387 // Draw by the 50 moves rule?
1388 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1391 // Draw by repetition?
1392 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1396 StateInfo* stp = st->previous->previous;
1399 stp = stp->previous->previous;
1401 if (stp->key == st->key)
1413 /// Position::flip() flips position with the white and black sides reversed. This
1414 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1416 void Position::flip() {
1418 const Position pos(*this);
1422 sideToMove = ~pos.side_to_move();
1423 thisThread = pos.this_thread();
1424 nodes = pos.nodes_searched();
1425 chess960 = pos.is_chess960();
1426 gamePly = pos.game_ply();
1428 for (Square s = SQ_A1; s <= SQ_H8; s++)
1429 if (!pos.is_empty(s))
1430 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1432 if (pos.can_castle(WHITE_OO))
1433 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1434 if (pos.can_castle(WHITE_OOO))
1435 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1436 if (pos.can_castle(BLACK_OO))
1437 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1438 if (pos.can_castle(BLACK_OOO))
1439 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1441 if (pos.st->epSquare != SQ_NONE)
1442 st->epSquare = ~pos.st->epSquare;
1444 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1446 st->key = compute_key();
1447 st->pawnKey = compute_pawn_key();
1448 st->materialKey = compute_material_key();
1449 st->psq = compute_psq_score();
1450 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1451 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1453 assert(pos_is_ok());
1457 /// Position::pos_is_ok() performs some consitency checks for the position object.
1458 /// This is meant to be helpful when debugging.
1460 bool Position::pos_is_ok(int* failedStep) const {
1462 int dummy, *step = failedStep ? failedStep : &dummy;
1464 // What features of the position should be verified?
1465 const bool all = false;
1467 const bool debugBitboards = all || false;
1468 const bool debugKingCount = all || false;
1469 const bool debugKingCapture = all || false;
1470 const bool debugCheckerCount = all || false;
1471 const bool debugKey = all || false;
1472 const bool debugMaterialKey = all || false;
1473 const bool debugPawnKey = all || false;
1474 const bool debugIncrementalEval = all || false;
1475 const bool debugNonPawnMaterial = all || false;
1476 const bool debugPieceCounts = all || false;
1477 const bool debugPieceList = all || false;
1478 const bool debugCastleSquares = all || false;
1482 if (sideToMove != WHITE && sideToMove != BLACK)
1485 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1488 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1491 if ((*step)++, debugKingCount)
1493 int kingCount[COLOR_NB] = {};
1495 for (Square s = SQ_A1; s <= SQ_H8; s++)
1496 if (type_of(piece_on(s)) == KING)
1497 kingCount[color_of(piece_on(s))]++;
1499 if (kingCount[0] != 1 || kingCount[1] != 1)
1503 if ((*step)++, debugKingCapture)
1504 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1507 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1510 if ((*step)++, debugBitboards)
1512 // The intersection of the white and black pieces must be empty
1513 if (pieces(WHITE) & pieces(BLACK))
1516 // The union of the white and black pieces must be equal to all
1518 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1521 // Separate piece type bitboards must have empty intersections
1522 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1523 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1524 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1528 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1531 if ((*step)++, debugKey && st->key != compute_key())
1534 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1537 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1540 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1543 if ((*step)++, debugNonPawnMaterial)
1545 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1546 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1550 if ((*step)++, debugPieceCounts)
1551 for (Color c = WHITE; c <= BLACK; c++)
1552 for (PieceType pt = PAWN; pt <= KING; pt++)
1553 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1556 if ((*step)++, debugPieceList)
1557 for (Color c = WHITE; c <= BLACK; c++)
1558 for (PieceType pt = PAWN; pt <= KING; pt++)
1559 for (int i = 0; i < pieceCount[c][pt]; i++)
1561 if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1564 if (index[piece_list(c, pt)[i]] != i)
1568 if ((*step)++, debugCastleSquares)
1569 for (Color c = WHITE; c <= BLACK; c++)
1570 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1572 CastleRight cr = make_castle_right(c, s);
1574 if (!can_castle(cr))
1577 if ((castleRightsMask[king_square(c)] & cr) != cr)
1580 if ( piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1581 || castleRightsMask[castleRookSquare[c][s]] != cr)