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 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 /// 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 ((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_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 an 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 {
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(castling_rook_square(WHITE, KING_SIDE)), false) : 'K');
362 if (can_castle(WHITE_OOO))
363 ss << (chess960 ? file_to_char(file_of(castling_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
365 if (can_castle(BLACK_OO))
366 ss << (chess960 ? file_to_char(file_of(castling_rook_square(BLACK, KING_SIDE)), true) : 'k');
368 if (can_castle(BLACK_OOO))
369 ss << (chess960 ? file_to_char(file_of(castling_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
371 if (st->castlingFlags == NO_CASTLING)
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 and
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 a 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 the occ bitboard to indicate 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) == CASTLING || !(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. We therefore have to take care that
597 // the 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));
632 // Is there a direct check ?
633 if (ci.checkSq[pt] & to)
636 // Is there a discovered check ?
637 if ( unlikely(ci.dcCandidates)
638 && (ci.dcCandidates & from)
639 && !aligned(from, to, king_square(~sideToMove)))
642 // Can we skip the ugly special cases ?
643 if (type_of(m) == NORMAL)
646 Color us = sideToMove;
647 Square ksq = king_square(~us);
652 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
654 // En passant capture with check ? We have already handled the case
655 // of direct checks and ordinary discovered check, so the only case we
656 // need to handle is the unusual case of a discovered check through
657 // the captured pawn.
660 Square capsq = file_of(to) | rank_of(from);
661 Bitboard b = (pieces() ^ from ^ capsq) | to;
663 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
664 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
669 Square rfrom = to; // Castling is encoded as 'King captures the rook'
670 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
671 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
673 return (PseudoAttacks[ROOK][rto] & ksq)
674 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
683 /// Position::do_move() makes a move, and saves all information necessary
684 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
685 /// moves should be filtered out before this function is called.
687 void Position::do_move(Move m, StateInfo& newSt) {
690 do_move(m, newSt, ci, gives_check(m, ci));
693 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
696 assert(&newSt != st);
701 // Copy some fields of old state to our new StateInfo object except the ones
702 // which are going to be recalculated from scratch anyway, then switch our state
703 // pointer to point to the new (ready to be updated) state.
704 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
709 // Update side to move
712 // Increment ply counters.In particular rule50 will be reset to zero later on
713 // in case of a capture or a pawn move.
718 Color us = sideToMove;
720 Square from = from_sq(m);
721 Square to = to_sq(m);
722 Piece pc = piece_on(from);
723 PieceType pt = type_of(pc);
724 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
726 assert(color_of(pc) == us);
727 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
728 assert(captured != KING);
730 if (type_of(m) == CASTLING)
732 assert(pc == make_piece(us, KING));
734 bool kingSide = to > from;
735 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
736 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
737 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
738 captured = NO_PIECE_TYPE;
740 do_castling(from, to, rfrom, rto);
742 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
743 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
750 // If the captured piece is a pawn, update pawn hash key, otherwise
751 // update non-pawn material.
752 if (captured == PAWN)
754 if (type_of(m) == ENPASSANT)
756 capsq += pawn_push(them);
759 assert(to == st->epSquare);
760 assert(relative_rank(us, to) == RANK_6);
761 assert(piece_on(to) == NO_PIECE);
762 assert(piece_on(capsq) == make_piece(them, PAWN));
764 board[capsq] = NO_PIECE;
767 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
770 st->npMaterial[them] -= PieceValue[MG][captured];
772 // Update board and piece lists
773 remove_piece(capsq, them, captured);
775 // Update material hash key and prefetch access to materialTable
776 k ^= Zobrist::psq[them][captured][capsq];
777 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
778 prefetch((char*)thisThread->materialTable[st->materialKey]);
780 // Update incremental scores
781 st->psq -= psq[them][captured][capsq];
783 // Reset rule 50 counter
788 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
790 // Reset en passant square
791 if (st->epSquare != SQ_NONE)
793 k ^= Zobrist::enpassant[file_of(st->epSquare)];
794 st->epSquare = SQ_NONE;
797 // Update castling flags if needed
798 if (st->castlingFlags && (castlingFlagsMask[from] | castlingFlagsMask[to]))
800 int cf = castlingFlagsMask[from] | castlingFlagsMask[to];
801 k ^= Zobrist::castling[st->castlingFlags & cf];
802 st->castlingFlags &= ~cf;
805 // Prefetch TT access as soon as we know the new hash key
806 prefetch((char*)TT.first_entry(k));
808 // Move the piece. The tricky Chess960 castling is handled earlier
809 if (type_of(m) != CASTLING)
810 move_piece(from, to, us, pt);
812 // If the moving piece is a pawn do some special extra work
815 // Set en-passant square if the moved pawn can be captured
816 if ( (int(to) ^ int(from)) == 16
817 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
819 st->epSquare = Square((from + to) / 2);
820 k ^= Zobrist::enpassant[file_of(st->epSquare)];
823 if (type_of(m) == PROMOTION)
825 PieceType promotion = promotion_type(m);
827 assert(relative_rank(us, to) == RANK_8);
828 assert(promotion >= KNIGHT && promotion <= QUEEN);
830 remove_piece(to, us, PAWN);
831 put_piece(to, us, promotion);
834 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
835 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
836 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
837 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
839 // Update incremental score
840 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
843 st->npMaterial[us] += PieceValue[MG][promotion];
846 // Update pawn hash key and prefetch access to pawnsTable
847 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
848 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
850 // Reset rule 50 draw counter
854 // Update incremental scores
855 st->psq += psq[us][pt][to] - psq[us][pt][from];
858 st->capturedType = captured;
860 // Update the key with the final value
863 // Update checkers bitboard: piece must be already moved
868 if (type_of(m) != NORMAL)
869 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
873 if (ci.checkSq[pt] & to)
874 st->checkersBB |= to;
877 if (ci.dcCandidates && (ci.dcCandidates & from))
880 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
883 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
888 sideToMove = ~sideToMove;
894 /// Position::undo_move() unmakes a move. When it returns, the position should
895 /// be restored to exactly the same state as before the move was made.
897 void Position::undo_move(Move m) {
901 sideToMove = ~sideToMove;
903 Color us = sideToMove;
905 Square from = from_sq(m);
906 Square to = to_sq(m);
907 PieceType pt = type_of(piece_on(to));
908 PieceType captured = st->capturedType;
910 assert(empty(from) || type_of(m) == CASTLING);
911 assert(captured != KING);
913 if (type_of(m) == PROMOTION)
915 PieceType promotion = promotion_type(m);
917 assert(promotion == pt);
918 assert(relative_rank(us, to) == RANK_8);
919 assert(promotion >= KNIGHT && promotion <= QUEEN);
921 remove_piece(to, us, promotion);
922 put_piece(to, us, PAWN);
926 if (type_of(m) == CASTLING)
928 bool kingSide = to > from;
929 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
930 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
931 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
932 captured = NO_PIECE_TYPE;
934 do_castling(to, from, rto, rfrom);
937 move_piece(to, from, us, pt); // Put the piece back at the source square
943 if (type_of(m) == ENPASSANT)
945 capsq -= pawn_push(us);
948 assert(to == st->previous->epSquare);
949 assert(relative_rank(us, to) == RANK_6);
950 assert(piece_on(capsq) == NO_PIECE);
953 put_piece(capsq, them, captured); // Restore the captured piece
956 // Finally point our state pointer back to the previous state
964 /// Position::do_castling() is a helper used to do/undo a castling move. This
965 /// is a bit tricky, especially in Chess960.
967 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
969 // Remove both pieces first since squares could overlap in Chess960
970 remove_piece(kfrom, sideToMove, KING);
971 remove_piece(rfrom, sideToMove, ROOK);
972 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
973 put_piece(kto, sideToMove, KING);
974 put_piece(rto, sideToMove, ROOK);
978 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
979 /// the side to move without executing any move on the board.
981 void Position::do_null_move(StateInfo& newSt) {
985 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
990 if (st->epSquare != SQ_NONE)
992 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
993 st->epSquare = SQ_NONE;
996 st->key ^= Zobrist::side;
997 prefetch((char*)TT.first_entry(st->key));
1000 st->pliesFromNull = 0;
1002 sideToMove = ~sideToMove;
1004 assert(pos_is_ok());
1007 void Position::undo_null_move() {
1009 assert(!checkers());
1012 sideToMove = ~sideToMove;
1016 /// Position::see() is a static exchange evaluator: It tries to estimate the
1017 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1018 /// tempi into account. If the side who initiated the capturing sequence does the
1019 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1020 /// the capturing sequence is considered bad.
1022 int Position::see_sign(Move m) const {
1026 // Early return if SEE cannot be negative because captured piece value
1027 // is not less then capturing one. Note that king moves always return
1028 // here because king midgame value is set to 0.
1029 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1035 int Position::see(Move m, int asymmThreshold) const {
1038 Bitboard occupied, attackers, stmAttackers;
1039 int swapList[32], slIndex = 1;
1047 swapList[0] = PieceValue[MG][piece_on(to)];
1048 stm = color_of(piece_on(from));
1049 occupied = pieces() ^ from;
1051 // Castling moves are implemented as king capturing the rook so cannot be
1052 // handled correctly. Simply return 0 that is always the correct value
1053 // unless in the rare case the rook ends up under attack.
1054 if (type_of(m) == CASTLING)
1057 if (type_of(m) == ENPASSANT)
1059 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1060 swapList[0] = PieceValue[MG][PAWN];
1063 // Find all attackers to the destination square, with the moving piece
1064 // removed, but possibly an X-ray attacker added behind it.
1065 attackers = attackers_to(to, occupied) & occupied;
1067 // If the opponent has no attackers we are finished
1069 stmAttackers = attackers & pieces(stm);
1073 // The destination square is defended, which makes things rather more
1074 // difficult to compute. We proceed by building up a "swap list" containing
1075 // the material gain or loss at each stop in a sequence of captures to the
1076 // destination square, where the sides alternately capture, and always
1077 // capture with the least valuable piece. After each capture, we look for
1078 // new X-ray attacks from behind the capturing piece.
1079 captured = type_of(piece_on(from));
1082 assert(slIndex < 32);
1084 // Add the new entry to the swap list
1085 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1088 // Locate and remove the next least valuable attacker
1089 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1091 stmAttackers = attackers & pieces(stm);
1093 // Stop before processing a king capture
1094 if (captured == KING && stmAttackers)
1096 swapList[slIndex++] = QueenValueMg * 16;
1100 } while (stmAttackers);
1102 // If we are doing asymmetric SEE evaluation and the same side does the first
1103 // and the last capture, he loses a tempo and gain must be at least worth
1104 // 'asymmThreshold', otherwise we replace the score with a very low value,
1105 // before negamaxing.
1107 for (int i = 0; i < slIndex; i += 2)
1108 if (swapList[i] < asymmThreshold)
1109 swapList[i] = - QueenValueMg * 16;
1111 // Having built the swap list, we negamax through it to find the best
1112 // achievable score from the point of view of the side to move.
1114 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1120 /// Position::clear() erases the position object to a pristine state, with an
1121 /// empty board, white to move, and no castling rights.
1123 void Position::clear() {
1125 std::memset(this, 0, sizeof(Position));
1126 startState.epSquare = SQ_NONE;
1129 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1130 for (int j = 0; j < 16; ++j)
1131 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1135 /// Position::compute_key() computes the hash key of the position. The hash
1136 /// key is usually updated incrementally as moves are made and unmade. The
1137 /// compute_key() function is only used when a new position is set up, and
1138 /// to verify the correctness of the hash key when running in debug mode.
1140 Key Position::compute_key() const {
1142 Key k = Zobrist::castling[st->castlingFlags];
1144 for (Bitboard b = pieces(); b; )
1146 Square s = pop_lsb(&b);
1147 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1150 if (ep_square() != SQ_NONE)
1151 k ^= Zobrist::enpassant[file_of(ep_square())];
1153 if (sideToMove == BLACK)
1160 /// Position::compute_pawn_key() computes the hash key of the position. The
1161 /// hash key is usually updated incrementally as moves are made and unmade.
1162 /// The compute_pawn_key() function is only used when a new position is set
1163 /// up, and to verify the correctness of the pawn hash key when running in
1166 Key Position::compute_pawn_key() const {
1170 for (Bitboard b = pieces(PAWN); b; )
1172 Square s = pop_lsb(&b);
1173 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1180 /// Position::compute_material_key() computes the hash key of the position.
1181 /// The hash key is usually updated incrementally as moves are made and unmade.
1182 /// The compute_material_key() function is only used when a new position is set
1183 /// up, and to verify the correctness of the material hash key when running in
1186 Key Position::compute_material_key() const {
1190 for (Color c = WHITE; c <= BLACK; ++c)
1191 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1192 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1193 k ^= Zobrist::psq[c][pt][cnt];
1199 /// Position::compute_psq_score() computes the incremental scores for the middle
1200 /// game and the endgame. These functions are used to initialize the incremental
1201 /// scores when a new position is set up, and to verify that the scores are correctly
1202 /// updated by do_move and undo_move when the program is running in debug mode.
1204 Score Position::compute_psq_score() const {
1206 Score score = SCORE_ZERO;
1208 for (Bitboard b = pieces(); b; )
1210 Square s = pop_lsb(&b);
1211 Piece pc = piece_on(s);
1212 score += psq[color_of(pc)][type_of(pc)][s];
1219 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1220 /// game material value for the given side. Material values are updated
1221 /// incrementally during the search. This function is only used when
1222 /// initializing a new Position object.
1224 Value Position::compute_non_pawn_material(Color c) const {
1226 Value value = VALUE_ZERO;
1228 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1229 value += pieceCount[c][pt] * PieceValue[MG][pt];
1235 /// Position::is_draw() tests whether the position is drawn by material,
1236 /// repetition, or the 50 moves rule. It does not detect stalemates: this
1237 /// must be done by the search.
1238 bool Position::is_draw() const {
1240 // Draw by material?
1242 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1245 // Draw by the 50 moves rule?
1246 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1249 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1253 StateInfo* stp = st->previous->previous;
1256 stp = stp->previous->previous;
1258 if (stp->key == st->key)
1259 return true; // Draw after first repetition
1270 /// Position::flip() flips position with the white and black sides reversed. This
1271 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1273 static char toggle_case(char c) {
1274 return char(islower(c) ? toupper(c) : tolower(c));
1277 void Position::flip() {
1280 std::stringstream ss(fen());
1282 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1284 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1285 f.insert(0, token + (f.empty() ? " " : "/"));
1288 ss >> token; // Active color
1289 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1291 ss >> token; // Castling availability
1294 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1296 ss >> token; // En passant square
1297 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1299 std::getline(ss, token); // Half and full moves
1302 set(f, is_chess960(), this_thread());
1304 assert(pos_is_ok());
1308 /// Position::pos_is_ok() performs some consistency checks for the position object.
1309 /// This is meant to be helpful when debugging.
1311 bool Position::pos_is_ok(int* failedStep) const {
1313 int dummy, *step = failedStep ? failedStep : &dummy;
1315 // What features of the position should be verified?
1316 const bool all = false;
1318 const bool debugBitboards = all || false;
1319 const bool debugKingCount = all || false;
1320 const bool debugKingCapture = all || false;
1321 const bool debugCheckerCount = all || false;
1322 const bool debugKey = all || false;
1323 const bool debugMaterialKey = all || false;
1324 const bool debugPawnKey = all || false;
1325 const bool debugIncrementalEval = all || false;
1326 const bool debugNonPawnMaterial = all || false;
1327 const bool debugPieceCounts = all || false;
1328 const bool debugPieceList = all || false;
1329 const bool debugCastlingSquares = all || false;
1333 if (sideToMove != WHITE && sideToMove != BLACK)
1336 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1339 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1342 if ((*step)++, debugKingCount)
1344 int kingCount[COLOR_NB] = {};
1346 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1347 if (type_of(piece_on(s)) == KING)
1348 ++kingCount[color_of(piece_on(s))];
1350 if (kingCount[0] != 1 || kingCount[1] != 1)
1354 if ((*step)++, debugKingCapture)
1355 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1358 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1361 if ((*step)++, debugBitboards)
1363 // The intersection of the white and black pieces must be empty
1364 if (pieces(WHITE) & pieces(BLACK))
1367 // The union of the white and black pieces must be equal to all
1369 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1372 // Separate piece type bitboards must have empty intersections
1373 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1374 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1375 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1379 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1382 if ((*step)++, debugKey && st->key != compute_key())
1385 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1388 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1391 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1394 if ((*step)++, debugNonPawnMaterial)
1395 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1396 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1399 if ((*step)++, debugPieceCounts)
1400 for (Color c = WHITE; c <= BLACK; ++c)
1401 for (PieceType pt = PAWN; pt <= KING; ++pt)
1402 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1405 if ((*step)++, debugPieceList)
1406 for (Color c = WHITE; c <= BLACK; ++c)
1407 for (PieceType pt = PAWN; pt <= KING; ++pt)
1408 for (int i = 0; i < pieceCount[c][pt]; ++i)
1409 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1410 || index[pieceList[c][pt][i]] != i)
1413 if ((*step)++, debugCastlingSquares)
1414 for (Color c = WHITE; c <= BLACK; ++c)
1415 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1417 CastlingFlag cf = make_castling_flag(c, s);
1419 if (!can_castle(cf))
1422 if ( (castlingFlagsMask[king_square(c)] & cf) != cf
1423 || piece_on(castlingRookSquare[c][s]) != make_piece(c, ROOK)
1424 || castlingFlagsMask[castlingRookSquare[c][s]] != cf)