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(Square ksq, Color c, Color toMove) const {
420 Bitboard b, pinners, result = 0;
422 // Pinners are sliders that give check when a pinned piece is removed
423 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
424 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
428 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
430 if (!more_than_one(b))
431 result |= b & pieces(toMove);
437 /// Position::attackers_to() computes a bitboard of all pieces which attack a
438 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
440 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
442 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
443 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
444 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
445 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
446 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
447 | (attacks_from<KING>(s) & pieces(KING));
451 /// Position::legal() tests whether a pseudo-legal move is legal
453 bool Position::legal(Move m, Bitboard pinned) const {
456 assert(pinned == pinned_pieces(sideToMove));
458 Color us = sideToMove;
459 Square from = from_sq(m);
461 assert(color_of(moved_piece(m)) == us);
462 assert(piece_on(king_square(us)) == make_piece(us, KING));
464 // En passant captures are a tricky special case. Because they are rather
465 // uncommon, we do it simply by testing whether the king is attacked after
467 if (type_of(m) == ENPASSANT)
470 Square to = to_sq(m);
471 Square capsq = to + pawn_push(them);
472 Square ksq = king_square(us);
473 Bitboard b = (pieces() ^ from ^ capsq) | to;
475 assert(to == ep_square());
476 assert(moved_piece(m) == make_piece(us, PAWN));
477 assert(piece_on(capsq) == make_piece(them, PAWN));
478 assert(piece_on(to) == NO_PIECE);
480 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
481 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
484 // If the moving piece is a king, check whether the destination
485 // square is attacked by the opponent. Castling moves are checked
486 // for legality during move generation.
487 if (type_of(piece_on(from)) == KING)
488 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
490 // A non-king move is legal if and only if it is not pinned or it
491 // is moving along the ray towards or away from the king.
494 || aligned(from, to_sq(m), king_square(us));
498 /// Position::pseudo_legal() takes a random move and tests whether the move is
499 /// pseudo legal. It is used to validate moves from TT that can be corrupted
500 /// due to SMP concurrent access or hash position key aliasing.
502 bool Position::pseudo_legal(const Move m) const {
504 Color us = sideToMove;
505 Square from = from_sq(m);
506 Square to = to_sq(m);
507 Piece pc = moved_piece(m);
509 // Use a slower but simpler function for uncommon cases
510 if (type_of(m) != NORMAL)
511 return MoveList<LEGAL>(*this).contains(m);
513 // Is not a promotion, so promotion piece must be empty
514 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
517 // If the from square is not occupied by a piece belonging to the side to
518 // move, the move is obviously not legal.
519 if (pc == NO_PIECE || color_of(pc) != us)
522 // The destination square cannot be occupied by a friendly piece
526 // Handle the special case of a pawn move
527 if (type_of(pc) == PAWN)
529 // Move direction must be compatible with pawn color
530 int direction = to - from;
531 if ((us == WHITE) != (direction > 0))
534 // We have already handled promotion moves, so destination
535 // cannot be on the 8th/1st rank.
536 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
539 // Proceed according to the square delta between the origin and
540 // destination squares.
547 // Capture. The destination square must be occupied by an enemy
548 // piece (en passant captures was handled earlier).
549 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
552 // From and to files must be one file apart, avoids a7h5
553 if (abs(file_of(from) - file_of(to)) != 1)
559 // Pawn push. The destination square must be empty.
565 // Double white pawn push. The destination square must be on the fourth
566 // rank, and both the destination square and the square between the
567 // source and destination squares must be empty.
568 if ( rank_of(to) != RANK_4
570 || !empty(from + DELTA_N))
575 // Double black pawn push. The destination square must be on the fifth
576 // rank, and both the destination square and the square between the
577 // source and destination squares must be empty.
578 if ( rank_of(to) != RANK_5
580 || !empty(from + DELTA_S))
588 else if (!(attacks_from(pc, from) & to))
591 // Evasions generator already takes care to avoid some kind of illegal moves
592 // and pl_move_is_legal() relies on this. We therefore have to take care that
593 // the same kind of moves are filtered out here.
596 if (type_of(pc) != KING)
598 // Double check? In this case a king move is required
599 if (more_than_one(checkers()))
602 // Our move must be a blocking evasion or a capture of the checking piece
603 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
606 // In case of king moves under check we have to remove king so to catch
607 // as invalid moves like b1a1 when opposite queen is on c1.
608 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
616 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
618 bool Position::gives_check(Move m, const CheckInfo& ci) const {
621 assert(ci.dcCandidates == discovered_check_candidates());
622 assert(color_of(moved_piece(m)) == sideToMove);
624 Square from = from_sq(m);
625 Square to = to_sq(m);
626 PieceType pt = type_of(piece_on(from));
628 // Is there a direct check ?
629 if (ci.checkSq[pt] & to)
632 // Is there a discovered check ?
633 if ( unlikely(ci.dcCandidates)
634 && (ci.dcCandidates & from)
635 && !aligned(from, to, king_square(~sideToMove)))
638 // Can we skip the ugly special cases ?
639 if (type_of(m) == NORMAL)
642 Color us = sideToMove;
643 Square ksq = king_square(~us);
648 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
650 // En passant capture with check ? We have already handled the case
651 // of direct checks and ordinary discovered check, so the only case we
652 // need to handle is the unusual case of a discovered check through
653 // the captured pawn.
656 Square capsq = file_of(to) | rank_of(from);
657 Bitboard b = (pieces() ^ from ^ capsq) | to;
659 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
660 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
665 Square rfrom = to; // Castling is encoded as 'King captures the rook'
666 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
667 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
669 return (PseudoAttacks[ROOK][rto] & ksq)
670 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
679 /// Position::do_move() makes a move, and saves all information necessary
680 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
681 /// moves should be filtered out before this function is called.
683 void Position::do_move(Move m, StateInfo& newSt) {
686 do_move(m, newSt, ci, gives_check(m, ci));
689 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
692 assert(&newSt != st);
697 // Copy some fields of old state to our new StateInfo object except the ones
698 // which are going to be recalculated from scratch anyway, then switch our state
699 // pointer to point to the new (ready to be updated) state.
700 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
705 // Update side to move
708 // Increment ply counters.In particular rule50 will be reset to zero later on
709 // in case of a capture or a pawn move.
714 Color us = sideToMove;
716 Square from = from_sq(m);
717 Square to = to_sq(m);
718 Piece pc = piece_on(from);
719 PieceType pt = type_of(pc);
720 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
722 assert(color_of(pc) == us);
723 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
724 assert(captured != KING);
726 if (type_of(m) == CASTLING)
728 assert(pc == make_piece(us, KING));
730 bool kingSide = to > from;
731 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
732 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
733 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
734 captured = NO_PIECE_TYPE;
736 do_castling(from, to, rfrom, rto);
738 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
739 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
746 // If the captured piece is a pawn, update pawn hash key, otherwise
747 // update non-pawn material.
748 if (captured == PAWN)
750 if (type_of(m) == ENPASSANT)
752 capsq += pawn_push(them);
755 assert(to == st->epSquare);
756 assert(relative_rank(us, to) == RANK_6);
757 assert(piece_on(to) == NO_PIECE);
758 assert(piece_on(capsq) == make_piece(them, PAWN));
760 board[capsq] = NO_PIECE;
763 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
766 st->npMaterial[them] -= PieceValue[MG][captured];
768 // Update board and piece lists
769 remove_piece(capsq, them, captured);
771 // Update material hash key and prefetch access to materialTable
772 k ^= Zobrist::psq[them][captured][capsq];
773 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
774 prefetch((char*)thisThread->materialTable[st->materialKey]);
776 // Update incremental scores
777 st->psq -= psq[them][captured][capsq];
779 // Reset rule 50 counter
784 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
786 // Reset en passant square
787 if (st->epSquare != SQ_NONE)
789 k ^= Zobrist::enpassant[file_of(st->epSquare)];
790 st->epSquare = SQ_NONE;
793 // Update castling flags if needed
794 if (st->castlingFlags && (castlingFlagsMask[from] | castlingFlagsMask[to]))
796 int cf = castlingFlagsMask[from] | castlingFlagsMask[to];
797 k ^= Zobrist::castling[st->castlingFlags & cf];
798 st->castlingFlags &= ~cf;
801 // Prefetch TT access as soon as we know the new hash key
802 prefetch((char*)TT.first_entry(k));
804 // Move the piece. The tricky Chess960 castling is handled earlier
805 if (type_of(m) != CASTLING)
806 move_piece(from, to, us, pt);
808 // If the moving piece is a pawn do some special extra work
811 // Set en-passant square if the moved pawn can be captured
812 if ( (int(to) ^ int(from)) == 16
813 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
815 st->epSquare = Square((from + to) / 2);
816 k ^= Zobrist::enpassant[file_of(st->epSquare)];
819 if (type_of(m) == PROMOTION)
821 PieceType promotion = promotion_type(m);
823 assert(relative_rank(us, to) == RANK_8);
824 assert(promotion >= KNIGHT && promotion <= QUEEN);
826 remove_piece(to, us, PAWN);
827 put_piece(to, us, promotion);
830 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
831 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
832 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
833 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
835 // Update incremental score
836 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
839 st->npMaterial[us] += PieceValue[MG][promotion];
842 // Update pawn hash key and prefetch access to pawnsTable
843 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
844 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
846 // Reset rule 50 draw counter
850 // Update incremental scores
851 st->psq += psq[us][pt][to] - psq[us][pt][from];
854 st->capturedType = captured;
856 // Update the key with the final value
859 // Update checkers bitboard: piece must be already moved
864 if (type_of(m) != NORMAL)
865 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
869 if (ci.checkSq[pt] & to)
870 st->checkersBB |= to;
873 if (ci.dcCandidates && (ci.dcCandidates & from))
876 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
879 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
884 sideToMove = ~sideToMove;
890 /// Position::undo_move() unmakes a move. When it returns, the position should
891 /// be restored to exactly the same state as before the move was made.
893 void Position::undo_move(Move m) {
897 sideToMove = ~sideToMove;
899 Color us = sideToMove;
901 Square from = from_sq(m);
902 Square to = to_sq(m);
903 PieceType pt = type_of(piece_on(to));
904 PieceType captured = st->capturedType;
906 assert(empty(from) || type_of(m) == CASTLING);
907 assert(captured != KING);
909 if (type_of(m) == PROMOTION)
911 PieceType promotion = promotion_type(m);
913 assert(promotion == pt);
914 assert(relative_rank(us, to) == RANK_8);
915 assert(promotion >= KNIGHT && promotion <= QUEEN);
917 remove_piece(to, us, promotion);
918 put_piece(to, us, PAWN);
922 if (type_of(m) == CASTLING)
924 bool kingSide = to > from;
925 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
926 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
927 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
928 captured = NO_PIECE_TYPE;
930 do_castling(to, from, rto, rfrom);
933 move_piece(to, from, us, pt); // Put the piece back at the source square
939 if (type_of(m) == ENPASSANT)
941 capsq -= pawn_push(us);
944 assert(to == st->previous->epSquare);
945 assert(relative_rank(us, to) == RANK_6);
946 assert(piece_on(capsq) == NO_PIECE);
949 put_piece(capsq, them, captured); // Restore the captured piece
952 // Finally point our state pointer back to the previous state
960 /// Position::do_castling() is a helper used to do/undo a castling move. This
961 /// is a bit tricky, especially in Chess960.
963 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
965 // Remove both pieces first since squares could overlap in Chess960
966 remove_piece(kfrom, sideToMove, KING);
967 remove_piece(rfrom, sideToMove, ROOK);
968 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
969 put_piece(kto, sideToMove, KING);
970 put_piece(rto, sideToMove, ROOK);
974 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
975 /// the side to move without executing any move on the board.
977 void Position::do_null_move(StateInfo& newSt) {
981 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
986 if (st->epSquare != SQ_NONE)
988 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
989 st->epSquare = SQ_NONE;
992 st->key ^= Zobrist::side;
993 prefetch((char*)TT.first_entry(st->key));
996 st->pliesFromNull = 0;
998 sideToMove = ~sideToMove;
1000 assert(pos_is_ok());
1003 void Position::undo_null_move() {
1005 assert(!checkers());
1008 sideToMove = ~sideToMove;
1012 /// Position::see() is a static exchange evaluator: It tries to estimate the
1013 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1014 /// tempi into account. If the side who initiated the capturing sequence does the
1015 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1016 /// the capturing sequence is considered bad.
1018 int Position::see_sign(Move m) const {
1022 // Early return if SEE cannot be negative because captured piece value
1023 // is not less then capturing one. Note that king moves always return
1024 // here because king midgame value is set to 0.
1025 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1031 int Position::see(Move m, int asymmThreshold) const {
1034 Bitboard occupied, attackers, stmAttackers;
1035 int swapList[32], slIndex = 1;
1043 swapList[0] = PieceValue[MG][piece_on(to)];
1044 stm = color_of(piece_on(from));
1045 occupied = pieces() ^ from;
1047 // Castling moves are implemented as king capturing the rook so cannot be
1048 // handled correctly. Simply return 0 that is always the correct value
1049 // unless in the rare case the rook ends up under attack.
1050 if (type_of(m) == CASTLING)
1053 if (type_of(m) == ENPASSANT)
1055 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1056 swapList[0] = PieceValue[MG][PAWN];
1059 // Find all attackers to the destination square, with the moving piece
1060 // removed, but possibly an X-ray attacker added behind it.
1061 attackers = attackers_to(to, occupied) & occupied;
1063 // If the opponent has no attackers we are finished
1065 stmAttackers = attackers & pieces(stm);
1069 // The destination square is defended, which makes things rather more
1070 // difficult to compute. We proceed by building up a "swap list" containing
1071 // the material gain or loss at each stop in a sequence of captures to the
1072 // destination square, where the sides alternately capture, and always
1073 // capture with the least valuable piece. After each capture, we look for
1074 // new X-ray attacks from behind the capturing piece.
1075 captured = type_of(piece_on(from));
1078 assert(slIndex < 32);
1080 // Add the new entry to the swap list
1081 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1084 // Locate and remove the next least valuable attacker
1085 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1087 stmAttackers = attackers & pieces(stm);
1089 // Stop before processing a king capture
1090 if (captured == KING && stmAttackers)
1092 swapList[slIndex++] = QueenValueMg * 16;
1096 } while (stmAttackers);
1098 // If we are doing asymmetric SEE evaluation and the same side does the first
1099 // and the last capture, he loses a tempo and gain must be at least worth
1100 // 'asymmThreshold', otherwise we replace the score with a very low value,
1101 // before negamaxing.
1103 for (int i = 0; i < slIndex; i += 2)
1104 if (swapList[i] < asymmThreshold)
1105 swapList[i] = - QueenValueMg * 16;
1107 // Having built the swap list, we negamax through it to find the best
1108 // achievable score from the point of view of the side to move.
1110 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1116 /// Position::clear() erases the position object to a pristine state, with an
1117 /// empty board, white to move, and no castling rights.
1119 void Position::clear() {
1121 std::memset(this, 0, sizeof(Position));
1122 startState.epSquare = SQ_NONE;
1125 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1126 for (int j = 0; j < 16; ++j)
1127 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1131 /// Position::compute_key() computes the hash key of the position. The hash
1132 /// key is usually updated incrementally as moves are made and unmade. The
1133 /// compute_key() function is only used when a new position is set up, and
1134 /// to verify the correctness of the hash key when running in debug mode.
1136 Key Position::compute_key() const {
1138 Key k = Zobrist::castling[st->castlingFlags];
1140 for (Bitboard b = pieces(); b; )
1142 Square s = pop_lsb(&b);
1143 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1146 if (ep_square() != SQ_NONE)
1147 k ^= Zobrist::enpassant[file_of(ep_square())];
1149 if (sideToMove == BLACK)
1156 /// Position::compute_pawn_key() computes the hash key of the position. The
1157 /// hash key is usually updated incrementally as moves are made and unmade.
1158 /// The compute_pawn_key() function is only used when a new position is set
1159 /// up, and to verify the correctness of the pawn hash key when running in
1162 Key Position::compute_pawn_key() const {
1166 for (Bitboard b = pieces(PAWN); b; )
1168 Square s = pop_lsb(&b);
1169 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1176 /// Position::compute_material_key() computes the hash key of the position.
1177 /// The hash key is usually updated incrementally as moves are made and unmade.
1178 /// The compute_material_key() function is only used when a new position is set
1179 /// up, and to verify the correctness of the material hash key when running in
1182 Key Position::compute_material_key() const {
1186 for (Color c = WHITE; c <= BLACK; ++c)
1187 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1188 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1189 k ^= Zobrist::psq[c][pt][cnt];
1195 /// Position::compute_psq_score() computes the incremental scores for the middle
1196 /// game and the endgame. These functions are used to initialize the incremental
1197 /// scores when a new position is set up, and to verify that the scores are correctly
1198 /// updated by do_move and undo_move when the program is running in debug mode.
1200 Score Position::compute_psq_score() const {
1202 Score score = SCORE_ZERO;
1204 for (Bitboard b = pieces(); b; )
1206 Square s = pop_lsb(&b);
1207 Piece pc = piece_on(s);
1208 score += psq[color_of(pc)][type_of(pc)][s];
1215 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1216 /// game material value for the given side. Material values are updated
1217 /// incrementally during the search. This function is only used when
1218 /// initializing a new Position object.
1220 Value Position::compute_non_pawn_material(Color c) const {
1222 Value value = VALUE_ZERO;
1224 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1225 value += pieceCount[c][pt] * PieceValue[MG][pt];
1231 /// Position::is_draw() tests whether the position is drawn by material,
1232 /// repetition, or the 50 moves rule. It does not detect stalemates: this
1233 /// must be done by the search.
1234 bool Position::is_draw() const {
1236 // Draw by material?
1238 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1241 // Draw by the 50 moves rule?
1242 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1245 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1249 StateInfo* stp = st->previous->previous;
1252 stp = stp->previous->previous;
1254 if (stp->key == st->key)
1255 return true; // Draw after first repetition
1266 /// Position::flip() flips position with the white and black sides reversed. This
1267 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1269 static char toggle_case(char c) {
1270 return char(islower(c) ? toupper(c) : tolower(c));
1273 void Position::flip() {
1276 std::stringstream ss(fen());
1278 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1280 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1281 f.insert(0, token + (f.empty() ? " " : "/"));
1284 ss >> token; // Active color
1285 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1287 ss >> token; // Castling availability
1290 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1292 ss >> token; // En passant square
1293 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1295 std::getline(ss, token); // Half and full moves
1298 set(f, is_chess960(), this_thread());
1300 assert(pos_is_ok());
1304 /// Position::pos_is_ok() performs some consistency checks for the position object.
1305 /// This is meant to be helpful when debugging.
1307 bool Position::pos_is_ok(int* failedStep) const {
1309 int dummy, *step = failedStep ? failedStep : &dummy;
1311 // What features of the position should be verified?
1312 const bool all = false;
1314 const bool debugBitboards = all || false;
1315 const bool debugKingCount = all || false;
1316 const bool debugKingCapture = all || false;
1317 const bool debugCheckerCount = all || false;
1318 const bool debugKey = all || false;
1319 const bool debugMaterialKey = all || false;
1320 const bool debugPawnKey = all || false;
1321 const bool debugIncrementalEval = all || false;
1322 const bool debugNonPawnMaterial = all || false;
1323 const bool debugPieceCounts = all || false;
1324 const bool debugPieceList = all || false;
1325 const bool debugCastlingSquares = all || false;
1329 if (sideToMove != WHITE && sideToMove != BLACK)
1332 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1335 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1338 if ((*step)++, debugKingCount)
1340 int kingCount[COLOR_NB] = {};
1342 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1343 if (type_of(piece_on(s)) == KING)
1344 ++kingCount[color_of(piece_on(s))];
1346 if (kingCount[0] != 1 || kingCount[1] != 1)
1350 if ((*step)++, debugKingCapture)
1351 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1354 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1357 if ((*step)++, debugBitboards)
1359 // The intersection of the white and black pieces must be empty
1360 if (pieces(WHITE) & pieces(BLACK))
1363 // The union of the white and black pieces must be equal to all
1365 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1368 // Separate piece type bitboards must have empty intersections
1369 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1370 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1371 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1375 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1378 if ((*step)++, debugKey && st->key != compute_key())
1381 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1384 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1387 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1390 if ((*step)++, debugNonPawnMaterial)
1391 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1392 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1395 if ((*step)++, debugPieceCounts)
1396 for (Color c = WHITE; c <= BLACK; ++c)
1397 for (PieceType pt = PAWN; pt <= KING; ++pt)
1398 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1401 if ((*step)++, debugPieceList)
1402 for (Color c = WHITE; c <= BLACK; ++c)
1403 for (PieceType pt = PAWN; pt <= KING; ++pt)
1404 for (int i = 0; i < pieceCount[c][pt]; ++i)
1405 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1406 || index[pieceList[c][pt][i]] != i)
1409 if ((*step)++, debugCastlingSquares)
1410 for (Color c = WHITE; c <= BLACK; ++c)
1411 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1413 CastlingFlag cf = make_castling_flag(c, s);
1415 if (!can_castle(cf))
1418 if ( (castlingFlagsMask[king_square(c)] & cf) != cf
1419 || piece_on(castlingRookSquare[c][s]) != make_piece(c, ROOK)
1420 || castlingFlagsMask[castlingRookSquare[c][s]] != cf)