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-2015 Marco Costalba, Joona Kiiski, Tord Romstad
5 Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
7 Stockfish is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
23 #include <cstring> // For std::memset, std::memcmp
39 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
40 Key enpassant[FILE_NB];
41 Key castling[CASTLING_RIGHT_NB];
46 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion; }
50 const string PieceToChar(" PNBRQK pnbrqk");
52 // min_attacker() is a helper function used by see() to locate the least
53 // valuable attacker for the side to move, remove the attacker we just found
54 // from the bitboards and scan for new X-ray attacks behind it.
57 PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
58 Bitboard& occupied, Bitboard& attackers) {
60 Bitboard b = stmAttackers & bb[Pt];
62 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
64 occupied ^= b & ~(b - 1);
66 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
67 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
69 if (Pt == ROOK || Pt == QUEEN)
70 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
72 attackers &= occupied; // After X-ray that may add already processed pieces
77 PieceType min_attacker<KING>(const Bitboard*, Square, Bitboard, Bitboard&, Bitboard&) {
78 return KING; // No need to update bitboards: it is the last cycle
84 /// operator<<(Position) returns an ASCII representation of the position
86 std::ostream& operator<<(std::ostream& os, const Position& pos) {
88 os << "\n +---+---+---+---+---+---+---+---+\n";
90 for (Rank r = RANK_8; r >= RANK_1; --r)
92 for (File f = FILE_A; f <= FILE_H; ++f)
93 os << " | " << PieceToChar[pos.piece_on(make_square(f, r))];
95 os << " |\n +---+---+---+---+---+---+---+---+\n";
98 os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase
99 << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: ";
101 for (Bitboard b = pos.checkers(); b; )
102 os << UCI::square(pop_lsb(&b)) << " ";
108 /// Position::init() initializes at startup the various arrays used to compute
111 void Position::init() {
115 for (Color c = WHITE; c <= BLACK; ++c)
116 for (PieceType pt = PAWN; pt <= KING; ++pt)
117 for (Square s = SQ_A1; s <= SQ_H8; ++s)
118 Zobrist::psq[c][pt][s] = rng.rand<Key>();
120 for (File f = FILE_A; f <= FILE_H; ++f)
121 Zobrist::enpassant[f] = rng.rand<Key>();
123 for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
125 Zobrist::castling[cr] = 0;
129 Key k = Zobrist::castling[1ULL << pop_lsb(&b)];
130 Zobrist::castling[cr] ^= k ? k : rng.rand<Key>();
134 Zobrist::side = rng.rand<Key>();
135 Zobrist::exclusion = rng.rand<Key>();
139 /// Position::set() initializes the position object with the given FEN string.
140 /// This function is not very robust - make sure that input FENs are correct,
141 /// this is assumed to be the responsibility of the GUI.
143 Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) {
145 A FEN string defines a particular position using only the ASCII character set.
147 A FEN string contains six fields separated by a space. The fields are:
149 1) Piece placement (from white's perspective). Each rank is described, starting
150 with rank 8 and ending with rank 1. Within each rank, the contents of each
151 square are described from file A through file H. Following the Standard
152 Algebraic Notation (SAN), each piece is identified by a single letter taken
153 from the standard English names. White pieces are designated using upper-case
154 letters ("PNBRQK") whilst Black uses lowercase ("pnbrqk"). Blank squares are
155 noted using digits 1 through 8 (the number of blank squares), and "/"
158 2) Active color. "w" means white moves next, "b" means black.
160 3) Castling availability. If neither side can castle, this is "-". Otherwise,
161 this has one or more letters: "K" (White can castle kingside), "Q" (White
162 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
163 can castle queenside).
165 4) En passant target square (in algebraic notation). If there's no en passant
166 target square, this is "-". If a pawn has just made a 2-square move, this
167 is the position "behind" the pawn. This is recorded regardless of whether
168 there is a pawn in position to make an en passant capture.
170 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
171 or capture. This is used to determine if a draw can be claimed under the
174 6) Fullmove number. The number of the full move. It starts at 1, and is
175 incremented after Black's move.
178 unsigned char col, row, token;
181 std::istringstream ss(fenStr);
183 std::memset(this, 0, sizeof(Position));
184 std::memset(si, 0, sizeof(StateInfo));
185 std::fill_n(&pieceList[0][0][0], sizeof(pieceList) / sizeof(Square), SQ_NONE);
190 // 1. Piece placement
191 while ((ss >> token) && !isspace(token))
194 sq += Square(token - '0'); // Advance the given number of files
196 else if (token == '/')
199 else if ((idx = PieceToChar.find(token)) != string::npos)
201 put_piece(color_of(Piece(idx)), type_of(Piece(idx)), sq);
208 sideToMove = (token == 'w' ? WHITE : BLACK);
211 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
212 // Shredder-FEN that uses the letters of the columns on which the rooks began
213 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
214 // if an inner rook is associated with the castling right, the castling tag is
215 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
216 while ((ss >> token) && !isspace(token))
219 Color c = islower(token) ? BLACK : WHITE;
220 Piece rook = make_piece(c, ROOK);
222 token = char(toupper(token));
225 for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) {}
227 else if (token == 'Q')
228 for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) {}
230 else if (token >= 'A' && token <= 'H')
231 rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1));
236 set_castling_right(c, rsq);
239 // 4. En passant square. Ignore if no pawn capture is possible
240 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
241 && ((ss >> row) && (row == '3' || row == '6')))
243 st->epSquare = make_square(File(col - 'a'), Rank(row - '1'));
245 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
246 st->epSquare = SQ_NONE;
249 st->epSquare = SQ_NONE;
251 // 5-6. Halfmove clock and fullmove number
252 ss >> std::skipws >> st->rule50 >> gamePly;
254 // Convert from fullmove starting from 1 to ply starting from 0,
255 // handle also common incorrect FEN with fullmove = 0.
256 gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK);
258 chess960 = isChess960;
268 /// Position::set_castling_right() is a helper function used to set castling
269 /// rights given the corresponding color and the rook starting square.
271 void Position::set_castling_right(Color c, Square rfrom) {
273 Square kfrom = square<KING>(c);
274 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
275 CastlingRight cr = (c | cs);
277 st->castlingRights |= cr;
278 castlingRightsMask[kfrom] |= cr;
279 castlingRightsMask[rfrom] |= cr;
280 castlingRookSquare[cr] = rfrom;
282 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
283 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
285 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
286 if (s != kfrom && s != rfrom)
287 castlingPath[cr] |= s;
289 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
290 if (s != kfrom && s != rfrom)
291 castlingPath[cr] |= s;
295 /// Position::set_check_info() sets king attacks to detect if a move gives check
297 void Position::set_check_info(CheckInfo* ci) const {
299 ci->blockersForKing[WHITE] = slider_blockers(pieces(BLACK), square<KING>(WHITE));
300 ci->blockersForKing[BLACK] = slider_blockers(pieces(WHITE), square<KING>(BLACK));
302 Square ksq = ci->ksq = square<KING>(~sideToMove);
304 ci->checkSquares[PAWN] = attacks_from<PAWN>(ksq, ~sideToMove);
305 ci->checkSquares[KNIGHT] = attacks_from<KNIGHT>(ksq);
306 ci->checkSquares[BISHOP] = attacks_from<BISHOP>(ksq);
307 ci->checkSquares[ROOK] = attacks_from<ROOK>(ksq);
308 ci->checkSquares[QUEEN] = ci->checkSquares[BISHOP] | ci->checkSquares[ROOK];
309 ci->checkSquares[KING] = 0;
313 /// Position::set_state() computes the hash keys of the position, and other
314 /// data that once computed is updated incrementally as moves are made.
315 /// The function is only used when a new position is set up, and to verify
316 /// the correctness of the StateInfo data when running in debug mode.
318 void Position::set_state(StateInfo* si) const {
320 si->key = si->pawnKey = si->materialKey = 0;
321 si->nonPawnMaterial[WHITE] = si->nonPawnMaterial[BLACK] = VALUE_ZERO;
322 si->psq = SCORE_ZERO;
323 si->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
325 set_check_info(&si->ci);
327 for (Bitboard b = pieces(); b; )
329 Square s = pop_lsb(&b);
330 Piece pc = piece_on(s);
331 si->key ^= Zobrist::psq[color_of(pc)][type_of(pc)][s];
332 si->psq += PSQT::psq[color_of(pc)][type_of(pc)][s];
335 if (si->epSquare != SQ_NONE)
336 si->key ^= Zobrist::enpassant[file_of(si->epSquare)];
338 if (sideToMove == BLACK)
339 si->key ^= Zobrist::side;
341 si->key ^= Zobrist::castling[si->castlingRights];
343 for (Bitboard b = pieces(PAWN); b; )
345 Square s = pop_lsb(&b);
346 si->pawnKey ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
349 for (Color c = WHITE; c <= BLACK; ++c)
350 for (PieceType pt = PAWN; pt <= KING; ++pt)
351 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
352 si->materialKey ^= Zobrist::psq[c][pt][cnt];
354 for (Color c = WHITE; c <= BLACK; ++c)
355 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
356 si->nonPawnMaterial[c] += pieceCount[c][pt] * PieceValue[MG][pt];
360 /// Position::fen() returns a FEN representation of the position. In case of
361 /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function.
363 const string Position::fen() const {
366 std::ostringstream ss;
368 for (Rank r = RANK_8; r >= RANK_1; --r)
370 for (File f = FILE_A; f <= FILE_H; ++f)
372 for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f)
379 ss << PieceToChar[piece_on(make_square(f, r))];
386 ss << (sideToMove == WHITE ? " w " : " b ");
388 if (can_castle(WHITE_OO))
389 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
391 if (can_castle(WHITE_OOO))
392 ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
394 if (can_castle(BLACK_OO))
395 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
397 if (can_castle(BLACK_OOO))
398 ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
400 if (!can_castle(WHITE) && !can_castle(BLACK))
403 ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ")
404 << st->rule50 << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2;
410 /// Position::game_phase() calculates the game phase interpolating total non-pawn
411 /// material between endgame and midgame limits.
413 Phase Position::game_phase() const {
415 Value npm = st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK];
417 npm = std::max(EndgameLimit, std::min(npm, MidgameLimit));
419 return Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
423 /// Position::slider_blockers() returns a bitboard of all the pieces (both colors) that
424 /// are blocking attacks on the square 's' from 'sliders'. A piece blocks a slider
425 /// if removing that piece from the board would result in a position where square 's'
426 /// is attacked. For example, a king-attack blocking piece can be either a pinned or
427 /// a discovered check piece, according if its color is the opposite or the same of
428 /// the color of the slider.
430 Bitboard Position::slider_blockers(Bitboard sliders, Square s) const {
432 Bitboard b, pinners, result = 0;
434 // Pinners are sliders that attack 's' when a pinned piece is removed
435 pinners = ( (PseudoAttacks[ROOK ][s] & pieces(QUEEN, ROOK))
436 | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
440 b = between_bb(s, pop_lsb(&pinners)) & pieces();
442 if (!more_than_one(b))
449 /// Position::attackers_to() computes a bitboard of all pieces which attack a
450 /// given square. Slider attacks use the occupied bitboard to indicate occupancy.
452 Bitboard Position::attackers_to(Square s, Bitboard occupied) const {
454 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
455 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
456 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
457 | (attacks_bb<ROOK >(s, occupied) & pieces(ROOK, QUEEN))
458 | (attacks_bb<BISHOP>(s, occupied) & pieces(BISHOP, QUEEN))
459 | (attacks_from<KING>(s) & pieces(KING));
463 /// Position::legal() tests whether a pseudo-legal move is legal
465 bool Position::legal(Move m) const {
469 Color us = sideToMove;
470 Square from = from_sq(m);
472 assert(color_of(moved_piece(m)) == us);
473 assert(piece_on(square<KING>(us)) == make_piece(us, KING));
475 // En passant captures are a tricky special case. Because they are rather
476 // uncommon, we do it simply by testing whether the king is attacked after
478 if (type_of(m) == ENPASSANT)
480 Square ksq = square<KING>(us);
481 Square to = to_sq(m);
482 Square capsq = to - pawn_push(us);
483 Bitboard occupied = (pieces() ^ from ^ capsq) | to;
485 assert(to == ep_square());
486 assert(moved_piece(m) == make_piece(us, PAWN));
487 assert(piece_on(capsq) == make_piece(~us, PAWN));
488 assert(piece_on(to) == NO_PIECE);
490 return !(attacks_bb< ROOK>(ksq, occupied) & pieces(~us, QUEEN, ROOK))
491 && !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
494 // If the moving piece is a king, check whether the destination
495 // square is attacked by the opponent. Castling moves are checked
496 // for legality during move generation.
497 if (type_of(piece_on(from)) == KING)
498 return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
500 // A non-king move is legal if and only if it is not pinned or it
501 // is moving along the ray towards or away from the king.
502 return !(pinned_pieces(us) & from)
503 || aligned(from, to_sq(m), square<KING>(us));
507 /// Position::pseudo_legal() takes a random move and tests whether the move is
508 /// pseudo legal. It is used to validate moves from TT that can be corrupted
509 /// due to SMP concurrent access or hash position key aliasing.
511 bool Position::pseudo_legal(const Move m) const {
513 Color us = sideToMove;
514 Square from = from_sq(m);
515 Square to = to_sq(m);
516 Piece pc = moved_piece(m);
518 // Use a slower but simpler function for uncommon cases
519 if (type_of(m) != NORMAL)
520 return MoveList<LEGAL>(*this).contains(m);
522 // Is not a promotion, so promotion piece must be empty
523 if (promotion_type(m) - KNIGHT != NO_PIECE_TYPE)
526 // If the 'from' square is not occupied by a piece belonging to the side to
527 // move, the move is obviously not legal.
528 if (pc == NO_PIECE || color_of(pc) != us)
531 // The destination square cannot be occupied by a friendly piece
535 // Handle the special case of a pawn move
536 if (type_of(pc) == PAWN)
538 // We have already handled promotion moves, so destination
539 // cannot be on the 8th/1st rank.
540 if (rank_of(to) == relative_rank(us, RANK_8))
543 if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
544 && !((from + pawn_push(us) == to) && empty(to)) // Not a single push
545 && !( (from + 2 * pawn_push(us) == to) // Not a double push
546 && (rank_of(from) == relative_rank(us, RANK_2))
548 && empty(to - pawn_push(us))))
551 else if (!(attacks_from(pc, from) & to))
554 // Evasions generator already takes care to avoid some kind of illegal moves
555 // and legal() relies on this. We therefore have to take care that the same
556 // kind of moves are filtered out here.
559 if (type_of(pc) != KING)
561 // Double check? In this case a king move is required
562 if (more_than_one(checkers()))
565 // Our move must be a blocking evasion or a capture of the checking piece
566 if (!((between_bb(lsb(checkers()), square<KING>(us)) | checkers()) & to))
569 // In case of king moves under check we have to remove king so as to catch
570 // invalid moves like b1a1 when opposite queen is on c1.
571 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
579 /// Position::gives_check() tests whether a pseudo-legal move gives a check
581 bool Position::gives_check(Move m) const {
584 assert(color_of(moved_piece(m)) == sideToMove);
586 Square from = from_sq(m);
587 Square to = to_sq(m);
589 // Is there a direct check?
590 if (st->ci.checkSquares[type_of(piece_on(from))] & to)
593 // Is there a discovered check?
594 if ( (discovered_check_candidates() & from)
595 && !aligned(from, to, st->ci.ksq))
604 return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & st->ci.ksq;
606 // En passant capture with check? We have already handled the case
607 // of direct checks and ordinary discovered check, so the only case we
608 // need to handle is the unusual case of a discovered check through
609 // the captured pawn.
612 Square capsq = make_square(file_of(to), rank_of(from));
613 Bitboard b = (pieces() ^ from ^ capsq) | to;
615 return (attacks_bb< ROOK>(st->ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK))
616 | (attacks_bb<BISHOP>(st->ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP));
621 Square rfrom = to; // Castling is encoded as 'King captures the rook'
622 Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1);
623 Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1);
625 return (PseudoAttacks[ROOK][rto] & st->ci.ksq)
626 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & st->ci.ksq);
635 /// Position::do_move() makes a move, and saves all information necessary
636 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
637 /// moves should be filtered out before this function is called.
639 void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
642 assert(&newSt != st);
645 Key k = st->key ^ Zobrist::side;
647 // Copy some fields of the old state to our new StateInfo object except the
648 // ones which are going to be recalculated from scratch anyway and then switch
649 // our state pointer to point to the new (ready to be updated) state.
650 std::memcpy(&newSt, st, offsetof(StateInfo, key));
654 // Increment ply counters. In particular, rule50 will be reset to zero later on
655 // in case of a capture or a pawn move.
660 Color us = sideToMove;
662 Square from = from_sq(m);
663 Square to = to_sq(m);
664 PieceType pt = type_of(piece_on(from));
665 PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
667 assert(color_of(piece_on(from)) == us);
668 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == (type_of(m) != CASTLING ? them : us));
669 assert(captured != KING);
671 if (type_of(m) == CASTLING)
676 do_castling<true>(us, from, to, rfrom, rto);
678 captured = NO_PIECE_TYPE;
679 st->psq += PSQT::psq[us][ROOK][rto] - PSQT::psq[us][ROOK][rfrom];
680 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
687 // If the captured piece is a pawn, update pawn hash key, otherwise
688 // update non-pawn material.
689 if (captured == PAWN)
691 if (type_of(m) == ENPASSANT)
693 capsq -= pawn_push(us);
696 assert(to == st->epSquare);
697 assert(relative_rank(us, to) == RANK_6);
698 assert(piece_on(to) == NO_PIECE);
699 assert(piece_on(capsq) == make_piece(them, PAWN));
701 board[capsq] = NO_PIECE; // Not done by remove_piece()
704 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
707 st->nonPawnMaterial[them] -= PieceValue[MG][captured];
709 // Update board and piece lists
710 remove_piece(them, captured, capsq);
712 // Update material hash key and prefetch access to materialTable
713 k ^= Zobrist::psq[them][captured][capsq];
714 st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]];
715 prefetch(thisThread->materialTable[st->materialKey]);
717 // Update incremental scores
718 st->psq -= PSQT::psq[them][captured][capsq];
720 // Reset rule 50 counter
725 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
727 // Reset en passant square
728 if (st->epSquare != SQ_NONE)
730 k ^= Zobrist::enpassant[file_of(st->epSquare)];
731 st->epSquare = SQ_NONE;
734 // Update castling rights if needed
735 if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to]))
737 int cr = castlingRightsMask[from] | castlingRightsMask[to];
738 k ^= Zobrist::castling[st->castlingRights & cr];
739 st->castlingRights &= ~cr;
742 // Move the piece. The tricky Chess960 castling is handled earlier
743 if (type_of(m) != CASTLING)
744 move_piece(us, pt, from, to);
746 // If the moving piece is a pawn do some special extra work
749 // Set en-passant square if the moved pawn can be captured
750 if ( (int(to) ^ int(from)) == 16
751 && (attacks_from<PAWN>(to - pawn_push(us), us) & pieces(them, PAWN)))
753 st->epSquare = (from + to) / 2;
754 k ^= Zobrist::enpassant[file_of(st->epSquare)];
757 else if (type_of(m) == PROMOTION)
759 PieceType promotion = promotion_type(m);
761 assert(relative_rank(us, to) == RANK_8);
762 assert(promotion >= KNIGHT && promotion <= QUEEN);
764 remove_piece(us, PAWN, to);
765 put_piece(us, promotion, to);
768 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
769 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
770 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
771 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
773 // Update incremental score
774 st->psq += PSQT::psq[us][promotion][to] - PSQT::psq[us][PAWN][to];
777 st->nonPawnMaterial[us] += PieceValue[MG][promotion];
780 // Update pawn hash key and prefetch access to pawnsTable
781 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
782 prefetch(thisThread->pawnsTable[st->pawnKey]);
784 // Reset rule 50 draw counter
788 // Update incremental scores
789 st->psq += PSQT::psq[us][pt][to] - PSQT::psq[us][pt][from];
792 st->capturedType = captured;
794 // Update the key with the final value
797 // Calculate checkers bitboard (if move gives check)
798 st->checkersBB = givesCheck ? attackers_to(square<KING>(them)) & pieces(us) : 0;
800 sideToMove = ~sideToMove;
803 set_check_info(&st->ci);
809 /// Position::undo_move() unmakes a move. When it returns, the position should
810 /// be restored to exactly the same state as before the move was made.
812 void Position::undo_move(Move m) {
816 sideToMove = ~sideToMove;
818 Color us = sideToMove;
819 Square from = from_sq(m);
820 Square to = to_sq(m);
821 PieceType pt = type_of(piece_on(to));
823 assert(empty(from) || type_of(m) == CASTLING);
824 assert(st->capturedType != KING);
826 if (type_of(m) == PROMOTION)
828 assert(relative_rank(us, to) == RANK_8);
829 assert(pt == promotion_type(m));
830 assert(pt >= KNIGHT && pt <= QUEEN);
832 remove_piece(us, pt, to);
833 put_piece(us, PAWN, to);
837 if (type_of(m) == CASTLING)
840 do_castling<false>(us, from, to, rfrom, rto);
844 move_piece(us, pt, to, from); // Put the piece back at the source square
846 if (st->capturedType)
850 if (type_of(m) == ENPASSANT)
852 capsq -= pawn_push(us);
855 assert(to == st->previous->epSquare);
856 assert(relative_rank(us, to) == RANK_6);
857 assert(piece_on(capsq) == NO_PIECE);
858 assert(st->capturedType == PAWN);
861 put_piece(~us, st->capturedType, capsq); // Restore the captured piece
865 // Finally point our state pointer back to the previous state
873 /// Position::do_castling() is a helper used to do/undo a castling move. This
874 /// is a bit tricky, especially in Chess960.
876 void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) {
878 bool kingSide = to > from;
879 rfrom = to; // Castling is encoded as "king captures friendly rook"
880 rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
881 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
883 // Remove both pieces first since squares could overlap in Chess960
884 remove_piece(us, KING, Do ? from : to);
885 remove_piece(us, ROOK, Do ? rfrom : rto);
886 board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us
887 put_piece(us, KING, Do ? to : from);
888 put_piece(us, ROOK, Do ? rto : rfrom);
892 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
893 /// the side to move without executing any move on the board.
895 void Position::do_null_move(StateInfo& newSt) {
898 assert(&newSt != st);
900 std::memcpy(&newSt, st, sizeof(StateInfo));
904 if (st->epSquare != SQ_NONE)
906 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
907 st->epSquare = SQ_NONE;
910 st->key ^= Zobrist::side;
911 prefetch(TT.first_entry(st->key));
914 st->pliesFromNull = 0;
916 sideToMove = ~sideToMove;
918 set_check_info(&st->ci);
923 void Position::undo_null_move() {
928 sideToMove = ~sideToMove;
932 /// Position::key_after() computes the new hash key after the given move. Needed
933 /// for speculative prefetch. It doesn't recognize special moves like castling,
934 /// en-passant and promotions.
936 Key Position::key_after(Move m) const {
938 Color us = sideToMove;
939 Square from = from_sq(m);
940 Square to = to_sq(m);
941 PieceType pt = type_of(piece_on(from));
942 PieceType captured = type_of(piece_on(to));
943 Key k = st->key ^ Zobrist::side;
946 k ^= Zobrist::psq[~us][captured][to];
948 return k ^ Zobrist::psq[us][pt][to] ^ Zobrist::psq[us][pt][from];
952 /// Position::see() is a static exchange evaluator: It tries to estimate the
953 /// material gain or loss resulting from a move.
955 Value Position::see_sign(Move m) const {
959 // Early return if SEE cannot be negative because captured piece value
960 // is not less then capturing one. Note that king moves always return
961 // here because king midgame value is set to 0.
962 if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
963 return VALUE_KNOWN_WIN;
968 Value Position::see(Move m) const {
971 Bitboard occupied, attackers, stmAttackers;
981 swapList[0] = PieceValue[MG][piece_on(to)];
982 stm = color_of(piece_on(from));
983 occupied = pieces() ^ from;
985 // Castling moves are implemented as king capturing the rook so cannot
986 // be handled correctly. Simply return VALUE_ZERO that is always correct
987 // unless in the rare case the rook ends up under attack.
988 if (type_of(m) == CASTLING)
991 if (type_of(m) == ENPASSANT)
993 occupied ^= to - pawn_push(stm); // Remove the captured pawn
994 swapList[0] = PieceValue[MG][PAWN];
997 // Find all attackers to the destination square, with the moving piece
998 // removed, but possibly an X-ray attacker added behind it.
999 attackers = attackers_to(to, occupied) & occupied;
1001 // If the opponent has no attackers we are finished
1003 stmAttackers = attackers & pieces(stm);
1007 // The destination square is defended, which makes things rather more
1008 // difficult to compute. We proceed by building up a "swap list" containing
1009 // the material gain or loss at each stop in a sequence of captures to the
1010 // destination square, where the sides alternately capture, and always
1011 // capture with the least valuable piece. After each capture, we look for
1012 // new X-ray attacks from behind the capturing piece.
1013 captured = type_of(piece_on(from));
1016 assert(slIndex < 32);
1018 // Add the new entry to the swap list
1019 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1021 // Locate and remove the next least valuable attacker
1022 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1024 stmAttackers = attackers & pieces(stm);
1027 } while (stmAttackers && (captured != KING || (--slIndex, false))); // Stop before a king capture
1029 // Having built the swap list, we negamax through it to find the best
1030 // achievable score from the point of view of the side to move.
1032 swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
1038 /// Position::is_draw() tests whether the position is drawn by 50-move rule
1039 /// or by repetition. It does not detect stalemates.
1041 bool Position::is_draw() const {
1043 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1046 StateInfo* stp = st;
1047 for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2)
1049 stp = stp->previous->previous;
1051 if (stp->key == st->key)
1052 return true; // Draw at first repetition
1059 /// Position::flip() flips position with the white and black sides reversed. This
1060 /// is only useful for debugging e.g. for finding evaluation symmetry bugs.
1062 void Position::flip() {
1065 std::stringstream ss(fen());
1067 for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement
1069 std::getline(ss, token, r > RANK_1 ? '/' : ' ');
1070 f.insert(0, token + (f.empty() ? " " : "/"));
1073 ss >> token; // Active color
1074 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1076 ss >> token; // Castling availability
1079 std::transform(f.begin(), f.end(), f.begin(),
1080 [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); });
1082 ss >> token; // En passant square
1083 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1085 std::getline(ss, token); // Half and full moves
1088 set(f, is_chess960(), st, this_thread());
1090 assert(pos_is_ok());
1094 /// Position::pos_is_ok() performs some consistency checks for the position object.
1095 /// This is meant to be helpful when debugging.
1097 bool Position::pos_is_ok(int* failedStep) const {
1099 const bool Fast = true; // Quick (default) or full check?
1101 enum { Default, King, Bitboards, State, Lists, Castling };
1103 for (int step = Default; step <= (Fast ? Default : Castling); step++)
1108 if (step == Default)
1109 if ( (sideToMove != WHITE && sideToMove != BLACK)
1110 || piece_on(square<KING>(WHITE)) != W_KING
1111 || piece_on(square<KING>(BLACK)) != B_KING
1112 || ( ep_square() != SQ_NONE
1113 && relative_rank(sideToMove, ep_square()) != RANK_6))
1117 if ( std::count(board, board + SQUARE_NB, W_KING) != 1
1118 || std::count(board, board + SQUARE_NB, B_KING) != 1
1119 || attackers_to(square<KING>(~sideToMove)) & pieces(sideToMove))
1122 if (step == Bitboards)
1124 if ( (pieces(WHITE) & pieces(BLACK))
1125 ||(pieces(WHITE) | pieces(BLACK)) != pieces())
1128 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1129 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1130 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1138 if (std::memcmp(&si, st, sizeof(StateInfo)))
1143 for (Color c = WHITE; c <= BLACK; ++c)
1144 for (PieceType pt = PAWN; pt <= KING; ++pt)
1146 if (pieceCount[c][pt] != popcount(pieces(c, pt)))
1149 for (int i = 0; i < pieceCount[c][pt]; ++i)
1150 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1151 || index[pieceList[c][pt][i]] != i)
1155 if (step == Castling)
1156 for (Color c = WHITE; c <= BLACK; ++c)
1157 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1159 if (!can_castle(c | s))
1162 if ( piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK)
1163 || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)
1164 ||(castlingRightsMask[square<KING>(c)] & (c | s)) != (c | s))