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 } };
49 Key Zobrist::psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
50 Key Zobrist::enpassant[FILE_NB];
51 Key Zobrist::castle[CASTLE_RIGHT_NB];
53 Key Zobrist::exclusion;
57 // next_attacker() is an helper function used by see() to locate the least
58 // valuable attacker for the side to move, remove the attacker we just found
59 // from the 'occupied' bitboard and scan for new X-ray attacks behind it.
61 template<int Pt> FORCE_INLINE
62 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
63 Bitboard& occupied, Bitboard& attackers) {
65 if (stmAttackers & bb[Pt])
67 Bitboard b = stmAttackers & bb[Pt];
68 occupied ^= b & ~(b - 1);
70 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
71 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
73 if (Pt == ROOK || Pt == QUEEN)
74 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
78 return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
81 template<> FORCE_INLINE
82 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
83 return KING; // No need to update bitboards, it is the last cycle
91 CheckInfo::CheckInfo(const Position& pos) {
93 Color them = ~pos.side_to_move();
94 ksq = pos.king_square(them);
96 pinned = pos.pinned_pieces();
97 dcCandidates = pos.discovered_check_candidates();
99 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
100 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
101 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
102 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
103 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
108 /// Position::init() initializes at startup the various arrays used to compute
109 /// hash keys and the piece square tables. The latter is a two-step operation:
110 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
111 /// the black halves of the tables are initialized by flipping and changing the
112 /// sign of the white scores.
114 void Position::init() {
118 for (Color c = WHITE; c <= BLACK; c++)
119 for (PieceType pt = PAWN; pt <= KING; pt++)
120 for (Square s = SQ_A1; s <= SQ_H8; s++)
121 Zobrist::psq[c][pt][s] = rk.rand<Key>();
123 for (File f = FILE_A; f <= FILE_H; f++)
124 Zobrist::enpassant[f] = rk.rand<Key>();
126 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
131 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
132 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
136 Zobrist::side = rk.rand<Key>();
137 Zobrist::exclusion = rk.rand<Key>();
139 for (PieceType pt = PAWN; pt <= KING; pt++)
141 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
142 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
144 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
146 for (Square s = SQ_A1; s <= SQ_H8; s++)
148 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
149 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
155 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
156 /// object do not depend on any external data so we detach state pointer from
159 Position& Position::operator=(const Position& pos) {
161 memcpy(this, &pos, sizeof(Position));
172 /// Position::set() initializes the position object with the given FEN string.
173 /// This function is not very robust - make sure that input FENs are correct,
174 /// this is assumed to be the responsibility of the GUI.
176 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
178 A FEN string defines a particular position using only the ASCII character set.
180 A FEN string contains six fields separated by a space. The fields are:
182 1) Piece placement (from white's perspective). Each rank is described, starting
183 with rank 8 and ending with rank 1; within each rank, the contents of each
184 square are described from file A through file H. Following the Standard
185 Algebraic Notation (SAN), each piece is identified by a single letter taken
186 from the standard English names. White pieces are designated using upper-case
187 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
188 noted using digits 1 through 8 (the number of blank squares), and "/"
191 2) Active color. "w" means white moves next, "b" means black.
193 3) Castling availability. If neither side can castle, this is "-". Otherwise,
194 this has one or more letters: "K" (White can castle kingside), "Q" (White
195 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
196 can castle queenside).
198 4) En passant target square (in algebraic notation). If there's no en passant
199 target square, this is "-". If a pawn has just made a 2-square move, this
200 is the position "behind" the pawn. This is recorded regardless of whether
201 there is a pawn in position to make an en passant capture.
203 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
204 or capture. This is used to determine if a draw can be claimed under the
207 6) Fullmove number. The number of the full move. It starts at 1, and is
208 incremented after Black's move.
211 char col, row, token;
214 std::istringstream ss(fenStr);
219 // 1. Piece placement
220 while ((ss >> token) && !isspace(token))
223 sq += Square(token - '0'); // Advance the given number of files
225 else if (token == '/')
228 else if ((p = PieceToChar.find(token)) != string::npos)
230 put_piece(Piece(p), sq);
237 sideToMove = (token == 'w' ? WHITE : BLACK);
240 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
241 // Shredder-FEN that uses the letters of the columns on which the rooks began
242 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
243 // if an inner rook is associated with the castling right, the castling tag is
244 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
245 while ((ss >> token) && !isspace(token))
248 Color c = islower(token) ? BLACK : WHITE;
250 token = char(toupper(token));
253 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
255 else if (token == 'Q')
256 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
258 else if (token >= 'A' && token <= 'H')
259 rsq = File(token - 'A') | relative_rank(c, RANK_1);
264 set_castle_right(c, rsq);
267 // 4. En passant square. Ignore if no pawn capture is possible
268 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
269 && ((ss >> row) && (row == '3' || row == '6')))
271 st->epSquare = File(col - 'a') | Rank(row - '1');
273 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
274 st->epSquare = SQ_NONE;
277 // 5-6. Halfmove clock and fullmove number
278 ss >> std::skipws >> st->rule50 >> gamePly;
280 // Convert from fullmove starting from 1 to ply starting from 0,
281 // handle also common incorrect FEN with fullmove = 0.
282 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
284 st->key = compute_key();
285 st->pawnKey = compute_pawn_key();
286 st->materialKey = compute_material_key();
287 st->psq = compute_psq_score();
288 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
289 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
290 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
291 chess960 = isChess960;
298 /// Position::set_castle_right() is an helper function used to set castling
299 /// rights given the corresponding color and the rook starting square.
301 void Position::set_castle_right(Color c, Square rfrom) {
303 Square kfrom = king_square(c);
304 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
305 CastleRight cr = make_castle_right(c, cs);
307 st->castleRights |= cr;
308 castleRightsMask[kfrom] |= cr;
309 castleRightsMask[rfrom] |= cr;
310 castleRookSquare[c][cs] = rfrom;
312 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
313 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
315 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
316 if (s != kfrom && s != rfrom)
317 castlePath[c][cs] |= s;
319 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
320 if (s != kfrom && s != rfrom)
321 castlePath[c][cs] |= s;
325 /// Position::fen() returns a FEN representation of the position. In case
326 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
328 const string Position::fen() const {
330 std::ostringstream ss;
332 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
334 for (File file = FILE_A; file <= FILE_H; file++)
336 Square sq = file | rank;
342 for ( ; file < FILE_H && is_empty(sq++); file++)
348 ss << PieceToChar[piece_on(sq)];
355 ss << (sideToMove == WHITE ? " w " : " b ");
357 if (can_castle(WHITE_OO))
358 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
360 if (can_castle(WHITE_OOO))
361 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
363 if (can_castle(BLACK_OO))
364 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
366 if (can_castle(BLACK_OOO))
367 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
369 if (st->castleRights == CASTLES_NONE)
372 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
373 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
379 /// Position::pretty() returns an ASCII representation of the position to be
380 /// printed to the standard output together with the move's san notation.
382 const string Position::pretty(Move move) const {
384 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
385 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
386 + dottedLine + "\n| . | | . | | . | | . | |";
388 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
390 std::ostringstream ss;
393 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
394 << move_to_san(*const_cast<Position*>(this), move);
396 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
397 if (piece_on(sq) != NO_PIECE)
398 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
400 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
401 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
403 for (Bitboard b = checkers(); b; )
404 ss << square_to_string(pop_lsb(&b)) << " ";
406 ss << "\nLegal moves: ";
407 for (MoveList<LEGAL> it(*this); *it; ++it)
408 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
414 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
415 /// king) pieces for the given color. Or, when template parameter FindPinned is
416 /// false, the function return the pieces of the given color candidate for a
417 /// discovery check against the enemy king.
418 template<bool FindPinned>
419 Bitboard Position::hidden_checkers() const {
421 // Pinned pieces protect our king, dicovery checks attack the enemy king
422 Bitboard b, result = 0;
423 Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
424 Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
426 // Pinners are sliders, that give check when candidate pinned is removed
427 pinners &= (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
428 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
432 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
434 if (b && !more_than_one(b) && (b & pieces(sideToMove)))
440 // Explicit template instantiations
441 template Bitboard Position::hidden_checkers<true>() const;
442 template Bitboard Position::hidden_checkers<false>() const;
445 /// Position::attackers_to() computes a bitboard of all pieces which attack a
446 /// given square. Slider attacks use occ bitboard as occupancy.
448 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
450 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
451 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
452 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
453 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
454 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
455 | (attacks_from<KING>(s) & pieces(KING));
459 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
460 /// put in a given square. Slider attacks use occ bitboard as occupancy.
462 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
468 case BISHOP: return attacks_bb<BISHOP>(s, occ);
469 case ROOK : return attacks_bb<ROOK>(s, occ);
470 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
471 default : return StepAttacksBB[p][s];
476 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
478 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
481 assert(pinned == pinned_pieces());
483 Color us = sideToMove;
484 Square from = from_sq(m);
486 assert(color_of(piece_moved(m)) == us);
487 assert(piece_on(king_square(us)) == make_piece(us, KING));
489 // En passant captures are a tricky special case. Because they are rather
490 // uncommon, we do it simply by testing whether the king is attacked after
492 if (type_of(m) == ENPASSANT)
495 Square to = to_sq(m);
496 Square capsq = to + pawn_push(them);
497 Square ksq = king_square(us);
498 Bitboard b = (pieces() ^ from ^ capsq) | to;
500 assert(to == ep_square());
501 assert(piece_moved(m) == make_piece(us, PAWN));
502 assert(piece_on(capsq) == make_piece(them, PAWN));
503 assert(piece_on(to) == NO_PIECE);
505 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
506 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
509 // If the moving piece is a king, check whether the destination
510 // square is attacked by the opponent. Castling moves are checked
511 // for legality during move generation.
512 if (type_of(piece_on(from)) == KING)
513 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
515 // A non-king move is legal if and only if it is not pinned or it
516 // is moving along the ray towards or away from the king.
519 || squares_aligned(from, to_sq(m), king_square(us));
523 /// Position::is_pseudo_legal() takes a random move and tests whether the move
524 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
525 /// due to SMP concurrent access or hash position key aliasing.
527 bool Position::is_pseudo_legal(const Move m) const {
529 Color us = sideToMove;
530 Square from = from_sq(m);
531 Square to = to_sq(m);
532 Piece pc = piece_moved(m);
534 // Use a slower but simpler function for uncommon cases
535 if (type_of(m) != NORMAL)
536 return MoveList<LEGAL>(*this).contains(m);
538 // Is not a promotion, so promotion piece must be empty
539 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
542 // If the from square is not occupied by a piece belonging to the side to
543 // move, the move is obviously not legal.
544 if (pc == NO_PIECE || color_of(pc) != us)
547 // The destination square cannot be occupied by a friendly piece
548 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
551 // Handle the special case of a pawn move
552 if (type_of(pc) == PAWN)
554 // Move direction must be compatible with pawn color
555 int direction = to - from;
556 if ((us == WHITE) != (direction > 0))
559 // We have already handled promotion moves, so destination
560 // cannot be on the 8/1th rank.
561 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
564 // Proceed according to the square delta between the origin and
565 // destination squares.
572 // Capture. The destination square must be occupied by an enemy
573 // piece (en passant captures was handled earlier).
574 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
577 // From and to files must be one file apart, avoids a7h5
578 if (abs(file_of(from) - file_of(to)) != 1)
584 // Pawn push. The destination square must be empty.
590 // Double white pawn push. The destination square must be on the fourth
591 // rank, and both the destination square and the square between the
592 // source and destination squares must be empty.
593 if ( rank_of(to) != RANK_4
595 || !is_empty(from + DELTA_N))
600 // Double black pawn push. The destination square must be on the fifth
601 // rank, and both the destination square and the square between the
602 // source and destination squares must be empty.
603 if ( rank_of(to) != RANK_5
605 || !is_empty(from + DELTA_S))
613 else if (!(attacks_from(pc, from) & to))
616 // Evasions generator already takes care to avoid some kind of illegal moves
617 // and pl_move_is_legal() relies on this. So we have to take care that the
618 // same kind of moves are filtered out here.
621 if (type_of(pc) != KING)
623 // Double check? In this case a king move is required
624 if (more_than_one(checkers()))
627 // Our move must be a blocking evasion or a capture of the checking piece
628 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
631 // In case of king moves under check we have to remove king so to catch
632 // as invalid moves like b1a1 when opposite queen is on c1.
633 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
641 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
643 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
646 assert(ci.dcCandidates == discovered_check_candidates());
647 assert(color_of(piece_moved(m)) == sideToMove);
649 Square from = from_sq(m);
650 Square to = to_sq(m);
651 PieceType pt = type_of(piece_on(from));
654 if (ci.checkSq[pt] & to)
658 if (ci.dcCandidates && (ci.dcCandidates & from))
660 // For pawn and king moves we need to verify also direction
661 if ( (pt != PAWN && pt != KING)
662 || !squares_aligned(from, to, king_square(~sideToMove)))
666 // Can we skip the ugly special cases ?
667 if (type_of(m) == NORMAL)
670 Color us = sideToMove;
671 Square ksq = king_square(~us);
676 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
678 // En passant capture with check ? We have already handled the case
679 // of direct checks and ordinary discovered check, the only case we
680 // need to handle is the unusual case of a discovered check through
681 // the captured pawn.
684 Square capsq = file_of(to) | rank_of(from);
685 Bitboard b = (pieces() ^ from ^ capsq) | to;
687 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
688 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
693 Square rfrom = to; // 'King captures the rook' notation
694 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
695 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
696 Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
698 return attacks_bb<ROOK>(rto, b) & ksq;
707 /// Position::do_move() makes a move, and saves all information necessary
708 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
709 /// moves should be filtered out before this function is called.
711 void Position::do_move(Move m, StateInfo& newSt) {
714 do_move(m, newSt, ci, move_gives_check(m, ci));
717 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
720 assert(&newSt != st);
725 // Copy some fields of old state to our new StateInfo object except the ones
726 // which are going to be recalculated from scratch anyway, then switch our state
727 // pointer to point to the new, ready to be updated, state.
728 memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
733 // Update side to move
736 // Increment ply counters.In particular rule50 will be later reset it to zero
737 // in case of a capture or a pawn move.
742 Color us = sideToMove;
744 Square from = from_sq(m);
745 Square to = to_sq(m);
746 Piece pc = piece_on(from);
747 PieceType pt = type_of(pc);
748 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
750 assert(color_of(pc) == us);
751 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
752 assert(capture != KING);
754 if (type_of(m) == CASTLE)
756 assert(pc == make_piece(us, KING));
758 bool kingSide = to > from;
759 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
760 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
761 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
762 capture = NO_PIECE_TYPE;
764 do_castle(from, to, rfrom, rto);
766 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
767 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
774 // If the captured piece is a pawn, update pawn hash key, otherwise
775 // update non-pawn material.
778 if (type_of(m) == ENPASSANT)
780 capsq += pawn_push(them);
783 assert(to == st->epSquare);
784 assert(relative_rank(us, to) == RANK_6);
785 assert(piece_on(to) == NO_PIECE);
786 assert(piece_on(capsq) == make_piece(them, PAWN));
788 board[capsq] = NO_PIECE;
791 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
794 st->npMaterial[them] -= PieceValue[MG][capture];
796 // Remove the captured piece
797 byTypeBB[ALL_PIECES] ^= capsq;
798 byTypeBB[capture] ^= capsq;
799 byColorBB[them] ^= capsq;
801 // Update piece list, move the last piece at index[capsq] position and
804 // WARNING: This is a not reversible operation. When we will reinsert the
805 // captured piece in undo_move() we will put it at the end of the list and
806 // not in its original place, it means index[] and pieceList[] are not
807 // guaranteed to be invariant to a do_move() + undo_move() sequence.
808 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
809 index[lastSquare] = index[capsq];
810 pieceList[them][capture][index[lastSquare]] = lastSquare;
811 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
813 // Update material hash key and prefetch access to materialTable
814 k ^= Zobrist::psq[them][capture][capsq];
815 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
816 prefetch((char*)thisThread->materialTable[st->materialKey]);
818 // Update incremental scores
819 st->psq -= psq[them][capture][capsq];
821 // Reset rule 50 counter
826 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
828 // Reset en passant square
829 if (st->epSquare != SQ_NONE)
831 k ^= Zobrist::enpassant[file_of(st->epSquare)];
832 st->epSquare = SQ_NONE;
835 // Update castle rights if needed
836 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
838 int cr = castleRightsMask[from] | castleRightsMask[to];
839 k ^= Zobrist::castle[st->castleRights & cr];
840 st->castleRights &= ~cr;
843 // Prefetch TT access as soon as we know the new hash key
844 prefetch((char*)TT.first_entry(k));
846 // Move the piece. The tricky Chess960 castle is handled earlier
847 if (type_of(m) != CASTLE)
849 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
850 byTypeBB[ALL_PIECES] ^= from_to_bb;
851 byTypeBB[pt] ^= from_to_bb;
852 byColorBB[us] ^= from_to_bb;
854 board[from] = NO_PIECE;
857 // Update piece lists, index[from] is not updated and becomes stale. This
858 // works as long as index[] is accessed just by known occupied squares.
859 index[to] = index[from];
860 pieceList[us][pt][index[to]] = to;
863 // If the moving piece is a pawn do some special extra work
866 // Set en-passant square, only if moved pawn can be captured
867 if ( (int(to) ^ int(from)) == 16
868 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
870 st->epSquare = Square((from + to) / 2);
871 k ^= Zobrist::enpassant[file_of(st->epSquare)];
874 if (type_of(m) == PROMOTION)
876 PieceType promotion = promotion_type(m);
878 assert(relative_rank(us, to) == RANK_8);
879 assert(promotion >= KNIGHT && promotion <= QUEEN);
881 // Replace the pawn with the promoted piece
882 byTypeBB[PAWN] ^= to;
883 byTypeBB[promotion] |= to;
884 board[to] = make_piece(us, promotion);
886 // Update piece lists, move the last pawn at index[to] position
887 // and shrink the list. Add a new promotion piece to the list.
888 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
889 index[lastSquare] = index[to];
890 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
891 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
892 index[to] = pieceCount[us][promotion];
893 pieceList[us][promotion][index[to]] = to;
896 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
897 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
898 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
899 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
901 // Update incremental score
902 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
905 st->npMaterial[us] += PieceValue[MG][promotion];
908 // Update pawn hash key and prefetch access to pawnsTable
909 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
910 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
912 // Reset rule 50 draw counter
916 // Update incremental scores
917 st->psq += psq[us][pt][to] - psq[us][pt][from];
920 st->capturedType = capture;
922 // Update the key with the final value
925 // Update checkers bitboard, piece must be already moved
930 if (type_of(m) != NORMAL)
931 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
935 if (ci.checkSq[pt] & to)
936 st->checkersBB |= to;
939 if (ci.dcCandidates && (ci.dcCandidates & from))
942 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
945 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
950 sideToMove = ~sideToMove;
956 /// Position::undo_move() unmakes a move. When it returns, the position should
957 /// be restored to exactly the same state as before the move was made.
959 void Position::undo_move(Move m) {
963 sideToMove = ~sideToMove;
965 Color us = sideToMove;
967 Square from = from_sq(m);
968 Square to = to_sq(m);
969 PieceType pt = type_of(piece_on(to));
970 PieceType capture = st->capturedType;
972 assert(is_empty(from) || type_of(m) == CASTLE);
973 assert(capture != KING);
975 if (type_of(m) == PROMOTION)
977 PieceType promotion = promotion_type(m);
979 assert(promotion == pt);
980 assert(relative_rank(us, to) == RANK_8);
981 assert(promotion >= KNIGHT && promotion <= QUEEN);
983 // Replace the promoted piece with the pawn
984 byTypeBB[promotion] ^= to;
985 byTypeBB[PAWN] |= to;
986 board[to] = make_piece(us, PAWN);
988 // Update piece lists, move the last promoted piece at index[to] position
989 // and shrink the list. Add a new pawn to the list.
990 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
991 index[lastSquare] = index[to];
992 pieceList[us][promotion][index[lastSquare]] = lastSquare;
993 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
994 index[to] = pieceCount[us][PAWN]++;
995 pieceList[us][PAWN][index[to]] = to;
1000 if (type_of(m) == CASTLE)
1002 bool kingSide = to > from;
1003 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1004 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1005 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1006 capture = NO_PIECE_TYPE;
1008 do_castle(to, from, rto, rfrom);
1012 // Put the piece back at the source square
1013 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1014 byTypeBB[ALL_PIECES] ^= from_to_bb;
1015 byTypeBB[pt] ^= from_to_bb;
1016 byColorBB[us] ^= from_to_bb;
1018 board[to] = NO_PIECE;
1019 board[from] = make_piece(us, pt);
1021 // Update piece lists, index[to] is not updated and becomes stale. This
1022 // works as long as index[] is accessed just by known occupied squares.
1023 index[from] = index[to];
1024 pieceList[us][pt][index[from]] = from;
1031 if (type_of(m) == ENPASSANT)
1033 capsq -= pawn_push(us);
1036 assert(to == st->previous->epSquare);
1037 assert(relative_rank(us, to) == RANK_6);
1038 assert(piece_on(capsq) == NO_PIECE);
1041 // Restore the captured piece
1042 byTypeBB[ALL_PIECES] |= capsq;
1043 byTypeBB[capture] |= capsq;
1044 byColorBB[them] |= capsq;
1046 board[capsq] = make_piece(them, capture);
1048 // Update piece list, add a new captured piece in capsq square
1049 index[capsq] = pieceCount[them][capture]++;
1050 pieceList[them][capture][index[capsq]] = capsq;
1053 // Finally point our state pointer back to the previous state
1057 assert(pos_is_ok());
1061 /// Position::do_castle() is a helper used to do/undo a castling move. This
1062 /// is a bit tricky, especially in Chess960.
1064 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1066 Color us = sideToMove;
1067 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1068 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1069 byTypeBB[KING] ^= k_from_to_bb;
1070 byTypeBB[ROOK] ^= r_from_to_bb;
1071 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1072 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1074 // Could be from == to, so first set NO_PIECE then KING and ROOK
1075 board[kfrom] = board[rfrom] = NO_PIECE;
1076 board[kto] = make_piece(us, KING);
1077 board[rto] = make_piece(us, ROOK);
1079 // Could be kfrom == rto, so use a 'tmp' variable
1080 int tmp = index[kfrom];
1081 index[rto] = index[rfrom];
1083 pieceList[us][KING][index[kto]] = kto;
1084 pieceList[us][ROOK][index[rto]] = rto;
1088 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1089 /// the side to move without executing any move on the board.
1091 void Position::do_null_move(StateInfo& newSt) {
1093 assert(!checkers());
1095 memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1097 newSt.previous = st;
1100 if (st->epSquare != SQ_NONE)
1102 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1103 st->epSquare = SQ_NONE;
1106 st->key ^= Zobrist::side;
1107 prefetch((char*)TT.first_entry(st->key));
1110 st->pliesFromNull = 0;
1112 sideToMove = ~sideToMove;
1114 assert(pos_is_ok());
1117 void Position::undo_null_move() {
1119 assert(!checkers());
1122 sideToMove = ~sideToMove;
1126 /// Position::see() is a static exchange evaluator: It tries to estimate the
1127 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1128 /// tempi into account. If the side who initiated the capturing sequence does the
1129 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1130 /// the capturing sequence is considered bad.
1132 int Position::see_sign(Move m) const {
1136 // Early return if SEE cannot be negative because captured piece value
1137 // is not less then capturing one. Note that king moves always return
1138 // here because king midgame value is set to 0.
1139 if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1145 int Position::see(Move m, int asymmThreshold) const {
1148 Bitboard occupied, attackers, stmAttackers;
1149 int swapList[32], slIndex = 1;
1157 captured = type_of(piece_on(to));
1158 occupied = pieces() ^ from;
1160 // Handle en passant moves
1161 if (type_of(m) == ENPASSANT)
1163 Square capQq = to - pawn_push(sideToMove);
1166 assert(type_of(piece_on(capQq)) == PAWN);
1168 // Remove the captured pawn
1172 else if (type_of(m) == CASTLE)
1173 // Castle moves are implemented as king capturing the rook so cannot be
1174 // handled correctly. Simply return 0 that is always the correct value
1175 // unless the rook is ends up under attack.
1178 // Find all attackers to the destination square, with the moving piece
1179 // removed, but possibly an X-ray attacker added behind it.
1180 attackers = attackers_to(to, occupied);
1182 // If the opponent has no attackers we are finished
1183 stm = ~color_of(piece_on(from));
1184 stmAttackers = attackers & pieces(stm);
1186 return PieceValue[MG][captured];
1188 // The destination square is defended, which makes things rather more
1189 // difficult to compute. We proceed by building up a "swap list" containing
1190 // the material gain or loss at each stop in a sequence of captures to the
1191 // destination square, where the sides alternately capture, and always
1192 // capture with the least valuable piece. After each capture, we look for
1193 // new X-ray attacks from behind the capturing piece.
1194 swapList[0] = PieceValue[MG][captured];
1195 captured = type_of(piece_on(from));
1198 assert(slIndex < 32);
1200 // Add the new entry to the swap list
1201 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1204 // Locate and remove from 'occupied' the next least valuable attacker
1205 captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1207 attackers &= occupied; // Remove the just found attacker
1209 stmAttackers = attackers & pieces(stm);
1211 if (captured == KING)
1213 // Stop before processing a king capture
1215 swapList[slIndex++] = QueenValueMg * 16;
1220 } while (stmAttackers);
1222 // If we are doing asymmetric SEE evaluation and the same side does the first
1223 // and the last capture, he loses a tempo and gain must be at least worth
1224 // 'asymmThreshold', otherwise we replace the score with a very low value,
1225 // before negamaxing.
1227 for (int i = 0; i < slIndex; i += 2)
1228 if (swapList[i] < asymmThreshold)
1229 swapList[i] = - QueenValueMg * 16;
1231 // Having built the swap list, we negamax through it to find the best
1232 // achievable score from the point of view of the side to move.
1234 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1240 /// Position::clear() erases the position object to a pristine state, with an
1241 /// empty board, white to move, and no castling rights.
1243 void Position::clear() {
1245 memset(this, 0, sizeof(Position));
1246 startState.epSquare = SQ_NONE;
1249 for (int i = 0; i < 8; i++)
1250 for (int j = 0; j < 16; j++)
1251 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1255 /// Position::put_piece() puts a piece on the given square of the board,
1256 /// updating the board array, pieces list, bitboards, and piece counts.
1258 void Position::put_piece(Piece p, Square s) {
1260 Color c = color_of(p);
1261 PieceType pt = type_of(p);
1264 index[s] = pieceCount[c][pt]++;
1265 pieceList[c][pt][index[s]] = s;
1267 byTypeBB[ALL_PIECES] |= s;
1273 /// Position::compute_key() computes the hash key of the position. The hash
1274 /// key is usually updated incrementally as moves are made and unmade, the
1275 /// compute_key() function is only used when a new position is set up, and
1276 /// to verify the correctness of the hash key when running in debug mode.
1278 Key Position::compute_key() const {
1280 Key k = Zobrist::castle[st->castleRights];
1282 for (Bitboard b = pieces(); b; )
1284 Square s = pop_lsb(&b);
1285 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1288 if (ep_square() != SQ_NONE)
1289 k ^= Zobrist::enpassant[file_of(ep_square())];
1291 if (sideToMove == BLACK)
1298 /// Position::compute_pawn_key() computes the hash key of the position. The
1299 /// hash key is usually updated incrementally as moves are made and unmade,
1300 /// the compute_pawn_key() function is only used when a new position is set
1301 /// up, and to verify the correctness of the pawn hash key when running in
1304 Key Position::compute_pawn_key() const {
1308 for (Bitboard b = pieces(PAWN); b; )
1310 Square s = pop_lsb(&b);
1311 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1318 /// Position::compute_material_key() computes the hash key of the position.
1319 /// The hash key is usually updated incrementally as moves are made and unmade,
1320 /// the compute_material_key() function is only used when a new position is set
1321 /// up, and to verify the correctness of the material hash key when running in
1324 Key Position::compute_material_key() const {
1328 for (Color c = WHITE; c <= BLACK; c++)
1329 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1330 for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1331 k ^= Zobrist::psq[c][pt][cnt];
1337 /// Position::compute_psq_score() computes the incremental scores for the middle
1338 /// game and the endgame. These functions are used to initialize the incremental
1339 /// scores when a new position is set up, and to verify that the scores are correctly
1340 /// updated by do_move and undo_move when the program is running in debug mode.
1341 Score Position::compute_psq_score() const {
1343 Score score = SCORE_ZERO;
1345 for (Bitboard b = pieces(); b; )
1347 Square s = pop_lsb(&b);
1348 Piece pc = piece_on(s);
1349 score += psq[color_of(pc)][type_of(pc)][s];
1356 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1357 /// game material value for the given side. Material values are updated
1358 /// incrementally during the search, this function is only used while
1359 /// initializing a new Position object.
1361 Value Position::compute_non_pawn_material(Color c) const {
1363 Value value = VALUE_ZERO;
1365 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1366 value += piece_count(c, pt) * PieceValue[MG][pt];
1372 /// Position::is_draw() tests whether the position is drawn by material,
1373 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1374 /// must be done by the search.
1375 bool Position::is_draw() const {
1377 // Draw by material?
1379 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1382 // Draw by the 50 moves rule?
1383 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1386 // Draw by repetition?
1387 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1391 StateInfo* stp = st->previous->previous;
1394 stp = stp->previous->previous;
1396 if (stp->key == st->key)
1408 /// Position::flip() flips position with the white and black sides reversed. This
1409 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1411 void Position::flip() {
1413 const Position pos(*this);
1417 sideToMove = ~pos.side_to_move();
1418 thisThread = pos.this_thread();
1419 nodes = pos.nodes_searched();
1420 chess960 = pos.is_chess960();
1421 gamePly = pos.game_ply();
1423 for (Square s = SQ_A1; s <= SQ_H8; s++)
1424 if (!pos.is_empty(s))
1425 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1427 if (pos.can_castle(WHITE_OO))
1428 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1429 if (pos.can_castle(WHITE_OOO))
1430 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1431 if (pos.can_castle(BLACK_OO))
1432 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1433 if (pos.can_castle(BLACK_OOO))
1434 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1436 if (pos.st->epSquare != SQ_NONE)
1437 st->epSquare = ~pos.st->epSquare;
1439 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1441 st->key = compute_key();
1442 st->pawnKey = compute_pawn_key();
1443 st->materialKey = compute_material_key();
1444 st->psq = compute_psq_score();
1445 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1446 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1448 assert(pos_is_ok());
1452 /// Position::pos_is_ok() performs some consitency checks for the position object.
1453 /// This is meant to be helpful when debugging.
1455 bool Position::pos_is_ok(int* failedStep) const {
1457 int dummy, *step = failedStep ? failedStep : &dummy;
1459 // What features of the position should be verified?
1460 const bool all = false;
1462 const bool debugBitboards = all || false;
1463 const bool debugKingCount = all || false;
1464 const bool debugKingCapture = all || false;
1465 const bool debugCheckerCount = all || false;
1466 const bool debugKey = all || false;
1467 const bool debugMaterialKey = all || false;
1468 const bool debugPawnKey = all || false;
1469 const bool debugIncrementalEval = all || false;
1470 const bool debugNonPawnMaterial = all || false;
1471 const bool debugPieceCounts = all || false;
1472 const bool debugPieceList = all || false;
1473 const bool debugCastleSquares = all || false;
1477 if (sideToMove != WHITE && sideToMove != BLACK)
1480 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1483 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1486 if ((*step)++, debugKingCount)
1488 int kingCount[COLOR_NB] = {};
1490 for (Square s = SQ_A1; s <= SQ_H8; s++)
1491 if (type_of(piece_on(s)) == KING)
1492 kingCount[color_of(piece_on(s))]++;
1494 if (kingCount[0] != 1 || kingCount[1] != 1)
1498 if ((*step)++, debugKingCapture)
1499 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1502 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1505 if ((*step)++, debugBitboards)
1507 // The intersection of the white and black pieces must be empty
1508 if (pieces(WHITE) & pieces(BLACK))
1511 // The union of the white and black pieces must be equal to all
1513 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1516 // Separate piece type bitboards must have empty intersections
1517 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1518 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1519 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1523 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1526 if ((*step)++, debugKey && st->key != compute_key())
1529 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1532 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1535 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1538 if ((*step)++, debugNonPawnMaterial)
1540 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1541 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1545 if ((*step)++, debugPieceCounts)
1546 for (Color c = WHITE; c <= BLACK; c++)
1547 for (PieceType pt = PAWN; pt <= KING; pt++)
1548 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1551 if ((*step)++, debugPieceList)
1552 for (Color c = WHITE; c <= BLACK; c++)
1553 for (PieceType pt = PAWN; pt <= KING; pt++)
1554 for (int i = 0; i < pieceCount[c][pt]; i++)
1556 if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1559 if (index[piece_list(c, pt)[i]] != i)
1563 if ((*step)++, debugCastleSquares)
1564 for (Color c = WHITE; c <= BLACK; c++)
1565 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1567 CastleRight cr = make_castle_right(c, s);
1569 if (!can_castle(cr))
1572 if ((castleRightsMask[king_square(c)] & cr) != cr)
1575 if ( piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1576 || castleRightsMask[castleRookSquare[c][s]] != cr)