2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // min_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the bitboards and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 Bitboard b = stmAttackers & bb[Pt];
74 occupied ^= b & ~(b - 1);
76 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
77 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
79 if (Pt == ROOK || Pt == QUEEN)
80 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
82 attackers &= occupied; // Remove the just found attacker
86 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
89 template<> FORCE_INLINE
90 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
91 return KING; // No need to update bitboards, it is the last cycle
99 CheckInfo::CheckInfo(const Position& pos) {
101 Color them = ~pos.side_to_move();
102 ksq = pos.king_square(them);
104 pinned = pos.pinned_pieces();
105 dcCandidates = pos.discovered_check_candidates();
107 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
108 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
109 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
110 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
111 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
116 /// Position::init() initializes at startup the various arrays used to compute
117 /// hash keys and the piece square tables. The latter is a two-step operation:
118 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
119 /// the black halves of the tables are initialized by flipping and changing the
120 /// sign of the white scores.
122 void Position::init() {
126 for (Color c = WHITE; c <= BLACK; c++)
127 for (PieceType pt = PAWN; pt <= KING; pt++)
128 for (Square s = SQ_A1; s <= SQ_H8; s++)
129 Zobrist::psq[c][pt][s] = rk.rand<Key>();
131 for (File f = FILE_A; f <= FILE_H; f++)
132 Zobrist::enpassant[f] = rk.rand<Key>();
134 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
139 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
140 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
144 Zobrist::side = rk.rand<Key>();
145 Zobrist::exclusion = rk.rand<Key>();
147 for (PieceType pt = PAWN; pt <= KING; pt++)
149 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
150 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
152 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
154 for (Square s = SQ_A1; s <= SQ_H8; s++)
156 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
157 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
163 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
164 /// object do not depend on any external data so we detach state pointer from
167 Position& Position::operator=(const Position& pos) {
169 std::memcpy(this, &pos, sizeof(Position));
180 /// Position::set() initializes the position object with the given FEN string.
181 /// This function is not very robust - make sure that input FENs are correct,
182 /// this is assumed to be the responsibility of the GUI.
184 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
186 A FEN string defines a particular position using only the ASCII character set.
188 A FEN string contains six fields separated by a space. The fields are:
190 1) Piece placement (from white's perspective). Each rank is described, starting
191 with rank 8 and ending with rank 1; within each rank, the contents of each
192 square are described from file A through file H. Following the Standard
193 Algebraic Notation (SAN), each piece is identified by a single letter taken
194 from the standard English names. White pieces are designated using upper-case
195 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
196 noted using digits 1 through 8 (the number of blank squares), and "/"
199 2) Active color. "w" means white moves next, "b" means black.
201 3) Castling availability. If neither side can castle, this is "-". Otherwise,
202 this has one or more letters: "K" (White can castle kingside), "Q" (White
203 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
204 can castle queenside).
206 4) En passant target square (in algebraic notation). If there's no en passant
207 target square, this is "-". If a pawn has just made a 2-square move, this
208 is the position "behind" the pawn. This is recorded regardless of whether
209 there is a pawn in position to make an en passant capture.
211 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
212 or capture. This is used to determine if a draw can be claimed under the
215 6) Fullmove number. The number of the full move. It starts at 1, and is
216 incremented after Black's move.
219 char col, row, token;
222 std::istringstream ss(fenStr);
227 // 1. Piece placement
228 while ((ss >> token) && !isspace(token))
231 sq += Square(token - '0'); // Advance the given number of files
233 else if (token == '/')
236 else if ((p = PieceToChar.find(token)) != string::npos)
238 put_piece(Piece(p), sq);
245 sideToMove = (token == 'w' ? WHITE : BLACK);
248 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
249 // Shredder-FEN that uses the letters of the columns on which the rooks began
250 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
251 // if an inner rook is associated with the castling right, the castling tag is
252 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
253 while ((ss >> token) && !isspace(token))
256 Color c = islower(token) ? BLACK : WHITE;
258 token = char(toupper(token));
261 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
263 else if (token == 'Q')
264 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
266 else if (token >= 'A' && token <= 'H')
267 rsq = File(token - 'A') | relative_rank(c, RANK_1);
272 set_castle_right(c, rsq);
275 // 4. En passant square. Ignore if no pawn capture is possible
276 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
277 && ((ss >> row) && (row == '3' || row == '6')))
279 st->epSquare = File(col - 'a') | Rank(row - '1');
281 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
282 st->epSquare = SQ_NONE;
285 // 5-6. Halfmove clock and fullmove number
286 ss >> std::skipws >> st->rule50 >> gamePly;
288 // Convert from fullmove starting from 1 to ply starting from 0,
289 // handle also common incorrect FEN with fullmove = 0.
290 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
292 st->key = compute_key();
293 st->pawnKey = compute_pawn_key();
294 st->materialKey = compute_material_key();
295 st->psq = compute_psq_score();
296 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
297 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
298 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
299 chess960 = isChess960;
306 /// Position::set_castle_right() is an helper function used to set castling
307 /// rights given the corresponding color and the rook starting square.
309 void Position::set_castle_right(Color c, Square rfrom) {
311 Square kfrom = king_square(c);
312 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
313 CastleRight cr = make_castle_right(c, cs);
315 st->castleRights |= cr;
316 castleRightsMask[kfrom] |= cr;
317 castleRightsMask[rfrom] |= cr;
318 castleRookSquare[c][cs] = rfrom;
320 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
321 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
323 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
324 if (s != kfrom && s != rfrom)
325 castlePath[c][cs] |= s;
327 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
328 if (s != kfrom && s != rfrom)
329 castlePath[c][cs] |= s;
333 /// Position::fen() returns a FEN representation of the position. In case
334 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
336 const string Position::fen() const {
338 std::ostringstream ss;
340 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
342 for (File file = FILE_A; file <= FILE_H; file++)
344 Square sq = file | rank;
350 for ( ; file < FILE_H && is_empty(sq++); file++)
356 ss << PieceToChar[piece_on(sq)];
363 ss << (sideToMove == WHITE ? " w " : " b ");
365 if (can_castle(WHITE_OO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
368 if (can_castle(WHITE_OOO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
371 if (can_castle(BLACK_OO))
372 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
374 if (can_castle(BLACK_OOO))
375 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
377 if (st->castleRights == CASTLES_NONE)
380 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
381 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
387 /// Position::pretty() returns an ASCII representation of the position to be
388 /// printed to the standard output together with the move's san notation.
390 const string Position::pretty(Move move) const {
392 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
393 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
394 + dottedLine + "\n| . | | . | | . | | . | |";
396 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
398 std::ostringstream ss;
401 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
402 << move_to_san(*const_cast<Position*>(this), move);
404 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
405 if (piece_on(sq) != NO_PIECE)
406 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
408 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
409 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
411 for (Bitboard b = checkers(); b; )
412 ss << square_to_string(pop_lsb(&b)) << " ";
414 ss << "\nLegal moves: ";
415 for (MoveList<LEGAL> it(*this); *it; ++it)
416 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
422 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
423 /// pieces, according to the call parameters. Pinned pieces protect our king,
424 /// discovery check pieces attack the enemy king.
426 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
428 Bitboard b, pinners, result = 0;
430 // Pinners are sliders that give check when pinned piece is removed
431 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
432 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
436 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
438 if (!more_than_one(b))
439 result |= b & pieces(sideToMove);
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);
697 return (PseudoAttacks[ROOK][rto] & ksq)
698 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & 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 std::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 std::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_moved(m)] <= PieceValue[MG][piece_on(to_sq(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 if (captured == KING) // Stop before processing a king capture
1202 swapList[slIndex++] = QueenValueMg * 16;
1206 // Add the new entry to the swap list
1207 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1210 // Locate and remove the next least valuable attacker
1211 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1213 stmAttackers = attackers & pieces(stm);
1215 } while (stmAttackers);
1217 // If we are doing asymmetric SEE evaluation and the same side does the first
1218 // and the last capture, he loses a tempo and gain must be at least worth
1219 // 'asymmThreshold', otherwise we replace the score with a very low value,
1220 // before negamaxing.
1222 for (int i = 0; i < slIndex; i += 2)
1223 if (swapList[i] < asymmThreshold)
1224 swapList[i] = - QueenValueMg * 16;
1226 // Having built the swap list, we negamax through it to find the best
1227 // achievable score from the point of view of the side to move.
1229 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1235 /// Position::clear() erases the position object to a pristine state, with an
1236 /// empty board, white to move, and no castling rights.
1238 void Position::clear() {
1240 std::memset(this, 0, sizeof(Position));
1241 startState.epSquare = SQ_NONE;
1244 for (int i = 0; i < 8; i++)
1245 for (int j = 0; j < 16; j++)
1246 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1250 /// Position::put_piece() puts a piece on the given square of the board,
1251 /// updating the board array, pieces list, bitboards, and piece counts.
1253 void Position::put_piece(Piece p, Square s) {
1255 Color c = color_of(p);
1256 PieceType pt = type_of(p);
1259 index[s] = pieceCount[c][pt]++;
1260 pieceList[c][pt][index[s]] = s;
1262 byTypeBB[ALL_PIECES] |= s;
1268 /// Position::compute_key() computes the hash key of the position. The hash
1269 /// key is usually updated incrementally as moves are made and unmade, the
1270 /// compute_key() function is only used when a new position is set up, and
1271 /// to verify the correctness of the hash key when running in debug mode.
1273 Key Position::compute_key() const {
1275 Key k = Zobrist::castle[st->castleRights];
1277 for (Bitboard b = pieces(); b; )
1279 Square s = pop_lsb(&b);
1280 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1283 if (ep_square() != SQ_NONE)
1284 k ^= Zobrist::enpassant[file_of(ep_square())];
1286 if (sideToMove == BLACK)
1293 /// Position::compute_pawn_key() computes the hash key of the position. The
1294 /// hash key is usually updated incrementally as moves are made and unmade,
1295 /// the compute_pawn_key() function is only used when a new position is set
1296 /// up, and to verify the correctness of the pawn hash key when running in
1299 Key Position::compute_pawn_key() const {
1303 for (Bitboard b = pieces(PAWN); b; )
1305 Square s = pop_lsb(&b);
1306 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1313 /// Position::compute_material_key() computes the hash key of the position.
1314 /// The hash key is usually updated incrementally as moves are made and unmade,
1315 /// the compute_material_key() function is only used when a new position is set
1316 /// up, and to verify the correctness of the material hash key when running in
1319 Key Position::compute_material_key() const {
1323 for (Color c = WHITE; c <= BLACK; c++)
1324 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1325 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1326 k ^= Zobrist::psq[c][pt][cnt];
1332 /// Position::compute_psq_score() computes the incremental scores for the middle
1333 /// game and the endgame. These functions are used to initialize the incremental
1334 /// scores when a new position is set up, and to verify that the scores are correctly
1335 /// updated by do_move and undo_move when the program is running in debug mode.
1336 Score Position::compute_psq_score() const {
1338 Score score = SCORE_ZERO;
1340 for (Bitboard b = pieces(); b; )
1342 Square s = pop_lsb(&b);
1343 Piece pc = piece_on(s);
1344 score += psq[color_of(pc)][type_of(pc)][s];
1351 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1352 /// game material value for the given side. Material values are updated
1353 /// incrementally during the search, this function is only used while
1354 /// initializing a new Position object.
1356 Value Position::compute_non_pawn_material(Color c) const {
1358 Value value = VALUE_ZERO;
1360 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1361 value += pieceCount[c][pt] * PieceValue[MG][pt];
1367 /// Position::is_draw() tests whether the position is drawn by material,
1368 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1369 /// must be done by the search.
1370 bool Position::is_draw() const {
1372 // Draw by material?
1374 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1377 // Draw by the 50 moves rule?
1378 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1381 // Draw by repetition?
1382 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1386 StateInfo* stp = st->previous->previous;
1389 stp = stp->previous->previous;
1391 if (stp->key == st->key)
1403 /// Position::flip() flips position with the white and black sides reversed. This
1404 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1406 void Position::flip() {
1408 const Position pos(*this);
1412 sideToMove = ~pos.side_to_move();
1413 thisThread = pos.this_thread();
1414 nodes = pos.nodes_searched();
1415 chess960 = pos.is_chess960();
1416 gamePly = pos.game_ply();
1418 for (Square s = SQ_A1; s <= SQ_H8; s++)
1419 if (!pos.is_empty(s))
1420 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1422 if (pos.can_castle(WHITE_OO))
1423 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1424 if (pos.can_castle(WHITE_OOO))
1425 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1426 if (pos.can_castle(BLACK_OO))
1427 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1428 if (pos.can_castle(BLACK_OOO))
1429 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1431 if (pos.st->epSquare != SQ_NONE)
1432 st->epSquare = ~pos.st->epSquare;
1434 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1436 st->key = compute_key();
1437 st->pawnKey = compute_pawn_key();
1438 st->materialKey = compute_material_key();
1439 st->psq = compute_psq_score();
1440 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1441 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1443 assert(pos_is_ok());
1447 /// Position::pos_is_ok() performs some consitency checks for the position object.
1448 /// This is meant to be helpful when debugging.
1450 bool Position::pos_is_ok(int* failedStep) const {
1452 int dummy, *step = failedStep ? failedStep : &dummy;
1454 // What features of the position should be verified?
1455 const bool all = false;
1457 const bool debugBitboards = all || false;
1458 const bool debugKingCount = all || false;
1459 const bool debugKingCapture = all || false;
1460 const bool debugCheckerCount = all || false;
1461 const bool debugKey = all || false;
1462 const bool debugMaterialKey = all || false;
1463 const bool debugPawnKey = all || false;
1464 const bool debugIncrementalEval = all || false;
1465 const bool debugNonPawnMaterial = all || false;
1466 const bool debugPieceCounts = all || false;
1467 const bool debugPieceList = all || false;
1468 const bool debugCastleSquares = all || false;
1472 if (sideToMove != WHITE && sideToMove != BLACK)
1475 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1478 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1481 if ((*step)++, debugKingCount)
1483 int kingCount[COLOR_NB] = {};
1485 for (Square s = SQ_A1; s <= SQ_H8; s++)
1486 if (type_of(piece_on(s)) == KING)
1487 kingCount[color_of(piece_on(s))]++;
1489 if (kingCount[0] != 1 || kingCount[1] != 1)
1493 if ((*step)++, debugKingCapture)
1494 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1497 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1500 if ((*step)++, debugBitboards)
1502 // The intersection of the white and black pieces must be empty
1503 if (pieces(WHITE) & pieces(BLACK))
1506 // The union of the white and black pieces must be equal to all
1508 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1511 // Separate piece type bitboards must have empty intersections
1512 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1513 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1514 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1518 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1521 if ((*step)++, debugKey && st->key != compute_key())
1524 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1527 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1530 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1533 if ((*step)++, debugNonPawnMaterial)
1534 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1535 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1538 if ((*step)++, debugPieceCounts)
1539 for (Color c = WHITE; c <= BLACK; c++)
1540 for (PieceType pt = PAWN; pt <= KING; pt++)
1541 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1544 if ((*step)++, debugPieceList)
1545 for (Color c = WHITE; c <= BLACK; c++)
1546 for (PieceType pt = PAWN; pt <= KING; pt++)
1547 for (int i = 0; i < pieceCount[c][pt]; i++)
1548 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1549 || index[pieceList[c][pt][i]] != i)
1552 if ((*step)++, debugCastleSquares)
1553 for (Color c = WHITE; c <= BLACK; c++)
1554 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1556 CastleRight cr = make_castle_right(c, s);
1558 if (!can_castle(cr))
1561 if ( (castleRightsMask[king_square(c)] & cr) != cr
1562 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1563 || castleRightsMask[castleRookSquare[c][s]] != cr)