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/>.
37 static const string PieceToChar(" PNBRQK pnbrqk");
41 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
42 Value PieceValue[PHASE_NB][PIECE_NB] = {
43 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
44 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
48 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
49 Key enpassant[FILE_NB];
50 Key castling[CASTLING_FLAG_NB];
55 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
59 // min_attacker() is a helper function used by see() to locate the least
60 // valuable attacker for the side to move, remove the attacker we just found
61 // from the bitboards and scan for new X-ray attacks behind it.
63 template<int Pt> FORCE_INLINE
64 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
65 Bitboard& occupied, Bitboard& attackers) {
67 Bitboard b = stmAttackers & bb[Pt];
69 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
71 occupied ^= b & ~(b - 1);
73 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
74 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
76 if (Pt == ROOK || Pt == QUEEN)
77 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
79 attackers &= occupied; // After X-ray that may add already processed pieces
83 template<> FORCE_INLINE
84 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
85 return KING; // No need to update bitboards: it is the last cycle
93 CheckInfo::CheckInfo(const Position& pos) {
95 Color them = ~pos.side_to_move();
96 ksq = pos.king_square(them);
98 pinned = pos.pinned_pieces(pos.side_to_move());
99 dcCandidates = pos.discovered_check_candidates();
101 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
102 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
103 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
104 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
105 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
110 /// Position::init() initializes at startup the various arrays used to compute
111 /// hash keys and the piece square tables. The latter is a two-step operation:
112 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
113 /// Secondly, the black halves of the tables are initialized by flipping and
114 /// changing the sign of the white scores.
116 void Position::init() {
120 for (Color c = WHITE; c <= BLACK; ++c)
121 for (PieceType pt = PAWN; pt <= KING; ++pt)
122 for (Square s = SQ_A1; s <= SQ_H8; ++s)
123 Zobrist::psq[c][pt][s] = rk.rand<Key>();
125 for (File f = FILE_A; f <= FILE_H; ++f)
126 Zobrist::enpassant[f] = rk.rand<Key>();
128 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
133 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
134 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
138 Zobrist::side = rk.rand<Key>();
139 Zobrist::exclusion = rk.rand<Key>();
141 for (PieceType pt = PAWN; pt <= KING; ++pt)
143 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
144 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
146 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
148 for (Square s = SQ_A1; s <= SQ_H8; ++s)
150 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
151 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
157 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
158 /// object to not depend on any external data so we detach state pointer from
161 Position& Position::operator=(const Position& pos) {
163 std::memcpy(this, &pos, sizeof(Position));
174 /// Position::set() initializes the position object with the given FEN string.
175 /// This function is not very robust - make sure that input FENs are correct,
176 /// this is assumed to be the responsibility of the GUI.
178 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
180 A FEN string defines a particular position using only the ASCII character set.
182 A FEN string contains six fields separated by a space. The fields are:
184 1) Piece placement (from white's perspective). Each rank is described, starting
185 with rank 8 and ending with rank 1. Within each rank, the contents of each
186 square are described from file A through file H. Following the Standard
187 Algebraic Notation (SAN), each piece is identified by a single letter taken
188 from the standard English names. White pieces are designated using upper-case
189 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
190 noted using digits 1 through 8 (the number of blank squares), and "/"
193 2) Active color. "w" means white moves next, "b" means black.
195 3) Castling availability. If neither side can castle, this is "-". Otherwise,
196 this has one or more letters: "K" (White can castle kingside), "Q" (White
197 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
198 can castle queenside).
200 4) En passant target square (in algebraic notation). If there's no en passant
201 target square, this is "-". If a pawn has just made a 2-square move, this
202 is the position "behind" the pawn. This is recorded regardless of whether
203 there is a pawn in position to make an en passant capture.
205 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
206 or capture. This is used to determine if a draw can be claimed under the
209 6) Fullmove number. The number of the full move. It starts at 1, and is
210 incremented after Black's move.
213 char col, row, token;
216 std::istringstream ss(fenStr);
221 // 1. Piece placement
222 while ((ss >> token) && !isspace(token))
225 sq += Square(token - '0'); // Advance the given number of files
227 else if (token == '/')
230 else if ((idx = PieceToChar.find(token)) != string::npos)
232 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
239 sideToMove = (token == 'w' ? WHITE : BLACK);
242 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
243 // Shredder-FEN that uses the letters of the columns on which the rooks began
244 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
245 // if an inner rook is associated with the castling right, the castling tag is
246 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
247 while ((ss >> token) && !isspace(token))
250 Color c = islower(token) ? BLACK : WHITE;
252 token = char(toupper(token));
255 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
257 else if (token == 'Q')
258 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
260 else if (token >= 'A' && token <= 'H')
261 rsq = File(token - 'A') | relative_rank(c, RANK_1);
266 set_castling_flag(c, rsq);
269 // 4. En passant square. Ignore if no pawn capture is possible
270 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
271 && ((ss >> row) && (row == '3' || row == '6')))
273 st->epSquare = File(col - 'a') | Rank(row - '1');
275 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
276 st->epSquare = SQ_NONE;
279 // 5-6. Halfmove clock and fullmove number
280 ss >> std::skipws >> st->rule50 >> gamePly;
282 // Convert from fullmove starting from 1 to ply starting from 0,
283 // handle also common incorrect FEN with fullmove = 0.
284 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
286 st->key = compute_key();
287 st->pawnKey = compute_pawn_key();
288 st->materialKey = compute_material_key();
289 st->psq = compute_psq_score();
290 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
291 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
292 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
293 chess960 = isChess960;
300 /// Position::set_castling_flag() is a helper function used to set castling
301 /// flags given the corresponding color and the rook starting square.
303 void Position::set_castling_flag(Color c, Square rfrom) {
305 Square kfrom = king_square(c);
306 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
307 CastlingFlag cf = make_castling_flag(c, cs);
309 st->castlingFlags |= cf;
310 castlingFlagsMask[kfrom] |= cf;
311 castlingFlagsMask[rfrom] |= cf;
312 castlingRookSquare[c][cs] = rfrom;
314 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
315 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
317 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
318 if (s != kfrom && s != rfrom)
319 castlingPath[c][cs] |= s;
321 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
322 if (s != kfrom && s != rfrom)
323 castlingPath[c][cs] |= s;
327 /// Position::fen() returns a FEN representation of the position. In case of
328 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
330 const string Position::fen() const {
333 std::ostringstream ss;
335 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
337 for (File file = FILE_A; file <= FILE_H; ++file)
339 for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file)
346 ss << PieceToChar[piece_on(file | rank)];
353 ss << (sideToMove == WHITE ? " w " : " b ");
355 if (can_castle(WHITE_OO))
356 ss << (chess960 ? file_to_char(file_of(castling_rook_square(WHITE, KING_SIDE)), false) : 'K');
358 if (can_castle(WHITE_OOO))
359 ss << (chess960 ? file_to_char(file_of(castling_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
361 if (can_castle(BLACK_OO))
362 ss << (chess960 ? file_to_char(file_of(castling_rook_square(BLACK, KING_SIDE)), true) : 'k');
364 if (can_castle(BLACK_OOO))
365 ss << (chess960 ? file_to_char(file_of(castling_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
367 if (!can_castle(WHITE) && !can_castle(BLACK))
370 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
371 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
377 /// Position::pretty() returns an ASCII representation of the position to be
378 /// printed to the standard output together with the move's san notation.
380 const string Position::pretty(Move move) const {
382 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
383 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
384 + dottedLine + "\n| . | | . | | . | | . | |";
386 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
388 for (Bitboard b = pieces(); b; )
390 Square s = pop_lsb(&b);
391 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
394 std::ostringstream ss;
397 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
398 << move_to_san(*const_cast<Position*>(this), move);
400 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
401 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
403 for (Bitboard b = checkers(); b; )
404 ss << square_to_string(pop_lsb(&b)) << " ";
406 ss << "\nLegal moves: ";
407 for (MoveList<LEGAL> it(*this); *it; ++it)
408 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
414 /// Position:hidden_checkers() returns a bitboard of all pinned / discovered check
415 /// pieces, according to the call parameters. Pinned pieces protect our king and
416 /// discovered check pieces attack the enemy king.
418 Bitboard Position::hidden_checkers(Color c, Color kingColor) const {
420 Bitboard b, pinners, result = 0;
421 Square ksq = king_square(kingColor);
423 // Pinners are sliders that give check when a pinned piece is removed
424 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
425 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
429 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
431 if (!more_than_one(b))
432 result |= b & pieces(c);
438 /// Position::attackers_to() computes a bitboard of all pieces which attack a
439 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
441 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
443 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
444 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
445 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
446 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
447 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
448 | (attacks_from<KING>(s) & pieces(KING));
452 /// Position::legal() tests whether a pseudo-legal move is legal
454 bool Position::legal(Move m, Bitboard pinned) const {
457 assert(pinned == pinned_pieces(sideToMove));
459 Color us = sideToMove;
460 Square from = from_sq(m);
462 assert(color_of(moved_piece(m)) == us);
463 assert(piece_on(king_square(us)) == make_piece(us, KING));
465 // En passant captures are a tricky special case. Because they are rather
466 // uncommon, we do it simply by testing whether the king is attacked after
468 if (type_of(m) == ENPASSANT)
471 Square to = to_sq(m);
472 Square capsq = to + pawn_push(them);
473 Square ksq = king_square(us);
474 Bitboard b = (pieces() ^ from ^ capsq) | to;
476 assert(to == ep_square());
477 assert(moved_piece(m) == make_piece(us, PAWN));
478 assert(piece_on(capsq) == make_piece(them, PAWN));
479 assert(piece_on(to) == NO_PIECE);
481 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
482 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
485 // If the moving piece is a king, check whether the destination
486 // square is attacked by the opponent. Castling moves are checked
487 // for legality during move generation.
488 if (type_of(piece_on(from)) == KING)
489 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
491 // A non-king move is legal if and only if it is not pinned or it
492 // is moving along the ray towards or away from the king.
495 || aligned(from, to_sq(m), king_square(us));
499 /// Position::pseudo_legal() takes a random move and tests whether the move is
500 /// pseudo legal. It is used to validate moves from TT that can be corrupted
501 /// due to SMP concurrent access or hash position key aliasing.
503 bool Position::pseudo_legal(const Move m) const {
505 Color us = sideToMove;
506 Square from = from_sq(m);
507 Square to = to_sq(m);
508 Piece pc = moved_piece(m);
510 // Use a slower but simpler function for uncommon cases
511 if (type_of(m) != NORMAL)
512 return MoveList<LEGAL>(*this).contains(m);
514 // Is not a promotion, so promotion piece must be empty
515 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
518 // If the from square is not occupied by a piece belonging to the side to
519 // move, the move is obviously not legal.
520 if (pc == NO_PIECE || color_of(pc) != us)
523 // The destination square cannot be occupied by a friendly piece
527 // Handle the special case of a pawn move
528 if (type_of(pc) == PAWN)
530 // Move direction must be compatible with pawn color
531 int direction = to - from;
532 if ((us == WHITE) != (direction > 0))
535 // We have already handled promotion moves, so destination
536 // cannot be on the 8th/1st rank.
537 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
540 // Proceed according to the square delta between the origin and
541 // destination squares.
548 // Capture. The destination square must be occupied by an enemy
549 // piece (en passant captures was handled earlier).
550 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
553 // From and to files must be one file apart, avoids a7h5
554 if (abs(file_of(from) - file_of(to)) != 1)
560 // Pawn push. The destination square must be empty.
566 // Double white pawn push. The destination square must be on the fourth
567 // rank, and both the destination square and the square between the
568 // source and destination squares must be empty.
569 if ( rank_of(to) != RANK_4
571 || !empty(from + DELTA_N))
576 // Double black pawn push. The destination square must be on the fifth
577 // rank, and both the destination square and the square between the
578 // source and destination squares must be empty.
579 if ( rank_of(to) != RANK_5
581 || !empty(from + DELTA_S))
589 else if (!(attacks_from(pc, from) & to))
592 // Evasions generator already takes care to avoid some kind of illegal moves
593 // and pl_move_is_legal() relies on this. We therefore have to take care that
594 // the same kind of moves are filtered out here.
597 if (type_of(pc) != KING)
599 // Double check? In this case a king move is required
600 if (more_than_one(checkers()))
603 // Our move must be a blocking evasion or a capture of the checking piece
604 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
607 // In case of king moves under check we have to remove king so to catch
608 // as invalid moves like b1a1 when opposite queen is on c1.
609 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
617 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
619 bool Position::gives_check(Move m, const CheckInfo& ci) const {
622 assert(ci.dcCandidates == discovered_check_candidates());
623 assert(color_of(moved_piece(m)) == sideToMove);
625 Square from = from_sq(m);
626 Square to = to_sq(m);
627 PieceType pt = type_of(piece_on(from));
629 // Is there a direct check ?
630 if (ci.checkSq[pt] & to)
633 // Is there a discovered check ?
634 if ( unlikely(ci.dcCandidates)
635 && (ci.dcCandidates & from)
636 && !aligned(from, to, king_square(~sideToMove)))
639 // Can we skip the ugly special cases ?
640 if (type_of(m) == NORMAL)
643 Color us = sideToMove;
644 Square ksq = king_square(~us);
649 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
651 // En passant capture with check ? We have already handled the case
652 // of direct checks and ordinary discovered check, so the only case we
653 // need to handle is the unusual case of a discovered check through
654 // the captured pawn.
657 Square capsq = file_of(to) | rank_of(from);
658 Bitboard b = (pieces() ^ from ^ capsq) | to;
660 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
661 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
666 Square rfrom = to; // Castling is encoded as 'King captures the rook'
667 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
668 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
670 return (PseudoAttacks[ROOK][rto] & ksq)
671 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
680 /// Position::do_move() makes a move, and saves all information necessary
681 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
682 /// moves should be filtered out before this function is called.
684 void Position::do_move(Move m, StateInfo& newSt) {
687 do_move(m, newSt, ci, gives_check(m, ci));
690 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
693 assert(&newSt != st);
698 // Copy some fields of old state to our new StateInfo object except the ones
699 // which are going to be recalculated from scratch anyway, then switch our state
700 // pointer to point to the new (ready to be updated) state.
701 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
706 // Update side to move
709 // Increment ply counters.In particular rule50 will be reset to zero later on
710 // in case of a capture or a pawn move.
715 Color us = sideToMove;
717 Square from = from_sq(m);
718 Square to = to_sq(m);
719 Piece pc = piece_on(from);
720 PieceType pt = type_of(pc);
721 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
723 assert(color_of(pc) == us);
724 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
725 assert(captured != KING);
727 if (type_of(m) == CASTLING)
729 assert(pc == make_piece(us, KING));
731 bool kingSide = to > from;
732 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
733 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
734 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
735 captured = NO_PIECE_TYPE;
737 do_castling(from, to, rfrom, rto);
739 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
740 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
747 // If the captured piece is a pawn, update pawn hash key, otherwise
748 // update non-pawn material.
749 if (captured == PAWN)
751 if (type_of(m) == ENPASSANT)
753 capsq += pawn_push(them);
756 assert(to == st->epSquare);
757 assert(relative_rank(us, to) == RANK_6);
758 assert(piece_on(to) == NO_PIECE);
759 assert(piece_on(capsq) == make_piece(them, PAWN));
761 board[capsq] = NO_PIECE;
764 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
767 st->npMaterial[them] -= PieceValue[MG][captured];
769 // Update board and piece lists
770 remove_piece(capsq, them, captured);
772 // Update material hash key and prefetch access to materialTable
773 k ^= Zobrist::psq[them][captured][capsq];
774 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
775 prefetch((char*)thisThread->materialTable[st->materialKey]);
777 // Update incremental scores
778 st->psq -= psq[them][captured][capsq];
780 // Reset rule 50 counter
785 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
787 // Reset en passant square
788 if (st->epSquare != SQ_NONE)
790 k ^= Zobrist::enpassant[file_of(st->epSquare)];
791 st->epSquare = SQ_NONE;
794 // Update castling flags if needed
795 if (st->castlingFlags && (castlingFlagsMask[from] | castlingFlagsMask[to]))
797 int cf = castlingFlagsMask[from] | castlingFlagsMask[to];
798 k ^= Zobrist::castling[st->castlingFlags & cf];
799 st->castlingFlags &= ~cf;
802 // Prefetch TT access as soon as we know the new hash key
803 prefetch((char*)TT.first_entry(k));
805 // Move the piece. The tricky Chess960 castling is handled earlier
806 if (type_of(m) != CASTLING)
807 move_piece(from, to, us, pt);
809 // If the moving piece is a pawn do some special extra work
812 // Set en-passant square if the moved pawn can be captured
813 if ( (int(to) ^ int(from)) == 16
814 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
816 st->epSquare = Square((from + to) / 2);
817 k ^= Zobrist::enpassant[file_of(st->epSquare)];
820 if (type_of(m) == PROMOTION)
822 PieceType promotion = promotion_type(m);
824 assert(relative_rank(us, to) == RANK_8);
825 assert(promotion >= KNIGHT && promotion <= QUEEN);
827 remove_piece(to, us, PAWN);
828 put_piece(to, us, promotion);
831 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
832 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
833 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
834 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
836 // Update incremental score
837 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
840 st->npMaterial[us] += PieceValue[MG][promotion];
843 // Update pawn hash key and prefetch access to pawnsTable
844 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
845 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
847 // Reset rule 50 draw counter
851 // Update incremental scores
852 st->psq += psq[us][pt][to] - psq[us][pt][from];
855 st->capturedType = captured;
857 // Update the key with the final value
860 // Update checkers bitboard: piece must be already moved
865 if (type_of(m) != NORMAL)
866 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
870 if (ci.checkSq[pt] & to)
871 st->checkersBB |= to;
874 if (ci.dcCandidates && (ci.dcCandidates & from))
877 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
880 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
885 sideToMove = ~sideToMove;
891 /// Position::undo_move() unmakes a move. When it returns, the position should
892 /// be restored to exactly the same state as before the move was made.
894 void Position::undo_move(Move m) {
898 sideToMove = ~sideToMove;
900 Color us = sideToMove;
902 Square from = from_sq(m);
903 Square to = to_sq(m);
904 PieceType pt = type_of(piece_on(to));
905 PieceType captured = st->capturedType;
907 assert(empty(from) || type_of(m) == CASTLING);
908 assert(captured != KING);
910 if (type_of(m) == PROMOTION)
912 PieceType promotion = promotion_type(m);
914 assert(promotion == pt);
915 assert(relative_rank(us, to) == RANK_8);
916 assert(promotion >= KNIGHT && promotion <= QUEEN);
918 remove_piece(to, us, promotion);
919 put_piece(to, us, PAWN);
923 if (type_of(m) == CASTLING)
925 bool kingSide = to > from;
926 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
927 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
928 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
929 captured = NO_PIECE_TYPE;
931 do_castling(to, from, rto, rfrom);
934 move_piece(to, from, us, pt); // Put the piece back at the source square
940 if (type_of(m) == ENPASSANT)
942 capsq -= pawn_push(us);
945 assert(to == st->previous->epSquare);
946 assert(relative_rank(us, to) == RANK_6);
947 assert(piece_on(capsq) == NO_PIECE);
950 put_piece(capsq, them, captured); // Restore the captured piece
953 // Finally point our state pointer back to the previous state
961 /// Position::do_castling() is a helper used to do/undo a castling move. This
962 /// is a bit tricky, especially in Chess960.
964 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
966 // Remove both pieces first since squares could overlap in Chess960
967 remove_piece(kfrom, sideToMove, KING);
968 remove_piece(rfrom, sideToMove, ROOK);
969 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
970 put_piece(kto, sideToMove, KING);
971 put_piece(rto, sideToMove, ROOK);
975 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
976 /// the side to move without executing any move on the board.
978 void Position::do_null_move(StateInfo& newSt) {
982 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
987 if (st->epSquare != SQ_NONE)
989 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
990 st->epSquare = SQ_NONE;
993 st->key ^= Zobrist::side;
994 prefetch((char*)TT.first_entry(st->key));
997 st->pliesFromNull = 0;
999 sideToMove = ~sideToMove;
1001 assert(pos_is_ok());
1004 void Position::undo_null_move() {
1006 assert(!checkers());
1009 sideToMove = ~sideToMove;
1013 /// Position::see() is a static exchange evaluator: It tries to estimate the
1014 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1015 /// tempi into account. If the side who initiated the capturing sequence does the
1016 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1017 /// the capturing sequence is considered bad.
1019 int Position::see_sign(Move m) const {
1023 // Early return if SEE cannot be negative because captured piece value
1024 // is not less then capturing one. Note that king moves always return
1025 // here because king midgame value is set to 0.
1026 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1032 int Position::see(Move m, int asymmThreshold) const {
1035 Bitboard occupied, attackers, stmAttackers;
1036 int swapList[32], slIndex = 1;
1044 swapList[0] = PieceValue[MG][piece_on(to)];
1045 stm = color_of(piece_on(from));
1046 occupied = pieces() ^ from;
1048 // Castling moves are implemented as king capturing the rook so cannot be
1049 // handled correctly. Simply return 0 that is always the correct value
1050 // unless in the rare case the rook ends up under attack.
1051 if (type_of(m) == CASTLING)
1054 if (type_of(m) == ENPASSANT)
1056 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1057 swapList[0] = PieceValue[MG][PAWN];
1060 // Find all attackers to the destination square, with the moving piece
1061 // removed, but possibly an X-ray attacker added behind it.
1062 attackers = attackers_to(to, occupied) & occupied;
1064 // If the opponent has no attackers we are finished
1066 stmAttackers = attackers & pieces(stm);
1070 // The destination square is defended, which makes things rather more
1071 // difficult to compute. We proceed by building up a "swap list" containing
1072 // the material gain or loss at each stop in a sequence of captures to the
1073 // destination square, where the sides alternately capture, and always
1074 // capture with the least valuable piece. After each capture, we look for
1075 // new X-ray attacks from behind the capturing piece.
1076 captured = type_of(piece_on(from));
1079 assert(slIndex < 32);
1081 // Add the new entry to the swap list
1082 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1085 // Locate and remove the next least valuable attacker
1086 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1088 stmAttackers = attackers & pieces(stm);
1090 // Stop before processing a king capture
1091 if (captured == KING && stmAttackers)
1093 swapList[slIndex++] = QueenValueMg * 16;
1097 } while (stmAttackers);
1099 // If we are doing asymmetric SEE evaluation and the same side does the first
1100 // and the last capture, he loses a tempo and gain must be at least worth
1101 // 'asymmThreshold', otherwise we replace the score with a very low value,
1102 // before negamaxing.
1104 for (int i = 0; i < slIndex; i += 2)
1105 if (swapList[i] < asymmThreshold)
1106 swapList[i] = - QueenValueMg * 16;
1108 // Having built the swap list, we negamax through it to find the best
1109 // achievable score from the point of view of the side to move.
1111 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1117 /// Position::clear() erases the position object to a pristine state, with an
1118 /// empty board, white to move, and no castling rights.
1120 void Position::clear() {
1122 std::memset(this, 0, sizeof(Position));
1123 startState.epSquare = SQ_NONE;
1126 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1127 for (int j = 0; j < 16; ++j)
1128 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1132 /// Position::compute_key() computes the hash key of the position. The hash
1133 /// key is usually updated incrementally as moves are made and unmade. The
1134 /// compute_key() function is only used when a new position is set up, and
1135 /// to verify the correctness of the hash key when running in debug mode.
1137 Key Position::compute_key() const {
1139 Key k = Zobrist::castling[st->castlingFlags];
1141 for (Bitboard b = pieces(); b; )
1143 Square s = pop_lsb(&b);
1144 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1147 if (ep_square() != SQ_NONE)
1148 k ^= Zobrist::enpassant[file_of(ep_square())];
1150 if (sideToMove == BLACK)
1157 /// Position::compute_pawn_key() computes the hash key of the position. The
1158 /// hash key is usually updated incrementally as moves are made and unmade.
1159 /// The compute_pawn_key() function is only used when a new position is set
1160 /// up, and to verify the correctness of the pawn hash key when running in
1163 Key Position::compute_pawn_key() const {
1167 for (Bitboard b = pieces(PAWN); b; )
1169 Square s = pop_lsb(&b);
1170 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1177 /// Position::compute_material_key() computes the hash key of the position.
1178 /// The hash key is usually updated incrementally as moves are made and unmade.
1179 /// The compute_material_key() function is only used when a new position is set
1180 /// up, and to verify the correctness of the material hash key when running in
1183 Key Position::compute_material_key() const {
1187 for (Color c = WHITE; c <= BLACK; ++c)
1188 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1189 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1190 k ^= Zobrist::psq[c][pt][cnt];
1196 /// Position::compute_psq_score() computes the incremental scores for the middle
1197 /// game and the endgame. These functions are used to initialize the incremental
1198 /// scores when a new position is set up, and to verify that the scores are correctly
1199 /// updated by do_move and undo_move when the program is running in debug mode.
1201 Score Position::compute_psq_score() const {
1203 Score score = SCORE_ZERO;
1205 for (Bitboard b = pieces(); b; )
1207 Square s = pop_lsb(&b);
1208 Piece pc = piece_on(s);
1209 score += psq[color_of(pc)][type_of(pc)][s];
1216 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1217 /// game material value for the given side. Material values are updated
1218 /// incrementally during the search. This function is only used when
1219 /// initializing a new Position object.
1221 Value Position::compute_non_pawn_material(Color c) const {
1223 Value value = VALUE_ZERO;
1225 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1226 value += pieceCount[c][pt] * PieceValue[MG][pt];
1232 /// Position::is_draw() tests whether the position is drawn by material,
1233 /// repetition, or the 50 moves rule. It does not detect stalemates: this
1234 /// must be done by the search.
1235 bool Position::is_draw() const {
1237 // Draw by material?
1239 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1242 // Draw by the 50 moves rule?
1243 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1246 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1250 StateInfo* stp = st->previous->previous;
1253 stp = stp->previous->previous;
1255 if (stp->key == st->key)
1256 return true; // Draw after first repetition
1267 /// Position::flip() flips position with the white and black sides reversed. This
1268 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1270 static char toggle_case(char c) {
1271 return char(islower(c) ? toupper(c) : tolower(c));
1274 void Position::flip() {
1277 std::stringstream ss(fen());
1279 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1281 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1282 f.insert(0, token + (f.empty() ? " " : "/"));
1285 ss >> token; // Active color
1286 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1288 ss >> token; // Castling availability
1291 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1293 ss >> token; // En passant square
1294 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1296 std::getline(ss, token); // Half and full moves
1299 set(f, is_chess960(), this_thread());
1301 assert(pos_is_ok());
1305 /// Position::pos_is_ok() performs some consistency checks for the position object.
1306 /// This is meant to be helpful when debugging.
1308 bool Position::pos_is_ok(int* failedStep) const {
1310 int dummy, *step = failedStep ? failedStep : &dummy;
1312 // What features of the position should be verified?
1313 const bool all = false;
1315 const bool debugBitboards = all || false;
1316 const bool debugKingCount = all || false;
1317 const bool debugKingCapture = all || false;
1318 const bool debugCheckerCount = all || false;
1319 const bool debugKey = all || false;
1320 const bool debugMaterialKey = all || false;
1321 const bool debugPawnKey = all || false;
1322 const bool debugIncrementalEval = all || false;
1323 const bool debugNonPawnMaterial = all || false;
1324 const bool debugPieceCounts = all || false;
1325 const bool debugPieceList = all || false;
1326 const bool debugCastlingSquares = all || false;
1330 if (sideToMove != WHITE && sideToMove != BLACK)
1333 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1336 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1339 if ((*step)++, debugKingCount)
1341 int kingCount[COLOR_NB] = {};
1343 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1344 if (type_of(piece_on(s)) == KING)
1345 ++kingCount[color_of(piece_on(s))];
1347 if (kingCount[0] != 1 || kingCount[1] != 1)
1351 if ((*step)++, debugKingCapture)
1352 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1355 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1358 if ((*step)++, debugBitboards)
1360 // The intersection of the white and black pieces must be empty
1361 if (pieces(WHITE) & pieces(BLACK))
1364 // The union of the white and black pieces must be equal to all
1366 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1369 // Separate piece type bitboards must have empty intersections
1370 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1371 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1372 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1376 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1379 if ((*step)++, debugKey && st->key != compute_key())
1382 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1385 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1388 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1391 if ((*step)++, debugNonPawnMaterial)
1392 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1393 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1396 if ((*step)++, debugPieceCounts)
1397 for (Color c = WHITE; c <= BLACK; ++c)
1398 for (PieceType pt = PAWN; pt <= KING; ++pt)
1399 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1402 if ((*step)++, debugPieceList)
1403 for (Color c = WHITE; c <= BLACK; ++c)
1404 for (PieceType pt = PAWN; pt <= KING; ++pt)
1405 for (int i = 0; i < pieceCount[c][pt]; ++i)
1406 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1407 || index[pieceList[c][pt][i]] != i)
1410 if ((*step)++, debugCastlingSquares)
1411 for (Color c = WHITE; c <= BLACK; ++c)
1412 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1414 CastlingFlag cf = make_castling_flag(c, s);
1416 if (!can_castle(cf))
1419 if ( (castlingFlagsMask[king_square(c)] & cf) != cf
1420 || piece_on(castlingRookSquare[c][s]) != make_piece(c, ROOK)
1421 || castlingFlagsMask[castlingRookSquare[c][s]] != cf)