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);
288 compute_non_pawn_material(st);
289 st->psq = compute_psq_score();
290 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
291 chess960 = isChess960;
298 /// Position::set_castling_right() is a helper function used to set castling
299 /// rights given the corresponding color and the rook starting square.
301 void Position::set_castling_right(Color c, Square rfrom) {
303 Square kfrom = king_square(c);
304 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
305 CastlingRight cr = (c | cs);
307 st->castlingRights |= cr;
308 castlingRightsMask[kfrom] |= cr;
309 castlingRightsMask[rfrom] |= cr;
310 castlingRookSquare[cr] = rfrom;
312 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
313 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
315 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
316 if (s != kfrom && s != rfrom)
317 castlingPath[cr] |= s;
319 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
320 if (s != kfrom && s != rfrom)
321 castlingPath[cr] |= s;
325 /// Position::fen() returns a FEN representation of the position. In case of
326 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
328 const string Position::fen() const {
331 std::ostringstream ss;
333 for (Rank rank = RANK_8; rank >= RANK_1; --rank)
335 for (File file = FILE_A; file <= FILE_H; ++file)
337 for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file)
344 ss << PieceToChar[piece_on(file | rank)];
351 ss << (sideToMove == WHITE ? " w " : " b ");
353 if (can_castle(WHITE_OO))
354 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | KING_SIDE)), false) : 'K');
356 if (can_castle(WHITE_OOO))
357 ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | QUEEN_SIDE)), false) : 'Q');
359 if (can_castle(BLACK_OO))
360 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | KING_SIDE)), true) : 'k');
362 if (can_castle(BLACK_OOO))
363 ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | QUEEN_SIDE)), true) : 'q');
365 if (!can_castle(WHITE) && !can_castle(BLACK))
368 ss << (ep_square() == SQ_NONE ? " - " : " " + to_string(ep_square()) + " ")
369 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
375 /// Position::pretty() returns an ASCII representation of the position to be
376 /// printed to the standard output together with the move's san notation.
378 const string Position::pretty(Move move) const {
380 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
381 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
382 + dottedLine + "\n| . | | . | | . | | . | |";
384 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
386 for (Bitboard b = pieces(); b; )
388 Square s = pop_lsb(&b);
389 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
392 std::ostringstream ss;
395 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
396 << move_to_san(*const_cast<Position*>(this), move);
398 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
399 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
401 for (Bitboard b = checkers(); b; )
402 ss << to_string(pop_lsb(&b)) << " ";
404 ss << "\nLegal moves: ";
405 for (MoveList<LEGAL> it(*this); *it; ++it)
406 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
412 /// Position::check_blockers() returns a bitboard of all the pieces with color
413 /// 'c' that are blocking check on the king with color 'kingColor'. A piece
414 /// blocks a check if removing that piece from the board would result in a
415 /// position where the king is in check. A check blocking piece can be either a
416 /// pinned or a discovered check piece, according if its color 'c' is the same
417 /// or the opposite of 'kingColor'.
419 Bitboard Position::check_blockers(Color c, Color kingColor) const {
421 Bitboard b, pinners, result = 0;
422 Square ksq = king_square(kingColor);
424 // Pinners are sliders that give check when a pinned piece is removed
425 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
426 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor);
430 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
432 if (!more_than_one(b))
433 result |= b & pieces(c);
439 /// Position::attackers_to() computes a bitboard of all pieces which attack a
440 /// given square. Slider attacks use the occ bitboard to indicate occupancy.
442 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
444 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
445 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
446 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
447 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
448 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
449 | (attacks_from<KING>(s) & pieces(KING));
453 /// Position::legal() tests whether a pseudo-legal move is legal
455 bool Position::legal(Move m, Bitboard pinned) const {
458 assert(pinned == pinned_pieces(sideToMove));
460 Color us = sideToMove;
461 Square from = from_sq(m);
463 assert(color_of(moved_piece(m)) == us);
464 assert(piece_on(king_square(us)) == make_piece(us, KING));
466 // En passant captures are a tricky special case. Because they are rather
467 // uncommon, we do it simply by testing whether the king is attacked after
469 if (type_of(m) == ENPASSANT)
472 Square to = to_sq(m);
473 Square capsq = to + pawn_push(them);
474 Square ksq = king_square(us);
475 Bitboard b = (pieces() ^ from ^ capsq) | to;
477 assert(to == ep_square());
478 assert(moved_piece(m) == make_piece(us, PAWN));
479 assert(piece_on(capsq) == make_piece(them, PAWN));
480 assert(piece_on(to) == NO_PIECE);
482 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
483 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
486 // If the moving piece is a king, check whether the destination
487 // square is attacked by the opponent. Castling moves are checked
488 // for legality during move generation.
489 if (type_of(piece_on(from)) == KING)
490 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
492 // A non-king move is legal if and only if it is not pinned or it
493 // is moving along the ray towards or away from the king.
496 || aligned(from, to_sq(m), king_square(us));
500 /// Position::pseudo_legal() takes a random move and tests whether the move is
501 /// pseudo legal. It is used to validate moves from TT that can be corrupted
502 /// due to SMP concurrent access or hash position key aliasing.
504 bool Position::pseudo_legal(const Move m) const {
506 Color us = sideToMove;
507 Square from = from_sq(m);
508 Square to = to_sq(m);
509 Piece pc = moved_piece(m);
511 // Use a slower but simpler function for uncommon cases
512 if (type_of(m) != NORMAL)
513 return MoveList<LEGAL>(*this).contains(m);
515 // Is not a promotion, so promotion piece must be empty
516 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
519 // If the 'from' square is not occupied by a piece belonging to the side to
520 // move, the move is obviously not legal.
521 if (pc == NO_PIECE || color_of(pc) != us)
524 // The destination square cannot be occupied by a friendly piece
528 // Handle the special case of a pawn move
529 if (type_of(pc) == PAWN)
531 // We have already handled promotion moves, so destination
532 // cannot be on the 8th/1st rank.
533 if (rank_of(to) == relative_rank(us, RANK_8))
536 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
538 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
540 && !( (from + 2 * pawn_push(us) == to) // Not a double push
541 && (rank_of(from) == relative_rank(us, RANK_2))
543 && empty(to - pawn_push(us))))
546 else if (!(attacks_from(pc, from) & to))
549 // Evasions generator already takes care to avoid some kind of illegal moves
550 // and legal() relies on this. We therefore have to take care that the same
551 // kind of moves are filtered out here.
554 if (type_of(pc) != KING)
556 // Double check? In this case a king move is required
557 if (more_than_one(checkers()))
560 // Our move must be a blocking evasion or a capture of the checking piece
561 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
564 // In case of king moves under check we have to remove king so as to catch
565 // invalid moves like b1a1 when opposite queen is on c1.
566 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
574 /// Position::gives_check() tests whether a pseudo-legal move gives a check
576 bool Position::gives_check(Move m, const CheckInfo& ci) const {
579 assert(ci.dcCandidates == discovered_check_candidates());
580 assert(color_of(moved_piece(m)) == sideToMove);
582 Square from = from_sq(m);
583 Square to = to_sq(m);
584 PieceType pt = type_of(piece_on(from));
586 // Is there a direct check?
587 if (ci.checkSq[pt] & to)
590 // Is there a discovered check?
591 if ( unlikely(ci.dcCandidates)
592 && (ci.dcCandidates & from)
593 && !aligned(from, to, ci.ksq))
602 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq;
604 // En passant capture with check? We have already handled the case
605 // of direct checks and ordinary discovered check, so the only case we
606 // need to handle is the unusual case of a discovered check through
607 // the captured pawn.
610 Square capsq = file_of(to) | rank_of(from);
611 Bitboard b = (pieces() ^ from ^ capsq) | to;
613 return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
614 | (attacks_bb<BISHOP>(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
619 Square rfrom = to; // Castling is encoded as 'King captures the rook'
620 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
621 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
623 return (PseudoAttacks[ROOK][rto] & ci.ksq)
624 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq);
633 /// Position::do_move() makes a move, and saves all information necessary
634 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
635 /// moves should be filtered out before this function is called.
637 void Position::do_move(Move m, StateInfo& newSt) {
640 do_move(m, newSt, ci, gives_check(m, ci));
643 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
646 assert(&newSt != st);
651 // Copy some fields of the old state to our new StateInfo object except the
652 // ones which are going to be recalculated from scratch anyway and then switch
653 // our state pointer to point to the new (ready to be updated) state.
654 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
659 // Update side to move
662 // Increment ply counters. In particular, rule50 will be reset to zero later on
663 // in case of a capture or a pawn move.
668 Color us = sideToMove;
670 Square from = from_sq(m);
671 Square to = to_sq(m);
672 Piece pc = piece_on(from);
673 PieceType pt = type_of(pc);
674 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
676 assert(color_of(pc) == us);
677 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING);
678 assert(captured != KING);
680 if (type_of(m) == CASTLING)
682 assert(pc == make_piece(us, KING));
684 bool kingSide = to > from;
685 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
686 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
687 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
688 captured = NO_PIECE_TYPE;
690 do_castling(from, to, rfrom, rto);
692 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
693 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
700 // If the captured piece is a pawn, update pawn hash key, otherwise
701 // update non-pawn material.
702 if (captured == PAWN)
704 if (type_of(m) == ENPASSANT)
706 capsq += pawn_push(them);
709 assert(to == st->epSquare);
710 assert(relative_rank(us, to) == RANK_6);
711 assert(piece_on(to) == NO_PIECE);
712 assert(piece_on(capsq) == make_piece(them, PAWN));
714 board[capsq] = NO_PIECE;
717 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
720 st->npMaterial[them] -= PieceValue[MG][captured];
722 // Update board and piece lists
723 remove_piece(capsq, them, captured);
725 // Update material hash key and prefetch access to materialTable
726 k ^= Zobrist::psq[them][captured][capsq];
727 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
728 prefetch((char*)thisThread->materialTable[st->materialKey]);
730 // Update incremental scores
731 st->psq -= psq[them][captured][capsq];
733 // Reset rule 50 counter
738 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
740 // Reset en passant square
741 if (st->epSquare != SQ_NONE)
743 k ^= Zobrist::enpassant[file_of(st->epSquare)];
744 st->epSquare = SQ_NONE;
747 // Update castling rights if needed
748 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
750 int cr = castlingRightsMask[from] | castlingRightsMask[to];
751 k ^= Zobrist::castling[st->castlingRights & cr];
752 st->castlingRights &= ~cr;
755 // Prefetch TT access as soon as we know the new hash key
756 prefetch((char*)TT.first_entry(k));
758 // Move the piece. The tricky Chess960 castling is handled earlier
759 if (type_of(m) != CASTLING)
760 move_piece(from, to, us, pt);
762 // If the moving piece is a pawn do some special extra work
765 // Set en-passant square if the moved pawn can be captured
766 if ( (int(to) ^ int(from)) == 16
767 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
769 st->epSquare = Square((from + to) / 2);
770 k ^= Zobrist::enpassant[file_of(st->epSquare)];
773 if (type_of(m) == PROMOTION)
775 PieceType promotion = promotion_type(m);
777 assert(relative_rank(us, to) == RANK_8);
778 assert(promotion >= KNIGHT && promotion <= QUEEN);
780 remove_piece(to, us, PAWN);
781 put_piece(to, us, promotion);
784 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
785 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
786 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
787 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
789 // Update incremental score
790 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
793 st->npMaterial[us] += PieceValue[MG][promotion];
796 // Update pawn hash key and prefetch access to pawnsTable
797 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
798 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
800 // Reset rule 50 draw counter
804 // Update incremental scores
805 st->psq += psq[us][pt][to] - psq[us][pt][from];
808 st->capturedType = captured;
810 // Update the key with the final value
813 // Update checkers bitboard: piece must be already moved
818 if (type_of(m) != NORMAL)
819 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
823 if (ci.checkSq[pt] & to)
824 st->checkersBB |= to;
827 if (ci.dcCandidates && (ci.dcCandidates & from))
830 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
833 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
838 sideToMove = ~sideToMove;
844 /// Position::undo_move() unmakes a move. When it returns, the position should
845 /// be restored to exactly the same state as before the move was made.
847 void Position::undo_move(Move m) {
851 sideToMove = ~sideToMove;
853 Color us = sideToMove;
855 Square from = from_sq(m);
856 Square to = to_sq(m);
857 PieceType pt = type_of(piece_on(to));
858 PieceType captured = st->capturedType;
860 assert(empty(from) || type_of(m) == CASTLING);
861 assert(captured != KING);
863 if (type_of(m) == PROMOTION)
865 PieceType promotion = promotion_type(m);
867 assert(promotion == pt);
868 assert(relative_rank(us, to) == RANK_8);
869 assert(promotion >= KNIGHT && promotion <= QUEEN);
871 remove_piece(to, us, promotion);
872 put_piece(to, us, PAWN);
876 if (type_of(m) == CASTLING)
878 bool kingSide = to > from;
879 Square rfrom = to; // Castling is encoded as "king captures friendly rook"
880 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
881 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
882 captured = NO_PIECE_TYPE;
884 do_castling(to, from, rto, rfrom);
887 move_piece(to, from, us, pt); // Put the piece back at the source square
893 if (type_of(m) == ENPASSANT)
895 capsq -= pawn_push(us);
898 assert(to == st->previous->epSquare);
899 assert(relative_rank(us, to) == RANK_6);
900 assert(piece_on(capsq) == NO_PIECE);
903 put_piece(capsq, them, captured); // Restore the captured piece
906 // Finally point our state pointer back to the previous state
914 /// Position::do_castling() is a helper used to do/undo a castling move. This
915 /// is a bit tricky, especially in Chess960.
917 void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) {
919 // Remove both pieces first since squares could overlap in Chess960
920 remove_piece(kfrom, sideToMove, KING);
921 remove_piece(rfrom, sideToMove, ROOK);
922 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
923 put_piece(kto, sideToMove, KING);
924 put_piece(rto, sideToMove, ROOK);
928 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
929 /// the side to move without executing any move on the board.
931 void Position::do_null_move(StateInfo& newSt) {
935 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
940 if (st->epSquare != SQ_NONE)
942 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
943 st->epSquare = SQ_NONE;
946 st->key ^= Zobrist::side;
947 prefetch((char*)TT.first_entry(st->key));
950 st->pliesFromNull = 0;
952 sideToMove = ~sideToMove;
957 void Position::undo_null_move() {
962 sideToMove = ~sideToMove;
966 /// Position::see() is a static exchange evaluator: It tries to estimate the
967 /// material gain or loss resulting from a move.
969 Value Position::see_sign(Move m) const {
973 // Early return if SEE cannot be negative because captured piece value
974 // is not less then capturing one. Note that king moves always return
975 // here because king midgame value is set to 0.
976 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
977 return VALUE_KNOWN_WIN;
982 Value Position::see(Move m) const {
985 Bitboard occupied, attackers, stmAttackers;
995 swapList[0] = PieceValue[MG][piece_on(to)];
996 stm = color_of(piece_on(from));
997 occupied = pieces() ^ from;
999 // Castling moves are implemented as king capturing the rook so cannot be
1000 // handled correctly. Simply return 0 that is always the correct value
1001 // unless in the rare case the rook ends up under attack.
1002 if (type_of(m) == CASTLING)
1005 if (type_of(m) == ENPASSANT)
1007 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1008 swapList[0] = PieceValue[MG][PAWN];
1011 // Find all attackers to the destination square, with the moving piece
1012 // removed, but possibly an X-ray attacker added behind it.
1013 attackers = attackers_to(to, occupied) & occupied;
1015 // If the opponent has no attackers we are finished
1017 stmAttackers = attackers & pieces(stm);
1021 // The destination square is defended, which makes things rather more
1022 // difficult to compute. We proceed by building up a "swap list" containing
1023 // the material gain or loss at each stop in a sequence of captures to the
1024 // destination square, where the sides alternately capture, and always
1025 // capture with the least valuable piece. After each capture, we look for
1026 // new X-ray attacks from behind the capturing piece.
1027 captured = type_of(piece_on(from));
1030 assert(slIndex < 32);
1032 // Add the new entry to the swap list
1033 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1035 // Locate and remove the next least valuable attacker
1036 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1038 // Stop before processing a king capture
1039 if (captured == KING)
1041 if (stmAttackers == attackers)
1048 stmAttackers = attackers & pieces(stm);
1051 } while (stmAttackers);
1053 // Having built the swap list, we negamax through it to find the best
1054 // achievable score from the point of view of the side to move.
1056 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1062 /// Position::clear() erases the position object to a pristine state, with an
1063 /// empty board, white to move, and no castling rights.
1065 void Position::clear() {
1067 std::memset(this, 0, sizeof(Position));
1068 startState.epSquare = SQ_NONE;
1071 for (int i = 0; i < PIECE_TYPE_NB; ++i)
1072 for (int j = 0; j < 16; ++j)
1073 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1077 /// Position::compute_keys() computes the hash keys of the position, pawns and
1078 /// material configuration. The hash keys are usually updated incrementally as
1079 /// moves are made and unmade. The function is only used when a new position is
1080 /// set up, and to verify the correctness of the keys when running in debug mode.
1082 void Position::compute_keys(StateInfo* si) const {
1084 si->key = si->pawnKey = si->materialKey = 0;
1086 for (Bitboard b = pieces(); b; )
1088 Square s = pop_lsb(&b);
1089 si->key ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1092 if (ep_square() != SQ_NONE)
1093 si->key ^= Zobrist::enpassant[file_of(ep_square())];
1095 if (sideToMove == BLACK)
1096 si->key ^= Zobrist::side;
1098 si->key ^= Zobrist::castling[st->castlingRights];
1100 for (Bitboard b = pieces(PAWN); b; )
1102 Square s = pop_lsb(&b);
1103 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1106 for (Color c = WHITE; c <= BLACK; ++c)
1107 for (PieceType pt = PAWN; pt <= KING; ++pt)
1108 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1109 si->materialKey ^= Zobrist::psq[c][pt][cnt];
1113 /// Position::compute_non_pawn_material() computes the total non-pawn middlegame
1114 /// material value for each side. Material values are updated incrementally during
1115 /// the search. This function is only used when initializing a new Position object.
1117 void Position::compute_non_pawn_material(StateInfo* si) const {
1119 si->npMaterial[WHITE] = si->npMaterial[BLACK] = VALUE_ZERO;
1121 for (Color c = WHITE; c <= BLACK; ++c)
1122 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1123 si->npMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
1127 /// Position::compute_psq_score() computes the incremental scores for the middlegame
1128 /// and the endgame. These functions are used to initialize the incremental scores
1129 /// when a new position is set up, and to verify that the scores are correctly
1130 /// updated by do_move and undo_move when the program is running in debug mode.
1132 Score Position::compute_psq_score() const {
1134 Score score = SCORE_ZERO;
1136 for (Bitboard b = pieces(); b; )
1138 Square s = pop_lsb(&b);
1139 Piece pc = piece_on(s);
1140 score += psq[color_of(pc)][type_of(pc)][s];
1147 /// Position::is_draw() tests whether the position is drawn by material, 50 moves
1148 /// rule or repetition. It does not detect stalemates.
1150 bool Position::is_draw() const {
1153 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1156 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1159 StateInfo* stp = st;
1160 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1162 stp = stp->previous->previous;
1164 if (stp->key == st->key)
1165 return true; // Draw at first repetition
1172 /// Position::flip() flips position with the white and black sides reversed. This
1173 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1175 static char toggle_case(char c) {
1176 return char(islower(c) ? toupper(c) : tolower(c));
1179 void Position::flip() {
1182 std::stringstream ss(fen());
1184 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1186 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1187 f.insert(0, token + (f.empty() ? " " : "/"));
1190 ss >> token; // Active color
1191 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1193 ss >> token; // Castling availability
1196 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1198 ss >> token; // En passant square
1199 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1201 std::getline(ss, token); // Half and full moves
1204 set(f, is_chess960(), this_thread());
1206 assert(pos_is_ok());
1210 /// Position::pos_is_ok() performs some consistency checks for the position object.
1211 /// This is meant to be helpful when debugging.
1213 bool Position::pos_is_ok(int* failedStep) const {
1215 int dummy, *step = failedStep ? failedStep : &dummy;
1217 // What features of the position should be verified?
1218 const bool all = false;
1220 const bool testBitboards = all || false;
1221 const bool testKingCount = all || false;
1222 const bool testKingCapture = all || false;
1223 const bool testCheckerCount = all || false;
1224 const bool testKeys = all || false;
1225 const bool testIncrementalEval = all || false;
1226 const bool testNonPawnMaterial = all || false;
1227 const bool testPieceCounts = all || false;
1228 const bool testPieceList = all || false;
1229 const bool testCastlingSquares = all || false;
1231 if (*step = 1, sideToMove != WHITE && sideToMove != BLACK)
1234 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1237 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1240 if ((*step)++, testKingCount)
1241 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1242 || std::count(board, board + SQUARE_NB, B_KING) != 1)
1245 if ((*step)++, testKingCapture)
1246 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1249 if ((*step)++, testCheckerCount && popcount<Full>(st->checkersBB) > 2)
1252 if ((*step)++, testBitboards)
1254 // The intersection of the white and black pieces must be empty
1255 if (pieces(WHITE) & pieces(BLACK))
1258 // The union of the white and black pieces must be equal to all
1260 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1263 // Separate piece type bitboards must have empty intersections
1264 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1265 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1266 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1270 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1273 if ((*step)++, testKeys)
1277 if (st->key != si.key || st->pawnKey != si.pawnKey || st->materialKey != si.materialKey)
1281 if ((*step)++, testNonPawnMaterial)
1284 compute_non_pawn_material(&si);
1285 if ( st->npMaterial[WHITE] != si.npMaterial[WHITE]
1286 || st->npMaterial[BLACK] != si.npMaterial[BLACK])
1290 if ((*step)++, testIncrementalEval && st->psq != compute_psq_score())
1293 if ((*step)++, testPieceCounts)
1294 for (Color c = WHITE; c <= BLACK; ++c)
1295 for (PieceType pt = PAWN; pt <= KING; ++pt)
1296 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1299 if ((*step)++, testPieceList)
1300 for (Color c = WHITE; c <= BLACK; ++c)
1301 for (PieceType pt = PAWN; pt <= KING; ++pt)
1302 for (int i = 0; i < pieceCount[c][pt]; ++i)
1303 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1304 || index[pieceList[c][pt][i]] != i)
1307 if ((*step)++, testCastlingSquares)
1308 for (Color c = WHITE; c <= BLACK; ++c)
1309 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1311 if (!can_castle(c | s))
1314 if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s)
1315 || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1316 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s))