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-2014 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 Value PieceValue[PHASE_NB][PIECE_NB] = {
42 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
43 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
45 static Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
49 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
50 Key enpassant[FILE_NB];
51 Key castling[CASTLING_RIGHT_NB];
56 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
60 // min_attacker() is a helper function used by see() to locate the least
61 // valuable attacker for the side to move, remove the attacker we just found
62 // from the bitboards and scan for new X-ray attacks behind it.
64 template<int Pt> FORCE_INLINE
65 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
66 Bitboard& occupied, Bitboard& attackers) {
68 Bitboard b = stmAttackers & bb[Pt];
70 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
72 occupied ^= b & ~(b - 1);
74 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
75 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
77 if (Pt == ROOK || Pt == QUEEN)
78 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
80 attackers &= occupied; // After X-ray that may add already processed pieces
84 template<> FORCE_INLINE
85 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
86 return KING; // No need to update bitboards: it is the last cycle
94 CheckInfo::CheckInfo(const Position& pos) {
96 Color them = ~pos.side_to_move();
97 ksq = pos.king_square(them);
99 pinned = pos.pinned_pieces(pos.side_to_move());
100 dcCandidates = pos.discovered_check_candidates();
102 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
103 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
104 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
105 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
106 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
111 /// Position::init() initializes at startup the various arrays used to compute
112 /// hash keys and the piece square tables. The latter is a two-step operation:
113 /// Firstly, the white halves of the tables are copied from PSQT[] tables.
114 /// Secondly, the black halves of the tables are initialized by flipping and
115 /// changing the sign of the white scores.
117 void Position::init() {
121 for (Color c = WHITE; c <= BLACK; ++c)
122 for (PieceType pt = PAWN; pt <= KING; ++pt)
123 for (Square s = SQ_A1; s <= SQ_H8; ++s)
124 Zobrist::psq[c][pt][s] = rk.rand<Key>();
126 for (File f = FILE_A; f <= FILE_H; ++f)
127 Zobrist::enpassant[f] = rk.rand<Key>();
129 for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf)
134 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
135 Zobrist::castling[cf] ^= k ? k : rk.rand<Key>();
139 Zobrist::side = rk.rand<Key>();
140 Zobrist::exclusion = rk.rand<Key>();
142 for (PieceType pt = PAWN; pt <= KING; ++pt)
144 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
145 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
147 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
149 for (Square s = SQ_A1; s <= SQ_H8; ++s)
151 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
152 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
158 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
159 /// object to not depend on any external data so we detach state pointer from
162 Position& Position::operator=(const Position& pos) {
164 std::memcpy(this, &pos, sizeof(Position));
175 /// Position::set() initializes the position object with the given FEN string.
176 /// This function is not very robust - make sure that input FENs are correct,
177 /// this is assumed to be the responsibility of the GUI.
179 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
181 A FEN string defines a particular position using only the ASCII character set.
183 A FEN string contains six fields separated by a space. The fields are:
185 1) Piece placement (from white's perspective). Each rank is described, starting
186 with rank 8 and ending with rank 1. Within each rank, the contents of each
187 square are described from file A through file H. Following the Standard
188 Algebraic Notation (SAN), each piece is identified by a single letter taken
189 from the standard English names. White pieces are designated using upper-case
190 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
191 noted using digits 1 through 8 (the number of blank squares), and "/"
194 2) Active color. "w" means white moves next, "b" means black.
196 3) Castling availability. If neither side can castle, this is "-". Otherwise,
197 this has one or more letters: "K" (White can castle kingside), "Q" (White
198 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
199 can castle queenside).
201 4) En passant target square (in algebraic notation). If there's no en passant
202 target square, this is "-". If a pawn has just made a 2-square move, this
203 is the position "behind" the pawn. This is recorded regardless of whether
204 there is a pawn in position to make an en passant capture.
206 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
207 or capture. This is used to determine if a draw can be claimed under the
210 6) Fullmove number. The number of the full move. It starts at 1, and is
211 incremented after Black's move.
214 char col, row, token;
217 std::istringstream ss(fenStr);
222 // 1. Piece placement
223 while ((ss >> token) && !isspace(token))
226 sq += Square(token - '0'); // Advance the given number of files
228 else if (token == '/')
231 else if ((idx = PieceToChar.find(token)) != string::npos)
233 put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx)));
240 sideToMove = (token == 'w' ? WHITE : BLACK);
243 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
244 // Shredder-FEN that uses the letters of the columns on which the rooks began
245 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
246 // if an inner rook is associated with the castling right, the castling tag is
247 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
248 while ((ss >> token) && !isspace(token))
251 Color c = islower(token) ? BLACK : WHITE;
253 token = char(toupper(token));
256 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {}
258 else if (token == 'Q')
259 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {}
261 else if (token >= 'A' && token <= 'H')
262 rsq = File(token - 'A') | relative_rank(c, RANK_1);
267 set_castling_right(c, rsq);
270 // 4. En passant square. Ignore if no pawn capture is possible
271 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
272 && ((ss >> row) && (row == '3' || row == '6')))
274 st->epSquare = File(col - 'a') | Rank(row - '1');
276 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
277 st->epSquare = SQ_NONE;
280 // 5-6. Halfmove clock and fullmove number
281 ss >> std::skipws >> st->rule50 >> gamePly;
283 // Convert from fullmove starting from 1 to ply starting from 0,
284 // handle also common incorrect FEN with fullmove = 0.
285 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
287 st->key = compute_key();
288 st->pawnKey = compute_pawn_key();
289 st->materialKey = compute_material_key();
290 st->psq = compute_psq_score();
291 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
292 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
293 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
294 chess960 = isChess960;
301 /// Position::set_castling_right() is a helper function used to set castling
302 /// rights given the corresponding color and the rook starting square.
304 void Position::set_castling_right(Color c, Square rfrom) {
306 Square kfrom = king_square(c);
307 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
308 CastlingRight cr = (c | cs);
310 st->castlingRights |= cr;
311 castlingRightsMask[kfrom] |= cr;
312 castlingRightsMask[rfrom] |= cr;
313 castlingRookSquare[cr] = rfrom;
315 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
316 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
318 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
319 if (s != kfrom && s != rfrom)
320 castlingPath[cr] |= s;
322 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
323 if (s != kfrom && s != rfrom)
324 castlingPath[cr] |= s;
328 /// Position::fen() returns a FEN representation of the position. In case of
329 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
331 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 for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file)
347 ss << PieceToChar[piece_on(file | rank)];
354 ss << (sideToMove == WHITE ? " w " : " b ");
356 if (can_castle(WHITE_OO))
357 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | KING_SIDE)), false) : 'K');
359 if (can_castle(WHITE_OOO))
360 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | QUEEN_SIDE)), false) : 'Q');
362 if (can_castle(BLACK_OO))
363 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | KING_SIDE)), true) : 'k');
365 if (can_castle(BLACK_OOO))
366 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | QUEEN_SIDE)), true) : 'q');
368 if (!can_castle(WHITE) && !can_castle(BLACK))
371 ss << (ep_square() == SQ_NONE ? " - " : " " + to_string(ep_square()) + " ")
372 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
378 /// Position::pretty() returns an ASCII representation of the position to be
379 /// printed to the standard output together with the move's san notation.
381 const string Position::pretty(Move move) const {
383 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
384 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
385 + dottedLine + "\n| . | | . | | . | | . | |";
387 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
389 for (Bitboard b = pieces(); b; )
391 Square s = pop_lsb(&b);
392 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
395 std::ostringstream ss;
398 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
399 << move_to_san(*const_cast<Position*>(this), move);
401 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
402 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
404 for (Bitboard b = checkers(); b; )
405 ss << to_string(pop_lsb(&b)) << " ";
407 ss << "\nLegal moves: ";
408 for (MoveList<LEGAL> it(*this); *it; ++it)
409 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
415 /// Position::check_blockers() returns a bitboard of all the pieces with color
416 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
417 /// blocks a check if removing that piece from the board would result in a
418 /// position where the king is in check. A check blocking piece can be either a
419 /// pinned or a discovered check piece, according if its color 'c' is the same
420 /// or the opposite of 'kingColor'.
422 Bitboard Position::check_blockers(Color c, Color kingColor) const {
424 Bitboard b, pinners, result = 0;
425 Square ksq = king_square(kingColor);
427 // Pinners are sliders that give check when a pinned piece is removed
428 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
429 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
433 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
435 if (!more_than_one(b))
436 result |= b & pieces(c);
442 /// Position::attackers_to() computes a bitboard of all pieces which attack a
443 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
445 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
447 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
448 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
449 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
450 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
451 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
452 | (attacks_from<KING>(s) & pieces(KING));
456 /// Position::legal() tests whether a pseudo-legal move is legal
458 bool Position::legal(Move m, Bitboard pinned) const {
461 assert(pinned == pinned_pieces(sideToMove));
463 Color us = sideToMove;
464 Square from = from_sq(m);
466 assert(color_of(moved_piece(m)) == us);
467 assert(piece_on(king_square(us)) == make_piece(us, KING));
469 // En passant captures are a tricky special case. Because they are rather
470 // uncommon, we do it simply by testing whether the king is attacked after
472 if (type_of(m) == ENPASSANT)
475 Square to = to_sq(m);
476 Square capsq = to + pawn_push(them);
477 Square ksq = king_square(us);
478 Bitboard b = (pieces() ^ from ^ capsq) | to;
480 assert(to == ep_square());
481 assert(moved_piece(m) == make_piece(us, PAWN));
482 assert(piece_on(capsq) == make_piece(them, PAWN));
483 assert(piece_on(to) == NO_PIECE);
485 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
486 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
489 // If the moving piece is a king, check whether the destination
490 // square is attacked by the opponent. Castling moves are checked
491 // for legality during move generation.
492 if (type_of(piece_on(from)) == KING)
493 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
495 // A non-king move is legal if and only if it is not pinned or it
496 // is moving along the ray towards or away from the king.
499 || aligned(from, to_sq(m), king_square(us));
503 /// Position::pseudo_legal() takes a random move and tests whether the move is
504 /// pseudo legal. It is used to validate moves from TT that can be corrupted
505 /// due to SMP concurrent access or hash position key aliasing.
507 bool Position::pseudo_legal(const Move m) const {
509 Color us = sideToMove;
510 Square from = from_sq(m);
511 Square to = to_sq(m);
512 Piece pc = moved_piece(m);
514 // Use a slower but simpler function for uncommon cases
515 if (type_of(m) != NORMAL)
516 return MoveList<LEGAL>(*this).contains(m);
518 // Is not a promotion, so promotion piece must be empty
519 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
522 // If the 'from' square is not occupied by a piece belonging to the side to
523 // move, the move is obviously not legal.
524 if (pc == NO_PIECE || color_of(pc) != us)
527 // The destination square cannot be occupied by a friendly piece
531 // Handle the special case of a pawn move
532 if (type_of(pc) == PAWN)
534 // We have already handled promotion moves, so destination
535 // cannot be on the 8th/1st rank.
536 if (rank_of(to) == relative_rank(us, RANK_8))
539 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
541 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
543 && !( (from + 2 * pawn_push(us) == to) // Not a double push
544 && (rank_of(from) == relative_rank(us, RANK_2))
546 && empty(to - pawn_push(us))))
549 else if (!(attacks_from(pc, from) & to))
552 // Evasions generator already takes care to avoid some kind of illegal moves
553 // and legal() relies on this. We therefore have to take care that the same
554 // kind of moves are filtered out here.
557 if (type_of(pc) != KING)
559 // Double check? In this case a king move is required
560 if (more_than_one(checkers()))
563 // Our move must be a blocking evasion or a capture of the checking piece
564 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
567 // In case of king moves under check we have to remove king so as to catch
568 // invalid moves like b1a1 when opposite queen is on c1.
569 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
577 /// Position::gives_check() tests whether a pseudo-legal move gives a check
579 bool Position::gives_check(Move m, const CheckInfo& ci) const {
582 assert(ci.dcCandidates == discovered_check_candidates());
583 assert(color_of(moved_piece(m)) == sideToMove);
585 Square from = from_sq(m);
586 Square to = to_sq(m);
587 PieceType pt = type_of(piece_on(from));
589 // Is there a direct check?
590 if (ci.checkSq[pt] & to)
593 // Is there a discovered check?
594 if ( unlikely(ci.dcCandidates)
595 && (ci.dcCandidates & from)
596 && !aligned(from, to, ci.ksq))
599 // Can we skip the ugly special cases?
600 if (type_of(m) == NORMAL)
606 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
608 // En passant capture with check? We have already handled the case
609 // of direct checks and ordinary discovered check, so the only case we
610 // need to handle is the unusual case of a discovered check through
611 // the captured pawn.
614 Square capsq = file_of(to) | rank_of(from);
615 Bitboard b = (pieces() ^ from ^ capsq) | to;
617 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
618 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
623 Square rfrom = to; // Castling is encoded as 'King captures the rook'
624 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
625 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
627 return (PseudoAttacks[ROOK][rto] & ci.ksq)
628 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
637 /// Position::do_move() makes a move, and saves all information necessary
638 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
639 /// moves should be filtered out before this function is called.
641 void Position::do_move(Move m, StateInfo& newSt) {
644 do_move(m, newSt, ci, gives_check(m, ci));
647 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
650 assert(&newSt != st);
655 // Copy some fields of the old state to our new StateInfo object except the
656 // ones which are going to be recalculated from scratch anyway and then switch
657 // our state pointer to point to the new (ready to be updated) state.
658 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
663 // Update side to move
666 // Increment ply counters. In particular, rule50 will be reset to zero later on
667 // in case of a capture or a pawn move.
672 Color us = sideToMove;
674 Square from = from_sq(m);
675 Square to = to_sq(m);
676 Piece pc = piece_on(from);
677 PieceType pt = type_of(pc);
678 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
680 assert(color_of(pc) == us);
681 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
682 assert(captured != KING);
684 if (type_of(m) == CASTLING)
686 assert(pc == make_piece(us, KING));
688 bool kingSide = to > from;
689 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
690 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
691 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
692 captured = NO_PIECE_TYPE;
694 do_castling(from, to, rfrom, rto);
696 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
697 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
704 // If the captured piece is a pawn, update pawn hash key, otherwise
705 // update non-pawn material.
706 if (captured == PAWN)
708 if (type_of(m) == ENPASSANT)
710 capsq += pawn_push(them);
713 assert(to == st->epSquare);
714 assert(relative_rank(us, to) == RANK_6);
715 assert(piece_on(to) == NO_PIECE);
716 assert(piece_on(capsq) == make_piece(them, PAWN));
718 board[capsq] = NO_PIECE;
721 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
724 st->npMaterial[them] -= PieceValue[MG][captured];
726 // Update board and piece lists
727 remove_piece(capsq, them, captured);
729 // Update material hash key and prefetch access to materialTable
730 k ^= Zobrist::psq[them][captured][capsq];
731 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
732 prefetch((char*)thisThread->materialTable[st->materialKey]);
734 // Update incremental scores
735 st->psq -= psq[them][captured][capsq];
737 // Reset rule 50 counter
742 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
744 // Reset en passant square
745 if (st->epSquare != SQ_NONE)
747 k ^= Zobrist::enpassant[file_of(st->epSquare)];
748 st->epSquare = SQ_NONE;
751 // Update castling rights if needed
752 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
754 int cr = castlingRightsMask[from] | castlingRightsMask[to];
755 k ^= Zobrist::castling[st->castlingRights & cr];
756 st->castlingRights &= ~cr;
759 // Prefetch TT access as soon as we know the new hash key
760 prefetch((char*)TT.first_entry(k));
762 // Move the piece. The tricky Chess960 castling is handled earlier
763 if (type_of(m) != CASTLING)
764 move_piece(from, to, us, pt);
766 // If the moving piece is a pawn do some special extra work
769 // Set en-passant square if the moved pawn can be captured
770 if ( (int(to) ^ int(from)) == 16
771 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
773 st->epSquare = Square((from + to) / 2);
774 k ^= Zobrist::enpassant[file_of(st->epSquare)];
777 if (type_of(m) == PROMOTION)
779 PieceType promotion = promotion_type(m);
781 assert(relative_rank(us, to) == RANK_8);
782 assert(promotion >= KNIGHT && promotion <= QUEEN);
784 remove_piece(to, us, PAWN);
785 put_piece(to, us, promotion);
788 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
789 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
790 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
791 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
793 // Update incremental score
794 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
797 st->npMaterial[us] += PieceValue[MG][promotion];
800 // Update pawn hash key and prefetch access to pawnsTable
801 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
802 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
804 // Reset rule 50 draw counter
808 // Update incremental scores
809 st->psq += psq[us][pt][to] - psq[us][pt][from];
812 st->capturedType = captured;
814 // Update the key with the final value
817 // Update checkers bitboard: piece must be already moved
822 if (type_of(m) != NORMAL)
823 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
827 if (ci.checkSq[pt] & to)
828 st->checkersBB |= to;
831 if (ci.dcCandidates && (ci.dcCandidates & from))
834 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
837 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
842 sideToMove = ~sideToMove;
848 /// Position::undo_move() unmakes a move. When it returns, the position should
849 /// be restored to exactly the same state as before the move was made.
851 void Position::undo_move(Move m) {
855 sideToMove = ~sideToMove;
857 Color us = sideToMove;
859 Square from = from_sq(m);
860 Square to = to_sq(m);
861 PieceType pt = type_of(piece_on(to));
862 PieceType captured = st->capturedType;
864 assert(empty(from) || type_of(m) == CASTLING);
865 assert(captured != KING);
867 if (type_of(m) == PROMOTION)
869 PieceType promotion = promotion_type(m);
871 assert(promotion == pt);
872 assert(relative_rank(us, to) == RANK_8);
873 assert(promotion >= KNIGHT && promotion <= QUEEN);
875 remove_piece(to, us, promotion);
876 put_piece(to, us, PAWN);
880 if (type_of(m) == CASTLING)
882 bool kingSide = to > from;
883 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
884 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
885 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
886 captured = NO_PIECE_TYPE;
888 do_castling(to, from, rto, rfrom);
891 move_piece(to, from, us, pt); // Put the piece back at the source square
897 if (type_of(m) == ENPASSANT)
899 capsq -= pawn_push(us);
902 assert(to == st->previous->epSquare);
903 assert(relative_rank(us, to) == RANK_6);
904 assert(piece_on(capsq) == NO_PIECE);
907 put_piece(capsq, them, captured); // Restore the captured piece
910 // Finally point our state pointer back to the previous state
918 /// Position::do_castling() is a helper used to do/undo a castling move. This
919 /// is a bit tricky, especially in Chess960.
921 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
923 // Remove both pieces first since squares could overlap in Chess960
924 remove_piece(kfrom, sideToMove, KING);
925 remove_piece(rfrom, sideToMove, ROOK);
926 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
927 put_piece(kto, sideToMove, KING);
928 put_piece(rto, sideToMove, ROOK);
932 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
933 /// the side to move without executing any move on the board.
935 void Position::do_null_move(StateInfo& newSt) {
939 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
944 if (st->epSquare != SQ_NONE)
946 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
947 st->epSquare = SQ_NONE;
950 st->key ^= Zobrist::side;
951 prefetch((char*)TT.first_entry(st->key));
954 st->pliesFromNull = 0;
956 sideToMove = ~sideToMove;
961 void Position::undo_null_move() {
966 sideToMove = ~sideToMove;
970 /// Position::see() is a static exchange evaluator: It tries to estimate the
971 /// material gain or loss resulting from a move.
973 Value Position::see_sign(Move m) const {
977 // Early return if SEE cannot be negative because captured piece value
978 // is not less then capturing one. Note that king moves always return
979 // here because king midgame value is set to 0.
980 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
981 return VALUE_KNOWN_WIN;
986 Value Position::see(Move m) const {
989 Bitboard occupied, attackers, stmAttackers;
999 swapList[0] = PieceValue[MG][piece_on(to)];
1000 stm = color_of(piece_on(from));
1001 occupied = pieces() ^ from;
1003 // Castling moves are implemented as king capturing the rook so cannot be
1004 // handled correctly. Simply return 0 that is always the correct value
1005 // unless in the rare case the rook ends up under attack.
1006 if (type_of(m) == CASTLING)
1009 if (type_of(m) == ENPASSANT)
1011 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1012 swapList[0] = PieceValue[MG][PAWN];
1015 // Find all attackers to the destination square, with the moving piece
1016 // removed, but possibly an X-ray attacker added behind it.
1017 attackers = attackers_to(to, occupied) & occupied;
1019 // If the opponent has no attackers we are finished
1021 stmAttackers = attackers & pieces(stm);
1025 // The destination square is defended, which makes things rather more
1026 // difficult to compute. We proceed by building up a "swap list" containing
1027 // the material gain or loss at each stop in a sequence of captures to the
1028 // destination square, where the sides alternately capture, and always
1029 // capture with the least valuable piece. After each capture, we look for
1030 // new X-ray attacks from behind the capturing piece.
1031 captured = type_of(piece_on(from));
1034 assert(slIndex < 32);
1036 // Add the new entry to the swap list
1037 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1039 // Locate and remove the next least valuable attacker
1040 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1042 // Stop before processing a king capture
1043 if (captured == KING)
1045 if (stmAttackers == attackers)
1052 stmAttackers = attackers & pieces(stm);
1055 } while (stmAttackers);
1057 // Having built the swap list, we negamax through it to find the best
1058 // achievable score from the point of view of the side to move.
1060 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1066 /// Position::clear() erases the position object to a pristine state, with an
1067 /// empty board, white to move, and no castling rights.
1069 void Position::clear() {
1071 std::memset(this, 0, sizeof(Position));
1072 startState.epSquare = SQ_NONE;
1075 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1076 for (int j = 0; j < 16; ++j)
1077 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1081 /// Position::compute_key() computes the hash key of the position. The hash
1082 /// key is usually updated incrementally as moves are made and unmade. The
1083 /// compute_key() function is only used when a new position is set up, and
1084 /// to verify the correctness of the hash key when running in debug mode.
1086 Key Position::compute_key() const {
1088 Key k = Zobrist::castling[st->castlingRights];
1090 for (Bitboard b = pieces(); b; )
1092 Square s = pop_lsb(&b);
1093 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1096 if (ep_square() != SQ_NONE)
1097 k ^= Zobrist::enpassant[file_of(ep_square())];
1099 if (sideToMove == BLACK)
1106 /// Position::compute_pawn_key() computes the hash key of the position. The
1107 /// hash key is usually updated incrementally as moves are made and unmade.
1108 /// The compute_pawn_key() function is only used when a new position is set
1109 /// up, and to verify the correctness of the pawn hash key when running in
1112 Key Position::compute_pawn_key() const {
1116 for (Bitboard b = pieces(PAWN); b; )
1118 Square s = pop_lsb(&b);
1119 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1126 /// Position::compute_material_key() computes the hash key of the position.
1127 /// The hash key is usually updated incrementally as moves are made and unmade.
1128 /// The compute_material_key() function is only used when a new position is set
1129 /// up, and to verify the correctness of the material hash key when running in
1132 Key Position::compute_material_key() const {
1136 for (Color c = WHITE; c <= BLACK; ++c)
1137 for (PieceType pt = PAWN; pt <= KING; ++pt)
1138 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1139 k ^= Zobrist::psq[c][pt][cnt];
1145 /// Position::compute_psq_score() computes the incremental scores for the middlegame
1146 /// and the endgame. These functions are used to initialize the incremental scores
1147 /// when a new position is set up, and to verify that the scores are correctly
1148 /// updated by do_move and undo_move when the program is running in debug mode.
1150 Score Position::compute_psq_score() const {
1152 Score score = SCORE_ZERO;
1154 for (Bitboard b = pieces(); b; )
1156 Square s = pop_lsb(&b);
1157 Piece pc = piece_on(s);
1158 score += psq[color_of(pc)][type_of(pc)][s];
1165 /// Position::compute_non_pawn_material() computes the total non-pawn middlegame
1166 /// material value for the given side. Material values are updated incrementally
1167 /// during the search. This function is only used when initializing a new Position
1170 Value Position::compute_non_pawn_material(Color c) const {
1172 Value value = VALUE_ZERO;
1174 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1175 value += pieceCount[c][pt] * PieceValue[MG][pt];
1181 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1182 /// rule or repetition. It does not detect stalemates.
1184 bool Position::is_draw() const {
1187 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1190 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1193 StateInfo* stp = st;
1194 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1196 stp = stp->previous->previous;
1198 if (stp->key == st->key)
1199 return true; // Draw at first repetition
1206 /// Position::flip() flips position with the white and black sides reversed. This
1207 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1209 static char toggle_case(char c) {
1210 return char(islower(c) ? toupper(c) : tolower(c));
1213 void Position::flip() {
1216 std::stringstream ss(fen());
1218 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1220 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1221 f.insert(0, token + (f.empty() ? " " : "/"));
1224 ss >> token; // Active color
1225 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1227 ss >> token; // Castling availability
1230 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1232 ss >> token; // En passant square
1233 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1235 std::getline(ss, token); // Half and full moves
1238 set(f, is_chess960(), this_thread());
1240 assert(pos_is_ok());
1244 /// Position::pos_is_ok() performs some consistency checks for the position object.
1245 /// This is meant to be helpful when debugging.
1247 bool Position::pos_is_ok(int* failedStep) const {
1249 int dummy, *step = failedStep ? failedStep : &dummy;
1251 // What features of the position should be verified?
1252 const bool all = false;
1254 const bool debugBitboards = all || false;
1255 const bool debugKingCount = all || false;
1256 const bool debugKingCapture = all || false;
1257 const bool debugCheckerCount = all || false;
1258 const bool debugKey = all || false;
1259 const bool debugMaterialKey = all || false;
1260 const bool debugPawnKey = all || false;
1261 const bool debugIncrementalEval = all || false;
1262 const bool debugNonPawnMaterial = all || false;
1263 const bool debugPieceCounts = all || false;
1264 const bool debugPieceList = all || false;
1265 const bool debugCastlingSquares = all || false;
1269 if (sideToMove != WHITE && sideToMove != BLACK)
1272 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1275 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1278 if ((*step)++, debugKingCount)
1280 int kingCount[COLOR_NB] = {};
1282 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1283 if (type_of(piece_on(s)) == KING)
1284 ++kingCount[color_of(piece_on(s))];
1286 if (kingCount[0] != 1 || kingCount[1] != 1)
1290 if ((*step)++, debugKingCapture)
1291 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1294 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1297 if ((*step)++, debugBitboards)
1299 // The intersection of the white and black pieces must be empty
1300 if (pieces(WHITE) & pieces(BLACK))
1303 // The union of the white and black pieces must be equal to all
1305 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1308 // Separate piece type bitboards must have empty intersections
1309 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1310 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1311 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1315 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1318 if ((*step)++, debugKey && st->key != compute_key())
1321 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1324 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1327 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1330 if ((*step)++, debugNonPawnMaterial)
1331 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1332 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1335 if ((*step)++, debugPieceCounts)
1336 for (Color c = WHITE; c <= BLACK; ++c)
1337 for (PieceType pt = PAWN; pt <= KING; ++pt)
1338 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1341 if ((*step)++, debugPieceList)
1342 for (Color c = WHITE; c <= BLACK; ++c)
1343 for (PieceType pt = PAWN; pt <= KING; ++pt)
1344 for (int i = 0; i < pieceCount[c][pt]; ++i)
1345 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1346 || index[pieceList[c][pt][i]] != i)
1349 if ((*step)++, debugCastlingSquares)
1350 for (Color c = WHITE; c <= BLACK; ++c)
1351 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1353 if (!can_castle(c | s))
1356 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1357 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1358 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))