2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // next_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the 'occupied' bitboard and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 if (stmAttackers & bb[Pt])
72 Bitboard b = stmAttackers & bb[Pt];
73 occupied ^= b & ~(b - 1);
75 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
76 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
78 if (Pt == ROOK || Pt == QUEEN)
79 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
83 return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
86 template<> FORCE_INLINE
87 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
88 return KING; // No need to update bitboards, it is the last cycle
96 CheckInfo::CheckInfo(const Position& pos) {
98 Color them = ~pos.side_to_move();
99 ksq = pos.king_square(them);
101 pinned = pos.pinned_pieces();
102 dcCandidates = pos.discovered_check_candidates();
104 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
105 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
106 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
107 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
108 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
113 /// Position::init() initializes at startup the various arrays used to compute
114 /// hash keys and the piece square tables. The latter is a two-step operation:
115 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
116 /// the black halves of the tables are initialized by flipping and changing the
117 /// sign of the white scores.
119 void Position::init() {
123 for (Color c = WHITE; c <= BLACK; c++)
124 for (PieceType pt = PAWN; pt <= KING; pt++)
125 for (Square s = SQ_A1; s <= SQ_H8; s++)
126 Zobrist::psq[c][pt][s] = rk.rand<Key>();
128 for (File f = FILE_A; f <= FILE_H; f++)
129 Zobrist::enpassant[f] = rk.rand<Key>();
131 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
136 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
137 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
141 Zobrist::side = rk.rand<Key>();
142 Zobrist::exclusion = rk.rand<Key>();
144 for (PieceType pt = PAWN; pt <= KING; pt++)
146 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
147 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
149 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
151 for (Square s = SQ_A1; s <= SQ_H8; s++)
153 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
154 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
160 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
161 /// object do not depend on any external data so we detach state pointer from
164 Position& Position::operator=(const Position& pos) {
166 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 std::ostringstream ss;
398 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
399 << move_to_san(*const_cast<Position*>(this), move);
401 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
402 if (piece_on(sq) != NO_PIECE)
403 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
405 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
406 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
408 for (Bitboard b = checkers(); b; )
409 ss << square_to_string(pop_lsb(&b)) << " ";
411 ss << "\nLegal moves: ";
412 for (MoveList<LEGAL> it(*this); *it; ++it)
413 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
419 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
420 /// pieces, according to the call parameters. Pinned pieces protect our king,
421 /// discovery check pieces attack the enemy king.
423 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
425 Bitboard b, pinners, result = 0;
427 // Pinners are sliders that give check when pinned piece is removed
428 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
429 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
433 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
435 if (!more_than_one(b))
436 result |= b & pieces(sideToMove);
442 /// Position::attackers_to() computes a bitboard of all pieces which attack a
443 /// given square. Slider attacks use occ bitboard as occupancy.
445 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
447 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
448 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
449 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
450 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
451 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
452 | (attacks_from<KING>(s) & pieces(KING));
456 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
457 /// put in a given square. Slider attacks use occ bitboard as occupancy.
459 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
465 case BISHOP: return attacks_bb<BISHOP>(s, occ);
466 case ROOK : return attacks_bb<ROOK>(s, occ);
467 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
468 default : return StepAttacksBB[p][s];
473 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
475 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
478 assert(pinned == pinned_pieces());
480 Color us = sideToMove;
481 Square from = from_sq(m);
483 assert(color_of(piece_moved(m)) == us);
484 assert(piece_on(king_square(us)) == make_piece(us, KING));
486 // En passant captures are a tricky special case. Because they are rather
487 // uncommon, we do it simply by testing whether the king is attacked after
489 if (type_of(m) == ENPASSANT)
492 Square to = to_sq(m);
493 Square capsq = to + pawn_push(them);
494 Square ksq = king_square(us);
495 Bitboard b = (pieces() ^ from ^ capsq) | to;
497 assert(to == ep_square());
498 assert(piece_moved(m) == make_piece(us, PAWN));
499 assert(piece_on(capsq) == make_piece(them, PAWN));
500 assert(piece_on(to) == NO_PIECE);
502 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
503 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
506 // If the moving piece is a king, check whether the destination
507 // square is attacked by the opponent. Castling moves are checked
508 // for legality during move generation.
509 if (type_of(piece_on(from)) == KING)
510 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
512 // A non-king move is legal if and only if it is not pinned or it
513 // is moving along the ray towards or away from the king.
516 || squares_aligned(from, to_sq(m), king_square(us));
520 /// Position::is_pseudo_legal() takes a random move and tests whether the move
521 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
522 /// due to SMP concurrent access or hash position key aliasing.
524 bool Position::is_pseudo_legal(const Move m) const {
526 Color us = sideToMove;
527 Square from = from_sq(m);
528 Square to = to_sq(m);
529 Piece pc = piece_moved(m);
531 // Use a slower but simpler function for uncommon cases
532 if (type_of(m) != NORMAL)
533 return MoveList<LEGAL>(*this).contains(m);
535 // Is not a promotion, so promotion piece must be empty
536 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
539 // If the from square is not occupied by a piece belonging to the side to
540 // move, the move is obviously not legal.
541 if (pc == NO_PIECE || color_of(pc) != us)
544 // The destination square cannot be occupied by a friendly piece
545 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
548 // Handle the special case of a pawn move
549 if (type_of(pc) == PAWN)
551 // Move direction must be compatible with pawn color
552 int direction = to - from;
553 if ((us == WHITE) != (direction > 0))
556 // We have already handled promotion moves, so destination
557 // cannot be on the 8/1th rank.
558 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
561 // Proceed according to the square delta between the origin and
562 // destination squares.
569 // Capture. The destination square must be occupied by an enemy
570 // piece (en passant captures was handled earlier).
571 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
574 // From and to files must be one file apart, avoids a7h5
575 if (abs(file_of(from) - file_of(to)) != 1)
581 // Pawn push. The destination square must be empty.
587 // Double white pawn push. The destination square must be on the fourth
588 // rank, and both the destination square and the square between the
589 // source and destination squares must be empty.
590 if ( rank_of(to) != RANK_4
592 || !is_empty(from + DELTA_N))
597 // Double black pawn push. The destination square must be on the fifth
598 // rank, and both the destination square and the square between the
599 // source and destination squares must be empty.
600 if ( rank_of(to) != RANK_5
602 || !is_empty(from + DELTA_S))
610 else if (!(attacks_from(pc, from) & to))
613 // Evasions generator already takes care to avoid some kind of illegal moves
614 // and pl_move_is_legal() relies on this. So we have to take care that the
615 // same kind of moves are filtered out here.
618 if (type_of(pc) != KING)
620 // Double check? In this case a king move is required
621 if (more_than_one(checkers()))
624 // Our move must be a blocking evasion or a capture of the checking piece
625 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
628 // In case of king moves under check we have to remove king so to catch
629 // as invalid moves like b1a1 when opposite queen is on c1.
630 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
638 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
640 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
643 assert(ci.dcCandidates == discovered_check_candidates());
644 assert(color_of(piece_moved(m)) == sideToMove);
646 Square from = from_sq(m);
647 Square to = to_sq(m);
648 PieceType pt = type_of(piece_on(from));
651 if (ci.checkSq[pt] & to)
655 if (ci.dcCandidates && (ci.dcCandidates & from))
657 // For pawn and king moves we need to verify also direction
658 if ( (pt != PAWN && pt != KING)
659 || !squares_aligned(from, to, king_square(~sideToMove)))
663 // Can we skip the ugly special cases ?
664 if (type_of(m) == NORMAL)
667 Color us = sideToMove;
668 Square ksq = king_square(~us);
673 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
675 // En passant capture with check ? We have already handled the case
676 // of direct checks and ordinary discovered check, the only case we
677 // need to handle is the unusual case of a discovered check through
678 // the captured pawn.
681 Square capsq = file_of(to) | rank_of(from);
682 Bitboard b = (pieces() ^ from ^ capsq) | to;
684 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
685 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
690 Square rfrom = to; // 'King captures the rook' notation
691 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
692 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
693 Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
695 return attacks_bb<ROOK>(rto, b) & ksq;
704 /// Position::do_move() makes a move, and saves all information necessary
705 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
706 /// moves should be filtered out before this function is called.
708 void Position::do_move(Move m, StateInfo& newSt) {
711 do_move(m, newSt, ci, move_gives_check(m, ci));
714 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
717 assert(&newSt != st);
722 // Copy some fields of old state to our new StateInfo object except the ones
723 // which are going to be recalculated from scratch anyway, then switch our state
724 // pointer to point to the new, ready to be updated, state.
725 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
730 // Update side to move
733 // Increment ply counters.In particular rule50 will be later reset it to zero
734 // in case of a capture or a pawn move.
739 Color us = sideToMove;
741 Square from = from_sq(m);
742 Square to = to_sq(m);
743 Piece pc = piece_on(from);
744 PieceType pt = type_of(pc);
745 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
747 assert(color_of(pc) == us);
748 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
749 assert(capture != KING);
751 if (type_of(m) == CASTLE)
753 assert(pc == make_piece(us, KING));
755 bool kingSide = to > from;
756 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
757 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
758 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
759 capture = NO_PIECE_TYPE;
761 do_castle(from, to, rfrom, rto);
763 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
764 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
771 // If the captured piece is a pawn, update pawn hash key, otherwise
772 // update non-pawn material.
775 if (type_of(m) == ENPASSANT)
777 capsq += pawn_push(them);
780 assert(to == st->epSquare);
781 assert(relative_rank(us, to) == RANK_6);
782 assert(piece_on(to) == NO_PIECE);
783 assert(piece_on(capsq) == make_piece(them, PAWN));
785 board[capsq] = NO_PIECE;
788 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
791 st->npMaterial[them] -= PieceValue[MG][capture];
793 // Remove the captured piece
794 byTypeBB[ALL_PIECES] ^= capsq;
795 byTypeBB[capture] ^= capsq;
796 byColorBB[them] ^= capsq;
798 // Update piece list, move the last piece at index[capsq] position and
801 // WARNING: This is a not reversible operation. When we will reinsert the
802 // captured piece in undo_move() we will put it at the end of the list and
803 // not in its original place, it means index[] and pieceList[] are not
804 // guaranteed to be invariant to a do_move() + undo_move() sequence.
805 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
806 index[lastSquare] = index[capsq];
807 pieceList[them][capture][index[lastSquare]] = lastSquare;
808 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
810 // Update material hash key and prefetch access to materialTable
811 k ^= Zobrist::psq[them][capture][capsq];
812 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
813 prefetch((char*)thisThread->materialTable[st->materialKey]);
815 // Update incremental scores
816 st->psq -= psq[them][capture][capsq];
818 // Reset rule 50 counter
823 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
825 // Reset en passant square
826 if (st->epSquare != SQ_NONE)
828 k ^= Zobrist::enpassant[file_of(st->epSquare)];
829 st->epSquare = SQ_NONE;
832 // Update castle rights if needed
833 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
835 int cr = castleRightsMask[from] | castleRightsMask[to];
836 k ^= Zobrist::castle[st->castleRights & cr];
837 st->castleRights &= ~cr;
840 // Prefetch TT access as soon as we know the new hash key
841 prefetch((char*)TT.first_entry(k));
843 // Move the piece. The tricky Chess960 castle is handled earlier
844 if (type_of(m) != CASTLE)
846 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
847 byTypeBB[ALL_PIECES] ^= from_to_bb;
848 byTypeBB[pt] ^= from_to_bb;
849 byColorBB[us] ^= from_to_bb;
851 board[from] = NO_PIECE;
854 // Update piece lists, index[from] is not updated and becomes stale. This
855 // works as long as index[] is accessed just by known occupied squares.
856 index[to] = index[from];
857 pieceList[us][pt][index[to]] = to;
860 // If the moving piece is a pawn do some special extra work
863 // Set en-passant square, only if moved pawn can be captured
864 if ( (int(to) ^ int(from)) == 16
865 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
867 st->epSquare = Square((from + to) / 2);
868 k ^= Zobrist::enpassant[file_of(st->epSquare)];
871 if (type_of(m) == PROMOTION)
873 PieceType promotion = promotion_type(m);
875 assert(relative_rank(us, to) == RANK_8);
876 assert(promotion >= KNIGHT && promotion <= QUEEN);
878 // Replace the pawn with the promoted piece
879 byTypeBB[PAWN] ^= to;
880 byTypeBB[promotion] |= to;
881 board[to] = make_piece(us, promotion);
883 // Update piece lists, move the last pawn at index[to] position
884 // and shrink the list. Add a new promotion piece to the list.
885 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
886 index[lastSquare] = index[to];
887 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
888 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
889 index[to] = pieceCount[us][promotion];
890 pieceList[us][promotion][index[to]] = to;
893 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
894 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
895 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
896 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
898 // Update incremental score
899 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
902 st->npMaterial[us] += PieceValue[MG][promotion];
905 // Update pawn hash key and prefetch access to pawnsTable
906 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
907 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
909 // Reset rule 50 draw counter
913 // Update incremental scores
914 st->psq += psq[us][pt][to] - psq[us][pt][from];
917 st->capturedType = capture;
919 // Update the key with the final value
922 // Update checkers bitboard, piece must be already moved
927 if (type_of(m) != NORMAL)
928 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
932 if (ci.checkSq[pt] & to)
933 st->checkersBB |= to;
936 if (ci.dcCandidates && (ci.dcCandidates & from))
939 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
942 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
947 sideToMove = ~sideToMove;
953 /// Position::undo_move() unmakes a move. When it returns, the position should
954 /// be restored to exactly the same state as before the move was made.
956 void Position::undo_move(Move m) {
960 sideToMove = ~sideToMove;
962 Color us = sideToMove;
964 Square from = from_sq(m);
965 Square to = to_sq(m);
966 PieceType pt = type_of(piece_on(to));
967 PieceType capture = st->capturedType;
969 assert(is_empty(from) || type_of(m) == CASTLE);
970 assert(capture != KING);
972 if (type_of(m) == PROMOTION)
974 PieceType promotion = promotion_type(m);
976 assert(promotion == pt);
977 assert(relative_rank(us, to) == RANK_8);
978 assert(promotion >= KNIGHT && promotion <= QUEEN);
980 // Replace the promoted piece with the pawn
981 byTypeBB[promotion] ^= to;
982 byTypeBB[PAWN] |= to;
983 board[to] = make_piece(us, PAWN);
985 // Update piece lists, move the last promoted piece at index[to] position
986 // and shrink the list. Add a new pawn to the list.
987 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
988 index[lastSquare] = index[to];
989 pieceList[us][promotion][index[lastSquare]] = lastSquare;
990 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
991 index[to] = pieceCount[us][PAWN]++;
992 pieceList[us][PAWN][index[to]] = to;
997 if (type_of(m) == CASTLE)
999 bool kingSide = to > from;
1000 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1001 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1002 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1003 capture = NO_PIECE_TYPE;
1005 do_castle(to, from, rto, rfrom);
1009 // Put the piece back at the source square
1010 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1011 byTypeBB[ALL_PIECES] ^= from_to_bb;
1012 byTypeBB[pt] ^= from_to_bb;
1013 byColorBB[us] ^= from_to_bb;
1015 board[to] = NO_PIECE;
1016 board[from] = make_piece(us, pt);
1018 // Update piece lists, index[to] is not updated and becomes stale. This
1019 // works as long as index[] is accessed just by known occupied squares.
1020 index[from] = index[to];
1021 pieceList[us][pt][index[from]] = from;
1028 if (type_of(m) == ENPASSANT)
1030 capsq -= pawn_push(us);
1033 assert(to == st->previous->epSquare);
1034 assert(relative_rank(us, to) == RANK_6);
1035 assert(piece_on(capsq) == NO_PIECE);
1038 // Restore the captured piece
1039 byTypeBB[ALL_PIECES] |= capsq;
1040 byTypeBB[capture] |= capsq;
1041 byColorBB[them] |= capsq;
1043 board[capsq] = make_piece(them, capture);
1045 // Update piece list, add a new captured piece in capsq square
1046 index[capsq] = pieceCount[them][capture]++;
1047 pieceList[them][capture][index[capsq]] = capsq;
1050 // Finally point our state pointer back to the previous state
1054 assert(pos_is_ok());
1058 /// Position::do_castle() is a helper used to do/undo a castling move. This
1059 /// is a bit tricky, especially in Chess960.
1061 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1063 Color us = sideToMove;
1064 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1065 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1066 byTypeBB[KING] ^= k_from_to_bb;
1067 byTypeBB[ROOK] ^= r_from_to_bb;
1068 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1069 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1071 // Could be from == to, so first set NO_PIECE then KING and ROOK
1072 board[kfrom] = board[rfrom] = NO_PIECE;
1073 board[kto] = make_piece(us, KING);
1074 board[rto] = make_piece(us, ROOK);
1076 // Could be kfrom == rto, so use a 'tmp' variable
1077 int tmp = index[kfrom];
1078 index[rto] = index[rfrom];
1080 pieceList[us][KING][index[kto]] = kto;
1081 pieceList[us][ROOK][index[rto]] = rto;
1085 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1086 /// the side to move without executing any move on the board.
1088 void Position::do_null_move(StateInfo& newSt) {
1090 assert(!checkers());
1092 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1094 newSt.previous = st;
1097 if (st->epSquare != SQ_NONE)
1099 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1100 st->epSquare = SQ_NONE;
1103 st->key ^= Zobrist::side;
1104 prefetch((char*)TT.first_entry(st->key));
1107 st->pliesFromNull = 0;
1109 sideToMove = ~sideToMove;
1111 assert(pos_is_ok());
1114 void Position::undo_null_move() {
1116 assert(!checkers());
1119 sideToMove = ~sideToMove;
1123 /// Position::see() is a static exchange evaluator: It tries to estimate the
1124 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1125 /// tempi into account. If the side who initiated the capturing sequence does the
1126 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1127 /// the capturing sequence is considered bad.
1129 int Position::see_sign(Move m) const {
1133 // Early return if SEE cannot be negative because captured piece value
1134 // is not less then capturing one. Note that king moves always return
1135 // here because king midgame value is set to 0.
1136 if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1142 int Position::see(Move m, int asymmThreshold) const {
1145 Bitboard occupied, attackers, stmAttackers;
1146 int swapList[32], slIndex = 1;
1154 captured = type_of(piece_on(to));
1155 occupied = pieces() ^ from;
1157 // Handle en passant moves
1158 if (type_of(m) == ENPASSANT)
1160 Square capQq = to - pawn_push(sideToMove);
1163 assert(type_of(piece_on(capQq)) == PAWN);
1165 // Remove the captured pawn
1169 else if (type_of(m) == CASTLE)
1170 // Castle moves are implemented as king capturing the rook so cannot be
1171 // handled correctly. Simply return 0 that is always the correct value
1172 // unless the rook is ends up under attack.
1175 // Find all attackers to the destination square, with the moving piece
1176 // removed, but possibly an X-ray attacker added behind it.
1177 attackers = attackers_to(to, occupied);
1179 // If the opponent has no attackers we are finished
1180 stm = ~color_of(piece_on(from));
1181 stmAttackers = attackers & pieces(stm);
1183 return PieceValue[MG][captured];
1185 // The destination square is defended, which makes things rather more
1186 // difficult to compute. We proceed by building up a "swap list" containing
1187 // the material gain or loss at each stop in a sequence of captures to the
1188 // destination square, where the sides alternately capture, and always
1189 // capture with the least valuable piece. After each capture, we look for
1190 // new X-ray attacks from behind the capturing piece.
1191 swapList[0] = PieceValue[MG][captured];
1192 captured = type_of(piece_on(from));
1195 assert(slIndex < 32);
1197 // Add the new entry to the swap list
1198 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1201 // Locate and remove from 'occupied' the next least valuable attacker
1202 captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1204 attackers &= occupied; // Remove the just found attacker
1206 stmAttackers = attackers & pieces(stm);
1208 if (captured == KING)
1210 // Stop before processing a king capture
1212 swapList[slIndex++] = QueenValueMg * 16;
1217 } while (stmAttackers);
1219 // If we are doing asymmetric SEE evaluation and the same side does the first
1220 // and the last capture, he loses a tempo and gain must be at least worth
1221 // 'asymmThreshold', otherwise we replace the score with a very low value,
1222 // before negamaxing.
1224 for (int i = 0; i < slIndex; i += 2)
1225 if (swapList[i] < asymmThreshold)
1226 swapList[i] = - QueenValueMg * 16;
1228 // Having built the swap list, we negamax through it to find the best
1229 // achievable score from the point of view of the side to move.
1231 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1237 /// Position::clear() erases the position object to a pristine state, with an
1238 /// empty board, white to move, and no castling rights.
1240 void Position::clear() {
1242 std::memset(this, 0, sizeof(Position));
1243 startState.epSquare = SQ_NONE;
1246 for (int i = 0; i < 8; i++)
1247 for (int j = 0; j < 16; j++)
1248 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1252 /// Position::put_piece() puts a piece on the given square of the board,
1253 /// updating the board array, pieces list, bitboards, and piece counts.
1255 void Position::put_piece(Piece p, Square s) {
1257 Color c = color_of(p);
1258 PieceType pt = type_of(p);
1261 index[s] = pieceCount[c][pt]++;
1262 pieceList[c][pt][index[s]] = s;
1264 byTypeBB[ALL_PIECES] |= s;
1270 /// Position::compute_key() computes the hash key of the position. The hash
1271 /// key is usually updated incrementally as moves are made and unmade, the
1272 /// compute_key() function is only used when a new position is set up, and
1273 /// to verify the correctness of the hash key when running in debug mode.
1275 Key Position::compute_key() const {
1277 Key k = Zobrist::castle[st->castleRights];
1279 for (Bitboard b = pieces(); b; )
1281 Square s = pop_lsb(&b);
1282 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1285 if (ep_square() != SQ_NONE)
1286 k ^= Zobrist::enpassant[file_of(ep_square())];
1288 if (sideToMove == BLACK)
1295 /// Position::compute_pawn_key() computes the hash key of the position. The
1296 /// hash key is usually updated incrementally as moves are made and unmade,
1297 /// the compute_pawn_key() function is only used when a new position is set
1298 /// up, and to verify the correctness of the pawn hash key when running in
1301 Key Position::compute_pawn_key() const {
1305 for (Bitboard b = pieces(PAWN); b; )
1307 Square s = pop_lsb(&b);
1308 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1315 /// Position::compute_material_key() computes the hash key of the position.
1316 /// The hash key is usually updated incrementally as moves are made and unmade,
1317 /// the compute_material_key() function is only used when a new position is set
1318 /// up, and to verify the correctness of the material hash key when running in
1321 Key Position::compute_material_key() const {
1325 for (Color c = WHITE; c <= BLACK; c++)
1326 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1327 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1328 k ^= Zobrist::psq[c][pt][cnt];
1334 /// Position::compute_psq_score() computes the incremental scores for the middle
1335 /// game and the endgame. These functions are used to initialize the incremental
1336 /// scores when a new position is set up, and to verify that the scores are correctly
1337 /// updated by do_move and undo_move when the program is running in debug mode.
1338 Score Position::compute_psq_score() const {
1340 Score score = SCORE_ZERO;
1342 for (Bitboard b = pieces(); b; )
1344 Square s = pop_lsb(&b);
1345 Piece pc = piece_on(s);
1346 score += psq[color_of(pc)][type_of(pc)][s];
1353 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1354 /// game material value for the given side. Material values are updated
1355 /// incrementally during the search, this function is only used while
1356 /// initializing a new Position object.
1358 Value Position::compute_non_pawn_material(Color c) const {
1360 Value value = VALUE_ZERO;
1362 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1363 value += pieceCount[c][pt] * PieceValue[MG][pt];
1369 /// Position::is_draw() tests whether the position is drawn by material,
1370 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1371 /// must be done by the search.
1372 bool Position::is_draw() const {
1374 // Draw by material?
1376 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1379 // Draw by the 50 moves rule?
1380 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1383 // Draw by repetition?
1384 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1388 StateInfo* stp = st->previous->previous;
1391 stp = stp->previous->previous;
1393 if (stp->key == st->key)
1405 /// Position::flip() flips position with the white and black sides reversed. This
1406 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1408 void Position::flip() {
1410 const Position pos(*this);
1414 sideToMove = ~pos.side_to_move();
1415 thisThread = pos.this_thread();
1416 nodes = pos.nodes_searched();
1417 chess960 = pos.is_chess960();
1418 gamePly = pos.game_ply();
1420 for (Square s = SQ_A1; s <= SQ_H8; s++)
1421 if (!pos.is_empty(s))
1422 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1424 if (pos.can_castle(WHITE_OO))
1425 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1426 if (pos.can_castle(WHITE_OOO))
1427 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1428 if (pos.can_castle(BLACK_OO))
1429 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1430 if (pos.can_castle(BLACK_OOO))
1431 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1433 if (pos.st->epSquare != SQ_NONE)
1434 st->epSquare = ~pos.st->epSquare;
1436 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1438 st->key = compute_key();
1439 st->pawnKey = compute_pawn_key();
1440 st->materialKey = compute_material_key();
1441 st->psq = compute_psq_score();
1442 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1443 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1445 assert(pos_is_ok());
1449 /// Position::pos_is_ok() performs some consitency checks for the position object.
1450 /// This is meant to be helpful when debugging.
1452 bool Position::pos_is_ok(int* failedStep) const {
1454 int dummy, *step = failedStep ? failedStep : &dummy;
1456 // What features of the position should be verified?
1457 const bool all = false;
1459 const bool debugBitboards = all || false;
1460 const bool debugKingCount = all || false;
1461 const bool debugKingCapture = all || false;
1462 const bool debugCheckerCount = all || false;
1463 const bool debugKey = all || false;
1464 const bool debugMaterialKey = all || false;
1465 const bool debugPawnKey = all || false;
1466 const bool debugIncrementalEval = all || false;
1467 const bool debugNonPawnMaterial = all || false;
1468 const bool debugPieceCounts = all || false;
1469 const bool debugPieceList = all || false;
1470 const bool debugCastleSquares = all || false;
1474 if (sideToMove != WHITE && sideToMove != BLACK)
1477 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1480 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1483 if ((*step)++, debugKingCount)
1485 int kingCount[COLOR_NB] = {};
1487 for (Square s = SQ_A1; s <= SQ_H8; s++)
1488 if (type_of(piece_on(s)) == KING)
1489 kingCount[color_of(piece_on(s))]++;
1491 if (kingCount[0] != 1 || kingCount[1] != 1)
1495 if ((*step)++, debugKingCapture)
1496 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1499 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1502 if ((*step)++, debugBitboards)
1504 // The intersection of the white and black pieces must be empty
1505 if (pieces(WHITE) & pieces(BLACK))
1508 // The union of the white and black pieces must be equal to all
1510 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1513 // Separate piece type bitboards must have empty intersections
1514 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1515 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1516 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1520 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1523 if ((*step)++, debugKey && st->key != compute_key())
1526 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1529 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1532 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1535 if ((*step)++, debugNonPawnMaterial)
1536 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1537 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1540 if ((*step)++, debugPieceCounts)
1541 for (Color c = WHITE; c <= BLACK; c++)
1542 for (PieceType pt = PAWN; pt <= KING; pt++)
1543 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1546 if ((*step)++, debugPieceList)
1547 for (Color c = WHITE; c <= BLACK; c++)
1548 for (PieceType pt = PAWN; pt <= KING; pt++)
1549 for (int i = 0; i < pieceCount[c][pt]; i++)
1550 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1551 || index[pieceList[c][pt][i]] != i)
1554 if ((*step)++, debugCastleSquares)
1555 for (Color c = WHITE; c <= BLACK; c++)
1556 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1558 CastleRight cr = make_castle_right(c, s);
1560 if (!can_castle(cr))
1563 if ( (castleRightsMask[king_square(c)] & cr) != cr
1564 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1565 || castleRightsMask[castleRookSquare[c][s]] != cr)