2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // min_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the bitboards and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 Bitboard b = stmAttackers & bb[Pt];
72 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
74 occupied ^= b & ~(b - 1);
76 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
77 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
79 if (Pt == ROOK || Pt == QUEEN)
80 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
82 attackers &= occupied; // After X-ray that may add already processed pieces
86 template<> FORCE_INLINE
87 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
88 return KING; // No need to update bitboards, it is the last cycle
96 CheckInfo::CheckInfo(const Position& pos) {
98 Color them = ~pos.side_to_move();
99 ksq = pos.king_square(them);
101 pinned = pos.pinned_pieces();
102 dcCandidates = pos.discovered_check_candidates();
104 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
105 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
106 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
107 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
108 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
113 /// Position::init() initializes at startup the various arrays used to compute
114 /// hash keys and the piece square tables. The latter is a two-step operation:
115 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
116 /// the black halves of the tables are initialized by flipping and changing the
117 /// sign of the white scores.
119 void Position::init() {
123 for (Color c = WHITE; c <= BLACK; c++)
124 for (PieceType pt = PAWN; pt <= KING; pt++)
125 for (Square s = SQ_A1; s <= SQ_H8; s++)
126 Zobrist::psq[c][pt][s] = rk.rand<Key>();
128 for (File f = FILE_A; f <= FILE_H; f++)
129 Zobrist::enpassant[f] = rk.rand<Key>();
131 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
136 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
137 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
141 Zobrist::side = rk.rand<Key>();
142 Zobrist::exclusion = rk.rand<Key>();
144 for (PieceType pt = PAWN; pt <= KING; pt++)
146 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
147 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
149 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
151 for (Square s = SQ_A1; s <= SQ_H8; s++)
153 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
154 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
160 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
161 /// object do not depend on any external data so we detach state pointer from
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
177 /// Position::set() initializes the position object with the given FEN string.
178 /// This function is not very robust - make sure that input FENs are correct,
179 /// this is assumed to be the responsibility of the GUI.
181 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
183 A FEN string defines a particular position using only the ASCII character set.
185 A FEN string contains six fields separated by a space. The fields are:
187 1) Piece placement (from white's perspective). Each rank is described, starting
188 with rank 8 and ending with rank 1; within each rank, the contents of each
189 square are described from file A through file H. Following the Standard
190 Algebraic Notation (SAN), each piece is identified by a single letter taken
191 from the standard English names. White pieces are designated using upper-case
192 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
193 noted using digits 1 through 8 (the number of blank squares), and "/"
196 2) Active color. "w" means white moves next, "b" means black.
198 3) Castling availability. If neither side can castle, this is "-". Otherwise,
199 this has one or more letters: "K" (White can castle kingside), "Q" (White
200 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
201 can castle queenside).
203 4) En passant target square (in algebraic notation). If there's no en passant
204 target square, this is "-". If a pawn has just made a 2-square move, this
205 is the position "behind" the pawn. This is recorded regardless of whether
206 there is a pawn in position to make an en passant capture.
208 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
209 or capture. This is used to determine if a draw can be claimed under the
212 6) Fullmove number. The number of the full move. It starts at 1, and is
213 incremented after Black's move.
216 char col, row, token;
219 std::istringstream ss(fenStr);
224 // 1. Piece placement
225 while ((ss >> token) && !isspace(token))
228 sq += Square(token - '0'); // Advance the given number of files
230 else if (token == '/')
233 else if ((p = PieceToChar.find(token)) != string::npos)
235 put_piece(Piece(p), sq);
242 sideToMove = (token == 'w' ? WHITE : BLACK);
245 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
246 // Shredder-FEN that uses the letters of the columns on which the rooks began
247 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
248 // if an inner rook is associated with the castling right, the castling tag is
249 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
250 while ((ss >> token) && !isspace(token))
253 Color c = islower(token) ? BLACK : WHITE;
255 token = char(toupper(token));
258 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
260 else if (token == 'Q')
261 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
263 else if (token >= 'A' && token <= 'H')
264 rsq = File(token - 'A') | relative_rank(c, RANK_1);
269 set_castle_right(c, rsq);
272 // 4. En passant square. Ignore if no pawn capture is possible
273 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
274 && ((ss >> row) && (row == '3' || row == '6')))
276 st->epSquare = File(col - 'a') | Rank(row - '1');
278 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
279 st->epSquare = SQ_NONE;
282 // 5-6. Halfmove clock and fullmove number
283 ss >> std::skipws >> st->rule50 >> gamePly;
285 // Convert from fullmove starting from 1 to ply starting from 0,
286 // handle also common incorrect FEN with fullmove = 0.
287 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
289 st->key = compute_key();
290 st->pawnKey = compute_pawn_key();
291 st->materialKey = compute_material_key();
292 st->psq = compute_psq_score();
293 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
294 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
295 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
296 chess960 = isChess960;
303 /// Position::set_castle_right() is an helper function used to set castling
304 /// rights given the corresponding color and the rook starting square.
306 void Position::set_castle_right(Color c, Square rfrom) {
308 Square kfrom = king_square(c);
309 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
310 CastleRight cr = make_castle_right(c, cs);
312 st->castleRights |= cr;
313 castleRightsMask[kfrom] |= cr;
314 castleRightsMask[rfrom] |= cr;
315 castleRookSquare[c][cs] = rfrom;
317 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
318 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
320 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
321 if (s != kfrom && s != rfrom)
322 castlePath[c][cs] |= s;
324 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
325 if (s != kfrom && s != rfrom)
326 castlePath[c][cs] |= s;
330 /// Position::fen() returns a FEN representation of the position. In case
331 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
333 const string Position::fen() const {
335 std::ostringstream ss;
337 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
339 for (File file = FILE_A; file <= FILE_H; file++)
341 Square sq = file | rank;
347 for ( ; file < FILE_H && is_empty(sq++); file++)
353 ss << PieceToChar[piece_on(sq)];
360 ss << (sideToMove == WHITE ? " w " : " b ");
362 if (can_castle(WHITE_OO))
363 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
365 if (can_castle(WHITE_OOO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
368 if (can_castle(BLACK_OO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
371 if (can_castle(BLACK_OOO))
372 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
374 if (st->castleRights == CASTLES_NONE)
377 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
378 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
384 /// Position::pretty() returns an ASCII representation of the position to be
385 /// printed to the standard output together with the move's san notation.
387 const string Position::pretty(Move move) const {
389 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
390 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
391 + dottedLine + "\n| . | | . | | . | | . | |";
393 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
395 for (Bitboard b = pieces(); b; )
397 Square s = pop_lsb(&b);
398 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
401 std::ostringstream ss;
404 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
405 << move_to_san(*const_cast<Position*>(this), move);
407 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
408 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
410 for (Bitboard b = checkers(); b; )
411 ss << square_to_string(pop_lsb(&b)) << " ";
413 ss << "\nLegal moves: ";
414 for (MoveList<LEGAL> it(*this); *it; ++it)
415 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
421 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
422 /// pieces, according to the call parameters. Pinned pieces protect our king,
423 /// discovery check pieces attack the enemy king.
425 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
427 Bitboard b, pinners, result = 0;
429 // Pinners are sliders that give check when pinned piece is removed
430 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
431 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
435 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
437 if (!more_than_one(b))
438 result |= b & pieces(sideToMove);
444 /// Position::attackers_to() computes a bitboard of all pieces which attack a
445 /// given square. Slider attacks use occ bitboard as occupancy.
447 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
449 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
450 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
451 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
452 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
453 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
454 | (attacks_from<KING>(s) & pieces(KING));
458 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
459 /// put in a given square. Slider attacks use occ bitboard as occupancy.
461 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
467 case BISHOP: return attacks_bb<BISHOP>(s, occ);
468 case ROOK : return attacks_bb<ROOK>(s, occ);
469 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
470 default : return StepAttacksBB[p][s];
475 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
477 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
480 assert(pinned == pinned_pieces());
482 Color us = sideToMove;
483 Square from = from_sq(m);
485 assert(color_of(piece_moved(m)) == us);
486 assert(piece_on(king_square(us)) == make_piece(us, KING));
488 // En passant captures are a tricky special case. Because they are rather
489 // uncommon, we do it simply by testing whether the king is attacked after
491 if (type_of(m) == ENPASSANT)
494 Square to = to_sq(m);
495 Square capsq = to + pawn_push(them);
496 Square ksq = king_square(us);
497 Bitboard b = (pieces() ^ from ^ capsq) | to;
499 assert(to == ep_square());
500 assert(piece_moved(m) == make_piece(us, PAWN));
501 assert(piece_on(capsq) == make_piece(them, PAWN));
502 assert(piece_on(to) == NO_PIECE);
504 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
505 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
508 // If the moving piece is a king, check whether the destination
509 // square is attacked by the opponent. Castling moves are checked
510 // for legality during move generation.
511 if (type_of(piece_on(from)) == KING)
512 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
514 // A non-king move is legal if and only if it is not pinned or it
515 // is moving along the ray towards or away from the king.
518 || squares_aligned(from, to_sq(m), king_square(us));
522 /// Position::is_pseudo_legal() takes a random move and tests whether the move
523 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
524 /// due to SMP concurrent access or hash position key aliasing.
526 bool Position::is_pseudo_legal(const Move m) const {
528 Color us = sideToMove;
529 Square from = from_sq(m);
530 Square to = to_sq(m);
531 Piece pc = piece_moved(m);
533 // Use a slower but simpler function for uncommon cases
534 if (type_of(m) != NORMAL)
535 return MoveList<LEGAL>(*this).contains(m);
537 // Is not a promotion, so promotion piece must be empty
538 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
541 // If the from square is not occupied by a piece belonging to the side to
542 // move, the move is obviously not legal.
543 if (pc == NO_PIECE || color_of(pc) != us)
546 // The destination square cannot be occupied by a friendly piece
550 // Handle the special case of a pawn move
551 if (type_of(pc) == PAWN)
553 // Move direction must be compatible with pawn color
554 int direction = to - from;
555 if ((us == WHITE) != (direction > 0))
558 // We have already handled promotion moves, so destination
559 // cannot be on the 8/1th rank.
560 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
563 // Proceed according to the square delta between the origin and
564 // destination squares.
571 // Capture. The destination square must be occupied by an enemy
572 // piece (en passant captures was handled earlier).
573 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
576 // From and to files must be one file apart, avoids a7h5
577 if (abs(file_of(from) - file_of(to)) != 1)
583 // Pawn push. The destination square must be empty.
589 // Double white pawn push. The destination square must be on the fourth
590 // rank, and both the destination square and the square between the
591 // source and destination squares must be empty.
592 if ( rank_of(to) != RANK_4
594 || !is_empty(from + DELTA_N))
599 // Double black pawn push. The destination square must be on the fifth
600 // rank, and both the destination square and the square between the
601 // source and destination squares must be empty.
602 if ( rank_of(to) != RANK_5
604 || !is_empty(from + DELTA_S))
612 else if (!(attacks_from(pc, from) & to))
615 // Evasions generator already takes care to avoid some kind of illegal moves
616 // and pl_move_is_legal() relies on this. So we have to take care that the
617 // same kind of moves are filtered out here.
620 if (type_of(pc) != KING)
622 // Double check? In this case a king move is required
623 if (more_than_one(checkers()))
626 // Our move must be a blocking evasion or a capture of the checking piece
627 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
630 // In case of king moves under check we have to remove king so to catch
631 // as invalid moves like b1a1 when opposite queen is on c1.
632 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
640 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
642 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
645 assert(ci.dcCandidates == discovered_check_candidates());
646 assert(color_of(piece_moved(m)) == sideToMove);
648 Square from = from_sq(m);
649 Square to = to_sq(m);
650 PieceType pt = type_of(piece_on(from));
653 if (ci.checkSq[pt] & to)
657 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
659 // For pawn and king moves we need to verify also direction
660 if ( (pt != PAWN && pt != KING)
661 || !squares_aligned(from, to, king_square(~sideToMove)))
665 // Can we skip the ugly special cases ?
666 if (type_of(m) == NORMAL)
669 Color us = sideToMove;
670 Square ksq = king_square(~us);
675 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
677 // En passant capture with check ? We have already handled the case
678 // of direct checks and ordinary discovered check, the only case we
679 // need to handle is the unusual case of a discovered check through
680 // the captured pawn.
683 Square capsq = file_of(to) | rank_of(from);
684 Bitboard b = (pieces() ^ from ^ capsq) | to;
686 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
687 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
692 Square rfrom = to; // 'King captures the rook' notation
693 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
694 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
696 return (PseudoAttacks[ROOK][rto] & ksq)
697 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
706 /// Position::do_move() makes a move, and saves all information necessary
707 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
708 /// moves should be filtered out before this function is called.
710 void Position::do_move(Move m, StateInfo& newSt) {
713 do_move(m, newSt, ci, move_gives_check(m, ci));
716 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
719 assert(&newSt != st);
724 // Copy some fields of old state to our new StateInfo object except the ones
725 // which are going to be recalculated from scratch anyway, then switch our state
726 // pointer to point to the new, ready to be updated, state.
727 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
732 // Update side to move
735 // Increment ply counters.In particular rule50 will be later reset it to zero
736 // in case of a capture or a pawn move.
741 Color us = sideToMove;
743 Square from = from_sq(m);
744 Square to = to_sq(m);
745 Piece pc = piece_on(from);
746 PieceType pt = type_of(pc);
747 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
749 assert(color_of(pc) == us);
750 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
751 assert(capture != KING);
753 if (type_of(m) == CASTLE)
755 assert(pc == make_piece(us, KING));
757 bool kingSide = to > from;
758 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
759 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
760 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
761 capture = NO_PIECE_TYPE;
763 do_castle(from, to, rfrom, rto);
765 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
766 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
773 // If the captured piece is a pawn, update pawn hash key, otherwise
774 // update non-pawn material.
777 if (type_of(m) == ENPASSANT)
779 capsq += pawn_push(them);
782 assert(to == st->epSquare);
783 assert(relative_rank(us, to) == RANK_6);
784 assert(piece_on(to) == NO_PIECE);
785 assert(piece_on(capsq) == make_piece(them, PAWN));
787 board[capsq] = NO_PIECE;
790 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
793 st->npMaterial[them] -= PieceValue[MG][capture];
795 // Remove the captured piece
796 byTypeBB[ALL_PIECES] ^= capsq;
797 byTypeBB[capture] ^= capsq;
798 byColorBB[them] ^= capsq;
800 // Update piece list, move the last piece at index[capsq] position and
803 // WARNING: This is a not reversible operation. When we will reinsert the
804 // captured piece in undo_move() we will put it at the end of the list and
805 // not in its original place, it means index[] and pieceList[] are not
806 // guaranteed to be invariant to a do_move() + undo_move() sequence.
807 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
808 index[lastSquare] = index[capsq];
809 pieceList[them][capture][index[lastSquare]] = lastSquare;
810 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
812 // Update material hash key and prefetch access to materialTable
813 k ^= Zobrist::psq[them][capture][capsq];
814 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
815 prefetch((char*)thisThread->materialTable[st->materialKey]);
817 // Update incremental scores
818 st->psq -= psq[them][capture][capsq];
820 // Reset rule 50 counter
825 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
827 // Reset en passant square
828 if (st->epSquare != SQ_NONE)
830 k ^= Zobrist::enpassant[file_of(st->epSquare)];
831 st->epSquare = SQ_NONE;
834 // Update castle rights if needed
835 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
837 int cr = castleRightsMask[from] | castleRightsMask[to];
838 k ^= Zobrist::castle[st->castleRights & cr];
839 st->castleRights &= ~cr;
842 // Prefetch TT access as soon as we know the new hash key
843 prefetch((char*)TT.first_entry(k));
845 // Move the piece. The tricky Chess960 castle is handled earlier
846 if (type_of(m) != CASTLE)
848 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
849 byTypeBB[ALL_PIECES] ^= from_to_bb;
850 byTypeBB[pt] ^= from_to_bb;
851 byColorBB[us] ^= from_to_bb;
853 board[from] = NO_PIECE;
856 // Update piece lists, index[from] is not updated and becomes stale. This
857 // works as long as index[] is accessed just by known occupied squares.
858 index[to] = index[from];
859 pieceList[us][pt][index[to]] = to;
862 // If the moving piece is a pawn do some special extra work
865 // Set en-passant square, only if moved pawn can be captured
866 if ( (int(to) ^ int(from)) == 16
867 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
869 st->epSquare = Square((from + to) / 2);
870 k ^= Zobrist::enpassant[file_of(st->epSquare)];
873 if (type_of(m) == PROMOTION)
875 PieceType promotion = promotion_type(m);
877 assert(relative_rank(us, to) == RANK_8);
878 assert(promotion >= KNIGHT && promotion <= QUEEN);
880 // Replace the pawn with the promoted piece
881 byTypeBB[PAWN] ^= to;
882 byTypeBB[promotion] |= to;
883 board[to] = make_piece(us, promotion);
885 // Update piece lists, move the last pawn at index[to] position
886 // and shrink the list. Add a new promotion piece to the list.
887 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
888 index[lastSquare] = index[to];
889 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
890 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
891 index[to] = pieceCount[us][promotion];
892 pieceList[us][promotion][index[to]] = to;
895 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
896 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
897 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
898 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
900 // Update incremental score
901 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
904 st->npMaterial[us] += PieceValue[MG][promotion];
907 // Update pawn hash key and prefetch access to pawnsTable
908 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
909 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
911 // Reset rule 50 draw counter
915 // Update incremental scores
916 st->psq += psq[us][pt][to] - psq[us][pt][from];
919 st->capturedType = capture;
921 // Update the key with the final value
924 // Update checkers bitboard, piece must be already moved
929 if (type_of(m) != NORMAL)
930 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
934 if (ci.checkSq[pt] & to)
935 st->checkersBB |= to;
938 if (ci.dcCandidates && (ci.dcCandidates & from))
941 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
944 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
949 sideToMove = ~sideToMove;
955 /// Position::undo_move() unmakes a move. When it returns, the position should
956 /// be restored to exactly the same state as before the move was made.
958 void Position::undo_move(Move m) {
962 sideToMove = ~sideToMove;
964 Color us = sideToMove;
966 Square from = from_sq(m);
967 Square to = to_sq(m);
968 PieceType pt = type_of(piece_on(to));
969 PieceType capture = st->capturedType;
971 assert(is_empty(from) || type_of(m) == CASTLE);
972 assert(capture != KING);
974 if (type_of(m) == PROMOTION)
976 PieceType promotion = promotion_type(m);
978 assert(promotion == pt);
979 assert(relative_rank(us, to) == RANK_8);
980 assert(promotion >= KNIGHT && promotion <= QUEEN);
982 // Replace the promoted piece with the pawn
983 byTypeBB[promotion] ^= to;
984 byTypeBB[PAWN] |= to;
985 board[to] = make_piece(us, PAWN);
987 // Update piece lists, move the last promoted piece at index[to] position
988 // and shrink the list. Add a new pawn to the list.
989 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
990 index[lastSquare] = index[to];
991 pieceList[us][promotion][index[lastSquare]] = lastSquare;
992 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
993 index[to] = pieceCount[us][PAWN]++;
994 pieceList[us][PAWN][index[to]] = to;
999 if (type_of(m) == CASTLE)
1001 bool kingSide = to > from;
1002 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1003 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1004 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1005 capture = NO_PIECE_TYPE;
1007 do_castle(to, from, rto, rfrom);
1011 // Put the piece back at the source square
1012 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1013 byTypeBB[ALL_PIECES] ^= from_to_bb;
1014 byTypeBB[pt] ^= from_to_bb;
1015 byColorBB[us] ^= from_to_bb;
1017 board[to] = NO_PIECE;
1018 board[from] = make_piece(us, pt);
1020 // Update piece lists, index[to] is not updated and becomes stale. This
1021 // works as long as index[] is accessed just by known occupied squares.
1022 index[from] = index[to];
1023 pieceList[us][pt][index[from]] = from;
1030 if (type_of(m) == ENPASSANT)
1032 capsq -= pawn_push(us);
1035 assert(to == st->previous->epSquare);
1036 assert(relative_rank(us, to) == RANK_6);
1037 assert(piece_on(capsq) == NO_PIECE);
1040 // Restore the captured piece
1041 byTypeBB[ALL_PIECES] |= capsq;
1042 byTypeBB[capture] |= capsq;
1043 byColorBB[them] |= capsq;
1045 board[capsq] = make_piece(them, capture);
1047 // Update piece list, add a new captured piece in capsq square
1048 index[capsq] = pieceCount[them][capture]++;
1049 pieceList[them][capture][index[capsq]] = capsq;
1052 // Finally point our state pointer back to the previous state
1056 assert(pos_is_ok());
1060 /// Position::do_castle() is a helper used to do/undo a castling move. This
1061 /// is a bit tricky, especially in Chess960.
1063 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1065 Color us = sideToMove;
1066 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1067 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1068 byTypeBB[KING] ^= k_from_to_bb;
1069 byTypeBB[ROOK] ^= r_from_to_bb;
1070 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1071 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1073 // Could be from == to, so first set NO_PIECE then KING and ROOK
1074 board[kfrom] = board[rfrom] = NO_PIECE;
1075 board[kto] = make_piece(us, KING);
1076 board[rto] = make_piece(us, ROOK);
1078 // Could be kfrom == rto, so use a 'tmp' variable
1079 int tmp = index[kfrom];
1080 index[rto] = index[rfrom];
1082 pieceList[us][KING][index[kto]] = kto;
1083 pieceList[us][ROOK][index[rto]] = rto;
1087 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1088 /// the side to move without executing any move on the board.
1090 void Position::do_null_move(StateInfo& newSt) {
1092 assert(!checkers());
1094 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1096 newSt.previous = st;
1099 if (st->epSquare != SQ_NONE)
1101 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1102 st->epSquare = SQ_NONE;
1105 st->key ^= Zobrist::side;
1106 prefetch((char*)TT.first_entry(st->key));
1109 st->pliesFromNull = 0;
1111 sideToMove = ~sideToMove;
1113 assert(pos_is_ok());
1116 void Position::undo_null_move() {
1118 assert(!checkers());
1121 sideToMove = ~sideToMove;
1125 /// Position::see() is a static exchange evaluator: It tries to estimate the
1126 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1127 /// tempi into account. If the side who initiated the capturing sequence does the
1128 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1129 /// the capturing sequence is considered bad.
1131 int Position::see_sign(Move m) const {
1135 // Early return if SEE cannot be negative because captured piece value
1136 // is not less then capturing one. Note that king moves always return
1137 // here because king midgame value is set to 0.
1138 if (PieceValue[MG][piece_moved(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1144 int Position::see(Move m, int asymmThreshold) const {
1147 Bitboard occupied, attackers, stmAttackers;
1148 int swapList[32], slIndex = 1;
1156 swapList[0] = PieceValue[MG][type_of(piece_on(to))];
1157 stm = color_of(piece_on(from));
1158 occupied = pieces() ^ from;
1160 // Castle moves are implemented as king capturing the rook so cannot be
1161 // handled correctly. Simply return 0 that is always the correct value
1162 // unless in the rare case the rook ends up under attack.
1163 if (type_of(m) == CASTLE)
1166 if (type_of(m) == ENPASSANT)
1168 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1169 swapList[0] = PieceValue[MG][PAWN];
1172 // Find all attackers to the destination square, with the moving piece
1173 // removed, but possibly an X-ray attacker added behind it.
1174 attackers = attackers_to(to, occupied) & occupied;
1176 // If the opponent has no attackers we are finished
1178 stmAttackers = attackers & pieces(stm);
1182 // The destination square is defended, which makes things rather more
1183 // difficult to compute. We proceed by building up a "swap list" containing
1184 // the material gain or loss at each stop in a sequence of captures to the
1185 // destination square, where the sides alternately capture, and always
1186 // capture with the least valuable piece. After each capture, we look for
1187 // new X-ray attacks from behind the capturing piece.
1188 captured = type_of(piece_on(from));
1191 assert(slIndex < 32);
1193 // Add the new entry to the swap list
1194 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1197 // Locate and remove the next least valuable attacker
1198 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1200 stmAttackers = attackers & pieces(stm);
1202 // Stop before processing a king capture
1203 if (captured == KING && stmAttackers)
1205 swapList[slIndex++] = QueenValueMg * 16;
1209 } while (stmAttackers);
1211 // If we are doing asymmetric SEE evaluation and the same side does the first
1212 // and the last capture, he loses a tempo and gain must be at least worth
1213 // 'asymmThreshold', otherwise we replace the score with a very low value,
1214 // before negamaxing.
1216 for (int i = 0; i < slIndex; i += 2)
1217 if (swapList[i] < asymmThreshold)
1218 swapList[i] = - QueenValueMg * 16;
1220 // Having built the swap list, we negamax through it to find the best
1221 // achievable score from the point of view of the side to move.
1223 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1229 /// Position::clear() erases the position object to a pristine state, with an
1230 /// empty board, white to move, and no castling rights.
1232 void Position::clear() {
1234 std::memset(this, 0, sizeof(Position));
1235 startState.epSquare = SQ_NONE;
1238 for (int i = 0; i < 8; i++)
1239 for (int j = 0; j < 16; j++)
1240 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1244 /// Position::put_piece() puts a piece on the given square of the board,
1245 /// updating the board array, pieces list, bitboards, and piece counts.
1247 void Position::put_piece(Piece p, Square s) {
1249 Color c = color_of(p);
1250 PieceType pt = type_of(p);
1253 index[s] = pieceCount[c][pt]++;
1254 pieceList[c][pt][index[s]] = s;
1256 byTypeBB[ALL_PIECES] |= s;
1262 /// Position::compute_key() computes the hash key of the position. The hash
1263 /// key is usually updated incrementally as moves are made and unmade, the
1264 /// compute_key() function is only used when a new position is set up, and
1265 /// to verify the correctness of the hash key when running in debug mode.
1267 Key Position::compute_key() const {
1269 Key k = Zobrist::castle[st->castleRights];
1271 for (Bitboard b = pieces(); b; )
1273 Square s = pop_lsb(&b);
1274 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1277 if (ep_square() != SQ_NONE)
1278 k ^= Zobrist::enpassant[file_of(ep_square())];
1280 if (sideToMove == BLACK)
1287 /// Position::compute_pawn_key() computes the hash key of the position. The
1288 /// hash key is usually updated incrementally as moves are made and unmade,
1289 /// the compute_pawn_key() function is only used when a new position is set
1290 /// up, and to verify the correctness of the pawn hash key when running in
1293 Key Position::compute_pawn_key() const {
1297 for (Bitboard b = pieces(PAWN); b; )
1299 Square s = pop_lsb(&b);
1300 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1307 /// Position::compute_material_key() computes the hash key of the position.
1308 /// The hash key is usually updated incrementally as moves are made and unmade,
1309 /// the compute_material_key() function is only used when a new position is set
1310 /// up, and to verify the correctness of the material hash key when running in
1313 Key Position::compute_material_key() const {
1317 for (Color c = WHITE; c <= BLACK; c++)
1318 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1319 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1320 k ^= Zobrist::psq[c][pt][cnt];
1326 /// Position::compute_psq_score() computes the incremental scores for the middle
1327 /// game and the endgame. These functions are used to initialize the incremental
1328 /// scores when a new position is set up, and to verify that the scores are correctly
1329 /// updated by do_move and undo_move when the program is running in debug mode.
1330 Score Position::compute_psq_score() const {
1332 Score score = SCORE_ZERO;
1334 for (Bitboard b = pieces(); b; )
1336 Square s = pop_lsb(&b);
1337 Piece pc = piece_on(s);
1338 score += psq[color_of(pc)][type_of(pc)][s];
1345 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1346 /// game material value for the given side. Material values are updated
1347 /// incrementally during the search, this function is only used while
1348 /// initializing a new Position object.
1350 Value Position::compute_non_pawn_material(Color c) const {
1352 Value value = VALUE_ZERO;
1354 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1355 value += pieceCount[c][pt] * PieceValue[MG][pt];
1361 /// Position::is_draw() tests whether the position is drawn by material,
1362 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1363 /// must be done by the search.
1364 bool Position::is_draw() const {
1366 // Draw by material?
1368 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1371 // Draw by the 50 moves rule?
1372 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1375 // Draw by repetition?
1376 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1380 StateInfo* stp = st->previous->previous;
1383 stp = stp->previous->previous;
1385 if (stp->key == st->key)
1397 /// Position::flip() flips position with the white and black sides reversed. This
1398 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1400 void Position::flip() {
1402 const Position pos(*this);
1406 sideToMove = ~pos.side_to_move();
1407 thisThread = pos.this_thread();
1408 nodes = pos.nodes_searched();
1409 chess960 = pos.is_chess960();
1410 gamePly = pos.game_ply();
1412 for (Square s = SQ_A1; s <= SQ_H8; s++)
1413 if (!pos.is_empty(s))
1414 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1416 if (pos.can_castle(WHITE_OO))
1417 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1418 if (pos.can_castle(WHITE_OOO))
1419 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1420 if (pos.can_castle(BLACK_OO))
1421 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1422 if (pos.can_castle(BLACK_OOO))
1423 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1425 if (pos.st->epSquare != SQ_NONE)
1426 st->epSquare = ~pos.st->epSquare;
1428 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1430 st->key = compute_key();
1431 st->pawnKey = compute_pawn_key();
1432 st->materialKey = compute_material_key();
1433 st->psq = compute_psq_score();
1434 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1435 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1437 assert(pos_is_ok());
1441 /// Position::pos_is_ok() performs some consitency checks for the position object.
1442 /// This is meant to be helpful when debugging.
1444 bool Position::pos_is_ok(int* failedStep) const {
1446 int dummy, *step = failedStep ? failedStep : &dummy;
1448 // What features of the position should be verified?
1449 const bool all = false;
1451 const bool debugBitboards = all || false;
1452 const bool debugKingCount = all || false;
1453 const bool debugKingCapture = all || false;
1454 const bool debugCheckerCount = all || false;
1455 const bool debugKey = all || false;
1456 const bool debugMaterialKey = all || false;
1457 const bool debugPawnKey = all || false;
1458 const bool debugIncrementalEval = all || false;
1459 const bool debugNonPawnMaterial = all || false;
1460 const bool debugPieceCounts = all || false;
1461 const bool debugPieceList = all || false;
1462 const bool debugCastleSquares = all || false;
1466 if (sideToMove != WHITE && sideToMove != BLACK)
1469 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1472 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1475 if ((*step)++, debugKingCount)
1477 int kingCount[COLOR_NB] = {};
1479 for (Square s = SQ_A1; s <= SQ_H8; s++)
1480 if (type_of(piece_on(s)) == KING)
1481 kingCount[color_of(piece_on(s))]++;
1483 if (kingCount[0] != 1 || kingCount[1] != 1)
1487 if ((*step)++, debugKingCapture)
1488 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1491 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1494 if ((*step)++, debugBitboards)
1496 // The intersection of the white and black pieces must be empty
1497 if (pieces(WHITE) & pieces(BLACK))
1500 // The union of the white and black pieces must be equal to all
1502 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1505 // Separate piece type bitboards must have empty intersections
1506 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1507 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1508 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1512 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1515 if ((*step)++, debugKey && st->key != compute_key())
1518 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1521 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1524 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1527 if ((*step)++, debugNonPawnMaterial)
1528 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1529 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1532 if ((*step)++, debugPieceCounts)
1533 for (Color c = WHITE; c <= BLACK; c++)
1534 for (PieceType pt = PAWN; pt <= KING; pt++)
1535 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1538 if ((*step)++, debugPieceList)
1539 for (Color c = WHITE; c <= BLACK; c++)
1540 for (PieceType pt = PAWN; pt <= KING; pt++)
1541 for (int i = 0; i < pieceCount[c][pt]; i++)
1542 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1543 || index[pieceList[c][pt][i]] != i)
1546 if ((*step)++, debugCastleSquares)
1547 for (Color c = WHITE; c <= BLACK; c++)
1548 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1550 CastleRight cr = make_castle_right(c, s);
1552 if (!can_castle(cr))
1555 if ( (castleRightsMask[king_square(c)] & cr) != cr
1556 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1557 || castleRightsMask[castleRookSquare[c][s]] != cr)