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 castle[CASTLE_RIGHT_NB];
55 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
59 // min_attacker() is an 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 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
113 /// the black halves of the tables are initialized by flipping and changing the
114 /// 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 cr = CASTLES_NONE; cr <= ALL_CASTLES; ++cr)
133 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
134 Zobrist::castle[cr] ^= 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 do 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") while Black take 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 ((p = PieceToChar.find(token)) != string::npos)
232 put_piece(sq, color_of(Piece(p)), type_of(Piece(p)));
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_castle_right(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_castle_right() is an helper function used to set castling
301 /// rights given the corresponding color and the rook starting square.
303 void Position::set_castle_right(Color c, Square rfrom) {
305 Square kfrom = king_square(c);
306 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
307 CastleRight cr = make_castle_right(c, cs);
309 st->castleRights |= cr;
310 castleRightsMask[kfrom] |= cr;
311 castleRightsMask[rfrom] |= cr;
312 castleRookSquare[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 castlePath[c][cs] |= s;
321 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
322 if (s != kfrom && s != rfrom)
323 castlePath[c][cs] |= s;
327 /// Position::fen() returns a FEN representation of the position. In case
328 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
330 const string Position::fen() const {
332 std::ostringstream ss;
334 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
336 for (File file = FILE_A; file <= FILE_H; ++file)
338 Square sq = file | rank;
344 for ( ; file < FILE_H && empty(++sq); ++file)
350 ss << PieceToChar[piece_on(sq)];
357 ss << (sideToMove == WHITE ? " w " : " b ");
359 if (can_castle(WHITE_OO))
360 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
362 if (can_castle(WHITE_OOO))
363 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
365 if (can_castle(BLACK_OO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
368 if (can_castle(BLACK_OOO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
371 if (st->castleRights == CASTLES_NONE)
374 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
375 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
381 /// Position::pretty() returns an ASCII representation of the position to be
382 /// printed to the standard output together with the move's san notation.
384 const string Position::pretty(Move move) const {
386 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
387 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
388 + dottedLine + "\n| . | | . | | . | | . | |";
390 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
392 for (Bitboard b = pieces(); b; )
394 Square s = pop_lsb(&b);
395 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
398 std::ostringstream ss;
401 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
402 << move_to_san(*const_cast<Position*>(this), move);
404 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
405 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
407 for (Bitboard b = checkers(); b; )
408 ss << square_to_string(pop_lsb(&b)) << " ";
410 ss << "\nLegal moves: ";
411 for (MoveList<LEGAL> it(*this); *it; ++it)
412 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
418 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
419 /// pieces, according to the call parameters. Pinned pieces protect our king,
420 /// discovery check pieces attack the enemy king.
422 Bitboard Position::hidden_checkers(Square ksq, Color c, Color toMove) const {
424 Bitboard b, pinners, result = 0;
426 // Pinners are sliders that give check when pinned piece is removed
427 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
428 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
432 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
434 if (!more_than_one(b))
435 result |= b & pieces(toMove);
441 /// Position::attackers_to() computes a bitboard of all pieces which attack a
442 /// given square. Slider attacks use occ bitboard as occupancy.
444 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
446 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
447 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
448 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
449 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
450 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
451 | (attacks_from<KING>(s) & pieces(KING));
455 /// Position::legal() tests whether a pseudo-legal move is legal
457 bool Position::legal(Move m, Bitboard pinned) const {
460 assert(pinned == pinned_pieces(sideToMove));
462 Color us = sideToMove;
463 Square from = from_sq(m);
465 assert(color_of(moved_piece(m)) == us);
466 assert(piece_on(king_square(us)) == make_piece(us, KING));
468 // En passant captures are a tricky special case. Because they are rather
469 // uncommon, we do it simply by testing whether the king is attacked after
471 if (type_of(m) == ENPASSANT)
474 Square to = to_sq(m);
475 Square capsq = to + pawn_push(them);
476 Square ksq = king_square(us);
477 Bitboard b = (pieces() ^ from ^ capsq) | to;
479 assert(to == ep_square());
480 assert(moved_piece(m) == make_piece(us, PAWN));
481 assert(piece_on(capsq) == make_piece(them, PAWN));
482 assert(piece_on(to) == NO_PIECE);
484 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
485 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
488 // If the moving piece is a king, check whether the destination
489 // square is attacked by the opponent. Castling moves are checked
490 // for legality during move generation.
491 if (type_of(piece_on(from)) == KING)
492 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
494 // A non-king move is legal if and only if it is not pinned or it
495 // is moving along the ray towards or away from the king.
498 || aligned(from, to_sq(m), king_square(us));
502 /// Position::pseudo_legal() takes a random move and tests whether the move is
503 /// pseudo legal. It is used to validate moves from TT that can be corrupted
504 /// due to SMP concurrent access or hash position key aliasing.
506 bool Position::pseudo_legal(const Move m) const {
508 Color us = sideToMove;
509 Square from = from_sq(m);
510 Square to = to_sq(m);
511 Piece pc = moved_piece(m);
513 // Use a slower but simpler function for uncommon cases
514 if (type_of(m) != NORMAL)
515 return MoveList<LEGAL>(*this).contains(m);
517 // Is not a promotion, so promotion piece must be empty
518 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
521 // If the from square is not occupied by a piece belonging to the side to
522 // move, the move is obviously not legal.
523 if (pc == NO_PIECE || color_of(pc) != us)
526 // The destination square cannot be occupied by a friendly piece
530 // Handle the special case of a pawn move
531 if (type_of(pc) == PAWN)
533 // Move direction must be compatible with pawn color
534 int direction = to - from;
535 if ((us == WHITE) != (direction > 0))
538 // We have already handled promotion moves, so destination
539 // cannot be on the 8/1th rank.
540 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
543 // Proceed according to the square delta between the origin and
544 // destination squares.
551 // Capture. The destination square must be occupied by an enemy
552 // piece (en passant captures was handled earlier).
553 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
556 // From and to files must be one file apart, avoids a7h5
557 if (abs(file_of(from) - file_of(to)) != 1)
563 // Pawn push. The destination square must be empty.
569 // Double white pawn push. The destination square must be on the fourth
570 // rank, and both the destination square and the square between the
571 // source and destination squares must be empty.
572 if ( rank_of(to) != RANK_4
574 || !empty(from + DELTA_N))
579 // Double black pawn push. The destination square must be on the fifth
580 // rank, and both the destination square and the square between the
581 // source and destination squares must be empty.
582 if ( rank_of(to) != RANK_5
584 || !empty(from + DELTA_S))
592 else if (!(attacks_from(pc, from) & to))
595 // Evasions generator already takes care to avoid some kind of illegal moves
596 // and pl_move_is_legal() relies on this. So we have to take care that the
597 // same kind of moves are filtered out here.
600 if (type_of(pc) != KING)
602 // Double check? In this case a king move is required
603 if (more_than_one(checkers()))
606 // Our move must be a blocking evasion or a capture of the checking piece
607 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
610 // In case of king moves under check we have to remove king so to catch
611 // as invalid moves like b1a1 when opposite queen is on c1.
612 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
620 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
622 bool Position::gives_check(Move m, const CheckInfo& ci) const {
625 assert(ci.dcCandidates == discovered_check_candidates());
626 assert(color_of(moved_piece(m)) == sideToMove);
628 Square from = from_sq(m);
629 Square to = to_sq(m);
630 PieceType pt = type_of(piece_on(from));
633 if (ci.checkSq[pt] & to)
637 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
639 // For pawn and king moves we need to verify also direction
640 if ( (pt != PAWN && pt != KING)
641 || !aligned(from, to, king_square(~sideToMove)))
645 // Can we skip the ugly special cases ?
646 if (type_of(m) == NORMAL)
649 Color us = sideToMove;
650 Square ksq = king_square(~us);
655 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
657 // En passant capture with check ? We have already handled the case
658 // of direct checks and ordinary discovered check, the only case we
659 // need to handle is the unusual case of a discovered check through
660 // the captured pawn.
663 Square capsq = file_of(to) | rank_of(from);
664 Bitboard b = (pieces() ^ from ^ capsq) | to;
666 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
667 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
672 Square rfrom = to; // 'King captures the rook' notation
673 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
674 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
676 return (PseudoAttacks[ROOK][rto] & ksq)
677 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
686 /// Position::do_move() makes a move, and saves all information necessary
687 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
688 /// moves should be filtered out before this function is called.
690 void Position::do_move(Move m, StateInfo& newSt) {
693 do_move(m, newSt, ci, gives_check(m, ci));
696 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
699 assert(&newSt != st);
704 // Copy some fields of old state to our new StateInfo object except the ones
705 // which are going to be recalculated from scratch anyway, then switch our state
706 // pointer to point to the new, ready to be updated, state.
707 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
712 // Update side to move
715 // Increment ply counters.In particular rule50 will be later reset it to zero
716 // in case of a capture or a pawn move.
721 Color us = sideToMove;
723 Square from = from_sq(m);
724 Square to = to_sq(m);
725 Piece pc = piece_on(from);
726 PieceType pt = type_of(pc);
727 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
729 assert(color_of(pc) == us);
730 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
731 assert(captured != KING);
733 if (type_of(m) == CASTLE)
735 assert(pc == make_piece(us, KING));
737 bool kingSide = to > from;
738 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
739 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
740 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
741 captured = NO_PIECE_TYPE;
743 do_castle(from, to, rfrom, rto);
745 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
746 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
753 // If the captured piece is a pawn, update pawn hash key, otherwise
754 // update non-pawn material.
755 if (captured == PAWN)
757 if (type_of(m) == ENPASSANT)
759 capsq += pawn_push(them);
762 assert(to == st->epSquare);
763 assert(relative_rank(us, to) == RANK_6);
764 assert(piece_on(to) == NO_PIECE);
765 assert(piece_on(capsq) == make_piece(them, PAWN));
767 board[capsq] = NO_PIECE;
770 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
773 st->npMaterial[them] -= PieceValue[MG][captured];
775 // Update board and piece lists
776 remove_piece(capsq, them, captured);
778 // Update material hash key and prefetch access to materialTable
779 k ^= Zobrist::psq[them][captured][capsq];
780 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
781 prefetch((char*)thisThread->materialTable[st->materialKey]);
783 // Update incremental scores
784 st->psq -= psq[them][captured][capsq];
786 // Reset rule 50 counter
791 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
793 // Reset en passant square
794 if (st->epSquare != SQ_NONE)
796 k ^= Zobrist::enpassant[file_of(st->epSquare)];
797 st->epSquare = SQ_NONE;
800 // Update castle rights if needed
801 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
803 int cr = castleRightsMask[from] | castleRightsMask[to];
804 k ^= Zobrist::castle[st->castleRights & cr];
805 st->castleRights &= ~cr;
808 // Prefetch TT access as soon as we know the new hash key
809 prefetch((char*)TT.first_entry(k));
811 // Move the piece. The tricky Chess960 castle is handled earlier
812 if (type_of(m) != CASTLE)
813 move_piece(from, to, us, pt);
815 // If the moving piece is a pawn do some special extra work
818 // Set en-passant square, only if moved pawn can be captured
819 if ( (int(to) ^ int(from)) == 16
820 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
822 st->epSquare = Square((from + to) / 2);
823 k ^= Zobrist::enpassant[file_of(st->epSquare)];
826 if (type_of(m) == PROMOTION)
828 PieceType promotion = promotion_type(m);
830 assert(relative_rank(us, to) == RANK_8);
831 assert(promotion >= KNIGHT && promotion <= QUEEN);
833 remove_piece(to, us, PAWN);
834 put_piece(to, us, promotion);
837 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
838 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
839 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
840 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
842 // Update incremental score
843 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
846 st->npMaterial[us] += PieceValue[MG][promotion];
849 // Update pawn hash key and prefetch access to pawnsTable
850 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
851 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
853 // Reset rule 50 draw counter
857 // Update incremental scores
858 st->psq += psq[us][pt][to] - psq[us][pt][from];
861 st->capturedType = captured;
863 // Update the key with the final value
866 // Update checkers bitboard, piece must be already moved
871 if (type_of(m) != NORMAL)
872 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
876 if (ci.checkSq[pt] & to)
877 st->checkersBB |= to;
880 if (ci.dcCandidates && (ci.dcCandidates & from))
883 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
886 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
891 sideToMove = ~sideToMove;
897 /// Position::undo_move() unmakes a move. When it returns, the position should
898 /// be restored to exactly the same state as before the move was made.
900 void Position::undo_move(Move m) {
904 sideToMove = ~sideToMove;
906 Color us = sideToMove;
908 Square from = from_sq(m);
909 Square to = to_sq(m);
910 PieceType pt = type_of(piece_on(to));
911 PieceType captured = st->capturedType;
913 assert(empty(from) || type_of(m) == CASTLE);
914 assert(captured != KING);
916 if (type_of(m) == PROMOTION)
918 PieceType promotion = promotion_type(m);
920 assert(promotion == pt);
921 assert(relative_rank(us, to) == RANK_8);
922 assert(promotion >= KNIGHT && promotion <= QUEEN);
924 remove_piece(to, us, promotion);
925 put_piece(to, us, PAWN);
929 if (type_of(m) == CASTLE)
931 bool kingSide = to > from;
932 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
933 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
934 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
935 captured = NO_PIECE_TYPE;
937 do_castle(to, from, rto, rfrom);
940 move_piece(to, from, us, pt); // Put the piece back at the source square
946 if (type_of(m) == ENPASSANT)
948 capsq -= pawn_push(us);
951 assert(to == st->previous->epSquare);
952 assert(relative_rank(us, to) == RANK_6);
953 assert(piece_on(capsq) == NO_PIECE);
956 put_piece(capsq, them, captured); // Restore the captured piece
959 // Finally point our state pointer back to the previous state
967 /// Position::do_castle() is a helper used to do/undo a castling move. This
968 /// is a bit tricky, especially in Chess960.
970 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
972 // Remove both pieces first since squares could overlap in Chess960
973 remove_piece(kfrom, sideToMove, KING);
974 remove_piece(rfrom, sideToMove, ROOK);
975 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
976 put_piece(kto, sideToMove, KING);
977 put_piece(rto, sideToMove, ROOK);
981 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
982 /// the side to move without executing any move on the board.
984 void Position::do_null_move(StateInfo& newSt) {
988 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
993 if (st->epSquare != SQ_NONE)
995 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
996 st->epSquare = SQ_NONE;
999 st->key ^= Zobrist::side;
1000 prefetch((char*)TT.first_entry(st->key));
1003 st->pliesFromNull = 0;
1005 sideToMove = ~sideToMove;
1007 assert(pos_is_ok());
1010 void Position::undo_null_move() {
1012 assert(!checkers());
1015 sideToMove = ~sideToMove;
1019 /// Position::see() is a static exchange evaluator: It tries to estimate the
1020 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1021 /// tempi into account. If the side who initiated the capturing sequence does the
1022 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1023 /// the capturing sequence is considered bad.
1025 int Position::see_sign(Move m) const {
1029 // Early return if SEE cannot be negative because captured piece value
1030 // is not less then capturing one. Note that king moves always return
1031 // here because king midgame value is set to 0.
1032 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1038 int Position::see(Move m, int asymmThreshold) const {
1041 Bitboard occupied, attackers, stmAttackers;
1042 int swapList[32], slIndex = 1;
1050 swapList[0] = PieceValue[MG][piece_on(to)];
1051 stm = color_of(piece_on(from));
1052 occupied = pieces() ^ from;
1054 // Castle moves are implemented as king capturing the rook so cannot be
1055 // handled correctly. Simply return 0 that is always the correct value
1056 // unless in the rare case the rook ends up under attack.
1057 if (type_of(m) == CASTLE)
1060 if (type_of(m) == ENPASSANT)
1062 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1063 swapList[0] = PieceValue[MG][PAWN];
1066 // Find all attackers to the destination square, with the moving piece
1067 // removed, but possibly an X-ray attacker added behind it.
1068 attackers = attackers_to(to, occupied) & occupied;
1070 // If the opponent has no attackers we are finished
1072 stmAttackers = attackers & pieces(stm);
1076 // The destination square is defended, which makes things rather more
1077 // difficult to compute. We proceed by building up a "swap list" containing
1078 // the material gain or loss at each stop in a sequence of captures to the
1079 // destination square, where the sides alternately capture, and always
1080 // capture with the least valuable piece. After each capture, we look for
1081 // new X-ray attacks from behind the capturing piece.
1082 captured = type_of(piece_on(from));
1085 assert(slIndex < 32);
1087 // Add the new entry to the swap list
1088 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1091 // Locate and remove the next least valuable attacker
1092 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1094 stmAttackers = attackers & pieces(stm);
1096 // Stop before processing a king capture
1097 if (captured == KING && stmAttackers)
1099 swapList[slIndex++] = QueenValueMg * 16;
1103 } while (stmAttackers);
1105 // If we are doing asymmetric SEE evaluation and the same side does the first
1106 // and the last capture, he loses a tempo and gain must be at least worth
1107 // 'asymmThreshold', otherwise we replace the score with a very low value,
1108 // before negamaxing.
1110 for (int i = 0; i < slIndex; i += 2)
1111 if (swapList[i] < asymmThreshold)
1112 swapList[i] = - QueenValueMg * 16;
1114 // Having built the swap list, we negamax through it to find the best
1115 // achievable score from the point of view of the side to move.
1117 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1123 /// Position::clear() erases the position object to a pristine state, with an
1124 /// empty board, white to move, and no castling rights.
1126 void Position::clear() {
1128 std::memset(this, 0, sizeof(Position));
1129 startState.epSquare = SQ_NONE;
1132 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1133 for (int j = 0; j < 16; ++j)
1134 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1138 /// Position::compute_key() computes the hash key of the position. The hash
1139 /// key is usually updated incrementally as moves are made and unmade, the
1140 /// compute_key() function is only used when a new position is set up, and
1141 /// to verify the correctness of the hash key when running in debug mode.
1143 Key Position::compute_key() const {
1145 Key k = Zobrist::castle[st->castleRights];
1147 for (Bitboard b = pieces(); b; )
1149 Square s = pop_lsb(&b);
1150 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1153 if (ep_square() != SQ_NONE)
1154 k ^= Zobrist::enpassant[file_of(ep_square())];
1156 if (sideToMove == BLACK)
1163 /// Position::compute_pawn_key() computes the hash key of the position. The
1164 /// hash key is usually updated incrementally as moves are made and unmade,
1165 /// the compute_pawn_key() function is only used when a new position is set
1166 /// up, and to verify the correctness of the pawn hash key when running in
1169 Key Position::compute_pawn_key() const {
1173 for (Bitboard b = pieces(PAWN); b; )
1175 Square s = pop_lsb(&b);
1176 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1183 /// Position::compute_material_key() computes the hash key of the position.
1184 /// The hash key is usually updated incrementally as moves are made and unmade,
1185 /// the compute_material_key() function is only used when a new position is set
1186 /// up, and to verify the correctness of the material hash key when running in
1189 Key Position::compute_material_key() const {
1193 for (Color c = WHITE; c <= BLACK; ++c)
1194 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1195 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1196 k ^= Zobrist::psq[c][pt][cnt];
1202 /// Position::compute_psq_score() computes the incremental scores for the middle
1203 /// game and the endgame. These functions are used to initialize the incremental
1204 /// scores when a new position is set up, and to verify that the scores are correctly
1205 /// updated by do_move and undo_move when the program is running in debug mode.
1207 Score Position::compute_psq_score() const {
1209 Score score = SCORE_ZERO;
1211 for (Bitboard b = pieces(); b; )
1213 Square s = pop_lsb(&b);
1214 Piece pc = piece_on(s);
1215 score += psq[color_of(pc)][type_of(pc)][s];
1222 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1223 /// game material value for the given side. Material values are updated
1224 /// incrementally during the search, this function is only used while
1225 /// initializing a new Position object.
1227 Value Position::compute_non_pawn_material(Color c) const {
1229 Value value = VALUE_ZERO;
1231 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1232 value += pieceCount[c][pt] * PieceValue[MG][pt];
1238 /// Position::is_draw() tests whether the position is drawn by material,
1239 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1240 /// must be done by the search.
1241 bool Position::is_draw() const {
1243 // Draw by material?
1245 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1248 // Draw by the 50 moves rule?
1249 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1252 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1256 StateInfo* stp = st->previous->previous;
1259 stp = stp->previous->previous;
1261 if (stp->key == st->key)
1262 return true; // Draw after first repetition
1273 /// Position::flip() flips position with the white and black sides reversed. This
1274 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1276 static char toggle_case(char c) {
1277 return char(islower(c) ? toupper(c) : tolower(c));
1280 void Position::flip() {
1283 std::stringstream ss(fen());
1285 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1287 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1288 f.insert(0, token + (f.empty() ? " " : "/"));
1291 ss >> token; // Active color
1292 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1294 ss >> token; // Castling availability
1297 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1299 ss >> token; // En passant square
1300 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1302 std::getline(ss, token); // Half and full moves
1305 set(f, is_chess960(), this_thread());
1307 assert(pos_is_ok());
1311 /// Position::pos_is_ok() performs some consitency checks for the position object.
1312 /// This is meant to be helpful when debugging.
1314 bool Position::pos_is_ok(int* failedStep) const {
1316 int dummy, *step = failedStep ? failedStep : &dummy;
1318 // What features of the position should be verified?
1319 const bool all = false;
1321 const bool debugBitboards = all || false;
1322 const bool debugKingCount = all || false;
1323 const bool debugKingCapture = all || false;
1324 const bool debugCheckerCount = all || false;
1325 const bool debugKey = all || false;
1326 const bool debugMaterialKey = all || false;
1327 const bool debugPawnKey = all || false;
1328 const bool debugIncrementalEval = all || false;
1329 const bool debugNonPawnMaterial = all || false;
1330 const bool debugPieceCounts = all || false;
1331 const bool debugPieceList = all || false;
1332 const bool debugCastleSquares = all || false;
1336 if (sideToMove != WHITE && sideToMove != BLACK)
1339 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1342 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1345 if ((*step)++, debugKingCount)
1347 int kingCount[COLOR_NB] = {};
1349 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1350 if (type_of(piece_on(s)) == KING)
1351 ++kingCount[color_of(piece_on(s))];
1353 if (kingCount[0] != 1 || kingCount[1] != 1)
1357 if ((*step)++, debugKingCapture)
1358 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1361 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1364 if ((*step)++, debugBitboards)
1366 // The intersection of the white and black pieces must be empty
1367 if (pieces(WHITE) & pieces(BLACK))
1370 // The union of the white and black pieces must be equal to all
1372 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1375 // Separate piece type bitboards must have empty intersections
1376 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1377 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1378 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1382 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1385 if ((*step)++, debugKey && st->key != compute_key())
1388 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1391 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1394 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1397 if ((*step)++, debugNonPawnMaterial)
1398 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1399 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1402 if ((*step)++, debugPieceCounts)
1403 for (Color c = WHITE; c <= BLACK; ++c)
1404 for (PieceType pt = PAWN; pt <= KING; ++pt)
1405 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1408 if ((*step)++, debugPieceList)
1409 for (Color c = WHITE; c <= BLACK; ++c)
1410 for (PieceType pt = PAWN; pt <= KING; ++pt)
1411 for (int i = 0; i < pieceCount[c][pt]; ++i)
1412 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1413 || index[pieceList[c][pt][i]] != i)
1416 if ((*step)++, debugCastleSquares)
1417 for (Color c = WHITE; c <= BLACK; ++c)
1418 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1420 CastleRight cr = make_castle_right(c, s);
1422 if (!can_castle(cr))
1425 if ( (castleRightsMask[king_square(c)] & cr) != cr
1426 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1427 || castleRightsMask[castleRookSquare[c][s]] != cr)