2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score pieceSquareTable[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];
57 /// init() initializes at startup the various arrays used to compute hash keys
58 /// and the piece square tables. The latter is a two-step operation: First, the
59 /// white halves of the tables are copied from PSQT[] tables. Second, the black
60 /// halves of the tables are initialized by flipping and changing the sign of
67 for (Color c = WHITE; c <= BLACK; c++)
68 for (PieceType pt = PAWN; pt <= KING; pt++)
69 for (Square s = SQ_A1; s <= SQ_H8; s++)
70 psq[c][pt][s] = rk.rand<Key>();
72 for (File f = FILE_A; f <= FILE_H; f++)
73 enpassant[f] = rk.rand<Key>();
75 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
80 Key k = castle[1ULL << pop_lsb(&b)];
81 castle[cr] ^= k ? k : rk.rand<Key>();
85 side = rk.rand<Key>();
86 exclusion = rk.rand<Key>();
88 for (PieceType pt = PAWN; pt <= KING; pt++)
90 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
91 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
93 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
95 for (Square s = SQ_A1; s <= SQ_H8; s++)
97 pieceSquareTable[WHITE][pt][ s] = (v + PSQT[pt][s]);
98 pieceSquareTable[BLACK][pt][~s] = -(v + PSQT[pt][s]);
103 } // namespace Zobrist
108 // next_attacker() is an helper function used by see() to locate the least
109 // valuable attacker for the side to move, remove the attacker we just found
110 // from the 'occupied' bitboard and scan for new X-ray attacks behind it.
112 template<int Pt> FORCE_INLINE
113 PieceType next_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
114 Bitboard& occupied, Bitboard& attackers) {
116 if (stmAttackers & bb[Pt])
118 Bitboard b = stmAttackers & bb[Pt];
119 occupied ^= b & ~(b - 1);
121 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
122 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
124 if (Pt == ROOK || Pt == QUEEN)
125 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
127 return (PieceType)Pt;
129 return next_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
132 template<> FORCE_INLINE
133 PieceType next_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
134 return KING; // No need to update bitboards, it is the last cycle
142 CheckInfo::CheckInfo(const Position& pos) {
144 Color them = ~pos.side_to_move();
145 ksq = pos.king_square(them);
147 pinned = pos.pinned_pieces();
148 dcCandidates = pos.discovered_check_candidates();
150 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
151 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
152 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
153 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
154 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
159 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
160 /// object do not depend on any external data so we detach state pointer from
163 Position& Position::operator=(const Position& pos) {
165 memcpy(this, &pos, sizeof(Position));
176 /// Position::set() initializes the position object with the given FEN string.
177 /// This function is not very robust - make sure that input FENs are correct,
178 /// this is assumed to be the responsibility of the GUI.
180 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
182 A FEN string defines a particular position using only the ASCII character set.
184 A FEN string contains six fields separated by a space. The fields are:
186 1) Piece placement (from white's perspective). Each rank is described, starting
187 with rank 8 and ending with rank 1; within each rank, the contents of each
188 square are described from file A through file H. Following the Standard
189 Algebraic Notation (SAN), each piece is identified by a single letter taken
190 from the standard English names. White pieces are designated using upper-case
191 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
192 noted using digits 1 through 8 (the number of blank squares), and "/"
195 2) Active color. "w" means white moves next, "b" means black.
197 3) Castling availability. If neither side can castle, this is "-". Otherwise,
198 this has one or more letters: "K" (White can castle kingside), "Q" (White
199 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
200 can castle queenside).
202 4) En passant target square (in algebraic notation). If there's no en passant
203 target square, this is "-". If a pawn has just made a 2-square move, this
204 is the position "behind" the pawn. This is recorded regardless of whether
205 there is a pawn in position to make an en passant capture.
207 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
208 or capture. This is used to determine if a draw can be claimed under the
211 6) Fullmove number. The number of the full move. It starts at 1, and is
212 incremented after Black's move.
215 char col, row, token;
218 std::istringstream ss(fenStr);
223 // 1. Piece placement
224 while ((ss >> token) && !isspace(token))
227 sq += Square(token - '0'); // Advance the given number of files
229 else if (token == '/')
232 else if ((p = PieceToChar.find(token)) != string::npos)
234 put_piece(Piece(p), sq);
241 sideToMove = (token == 'w' ? WHITE : BLACK);
244 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
245 // Shredder-FEN that uses the letters of the columns on which the rooks began
246 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
247 // if an inner rook is associated with the castling right, the castling tag is
248 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
249 while ((ss >> token) && !isspace(token))
252 Color c = islower(token) ? BLACK : WHITE;
254 token = char(toupper(token));
257 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
259 else if (token == 'Q')
260 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
262 else if (token >= 'A' && token <= 'H')
263 rsq = File(token - 'A') | relative_rank(c, RANK_1);
268 set_castle_right(c, rsq);
271 // 4. En passant square. Ignore if no pawn capture is possible
272 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
273 && ((ss >> row) && (row == '3' || row == '6')))
275 st->epSquare = File(col - 'a') | Rank(row - '1');
277 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
278 st->epSquare = SQ_NONE;
281 // 5-6. Halfmove clock and fullmove number
282 ss >> std::skipws >> st->rule50 >> gamePly;
284 // Convert from fullmove starting from 1 to ply starting from 0,
285 // handle also common incorrect FEN with fullmove = 0.
286 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
288 st->key = compute_key();
289 st->pawnKey = compute_pawn_key();
290 st->materialKey = compute_material_key();
291 st->psqScore = compute_psq_score();
292 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
293 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
294 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
295 chess960 = isChess960;
302 /// Position::set_castle_right() is an helper function used to set castling
303 /// rights given the corresponding color and the rook starting square.
305 void Position::set_castle_right(Color c, Square rfrom) {
307 Square kfrom = king_square(c);
308 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
309 CastleRight cr = make_castle_right(c, cs);
311 st->castleRights |= cr;
312 castleRightsMask[kfrom] |= cr;
313 castleRightsMask[rfrom] |= cr;
314 castleRookSquare[c][cs] = rfrom;
316 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
317 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
319 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
320 if (s != kfrom && s != rfrom)
321 castlePath[c][cs] |= s;
323 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
324 if (s != kfrom && s != rfrom)
325 castlePath[c][cs] |= s;
329 /// Position::fen() returns a FEN representation of the position. In case
330 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
332 const string Position::fen() const {
334 std::ostringstream ss;
336 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
338 for (File file = FILE_A; file <= FILE_H; file++)
340 Square sq = file | rank;
346 for ( ; file < FILE_H && is_empty(sq++); file++)
352 ss << PieceToChar[piece_on(sq)];
359 ss << (sideToMove == WHITE ? " w " : " b ");
361 if (can_castle(WHITE_OO))
362 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
364 if (can_castle(WHITE_OOO))
365 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
367 if (can_castle(BLACK_OO))
368 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
370 if (can_castle(BLACK_OOO))
371 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
373 if (st->castleRights == CASTLES_NONE)
376 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
377 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
383 /// Position::pretty() returns an ASCII representation of the position to be
384 /// printed to the standard output together with the move's san notation.
386 const string Position::pretty(Move move) const {
388 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
389 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
390 + dottedLine + "\n| . | | . | | . | | . | |";
392 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
394 std::ostringstream ss;
397 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
398 << move_to_san(*const_cast<Position*>(this), move);
400 for (Square sq = SQ_A1; sq <= SQ_H8; sq++)
401 if (piece_on(sq) != NO_PIECE)
402 brd[513 - 68*rank_of(sq) + 4*file_of(sq)] = PieceToChar[piece_on(sq)];
404 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
405 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
407 for (Bitboard b = checkers(); b; )
408 ss << square_to_string(pop_lsb(&b)) << " ";
410 ss << "\nLegal moves: ";
411 for (MoveList<LEGAL> it(*this); *it; ++it)
412 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
418 /// Position:hidden_checkers<>() returns a bitboard of all pinned (against the
419 /// king) pieces for the given color. Or, when template parameter FindPinned is
420 /// false, the function return the pieces of the given color candidate for a
421 /// discovery check against the enemy king.
422 template<bool FindPinned>
423 Bitboard Position::hidden_checkers() const {
425 // Pinned pieces protect our king, dicovery checks attack the enemy king
426 Bitboard b, result = 0;
427 Bitboard pinners = pieces(FindPinned ? ~sideToMove : sideToMove);
428 Square ksq = king_square(FindPinned ? sideToMove : ~sideToMove);
430 // Pinners are sliders, that give check when candidate pinned is removed
431 pinners &= (pieces(ROOK, QUEEN) & PseudoAttacks[ROOK][ksq])
432 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq]);
436 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
438 if (b && !more_than_one(b) && (b & pieces(sideToMove)))
444 // Explicit template instantiations
445 template Bitboard Position::hidden_checkers<true>() const;
446 template Bitboard Position::hidden_checkers<false>() const;
449 /// Position::attackers_to() computes a bitboard of all pieces which attack a
450 /// given square. Slider attacks use occ bitboard as occupancy.
452 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
454 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
455 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
456 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
457 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
458 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
459 | (attacks_from<KING>(s) & pieces(KING));
463 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
464 /// put in a given square. Slider attacks use occ bitboard as occupancy.
466 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
472 case BISHOP: return attacks_bb<BISHOP>(s, occ);
473 case ROOK : return attacks_bb<ROOK>(s, occ);
474 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
475 default : return StepAttacksBB[p][s];
480 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
482 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
485 assert(pinned == pinned_pieces());
487 Color us = sideToMove;
488 Square from = from_sq(m);
490 assert(color_of(piece_moved(m)) == us);
491 assert(piece_on(king_square(us)) == make_piece(us, KING));
493 // En passant captures are a tricky special case. Because they are rather
494 // uncommon, we do it simply by testing whether the king is attacked after
496 if (type_of(m) == ENPASSANT)
499 Square to = to_sq(m);
500 Square capsq = to + pawn_push(them);
501 Square ksq = king_square(us);
502 Bitboard b = (pieces() ^ from ^ capsq) | to;
504 assert(to == ep_square());
505 assert(piece_moved(m) == make_piece(us, PAWN));
506 assert(piece_on(capsq) == make_piece(them, PAWN));
507 assert(piece_on(to) == NO_PIECE);
509 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
510 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
513 // If the moving piece is a king, check whether the destination
514 // square is attacked by the opponent. Castling moves are checked
515 // for legality during move generation.
516 if (type_of(piece_on(from)) == KING)
517 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
519 // A non-king move is legal if and only if it is not pinned or it
520 // is moving along the ray towards or away from the king.
523 || squares_aligned(from, to_sq(m), king_square(us));
527 /// Position::is_pseudo_legal() takes a random move and tests whether the move
528 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
529 /// due to SMP concurrent access or hash position key aliasing.
531 bool Position::is_pseudo_legal(const Move m) const {
533 Color us = sideToMove;
534 Square from = from_sq(m);
535 Square to = to_sq(m);
536 Piece pc = piece_moved(m);
538 // Use a slower but simpler function for uncommon cases
539 if (type_of(m) != NORMAL)
540 return MoveList<LEGAL>(*this).contains(m);
542 // Is not a promotion, so promotion piece must be empty
543 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
546 // If the from square is not occupied by a piece belonging to the side to
547 // move, the move is obviously not legal.
548 if (pc == NO_PIECE || color_of(pc) != us)
551 // The destination square cannot be occupied by a friendly piece
552 if (piece_on(to) != NO_PIECE && color_of(piece_on(to)) == us)
555 // Handle the special case of a pawn move
556 if (type_of(pc) == PAWN)
558 // Move direction must be compatible with pawn color
559 int direction = to - from;
560 if ((us == WHITE) != (direction > 0))
563 // We have already handled promotion moves, so destination
564 // cannot be on the 8/1th rank.
565 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
568 // Proceed according to the square delta between the origin and
569 // destination squares.
576 // Capture. The destination square must be occupied by an enemy
577 // piece (en passant captures was handled earlier).
578 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
581 // From and to files must be one file apart, avoids a7h5
582 if (abs(file_of(from) - file_of(to)) != 1)
588 // Pawn push. The destination square must be empty.
594 // Double white pawn push. The destination square must be on the fourth
595 // rank, and both the destination square and the square between the
596 // source and destination squares must be empty.
597 if ( rank_of(to) != RANK_4
599 || !is_empty(from + DELTA_N))
604 // Double black pawn push. The destination square must be on the fifth
605 // rank, and both the destination square and the square between the
606 // source and destination squares must be empty.
607 if ( rank_of(to) != RANK_5
609 || !is_empty(from + DELTA_S))
617 else if (!(attacks_from(pc, from) & to))
620 // Evasions generator already takes care to avoid some kind of illegal moves
621 // and pl_move_is_legal() relies on this. So we have to take care that the
622 // same kind of moves are filtered out here.
625 if (type_of(pc) != KING)
627 // Double check? In this case a king move is required
628 if (more_than_one(checkers()))
631 // Our move must be a blocking evasion or a capture of the checking piece
632 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
635 // In case of king moves under check we have to remove king so to catch
636 // as invalid moves like b1a1 when opposite queen is on c1.
637 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
645 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
647 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
650 assert(ci.dcCandidates == discovered_check_candidates());
651 assert(color_of(piece_moved(m)) == sideToMove);
653 Square from = from_sq(m);
654 Square to = to_sq(m);
655 PieceType pt = type_of(piece_on(from));
658 if (ci.checkSq[pt] & to)
662 if (ci.dcCandidates && (ci.dcCandidates & from))
664 // For pawn and king moves we need to verify also direction
665 if ( (pt != PAWN && pt != KING)
666 || !squares_aligned(from, to, king_square(~sideToMove)))
670 // Can we skip the ugly special cases ?
671 if (type_of(m) == NORMAL)
674 Color us = sideToMove;
675 Square ksq = king_square(~us);
680 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
682 // En passant capture with check ? We have already handled the case
683 // of direct checks and ordinary discovered check, the only case we
684 // need to handle is the unusual case of a discovered check through
685 // the captured pawn.
688 Square capsq = file_of(to) | rank_of(from);
689 Bitboard b = (pieces() ^ from ^ capsq) | to;
691 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
692 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
697 Square rfrom = to; // 'King captures the rook' notation
698 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
699 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
700 Bitboard b = (pieces() ^ kfrom ^ rfrom) | rto | kto;
702 return attacks_bb<ROOK>(rto, b) & ksq;
711 /// Position::do_move() makes a move, and saves all information necessary
712 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
713 /// moves should be filtered out before this function is called.
715 void Position::do_move(Move m, StateInfo& newSt) {
718 do_move(m, newSt, ci, move_gives_check(m, ci));
721 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
724 assert(&newSt != st);
729 // Copy some fields of old state to our new StateInfo object except the ones
730 // which are going to be recalculated from scratch anyway, then switch our state
731 // pointer to point to the new, ready to be updated, state.
732 memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
737 // Update side to move
740 // Increment ply counters.In particular rule50 will be later reset it to zero
741 // in case of a capture or a pawn move.
746 Color us = sideToMove;
748 Square from = from_sq(m);
749 Square to = to_sq(m);
750 Piece pc = piece_on(from);
751 PieceType pt = type_of(pc);
752 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
754 assert(color_of(pc) == us);
755 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
756 assert(capture != KING);
758 if (type_of(m) == CASTLE)
760 assert(pc == make_piece(us, KING));
762 bool kingSide = to > from;
763 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
764 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
765 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
766 capture = NO_PIECE_TYPE;
768 do_castle(from, to, rfrom, rto);
770 st->psqScore += pieceSquareTable[us][ROOK][rto] - pieceSquareTable[us][ROOK][rfrom];
771 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
778 // If the captured piece is a pawn, update pawn hash key, otherwise
779 // update non-pawn material.
782 if (type_of(m) == ENPASSANT)
784 capsq += pawn_push(them);
787 assert(to == st->epSquare);
788 assert(relative_rank(us, to) == RANK_6);
789 assert(piece_on(to) == NO_PIECE);
790 assert(piece_on(capsq) == make_piece(them, PAWN));
792 board[capsq] = NO_PIECE;
795 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
798 st->npMaterial[them] -= PieceValue[MG][capture];
800 // Remove the captured piece
801 byTypeBB[ALL_PIECES] ^= capsq;
802 byTypeBB[capture] ^= capsq;
803 byColorBB[them] ^= capsq;
805 // Update piece list, move the last piece at index[capsq] position and
808 // WARNING: This is a not reversible operation. When we will reinsert the
809 // captured piece in undo_move() we will put it at the end of the list and
810 // not in its original place, it means index[] and pieceList[] are not
811 // guaranteed to be invariant to a do_move() + undo_move() sequence.
812 Square lastSquare = pieceList[them][capture][--pieceCount[them][capture]];
813 index[lastSquare] = index[capsq];
814 pieceList[them][capture][index[lastSquare]] = lastSquare;
815 pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
817 // Update material hash key and prefetch access to materialTable
818 k ^= Zobrist::psq[them][capture][capsq];
819 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
820 prefetch((char*)thisThread->materialTable[st->materialKey]);
822 // Update incremental scores
823 st->psqScore -= pieceSquareTable[them][capture][capsq];
825 // Reset rule 50 counter
830 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
832 // Reset en passant square
833 if (st->epSquare != SQ_NONE)
835 k ^= Zobrist::enpassant[file_of(st->epSquare)];
836 st->epSquare = SQ_NONE;
839 // Update castle rights if needed
840 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
842 int cr = castleRightsMask[from] | castleRightsMask[to];
843 k ^= Zobrist::castle[st->castleRights & cr];
844 st->castleRights &= ~cr;
847 // Prefetch TT access as soon as we know the new hash key
848 prefetch((char*)TT.first_entry(k));
850 // Move the piece. The tricky Chess960 castle is handled earlier
851 if (type_of(m) != CASTLE)
853 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
854 byTypeBB[ALL_PIECES] ^= from_to_bb;
855 byTypeBB[pt] ^= from_to_bb;
856 byColorBB[us] ^= from_to_bb;
858 board[from] = NO_PIECE;
861 // Update piece lists, index[from] is not updated and becomes stale. This
862 // works as long as index[] is accessed just by known occupied squares.
863 index[to] = index[from];
864 pieceList[us][pt][index[to]] = to;
867 // If the moving piece is a pawn do some special extra work
870 // Set en-passant square, only if moved pawn can be captured
871 if ( (int(to) ^ int(from)) == 16
872 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
874 st->epSquare = Square((from + to) / 2);
875 k ^= Zobrist::enpassant[file_of(st->epSquare)];
878 if (type_of(m) == PROMOTION)
880 PieceType promotion = promotion_type(m);
882 assert(relative_rank(us, to) == RANK_8);
883 assert(promotion >= KNIGHT && promotion <= QUEEN);
885 // Replace the pawn with the promoted piece
886 byTypeBB[PAWN] ^= to;
887 byTypeBB[promotion] |= to;
888 board[to] = make_piece(us, promotion);
890 // Update piece lists, move the last pawn at index[to] position
891 // and shrink the list. Add a new promotion piece to the list.
892 Square lastSquare = pieceList[us][PAWN][--pieceCount[us][PAWN]];
893 index[lastSquare] = index[to];
894 pieceList[us][PAWN][index[lastSquare]] = lastSquare;
895 pieceList[us][PAWN][pieceCount[us][PAWN]] = SQ_NONE;
896 index[to] = pieceCount[us][promotion];
897 pieceList[us][promotion][index[to]] = to;
900 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
901 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
902 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]++]
903 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
905 // Update incremental score
906 st->psqScore += pieceSquareTable[us][promotion][to] - pieceSquareTable[us][PAWN][to];
909 st->npMaterial[us] += PieceValue[MG][promotion];
912 // Update pawn hash key and prefetch access to pawnsTable
913 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
914 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
916 // Reset rule 50 draw counter
920 // Update incremental scores
921 st->psqScore += pieceSquareTable[us][pt][to] - pieceSquareTable[us][pt][from];
924 st->capturedType = capture;
926 // Update the key with the final value
929 // Update checkers bitboard, piece must be already moved
934 if (type_of(m) != NORMAL)
935 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
939 if (ci.checkSq[pt] & to)
940 st->checkersBB |= to;
943 if (ci.dcCandidates && (ci.dcCandidates & from))
946 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
949 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
954 sideToMove = ~sideToMove;
960 /// Position::undo_move() unmakes a move. When it returns, the position should
961 /// be restored to exactly the same state as before the move was made.
963 void Position::undo_move(Move m) {
967 sideToMove = ~sideToMove;
969 Color us = sideToMove;
971 Square from = from_sq(m);
972 Square to = to_sq(m);
973 PieceType pt = type_of(piece_on(to));
974 PieceType capture = st->capturedType;
976 assert(is_empty(from) || type_of(m) == CASTLE);
977 assert(capture != KING);
979 if (type_of(m) == PROMOTION)
981 PieceType promotion = promotion_type(m);
983 assert(promotion == pt);
984 assert(relative_rank(us, to) == RANK_8);
985 assert(promotion >= KNIGHT && promotion <= QUEEN);
987 // Replace the promoted piece with the pawn
988 byTypeBB[promotion] ^= to;
989 byTypeBB[PAWN] |= to;
990 board[to] = make_piece(us, PAWN);
992 // Update piece lists, move the last promoted piece at index[to] position
993 // and shrink the list. Add a new pawn to the list.
994 Square lastSquare = pieceList[us][promotion][--pieceCount[us][promotion]];
995 index[lastSquare] = index[to];
996 pieceList[us][promotion][index[lastSquare]] = lastSquare;
997 pieceList[us][promotion][pieceCount[us][promotion]] = SQ_NONE;
998 index[to] = pieceCount[us][PAWN]++;
999 pieceList[us][PAWN][index[to]] = to;
1004 if (type_of(m) == CASTLE)
1006 bool kingSide = to > from;
1007 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
1008 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
1009 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
1010 capture = NO_PIECE_TYPE;
1012 do_castle(to, from, rto, rfrom);
1016 // Put the piece back at the source square
1017 Bitboard from_to_bb = SquareBB[from] ^ SquareBB[to];
1018 byTypeBB[ALL_PIECES] ^= from_to_bb;
1019 byTypeBB[pt] ^= from_to_bb;
1020 byColorBB[us] ^= from_to_bb;
1022 board[to] = NO_PIECE;
1023 board[from] = make_piece(us, pt);
1025 // Update piece lists, index[to] is not updated and becomes stale. This
1026 // works as long as index[] is accessed just by known occupied squares.
1027 index[from] = index[to];
1028 pieceList[us][pt][index[from]] = from;
1035 if (type_of(m) == ENPASSANT)
1037 capsq -= pawn_push(us);
1040 assert(to == st->previous->epSquare);
1041 assert(relative_rank(us, to) == RANK_6);
1042 assert(piece_on(capsq) == NO_PIECE);
1045 // Restore the captured piece
1046 byTypeBB[ALL_PIECES] |= capsq;
1047 byTypeBB[capture] |= capsq;
1048 byColorBB[them] |= capsq;
1050 board[capsq] = make_piece(them, capture);
1052 // Update piece list, add a new captured piece in capsq square
1053 index[capsq] = pieceCount[them][capture]++;
1054 pieceList[them][capture][index[capsq]] = capsq;
1057 // Finally point our state pointer back to the previous state
1061 assert(pos_is_ok());
1065 /// Position::do_castle() is a helper used to do/undo a castling move. This
1066 /// is a bit tricky, especially in Chess960.
1068 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
1070 Color us = sideToMove;
1071 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
1072 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
1073 byTypeBB[KING] ^= k_from_to_bb;
1074 byTypeBB[ROOK] ^= r_from_to_bb;
1075 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
1076 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1078 // Could be from == to, so first set NO_PIECE then KING and ROOK
1079 board[kfrom] = board[rfrom] = NO_PIECE;
1080 board[kto] = make_piece(us, KING);
1081 board[rto] = make_piece(us, ROOK);
1083 // Could be kfrom == rto, so use a 'tmp' variable
1084 int tmp = index[kfrom];
1085 index[rto] = index[rfrom];
1087 pieceList[us][KING][index[kto]] = kto;
1088 pieceList[us][ROOK][index[rto]] = rto;
1092 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1093 /// the side to move without executing any move on the board.
1095 void Position::do_null_move(StateInfo& newSt) {
1097 assert(!checkers());
1099 memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1101 newSt.previous = st;
1104 if (st->epSquare != SQ_NONE)
1106 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1107 st->epSquare = SQ_NONE;
1110 st->key ^= Zobrist::side;
1111 prefetch((char*)TT.first_entry(st->key));
1114 st->pliesFromNull = 0;
1116 sideToMove = ~sideToMove;
1118 assert(pos_is_ok());
1121 void Position::undo_null_move() {
1123 assert(!checkers());
1126 sideToMove = ~sideToMove;
1130 /// Position::see() is a static exchange evaluator: It tries to estimate the
1131 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1132 /// tempi into account. If the side who initiated the capturing sequence does the
1133 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1134 /// the capturing sequence is considered bad.
1136 int Position::see_sign(Move m) const {
1140 // Early return if SEE cannot be negative because captured piece value
1141 // is not less then capturing one. Note that king moves always return
1142 // here because king midgame value is set to 0.
1143 if (PieceValue[MG][piece_on(to_sq(m))] >= PieceValue[MG][piece_moved(m)])
1149 int Position::see(Move m, int asymmThreshold) const {
1152 Bitboard occupied, attackers, stmAttackers;
1153 int swapList[32], slIndex = 1;
1161 captured = type_of(piece_on(to));
1162 occupied = pieces() ^ from;
1164 // Handle en passant moves
1165 if (type_of(m) == ENPASSANT)
1167 Square capQq = to - pawn_push(sideToMove);
1170 assert(type_of(piece_on(capQq)) == PAWN);
1172 // Remove the captured pawn
1176 else if (type_of(m) == CASTLE)
1177 // Castle moves are implemented as king capturing the rook so cannot be
1178 // handled correctly. Simply return 0 that is always the correct value
1179 // unless the rook is ends up under attack.
1182 // Find all attackers to the destination square, with the moving piece
1183 // removed, but possibly an X-ray attacker added behind it.
1184 attackers = attackers_to(to, occupied);
1186 // If the opponent has no attackers we are finished
1187 stm = ~color_of(piece_on(from));
1188 stmAttackers = attackers & pieces(stm);
1190 return PieceValue[MG][captured];
1192 // The destination square is defended, which makes things rather more
1193 // difficult to compute. We proceed by building up a "swap list" containing
1194 // the material gain or loss at each stop in a sequence of captures to the
1195 // destination square, where the sides alternately capture, and always
1196 // capture with the least valuable piece. After each capture, we look for
1197 // new X-ray attacks from behind the capturing piece.
1198 swapList[0] = PieceValue[MG][captured];
1199 captured = type_of(piece_on(from));
1202 assert(slIndex < 32);
1204 // Add the new entry to the swap list
1205 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1208 // Locate and remove from 'occupied' the next least valuable attacker
1209 captured = next_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1211 attackers &= occupied; // Remove the just found attacker
1213 stmAttackers = attackers & pieces(stm);
1215 if (captured == KING)
1217 // Stop before processing a king capture
1219 swapList[slIndex++] = QueenValueMg * 16;
1224 } while (stmAttackers);
1226 // If we are doing asymmetric SEE evaluation and the same side does the first
1227 // and the last capture, he loses a tempo and gain must be at least worth
1228 // 'asymmThreshold', otherwise we replace the score with a very low value,
1229 // before negamaxing.
1231 for (int i = 0; i < slIndex; i += 2)
1232 if (swapList[i] < asymmThreshold)
1233 swapList[i] = - QueenValueMg * 16;
1235 // Having built the swap list, we negamax through it to find the best
1236 // achievable score from the point of view of the side to move.
1238 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1244 /// Position::clear() erases the position object to a pristine state, with an
1245 /// empty board, white to move, and no castling rights.
1247 void Position::clear() {
1249 memset(this, 0, sizeof(Position));
1250 startState.epSquare = SQ_NONE;
1253 for (int i = 0; i < 8; i++)
1254 for (int j = 0; j < 16; j++)
1255 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1259 /// Position::put_piece() puts a piece on the given square of the board,
1260 /// updating the board array, pieces list, bitboards, and piece counts.
1262 void Position::put_piece(Piece p, Square s) {
1264 Color c = color_of(p);
1265 PieceType pt = type_of(p);
1268 index[s] = pieceCount[c][pt]++;
1269 pieceList[c][pt][index[s]] = s;
1271 byTypeBB[ALL_PIECES] |= s;
1277 /// Position::compute_key() computes the hash key of the position. The hash
1278 /// key is usually updated incrementally as moves are made and unmade, the
1279 /// compute_key() function is only used when a new position is set up, and
1280 /// to verify the correctness of the hash key when running in debug mode.
1282 Key Position::compute_key() const {
1284 Key k = Zobrist::castle[st->castleRights];
1286 for (Bitboard b = pieces(); b; )
1288 Square s = pop_lsb(&b);
1289 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1292 if (ep_square() != SQ_NONE)
1293 k ^= Zobrist::enpassant[file_of(ep_square())];
1295 if (sideToMove == BLACK)
1302 /// Position::compute_pawn_key() computes the hash key of the position. The
1303 /// hash key is usually updated incrementally as moves are made and unmade,
1304 /// the compute_pawn_key() function is only used when a new position is set
1305 /// up, and to verify the correctness of the pawn hash key when running in
1308 Key Position::compute_pawn_key() const {
1312 for (Bitboard b = pieces(PAWN); b; )
1314 Square s = pop_lsb(&b);
1315 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1322 /// Position::compute_material_key() computes the hash key of the position.
1323 /// The hash key is usually updated incrementally as moves are made and unmade,
1324 /// the compute_material_key() function is only used when a new position is set
1325 /// up, and to verify the correctness of the material hash key when running in
1328 Key Position::compute_material_key() const {
1332 for (Color c = WHITE; c <= BLACK; c++)
1333 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1334 for (int cnt = 0; cnt < piece_count(c, pt); cnt++)
1335 k ^= Zobrist::psq[c][pt][cnt];
1341 /// Position::compute_psq_score() computes the incremental scores for the middle
1342 /// game and the endgame. These functions are used to initialize the incremental
1343 /// scores when a new position is set up, and to verify that the scores are correctly
1344 /// updated by do_move and undo_move when the program is running in debug mode.
1345 Score Position::compute_psq_score() const {
1347 Score score = SCORE_ZERO;
1349 for (Bitboard b = pieces(); b; )
1351 Square s = pop_lsb(&b);
1352 Piece pc = piece_on(s);
1353 score += pieceSquareTable[color_of(pc)][type_of(pc)][s];
1360 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1361 /// game material value for the given side. Material values are updated
1362 /// incrementally during the search, this function is only used while
1363 /// initializing a new Position object.
1365 Value Position::compute_non_pawn_material(Color c) const {
1367 Value value = VALUE_ZERO;
1369 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1370 value += piece_count(c, pt) * PieceValue[MG][pt];
1376 /// Position::is_draw() tests whether the position is drawn by material,
1377 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1378 /// must be done by the search.
1379 bool Position::is_draw() const {
1381 // Draw by material?
1383 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1386 // Draw by the 50 moves rule?
1387 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1390 // Draw by repetition?
1391 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1395 StateInfo* stp = st->previous->previous;
1398 stp = stp->previous->previous;
1400 if (stp->key == st->key)
1412 /// Position::flip() flips position with the white and black sides reversed. This
1413 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1415 void Position::flip() {
1417 const Position pos(*this);
1421 sideToMove = ~pos.side_to_move();
1422 thisThread = pos.this_thread();
1423 nodes = pos.nodes_searched();
1424 chess960 = pos.is_chess960();
1425 gamePly = pos.game_ply();
1427 for (Square s = SQ_A1; s <= SQ_H8; s++)
1428 if (!pos.is_empty(s))
1429 put_piece(Piece(pos.piece_on(s) ^ 8), ~s);
1431 if (pos.can_castle(WHITE_OO))
1432 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1433 if (pos.can_castle(WHITE_OOO))
1434 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1435 if (pos.can_castle(BLACK_OO))
1436 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1437 if (pos.can_castle(BLACK_OOO))
1438 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1440 if (pos.st->epSquare != SQ_NONE)
1441 st->epSquare = ~pos.st->epSquare;
1443 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1445 st->key = compute_key();
1446 st->pawnKey = compute_pawn_key();
1447 st->materialKey = compute_material_key();
1448 st->psqScore = compute_psq_score();
1449 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1450 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1452 assert(pos_is_ok());
1456 /// Position::pos_is_ok() performs some consitency checks for the position object.
1457 /// This is meant to be helpful when debugging.
1459 bool Position::pos_is_ok(int* failedStep) const {
1461 int dummy, *step = failedStep ? failedStep : &dummy;
1463 // What features of the position should be verified?
1464 const bool all = false;
1466 const bool debugBitboards = all || false;
1467 const bool debugKingCount = all || false;
1468 const bool debugKingCapture = all || false;
1469 const bool debugCheckerCount = all || false;
1470 const bool debugKey = all || false;
1471 const bool debugMaterialKey = all || false;
1472 const bool debugPawnKey = all || false;
1473 const bool debugIncrementalEval = all || false;
1474 const bool debugNonPawnMaterial = all || false;
1475 const bool debugPieceCounts = all || false;
1476 const bool debugPieceList = all || false;
1477 const bool debugCastleSquares = all || false;
1481 if (sideToMove != WHITE && sideToMove != BLACK)
1484 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1487 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1490 if ((*step)++, debugKingCount)
1492 int kingCount[COLOR_NB] = {};
1494 for (Square s = SQ_A1; s <= SQ_H8; s++)
1495 if (type_of(piece_on(s)) == KING)
1496 kingCount[color_of(piece_on(s))]++;
1498 if (kingCount[0] != 1 || kingCount[1] != 1)
1502 if ((*step)++, debugKingCapture)
1503 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1506 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1509 if ((*step)++, debugBitboards)
1511 // The intersection of the white and black pieces must be empty
1512 if (pieces(WHITE) & pieces(BLACK))
1515 // The union of the white and black pieces must be equal to all
1517 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1520 // Separate piece type bitboards must have empty intersections
1521 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1522 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1523 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1527 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1530 if ((*step)++, debugKey && st->key != compute_key())
1533 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1536 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1539 if ((*step)++, debugIncrementalEval && st->psqScore != compute_psq_score())
1542 if ((*step)++, debugNonPawnMaterial)
1544 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1545 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1549 if ((*step)++, debugPieceCounts)
1550 for (Color c = WHITE; c <= BLACK; c++)
1551 for (PieceType pt = PAWN; pt <= KING; pt++)
1552 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1555 if ((*step)++, debugPieceList)
1556 for (Color c = WHITE; c <= BLACK; c++)
1557 for (PieceType pt = PAWN; pt <= KING; pt++)
1558 for (int i = 0; i < pieceCount[c][pt]; i++)
1560 if (piece_on(piece_list(c, pt)[i]) != make_piece(c, pt))
1563 if (index[piece_list(c, pt)[i]] != i)
1567 if ((*step)++, debugCastleSquares)
1568 for (Color c = WHITE; c <= BLACK; c++)
1569 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1571 CastleRight cr = make_castle_right(c, s);
1573 if (!can_castle(cr))
1576 if ((castleRightsMask[king_square(c)] & cr) != cr)
1579 if ( piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1580 || castleRightsMask[castleRookSquare[c][s]] != cr)