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 pieceSquareTable[PIECE_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];
57 /// init() initializes at startup the various arrays used to compute hash keys
58 /// and the piece square tables. The latter is a two-step operation: First, the
59 /// white halves of the tables are copied from PSQT[] tables. Second, the black
60 /// halves of the tables are initialized by flipping and changing the sign of
67 for (Color c = WHITE; c <= BLACK; c++)
68 for (PieceType pt = PAWN; pt <= KING; pt++)
69 for (Square s = SQ_A1; s <= SQ_H8; s++)
70 psq[c][pt][s] = rk.rand<Key>();
72 for (File f = FILE_A; f <= FILE_H; f++)
73 enpassant[f] = rk.rand<Key>();
75 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
80 Key k = castle[1ULL << pop_lsb(&b)];
81 castle[cr] ^= k ? k : rk.rand<Key>();
85 side = rk.rand<Key>();
86 exclusion = rk.rand<Key>();
88 for (PieceType pt = PAWN; pt <= KING; pt++)
90 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
91 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
93 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
95 for (Square s = SQ_A1; s <= SQ_H8; s++)
97 pieceSquareTable[make_piece(WHITE, pt)][ s] = (v + PSQT[pt][s]);
98 pieceSquareTable[make_piece(BLACK, pt)][~s] = -(v + PSQT[pt][s]);
103 } // namespace Zobrist
108 /// next_attacker() is an helper function used by see() to locate the least
109 /// valuable attacker for the side to move, remove the attacker we just found
110 /// from the 'occupied' bitboard and scan for new X-ray attacks behind it.
112 template<int Pt> FORCE_INLINE
113 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
114 Bitboard& occupied, Bitboard& attackers) {
116 if (stmAttackers & bb[Pt])
118 Bitboard b = stmAttackers & bb[Pt];
119 occupied ^= b & ~(b - 1);
121 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
122 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
124 if (Pt == ROOK || Pt == QUEEN)
125 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
127 return (PieceType)Pt;
129 return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
132 template<> FORCE_INLINE
133 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
134 return KING; // No need to update bitboards, it is the last cycle
142 CheckInfo::CheckInfo(const Position& pos) {
144 Color them = ~pos.side_to_move();
145 ksq = pos.king_square(them);
147 pinned = pos.pinned_pieces();
148 dcCandidates = pos.discovered_check_candidates();
150 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
151 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
152 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
153 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
154 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
159 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
160 /// object do not depend on any external data so we detach state pointer from
163 Position& Position::operator=(const Position& pos) {
165 memcpy(this, &pos, sizeof(Position));
176 /// Position::set() initializes the position object with the given FEN string.
177 /// This function is not very robust - make sure that input FENs are correct,
178 /// this is assumed to be the responsibility of the GUI.
180 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
182 A FEN string defines a particular position using only the ASCII character set.
184 A FEN string contains six fields separated by a space. The fields are:
186 1) Piece placement (from white's perspective). Each rank is described, starting
187 with rank 8 and ending with rank 1; within each rank, the contents of each
188 square are described from file A through file H. Following the Standard
189 Algebraic Notation (SAN), each piece is identified by a single letter taken
190 from the standard English names. White pieces are designated using upper-case
191 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
192 noted using digits 1 through 8 (the number of blank squares), and "/"
195 2) Active color. "w" means white moves next, "b" means black.
197 3) Castling availability. If neither side can castle, this is "-". Otherwise,
198 this has one or more letters: "K" (White can castle kingside), "Q" (White
199 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
200 can castle queenside).
202 4) En passant target square (in algebraic notation). If there's no en passant
203 target square, this is "-". If a pawn has just made a 2-square move, this
204 is the position "behind" the pawn. This is recorded regardless of whether
205 there is a pawn in position to make an en passant capture.
207 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
208 or capture. This is used to determine if a draw can be claimed under the
211 6) Fullmove number. The number of the full move. It starts at 1, and is
212 incremented after Black's move.
215 char col, row, token;
218 std::istringstream ss(fenStr);
223 // 1. Piece placement
224 while ((ss >> token) && !isspace(token))
227 sq += Square(token - '0'); // Advance the given number of files
229 else if (token == '/')
232 else if ((p = PieceToChar.find(token)) != string::npos)
234 put_piece(Piece(p), sq);
241 sideToMove = (token == 'w' ? WHITE : BLACK);
244 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
245 // Shredder-FEN that uses the letters of the columns on which the rooks began
246 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
247 // if an inner rook is associated with the castling right, the castling tag is
248 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
249 while ((ss >> token) && !isspace(token))
252 Color c = islower(token) ? BLACK : WHITE;
254 token = char(toupper(token));
257 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
259 else if (token == 'Q')
260 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
262 else if (token >= 'A' && token <= 'H')
263 rsq = File(token - 'A') | relative_rank(c, RANK_1);
268 set_castle_right(c, rsq);
271 // 4. En passant square. Ignore if no pawn capture is possible
272 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
273 && ((ss >> row) && (row == '3' || row == '6')))
275 st->epSquare = File(col - 'a') | Rank(row - '1');
277 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
278 st->epSquare = SQ_NONE;
281 // 5-6. Halfmove clock and fullmove number
282 ss >> std::skipws >> st->rule50 >> gamePly;
284 // Convert from fullmove starting from 1 to ply starting from 0,
285 // handle also common incorrect FEN with fullmove = 0.
286 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
288 st->key = compute_key();
289 st->pawnKey = compute_pawn_key();
290 st->materialKey = compute_material_key();
291 st->psqScore = compute_psq_score();
292 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
293 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
294 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
295 chess960 = isChess960;
302 /// Position::set_castle_right() is an helper function used to set castling
303 /// rights given the corresponding color and the rook starting square.
305 void Position::set_castle_right(Color c, Square rfrom) {
307 Square kfrom = king_square(c);
308 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
309 CastleRight cr = make_castle_right(c, cs);
311 st->castleRights |= cr;
312 castleRightsMask[kfrom] |= cr;
313 castleRightsMask[rfrom] |= cr;
314 castleRookSquare[c][cs] = rfrom;
316 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
317 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
319 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
320 if (s != kfrom && s != rfrom)
321 castlePath[c][cs] |= s;
323 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
324 if (s != kfrom && s != rfrom)
325 castlePath[c][cs] |= s;
329 /// Position::fen() returns a FEN representation of the position. In case
330 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
332 const string Position::fen() const {
334 std::ostringstream ss;
336 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
338 for (File file = FILE_A; file <= FILE_H; file++)
340 Square sq = file | rank;
346 for ( ; file < FILE_H && is_empty(sq++); file++)
352 ss << PieceToChar[piece_on(sq)];
359 ss << (sideToMove == WHITE ? " w " : " b ");
361 if (can_castle(WHITE_OO))
362 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
364 if (can_castle(WHITE_OOO))
365 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
367 if (can_castle(BLACK_OO))
368 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
370 if (can_castle(BLACK_OOO))
371 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
373 if (st->castleRights == CASTLES_NONE)
376 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
377 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
383 /// Position::pretty() returns an ASCII representation of the position to be
384 /// printed to the standard output together with the move's san notation.
386 const string Position::pretty(Move move) const {
388 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
389 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
390 + dottedLine + "\n| . | | . | | . | | . | |";
392 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
394 std::ostringstream ss;
397 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
398 << move_to_san(*const_cast<Position*>(this), move);
400 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
401 if (piece_on(sq) != NO_PIECE)
402 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
404 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
405 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
407 for (Bitboard b = checkers(); b; )
408 ss << square_to_string(pop_lsb(&b)) << " ";
410 ss << "\nLegal moves: ";
411 for (MoveList<LEGAL> ml(*this); !ml.end(); ++ml)
412 ss << move_to_san(*const_cast<Position*>(this), ml.move()) << " ";
418 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
419 /// king) pieces for the given color. Or, when template parameter FindPinned is
420 /// false, the function return the pieces of the given color candidate for a
421 /// discovery check against the enemy king.
422 template<bool FindPinned>
423 Bitboard Position::hidden_checkers() const {
425 // Pinned pieces protect our king, dicovery checks attack the enemy king
426 Bitboard b, result = 0;
427 Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
428 Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
430 // Pinners are sliders, that give check when candidate pinned is removed
431 pinners &= (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
432 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
436 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
438 if (b && !more_than_one(b) && (b & pieces(sideToMove)))
444 // Explicit template instantiations
445 template Bitboard Position::hidden_checkers<true>() const;
446 template Bitboard Position::hidden_checkers<false>() const;
449 /// Position::attackers_to() computes a bitboard of all pieces which attack a
450 /// given square. Slider attacks use occ bitboard as occupancy.
452 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
454 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
455 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
456 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
457 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
458 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
459 | (attacks_from<KING>(s) & pieces(KING));
463 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
464 /// put in a given square. Slider attacks use occ bitboard as occupancy.
466 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
472 case BISHOP: return attacks_bb<BISHOP>(s, occ);
473 case ROOK : return attacks_bb<ROOK>(s, occ);
474 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
475 default : return StepAttacksBB[p][s];
480 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
482 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
485 assert(pinned == pinned_pieces());
487 Color us = sideToMove;
488 Square from = from_sq(m);
490 assert(color_of(piece_moved(m)) == us);
491 assert(piece_on(king_square(us)) == make_piece(us, KING));
493 // En passant captures are a tricky special case. Because they are rather
494 // uncommon, we do it simply by testing whether the king is attacked after
496 if (type_of(m) == ENPASSANT)
499 Square to = to_sq(m);
500 Square capsq = to + pawn_push(them);
501 Square ksq = king_square(us);
502 Bitboard b = (pieces() ^ from ^ capsq) | to;
504 assert(to == ep_square());
505 assert(piece_moved(m) == make_piece(us, PAWN));
506 assert(piece_on(capsq) == make_piece(them, PAWN));
507 assert(piece_on(to) == NO_PIECE);
509 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
510 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
513 // If the moving piece is a king, check whether the destination
514 // square is attacked by the opponent. Castling moves are checked
515 // for legality during move generation.
516 if (type_of(piece_on(from)) == KING)
517 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
519 // A non-king move is legal if and only if it is not pinned or it
520 // is moving along the ray towards or away from the king.
523 || squares_aligned(from, to_sq(m), king_square(us));
527 /// Position::is_pseudo_legal() takes a random move and tests whether the move
528 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
529 /// due to SMP concurrent access or hash position key aliasing.
531 bool Position::is_pseudo_legal(const Move m) const {
533 Color us = sideToMove;
534 Square from = from_sq(m);
535 Square to = to_sq(m);
536 Piece pc = piece_moved(m);
538 // Use a slower but simpler function for uncommon cases
539 if (type_of(m) != NORMAL)
540 return MoveList<LEGAL>(*this).contains(m);
542 // Is not a promotion, so promotion piece must be empty
543 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
546 // If the from square is not occupied by a piece belonging to the side to
547 // move, the move is obviously not legal.
548 if (pc == NO_PIECE || color_of(pc) != us)
551 // The destination square cannot be occupied by a friendly piece
552 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
555 // Handle the special case of a pawn move
556 if (type_of(pc) == PAWN)
558 // Move direction must be compatible with pawn color
559 int direction = to - from;
560 if ((us == WHITE) != (direction > 0))
563 // We have already handled promotion moves, so destination
564 // cannot be on the 8/1th rank.
565 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
568 // Proceed according to the square delta between the origin and
569 // destination squares.
576 // Capture. The destination square must be occupied by an enemy
577 // piece (en passant captures was handled earlier).
578 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
581 // From and to files must be one file apart, avoids a7h5
582 if (abs(file_of(from) - file_of(to)) != 1)
588 // Pawn push. The destination square must be empty.
594 // Double white pawn push. The destination square must be on the fourth
595 // rank, and both the destination square and the square between the
596 // source and destination squares must be empty.
597 if ( rank_of(to) != RANK_4
599 || !is_empty(from + DELTA_N))
604 // Double black pawn push. The destination square must be on the fifth
605 // rank, and both the destination square and the square between the
606 // source and destination squares must be empty.
607 if ( rank_of(to) != RANK_5
609 || !is_empty(from + DELTA_S))
617 else if (!(attacks_from(pc, from) & to))
620 // Evasions generator already takes care to avoid some kind of illegal moves
621 // and pl_move_is_legal() relies on this. So we have to take care that the
622 // same kind of moves are filtered out here.
625 if (type_of(pc) != KING)
627 // Double check? In this case a king move is required
628 if (more_than_one(checkers()))
631 // Our move must be a blocking evasion or a capture of the checking piece
632 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
635 // In case of king moves under check we have to remove king so to catch
636 // as invalid moves like b1a1 when opposite queen is on c1.
637 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
645 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
647 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
650 assert(ci.dcCandidates == discovered_check_candidates());
651 assert(color_of(piece_moved(m)) == sideToMove);
653 Square from = from_sq(m);
654 Square to = to_sq(m);
655 PieceType pt = type_of(piece_on(from));
658 if (ci.checkSq[pt] & to)
662 if (ci.dcCandidates && (ci.dcCandidates & from))
664 // For pawn and king moves we need to verify also direction
665 if ( (pt != PAWN && pt != KING)
666 || !squares_aligned(from, to, king_square(~sideToMove)))
670 // Can we skip the ugly special cases ?
671 if (type_of(m) == NORMAL)
674 Color us = sideToMove;
675 Square ksq = king_square(~us);
680 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
682 // En passant capture with check ? We have already handled the case
683 // of direct checks and ordinary discovered check, the only case we
684 // need to handle is the unusual case of a discovered check through
685 // the captured pawn.
688 Square capsq = file_of(to) | rank_of(from);
689 Bitboard b = (pieces() ^ from ^ capsq) | to;
691 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
692 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
697 Square rfrom = to; // 'King captures the rook' notation
698 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
699 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
700 Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
702 return attacks_bb<ROOK>(rto, b) & ksq;
711 /// Position::do_move() makes a move, and saves all information necessary
712 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
713 /// moves should be filtered out before this function is called.
715 void Position::do_move(Move m, StateInfo& newSt) {
718 do_move(m, newSt, ci, move_gives_check(m, ci));
721 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
724 assert(&newSt != st);
729 // Copy some fields of old state to our new StateInfo object except the ones
730 // which are going to be recalculated from scratch anyway, then switch our state
731 // pointer to point to the new, ready to be updated, state.
732 memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
737 // Update side to move
740 // Increment ply counters.In particular rule50 will be later reset it to zero
741 // in case of a capture or a pawn move.
746 Color us = sideToMove;
748 Square from = from_sq(m);
749 Square to = to_sq(m);
750 Piece piece = piece_on(from);
751 PieceType pt = type_of(piece);
752 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
754 assert(color_of(piece) == us);
755 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
756 assert(capture != KING);
758 if (type_of(m) == CASTLE)
760 assert(piece == make_piece(us, KING));
762 bool kingSide = to > from;
763 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
764 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
765 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
766 capture = NO_PIECE_TYPE;
768 do_castle(from, to, rfrom, rto);
770 st->psqScore += psq_delta(make_piece(us, ROOK), rfrom, rto);
771 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
778 // If the captured piece is a pawn, update pawn hash key, otherwise
779 // update non-pawn material.
782 if (type_of(m) == ENPASSANT)
784 capsq += pawn_push(them);
787 assert(to == st->epSquare);
788 assert(relative_rank(us, to) == RANK_6);
789 assert(piece_on(to) == NO_PIECE);
790 assert(piece_on(capsq) == make_piece(them, PAWN));
792 board[capsq] = NO_PIECE;
795 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
798 st->npMaterial[them] -= PieceValue[MG][capture];
800 // Remove the captured piece
801 byTypeBB[ALL_PIECES] ^= capsq;
802 byTypeBB[capture] ^= capsq;
803 byColorBB[them] ^= capsq;
805 // Update piece list, move the last piece at index[capsq] position and
808 // WARNING: This is a not reversible operation. When we will reinsert the
809 // captured piece in undo_move() we will put it at the end of the list and
810 // not in its original place, it means index[] and pieceList[] are not
811 // guaranteed to be invariant to a do_move() + undo_move() sequence.
812 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
813 index[lastSquare] = index[capsq];
814 pieceList[them][capture][index[lastSquare]] = lastSquare;
815 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
817 // Update material hash key and prefetch access to materialTable
818 k ^= Zobrist::psq[them][capture][capsq];
819 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
820 prefetch((char*)thisThread->materialTable[st->materialKey]);
822 // Update incremental scores
823 st->psqScore -= pieceSquareTable[make_piece(them, capture)][capsq];
825 // Reset rule 50 counter
830 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
832 // Reset en passant square
833 if (st->epSquare != SQ_NONE)
835 k ^= Zobrist::enpassant[file_of(st->epSquare)];
836 st->epSquare = SQ_NONE;
839 // Update castle rights if needed
840 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
842 int cr = castleRightsMask[from] | castleRightsMask[to];
843 k ^= Zobrist::castle[st->castleRights & cr];
844 st->castleRights &= ~cr;
847 // Prefetch TT access as soon as we know the new hash key
848 prefetch((char*)TT.first_entry(k));
850 // Move the piece. The tricky Chess960 castle is handled earlier
851 if (type_of(m) != CASTLE)
853 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
854 byTypeBB[ALL_PIECES] ^= from_to_bb;
855 byTypeBB[pt] ^= from_to_bb;
856 byColorBB[us] ^= from_to_bb;
858 board[from] = NO_PIECE;
861 // Update piece lists, index[from] is not updated and becomes stale. This
862 // works as long as index[] is accessed just by known occupied squares.
863 index[to] = index[from];
864 pieceList[us][pt][index[to]] = to;
867 // If the moving piece is a pawn do some special extra work
870 // Set en-passant square, only if moved pawn can be captured
871 if ( (int(to) ^ int(from)) == 16
872 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
874 st->epSquare = Square((from + to) / 2);
875 k ^= Zobrist::enpassant[file_of(st->epSquare)];
878 if (type_of(m) == PROMOTION)
880 PieceType promotion = promotion_type(m);
882 assert(relative_rank(us, to) == RANK_8);
883 assert(promotion >= KNIGHT && promotion <= QUEEN);
885 // Replace the pawn with the promoted piece
886 byTypeBB[PAWN] ^= to;
887 byTypeBB[promotion] |= to;
888 board[to] = make_piece(us, promotion);
890 // Update piece lists, move the last pawn at index[to] position
891 // and shrink the list. Add a new promotion piece to the list.
892 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
893 index[lastSquare] = index[to];
894 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
895 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
896 index[to] = pieceCount[us][promotion];
897 pieceList[us][promotion][index[to]] = to;
900 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
901 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
902 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
903 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
905 // Update incremental score
906 st->psqScore += pieceSquareTable[make_piece(us, promotion)][to]
907 - pieceSquareTable[make_piece(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->psqScore += psq_delta(piece, from, to);
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. There are three versions of
1133 /// this function: One which takes a destination square as input, one takes a
1134 /// move, and one which takes a 'from' and a 'to' square. The function does
1135 /// not yet understand promotions captures.
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) const {
1151 return do_see<false>(m, 0);
1154 int Position::see_asymm(Move m, int asymmThreshold) const
1156 return do_see<true>(m, asymmThreshold);
1159 template <bool Asymmetric>
1160 int Position::do_see(Move m, int asymmThreshold) const {
1163 Bitboard occupied, attackers, stmAttackers;
1164 int swapList[32], slIndex = 1;
1172 captured = type_of(piece_on(to));
1173 occupied = pieces() ^ from;
1175 // Handle en passant moves
1176 if (type_of(m) == ENPASSANT)
1178 Square capQq = to - pawn_push(sideToMove);
1181 assert(type_of(piece_on(capQq)) == PAWN);
1183 // Remove the captured pawn
1187 else if (type_of(m) == CASTLE)
1188 // Castle moves are implemented as king capturing the rook so cannot be
1189 // handled correctly. Simply return 0 that is always the correct value
1190 // unless the rook is ends up under attack.
1193 // Find all attackers to the destination square, with the moving piece
1194 // removed, but possibly an X-ray attacker added behind it.
1195 attackers = attackers_to(to, occupied);
1197 // If the opponent has no attackers we are finished
1198 stm = ~color_of(piece_on(from));
1199 stmAttackers = attackers & pieces(stm);
1201 return PieceValue[MG][captured];
1203 // The destination square is defended, which makes things rather more
1204 // difficult to compute. We proceed by building up a "swap list" containing
1205 // the material gain or loss at each stop in a sequence of captures to the
1206 // destination square, where the sides alternately capture, and always
1207 // capture with the least valuable piece. After each capture, we look for
1208 // new X-ray attacks from behind the capturing piece.
1209 swapList[0] = PieceValue[MG][captured];
1210 captured = type_of(piece_on(from));
1213 assert(slIndex < 32);
1215 // Add the new entry to the swap list
1216 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1219 // Locate and remove from 'occupied' the next least valuable attacker
1220 captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1222 attackers &= occupied; // Remove the just found attacker
1224 stmAttackers = attackers & pieces(stm);
1226 if (captured == KING)
1228 // Stop before processing a king capture
1230 swapList[slIndex++] = QueenValueMg * 16;
1235 } while (stmAttackers);
1240 for (int i = 0; i < slIndex ; i += 2)
1242 if (swapList[i] < asymmThreshold)
1243 swapList[i] = - QueenValueMg * 16;
1247 // Having built the swap list, we negamax through it to find the best
1248 // achievable score from the point of view of the side to move.
1250 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1256 /// Position::clear() erases the position object to a pristine state, with an
1257 /// empty board, white to move, and no castling rights.
1259 void Position::clear() {
1261 memset(this, 0, sizeof(Position));
1262 startState.epSquare = SQ_NONE;
1265 for (int i = 0; i < 8; i++)
1266 for (int j = 0; j < 16; j++)
1267 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1271 /// Position::put_piece() puts a piece on the given square of the board,
1272 /// updating the board array, pieces list, bitboards, and piece counts.
1274 void Position::put_piece(Piece p, Square s) {
1276 Color c = color_of(p);
1277 PieceType pt = type_of(p);
1280 index[s] = pieceCount[c][pt]++;
1281 pieceList[c][pt][index[s]] = s;
1283 byTypeBB[ALL_PIECES] |= s;
1289 /// Position::compute_key() computes the hash key of the position. The hash
1290 /// key is usually updated incrementally as moves are made and unmade, the
1291 /// compute_key() function is only used when a new position is set up, and
1292 /// to verify the correctness of the hash key when running in debug mode.
1294 Key Position::compute_key() const {
1296 Key k = Zobrist::castle[st->castleRights];
1298 for (Bitboard b = pieces(); b; )
1300 Square s = pop_lsb(&b);
1301 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1304 if (ep_square() != SQ_NONE)
1305 k ^= Zobrist::enpassant[file_of(ep_square())];
1307 if (sideToMove == BLACK)
1314 /// Position::compute_pawn_key() computes the hash key of the position. The
1315 /// hash key is usually updated incrementally as moves are made and unmade,
1316 /// the compute_pawn_key() function is only used when a new position is set
1317 /// up, and to verify the correctness of the pawn hash key when running in
1320 Key Position::compute_pawn_key() const {
1324 for (Bitboard b = pieces(PAWN); b; )
1326 Square s = pop_lsb(&b);
1327 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1334 /// Position::compute_material_key() computes the hash key of the position.
1335 /// The hash key is usually updated incrementally as moves are made and unmade,
1336 /// the compute_material_key() function is only used when a new position is set
1337 /// up, and to verify the correctness of the material hash key when running in
1340 Key Position::compute_material_key() const {
1344 for (Color c = WHITE; c <= BLACK; c++)
1345 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1346 for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1347 k ^= Zobrist::psq[c][pt][cnt];
1353 /// Position::compute_psq_score() computes the incremental scores for the middle
1354 /// game and the endgame. These functions are used to initialize the incremental
1355 /// scores when a new position is set up, and to verify that the scores are correctly
1356 /// updated by do_move and undo_move when the program is running in debug mode.
1357 Score Position::compute_psq_score() const {
1359 Score score = SCORE_ZERO;
1361 for (Bitboard b = pieces(); b; )
1363 Square s = pop_lsb(&b);
1364 score += pieceSquareTable[piece_on(s)][s];
1371 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1372 /// game material value for the given side. Material values are updated
1373 /// incrementally during the search, this function is only used while
1374 /// initializing a new Position object.
1376 Value Position::compute_non_pawn_material(Color c) const {
1378 Value value = VALUE_ZERO;
1380 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1381 value += piece_count(c, pt) * PieceValue[MG][pt];
1387 /// Position::is_draw() tests whether the position is drawn by material,
1388 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1389 /// must be done by the search.
1390 template<bool SkipRepetition>
1391 bool Position::is_draw() const {
1393 // Draw by material?
1395 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1398 // Draw by the 50 moves rule?
1399 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1402 // Draw by repetition?
1403 if (!SkipRepetition)
1405 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1409 StateInfo* stp = st->previous->previous;
1412 stp = stp->previous->previous;
1414 if (stp->key == st->key)
1426 // Explicit template instantiations
1427 template bool Position::is_draw<false>() const;
1428 template bool Position::is_draw<true>() const;
1431 /// Position::flip() flips position with the white and black sides reversed. This
1432 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1434 void Position::flip() {
1436 const Position pos(*this);
1440 sideToMove = ~pos.side_to_move();
1441 thisThread = pos.this_thread();
1442 nodes = pos.nodes_searched();
1443 chess960 = pos.is_chess960();
1444 gamePly = pos.game_ply();
1446 for (Square s = SQ_A1; s <= SQ_H8; s++)
1447 if (!pos.is_empty(s))
1448 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1450 if (pos.can_castle(WHITE_OO))
1451 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1452 if (pos.can_castle(WHITE_OOO))
1453 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1454 if (pos.can_castle(BLACK_OO))
1455 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1456 if (pos.can_castle(BLACK_OOO))
1457 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1459 if (pos.st->epSquare != SQ_NONE)
1460 st->epSquare = ~pos.st->epSquare;
1462 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1464 st->key = compute_key();
1465 st->pawnKey = compute_pawn_key();
1466 st->materialKey = compute_material_key();
1467 st->psqScore = compute_psq_score();
1468 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1469 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1471 assert(pos_is_ok());
1475 /// Position::pos_is_ok() performs some consitency checks for the position object.
1476 /// This is meant to be helpful when debugging.
1478 bool Position::pos_is_ok(int* failedStep) const {
1480 int dummy, *step = failedStep ? failedStep : &dummy;
1482 // What features of the position should be verified?
1483 const bool all = false;
1485 const bool debugBitboards = all || false;
1486 const bool debugKingCount = all || false;
1487 const bool debugKingCapture = all || false;
1488 const bool debugCheckerCount = all || false;
1489 const bool debugKey = all || false;
1490 const bool debugMaterialKey = all || false;
1491 const bool debugPawnKey = all || false;
1492 const bool debugIncrementalEval = all || false;
1493 const bool debugNonPawnMaterial = all || false;
1494 const bool debugPieceCounts = all || false;
1495 const bool debugPieceList = all || false;
1496 const bool debugCastleSquares = all || false;
1500 if (sideToMove != WHITE && sideToMove != BLACK)
1503 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1506 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1509 if ((*step)++, debugKingCount)
1511 int kingCount[COLOR_NB] = {};
1513 for (Square s = SQ_A1; s <= SQ_H8; s++)
1514 if (type_of(piece_on(s)) == KING)
1515 kingCount[color_of(piece_on(s))]++;
1517 if (kingCount[0] != 1 || kingCount[1] != 1)
1521 if ((*step)++, debugKingCapture)
1522 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1525 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1528 if ((*step)++, debugBitboards)
1530 // The intersection of the white and black pieces must be empty
1531 if (pieces(WHITE) & pieces(BLACK))
1534 // The union of the white and black pieces must be equal to all
1536 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1539 // Separate piece type bitboards must have empty intersections
1540 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1541 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1542 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1546 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1549 if ((*step)++, debugKey && st->key != compute_key())
1552 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1555 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1558 if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1561 if ((*step)++, debugNonPawnMaterial)
1563 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1564 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1568 if ((*step)++, debugPieceCounts)
1569 for (Color c = WHITE; c <= BLACK; c++)
1570 for (PieceType pt = PAWN; pt <= KING; pt++)
1571 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1574 if ((*step)++, debugPieceList)
1575 for (Color c = WHITE; c <= BLACK; c++)
1576 for (PieceType pt = PAWN; pt <= KING; pt++)
1577 for (int i = 0; i < pieceCount[c][pt]; i++)
1579 if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1582 if (index[piece_list(c, pt)[i]] != i)
1586 if ((*step)++, debugCastleSquares)
1587 for (Color c = WHITE; c <= BLACK; c++)
1588 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1590 CastleRight cr = make_castle_right(c, s);
1592 if (!can_castle(cr))
1595 if ((castleRightsMask[king_square(c)] & cr) != cr)
1598 if ( piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1599 || castleRightsMask[castleRookSquare[c][s]] != cr)