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/>.
40 static const string PieceToChar(" PNBRQK pnbrqk");
44 Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
45 Value PieceValue[PHASE_NB][PIECE_NB] = {
46 { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg },
47 { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } };
51 Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
52 Key enpassant[FILE_NB];
53 Key castle[CASTLE_RIGHT_NB];
58 Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;}
62 // min_attacker() is an helper function used by see() to locate the least
63 // valuable attacker for the side to move, remove the attacker we just found
64 // from the bitboards and scan for new X-ray attacks behind it.
66 template<int Pt> FORCE_INLINE
67 PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers,
68 Bitboard& occupied, Bitboard& attackers) {
70 Bitboard b = stmAttackers & bb[Pt];
72 return min_attacker<Pt+1>(bb, to, stmAttackers, occupied, attackers);
74 occupied ^= b & ~(b - 1);
76 if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
77 attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
79 if (Pt == ROOK || Pt == QUEEN)
80 attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
82 attackers &= occupied; // After X-ray that may add already processed pieces
86 template<> FORCE_INLINE
87 PieceType min_attacker<KING>(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) {
88 return KING; // No need to update bitboards, it is the last cycle
96 CheckInfo::CheckInfo(const Position& pos) {
98 Color them = ~pos.side_to_move();
99 ksq = pos.king_square(them);
101 pinned = pos.pinned_pieces();
102 dcCandidates = pos.discovered_check_candidates();
104 checkSq[PAWN] = pos.attacks_from<PAWN>(ksq, them);
105 checkSq[KNIGHT] = pos.attacks_from<KNIGHT>(ksq);
106 checkSq[BISHOP] = pos.attacks_from<BISHOP>(ksq);
107 checkSq[ROOK] = pos.attacks_from<ROOK>(ksq);
108 checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK];
113 /// Position::init() initializes at startup the various arrays used to compute
114 /// hash keys and the piece square tables. The latter is a two-step operation:
115 /// First, the white halves of the tables are copied from PSQT[] tables. Second,
116 /// the black halves of the tables are initialized by flipping and changing the
117 /// sign of the white scores.
119 void Position::init() {
123 for (Color c = WHITE; c <= BLACK; c++)
124 for (PieceType pt = PAWN; pt <= KING; pt++)
125 for (Square s = SQ_A1; s <= SQ_H8; s++)
126 Zobrist::psq[c][pt][s] = rk.rand<Key>();
128 for (File f = FILE_A; f <= FILE_H; f++)
129 Zobrist::enpassant[f] = rk.rand<Key>();
131 for (int cr = CASTLES_NONE; cr <= ALL_CASTLES; cr++)
136 Key k = Zobrist::castle[1ULL << pop_lsb(&b)];
137 Zobrist::castle[cr] ^= k ? k : rk.rand<Key>();
141 Zobrist::side = rk.rand<Key>();
142 Zobrist::exclusion = rk.rand<Key>();
144 for (PieceType pt = PAWN; pt <= KING; pt++)
146 PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt];
147 PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt];
149 Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]);
151 for (Square s = SQ_A1; s <= SQ_H8; s++)
153 psq[WHITE][pt][ s] = (v + PSQT[pt][s]);
154 psq[BLACK][pt][~s] = -(v + PSQT[pt][s]);
160 /// Position::operator=() creates a copy of 'pos'. We want the new born Position
161 /// object do not depend on any external data so we detach state pointer from
164 Position& Position::operator=(const Position& pos) {
166 std::memcpy(this, &pos, sizeof(Position));
177 /// Position::set() initializes the position object with the given FEN string.
178 /// This function is not very robust - make sure that input FENs are correct,
179 /// this is assumed to be the responsibility of the GUI.
181 void Position::set(const string& fenStr, bool isChess960, Thread* th) {
183 A FEN string defines a particular position using only the ASCII character set.
185 A FEN string contains six fields separated by a space. The fields are:
187 1) Piece placement (from white's perspective). Each rank is described, starting
188 with rank 8 and ending with rank 1; within each rank, the contents of each
189 square are described from file A through file H. Following the Standard
190 Algebraic Notation (SAN), each piece is identified by a single letter taken
191 from the standard English names. White pieces are designated using upper-case
192 letters ("PNBRQK") while Black take lowercase ("pnbrqk"). Blank squares are
193 noted using digits 1 through 8 (the number of blank squares), and "/"
196 2) Active color. "w" means white moves next, "b" means black.
198 3) Castling availability. If neither side can castle, this is "-". Otherwise,
199 this has one or more letters: "K" (White can castle kingside), "Q" (White
200 can castle queenside), "k" (Black can castle kingside), and/or "q" (Black
201 can castle queenside).
203 4) En passant target square (in algebraic notation). If there's no en passant
204 target square, this is "-". If a pawn has just made a 2-square move, this
205 is the position "behind" the pawn. This is recorded regardless of whether
206 there is a pawn in position to make an en passant capture.
208 5) Halfmove clock. This is the number of halfmoves since the last pawn advance
209 or capture. This is used to determine if a draw can be claimed under the
212 6) Fullmove number. The number of the full move. It starts at 1, and is
213 incremented after Black's move.
216 char col, row, token;
219 std::istringstream ss(fenStr);
224 // 1. Piece placement
225 while ((ss >> token) && !isspace(token))
228 sq += Square(token - '0'); // Advance the given number of files
230 else if (token == '/')
233 else if ((p = PieceToChar.find(token)) != string::npos)
235 put_piece(sq, color_of(Piece(p)), type_of(Piece(p)));
242 sideToMove = (token == 'w' ? WHITE : BLACK);
245 // 3. Castling availability. Compatible with 3 standards: Normal FEN standard,
246 // Shredder-FEN that uses the letters of the columns on which the rooks began
247 // the game instead of KQkq and also X-FEN standard that, in case of Chess960,
248 // if an inner rook is associated with the castling right, the castling tag is
249 // replaced by the file letter of the involved rook, as for the Shredder-FEN.
250 while ((ss >> token) && !isspace(token))
253 Color c = islower(token) ? BLACK : WHITE;
255 token = char(toupper(token));
258 for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; rsq--) {}
260 else if (token == 'Q')
261 for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; rsq++) {}
263 else if (token >= 'A' && token <= 'H')
264 rsq = File(token - 'A') | relative_rank(c, RANK_1);
269 set_castle_right(c, rsq);
272 // 4. En passant square. Ignore if no pawn capture is possible
273 if ( ((ss >> col) && (col >= 'a' && col <= 'h'))
274 && ((ss >> row) && (row == '3' || row == '6')))
276 st->epSquare = File(col - 'a') | Rank(row - '1');
278 if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)))
279 st->epSquare = SQ_NONE;
282 // 5-6. Halfmove clock and fullmove number
283 ss >> std::skipws >> st->rule50 >> gamePly;
285 // Convert from fullmove starting from 1 to ply starting from 0,
286 // handle also common incorrect FEN with fullmove = 0.
287 gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK);
289 st->key = compute_key();
290 st->pawnKey = compute_pawn_key();
291 st->materialKey = compute_material_key();
292 st->psq = compute_psq_score();
293 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
294 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
295 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
296 chess960 = isChess960;
303 /// Position::set_castle_right() is an helper function used to set castling
304 /// rights given the corresponding color and the rook starting square.
306 void Position::set_castle_right(Color c, Square rfrom) {
308 Square kfrom = king_square(c);
309 CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE;
310 CastleRight cr = make_castle_right(c, cs);
312 st->castleRights |= cr;
313 castleRightsMask[kfrom] |= cr;
314 castleRightsMask[rfrom] |= cr;
315 castleRookSquare[c][cs] = rfrom;
317 Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
318 Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
320 for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
321 if (s != kfrom && s != rfrom)
322 castlePath[c][cs] |= s;
324 for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
325 if (s != kfrom && s != rfrom)
326 castlePath[c][cs] |= s;
330 /// Position::fen() returns a FEN representation of the position. In case
331 /// of Chess960 the Shredder-FEN notation is used. Mainly a debugging function.
333 const string Position::fen() const {
335 std::ostringstream ss;
337 for (Rank rank = RANK_8; rank >= RANK_1; rank--)
339 for (File file = FILE_A; file <= FILE_H; file++)
341 Square sq = file | rank;
347 for ( ; file < FILE_H && is_empty(sq++); file++)
353 ss << PieceToChar[piece_on(sq)];
360 ss << (sideToMove == WHITE ? " w " : " b ");
362 if (can_castle(WHITE_OO))
363 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, KING_SIDE)), false) : 'K');
365 if (can_castle(WHITE_OOO))
366 ss << (chess960 ? file_to_char(file_of(castle_rook_square(WHITE, QUEEN_SIDE)), false) : 'Q');
368 if (can_castle(BLACK_OO))
369 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, KING_SIDE)), true) : 'k');
371 if (can_castle(BLACK_OOO))
372 ss << (chess960 ? file_to_char(file_of(castle_rook_square(BLACK, QUEEN_SIDE)), true) : 'q');
374 if (st->castleRights == CASTLES_NONE)
377 ss << (ep_square() == SQ_NONE ? " - " : " " + square_to_string(ep_square()) + " ")
378 << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2;
384 /// Position::pretty() returns an ASCII representation of the position to be
385 /// printed to the standard output together with the move's san notation.
387 const string Position::pretty(Move move) const {
389 const string dottedLine = "\n+---+---+---+---+---+---+---+---+";
390 const string twoRows = dottedLine + "\n| | . | | . | | . | | . |"
391 + dottedLine + "\n| . | | . | | . | | . | |";
393 string brd = twoRows + twoRows + twoRows + twoRows + dottedLine;
395 for (Bitboard b = pieces(); b; )
397 Square s = pop_lsb(&b);
398 brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)];
401 std::ostringstream ss;
404 ss << "\nMove: " << (sideToMove == BLACK ? ".." : "")
405 << move_to_san(*const_cast<Position*>(this), move);
407 ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase
408 << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: ";
410 for (Bitboard b = checkers(); b; )
411 ss << square_to_string(pop_lsb(&b)) << " ";
413 ss << "\nLegal moves: ";
414 for (MoveList<LEGAL> it(*this); *it; ++it)
415 ss << move_to_san(*const_cast<Position*>(this), *it) << " ";
421 /// Position:hidden_checkers() returns a bitboard of all pinned / discovery check
422 /// pieces, according to the call parameters. Pinned pieces protect our king,
423 /// discovery check pieces attack the enemy king.
425 Bitboard Position::hidden_checkers(Square ksq, Color c) const {
427 Bitboard b, pinners, result = 0;
429 // Pinners are sliders that give check when pinned piece is removed
430 pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq])
431 | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(c);
435 b = between_bb(ksq, pop_lsb(&pinners)) & pieces();
437 if (!more_than_one(b))
438 result |= b & pieces(sideToMove);
444 /// Position::attackers_to() computes a bitboard of all pieces which attack a
445 /// given square. Slider attacks use occ bitboard as occupancy.
447 Bitboard Position::attackers_to(Square s, Bitboard occ) const {
449 return (attacks_from<PAWN>(s, BLACK) & pieces(WHITE, PAWN))
450 | (attacks_from<PAWN>(s, WHITE) & pieces(BLACK, PAWN))
451 | (attacks_from<KNIGHT>(s) & pieces(KNIGHT))
452 | (attacks_bb<ROOK>(s, occ) & pieces(ROOK, QUEEN))
453 | (attacks_bb<BISHOP>(s, occ) & pieces(BISHOP, QUEEN))
454 | (attacks_from<KING>(s) & pieces(KING));
458 /// Position::attacks_from() computes a bitboard of all attacks of a given piece
459 /// put in a given square. Slider attacks use occ bitboard as occupancy.
461 Bitboard Position::attacks_from(Piece p, Square s, Bitboard occ) {
467 case BISHOP: return attacks_bb<BISHOP>(s, occ);
468 case ROOK : return attacks_bb<ROOK>(s, occ);
469 case QUEEN : return attacks_bb<BISHOP>(s, occ) | attacks_bb<ROOK>(s, occ);
470 default : return StepAttacksBB[p][s];
475 /// Position::pl_move_is_legal() tests whether a pseudo-legal move is legal
477 bool Position::pl_move_is_legal(Move m, Bitboard pinned) const {
480 assert(pinned == pinned_pieces());
482 Color us = sideToMove;
483 Square from = from_sq(m);
485 assert(color_of(piece_moved(m)) == us);
486 assert(piece_on(king_square(us)) == make_piece(us, KING));
488 // En passant captures are a tricky special case. Because they are rather
489 // uncommon, we do it simply by testing whether the king is attacked after
491 if (type_of(m) == ENPASSANT)
494 Square to = to_sq(m);
495 Square capsq = to + pawn_push(them);
496 Square ksq = king_square(us);
497 Bitboard b = (pieces() ^ from ^ capsq) | to;
499 assert(to == ep_square());
500 assert(piece_moved(m) == make_piece(us, PAWN));
501 assert(piece_on(capsq) == make_piece(them, PAWN));
502 assert(piece_on(to) == NO_PIECE);
504 return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK))
505 && !(attacks_bb<BISHOP>(ksq, b) & pieces(them, QUEEN, BISHOP));
508 // If the moving piece is a king, check whether the destination
509 // square is attacked by the opponent. Castling moves are checked
510 // for legality during move generation.
511 if (type_of(piece_on(from)) == KING)
512 return type_of(m) == CASTLE || !(attackers_to(to_sq(m)) & pieces(~us));
514 // A non-king move is legal if and only if it is not pinned or it
515 // is moving along the ray towards or away from the king.
518 || squares_aligned(from, to_sq(m), king_square(us));
522 /// Position::is_pseudo_legal() takes a random move and tests whether the move
523 /// is pseudo legal. It is used to validate moves from TT that can be corrupted
524 /// due to SMP concurrent access or hash position key aliasing.
526 bool Position::is_pseudo_legal(const Move m) const {
528 Color us = sideToMove;
529 Square from = from_sq(m);
530 Square to = to_sq(m);
531 Piece pc = piece_moved(m);
533 // Use a slower but simpler function for uncommon cases
534 if (type_of(m) != NORMAL)
535 return MoveList<LEGAL>(*this).contains(m);
537 // Is not a promotion, so promotion piece must be empty
538 if (promotion_type(m) - 2 != NO_PIECE_TYPE)
541 // If the from square is not occupied by a piece belonging to the side to
542 // move, the move is obviously not legal.
543 if (pc == NO_PIECE || color_of(pc) != us)
546 // The destination square cannot be occupied by a friendly piece
550 // Handle the special case of a pawn move
551 if (type_of(pc) == PAWN)
553 // Move direction must be compatible with pawn color
554 int direction = to - from;
555 if ((us == WHITE) != (direction > 0))
558 // We have already handled promotion moves, so destination
559 // cannot be on the 8/1th rank.
560 if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1)
563 // Proceed according to the square delta between the origin and
564 // destination squares.
571 // Capture. The destination square must be occupied by an enemy
572 // piece (en passant captures was handled earlier).
573 if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us)
576 // From and to files must be one file apart, avoids a7h5
577 if (abs(file_of(from) - file_of(to)) != 1)
583 // Pawn push. The destination square must be empty.
589 // Double white pawn push. The destination square must be on the fourth
590 // rank, and both the destination square and the square between the
591 // source and destination squares must be empty.
592 if ( rank_of(to) != RANK_4
594 || !is_empty(from + DELTA_N))
599 // Double black pawn push. The destination square must be on the fifth
600 // rank, and both the destination square and the square between the
601 // source and destination squares must be empty.
602 if ( rank_of(to) != RANK_5
604 || !is_empty(from + DELTA_S))
612 else if (!(attacks_from(pc, from) & to))
615 // Evasions generator already takes care to avoid some kind of illegal moves
616 // and pl_move_is_legal() relies on this. So we have to take care that the
617 // same kind of moves are filtered out here.
620 if (type_of(pc) != KING)
622 // Double check? In this case a king move is required
623 if (more_than_one(checkers()))
626 // Our move must be a blocking evasion or a capture of the checking piece
627 if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to))
630 // In case of king moves under check we have to remove king so to catch
631 // as invalid moves like b1a1 when opposite queen is on c1.
632 else if (attackers_to(to, pieces() ^ from) & pieces(~us))
640 /// Position::move_gives_check() tests whether a pseudo-legal move gives a check
642 bool Position::move_gives_check(Move m, const CheckInfo& ci) const {
645 assert(ci.dcCandidates == discovered_check_candidates());
646 assert(color_of(piece_moved(m)) == sideToMove);
648 Square from = from_sq(m);
649 Square to = to_sq(m);
650 PieceType pt = type_of(piece_on(from));
653 if (ci.checkSq[pt] & to)
657 if (unlikely(ci.dcCandidates) && (ci.dcCandidates & from))
659 // For pawn and king moves we need to verify also direction
660 if ( (pt != PAWN && pt != KING)
661 || !squares_aligned(from, to, king_square(~sideToMove)))
665 // Can we skip the ugly special cases ?
666 if (type_of(m) == NORMAL)
669 Color us = sideToMove;
670 Square ksq = king_square(~us);
675 return attacks_from(Piece(promotion_type(m)), to, pieces() ^ from) & ksq;
677 // En passant capture with check ? We have already handled the case
678 // of direct checks and ordinary discovered check, the only case we
679 // need to handle is the unusual case of a discovered check through
680 // the captured pawn.
683 Square capsq = file_of(to) | rank_of(from);
684 Bitboard b = (pieces() ^ from ^ capsq) | to;
686 return (attacks_bb< ROOK>(ksq, b) & pieces(us, QUEEN, ROOK))
687 | (attacks_bb<BISHOP>(ksq, b) & pieces(us, QUEEN, BISHOP));
692 Square rfrom = to; // 'King captures the rook' notation
693 Square kto = relative_square(us, rfrom > kfrom ? SQ_G1 : SQ_C1);
694 Square rto = relative_square(us, rfrom > kfrom ? SQ_F1 : SQ_D1);
696 return (PseudoAttacks[ROOK][rto] & ksq)
697 && (attacks_bb<ROOK>(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ksq);
706 /// Position::do_move() makes a move, and saves all information necessary
707 /// to a StateInfo object. The move is assumed to be legal. Pseudo-legal
708 /// moves should be filtered out before this function is called.
710 void Position::do_move(Move m, StateInfo& newSt) {
713 do_move(m, newSt, ci, move_gives_check(m, ci));
716 void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) {
719 assert(&newSt != st);
724 // Copy some fields of old state to our new StateInfo object except the ones
725 // which are going to be recalculated from scratch anyway, then switch our state
726 // pointer to point to the new, ready to be updated, state.
727 std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t));
732 // Update side to move
735 // Increment ply counters.In particular rule50 will be later reset it to zero
736 // in case of a capture or a pawn move.
741 Color us = sideToMove;
743 Square from = from_sq(m);
744 Square to = to_sq(m);
745 Piece pc = piece_on(from);
746 PieceType pt = type_of(pc);
747 PieceType capture = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to));
749 assert(color_of(pc) == us);
750 assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLE);
751 assert(capture != KING);
753 if (type_of(m) == CASTLE)
755 assert(pc == make_piece(us, KING));
757 bool kingSide = to > from;
758 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
759 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
760 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
761 capture = NO_PIECE_TYPE;
763 do_castle(from, to, rfrom, rto);
765 st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom];
766 k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto];
773 // If the captured piece is a pawn, update pawn hash key, otherwise
774 // update non-pawn material.
777 if (type_of(m) == ENPASSANT)
779 capsq += pawn_push(them);
782 assert(to == st->epSquare);
783 assert(relative_rank(us, to) == RANK_6);
784 assert(piece_on(to) == NO_PIECE);
785 assert(piece_on(capsq) == make_piece(them, PAWN));
787 board[capsq] = NO_PIECE;
790 st->pawnKey ^= Zobrist::psq[them][PAWN][capsq];
793 st->npMaterial[them] -= PieceValue[MG][capture];
795 // Update board and piece lists
796 remove_piece(capsq, them, capture);
798 // Update material hash key and prefetch access to materialTable
799 k ^= Zobrist::psq[them][capture][capsq];
800 st->materialKey ^= Zobrist::psq[them][capture][pieceCount[them][capture]];
801 prefetch((char*)thisThread->materialTable[st->materialKey]);
803 // Update incremental scores
804 st->psq -= psq[them][capture][capsq];
806 // Reset rule 50 counter
811 k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to];
813 // Reset en passant square
814 if (st->epSquare != SQ_NONE)
816 k ^= Zobrist::enpassant[file_of(st->epSquare)];
817 st->epSquare = SQ_NONE;
820 // Update castle rights if needed
821 if (st->castleRights && (castleRightsMask[from] | castleRightsMask[to]))
823 int cr = castleRightsMask[from] | castleRightsMask[to];
824 k ^= Zobrist::castle[st->castleRights & cr];
825 st->castleRights &= ~cr;
828 // Prefetch TT access as soon as we know the new hash key
829 prefetch((char*)TT.first_entry(k));
831 // Move the piece. The tricky Chess960 castle is handled earlier
832 if (type_of(m) != CASTLE)
833 move_piece(from, to, us, pt);
835 // If the moving piece is a pawn do some special extra work
838 // Set en-passant square, only if moved pawn can be captured
839 if ( (int(to) ^ int(from)) == 16
840 && (attacks_from<PAWN>(from + pawn_push(us), us) & pieces(them, PAWN)))
842 st->epSquare = Square((from + to) / 2);
843 k ^= Zobrist::enpassant[file_of(st->epSquare)];
846 if (type_of(m) == PROMOTION)
848 PieceType promotion = promotion_type(m);
850 assert(relative_rank(us, to) == RANK_8);
851 assert(promotion >= KNIGHT && promotion <= QUEEN);
853 remove_piece(to, us, PAWN);
854 put_piece(to, us, promotion);
857 k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to];
858 st->pawnKey ^= Zobrist::psq[us][PAWN][to];
859 st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1]
860 ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]];
862 // Update incremental score
863 st->psq += psq[us][promotion][to] - psq[us][PAWN][to];
866 st->npMaterial[us] += PieceValue[MG][promotion];
869 // Update pawn hash key and prefetch access to pawnsTable
870 st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to];
871 prefetch((char*)thisThread->pawnsTable[st->pawnKey]);
873 // Reset rule 50 draw counter
877 // Update incremental scores
878 st->psq += psq[us][pt][to] - psq[us][pt][from];
881 st->capturedType = capture;
883 // Update the key with the final value
886 // Update checkers bitboard, piece must be already moved
891 if (type_of(m) != NORMAL)
892 st->checkersBB = attackers_to(king_square(them)) & pieces(us);
896 if (ci.checkSq[pt] & to)
897 st->checkersBB |= to;
900 if (ci.dcCandidates && (ci.dcCandidates & from))
903 st->checkersBB |= attacks_from<ROOK>(king_square(them)) & pieces(us, QUEEN, ROOK);
906 st->checkersBB |= attacks_from<BISHOP>(king_square(them)) & pieces(us, QUEEN, BISHOP);
911 sideToMove = ~sideToMove;
917 /// Position::undo_move() unmakes a move. When it returns, the position should
918 /// be restored to exactly the same state as before the move was made.
920 void Position::undo_move(Move m) {
924 sideToMove = ~sideToMove;
926 Color us = sideToMove;
928 Square from = from_sq(m);
929 Square to = to_sq(m);
930 PieceType pt = type_of(piece_on(to));
931 PieceType capture = st->capturedType;
933 assert(is_empty(from) || type_of(m) == CASTLE);
934 assert(capture != KING);
936 if (type_of(m) == PROMOTION)
938 PieceType promotion = promotion_type(m);
940 assert(promotion == pt);
941 assert(relative_rank(us, to) == RANK_8);
942 assert(promotion >= KNIGHT && promotion <= QUEEN);
944 remove_piece(to, us, promotion);
945 put_piece(to, us, PAWN);
949 if (type_of(m) == CASTLE)
951 bool kingSide = to > from;
952 Square rfrom = to; // Castle is encoded as "king captures friendly rook"
953 Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1);
954 to = relative_square(us, kingSide ? SQ_G1 : SQ_C1);
955 capture = NO_PIECE_TYPE;
957 do_castle(to, from, rto, rfrom);
960 move_piece(to, from, us, pt); // Put the piece back at the source square
966 if (type_of(m) == ENPASSANT)
968 capsq -= pawn_push(us);
971 assert(to == st->previous->epSquare);
972 assert(relative_rank(us, to) == RANK_6);
973 assert(piece_on(capsq) == NO_PIECE);
976 put_piece(capsq, them, capture); // Restore the captured piece
979 // Finally point our state pointer back to the previous state
987 /// Position::do_castle() is a helper used to do/undo a castling move. This
988 /// is a bit tricky, especially in Chess960.
990 void Position::do_castle(Square kfrom, Square kto, Square rfrom, Square rto) {
992 Color us = sideToMove;
993 Bitboard k_from_to_bb = SquareBB[kfrom] ^ SquareBB[kto];
994 Bitboard r_from_to_bb = SquareBB[rfrom] ^ SquareBB[rto];
995 byTypeBB[KING] ^= k_from_to_bb;
996 byTypeBB[ROOK] ^= r_from_to_bb;
997 byTypeBB[ALL_PIECES] ^= k_from_to_bb ^ r_from_to_bb;
998 byColorBB[us] ^= k_from_to_bb ^ r_from_to_bb;
1000 // Could be from == to, so first set NO_PIECE then KING and ROOK
1001 board[kfrom] = board[rfrom] = NO_PIECE;
1002 board[kto] = make_piece(us, KING);
1003 board[rto] = make_piece(us, ROOK);
1005 // Could be kfrom == rto, so use a 'tmp' variable
1006 int tmp = index[kfrom];
1007 index[rto] = index[rfrom];
1009 pieceList[us][KING][index[kto]] = kto;
1010 pieceList[us][ROOK][index[rto]] = rto;
1014 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1015 /// the side to move without executing any move on the board.
1017 void Position::do_null_move(StateInfo& newSt) {
1019 assert(!checkers());
1021 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1023 newSt.previous = st;
1026 if (st->epSquare != SQ_NONE)
1028 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1029 st->epSquare = SQ_NONE;
1032 st->key ^= Zobrist::side;
1033 prefetch((char*)TT.first_entry(st->key));
1036 st->pliesFromNull = 0;
1038 sideToMove = ~sideToMove;
1040 assert(pos_is_ok());
1043 void Position::undo_null_move() {
1045 assert(!checkers());
1048 sideToMove = ~sideToMove;
1052 /// Position::see() is a static exchange evaluator: It tries to estimate the
1053 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1054 /// tempi into account. If the side who initiated the capturing sequence does the
1055 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1056 /// the capturing sequence is considered bad.
1058 int Position::see_sign(Move m) const {
1062 // Early return if SEE cannot be negative because captured piece value
1063 // is not less then capturing one. Note that king moves always return
1064 // here because king midgame value is set to 0.
1065 if (PieceValue[MG][piece_moved(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1071 int Position::see(Move m, int asymmThreshold) const {
1074 Bitboard occupied, attackers, stmAttackers;
1075 int swapList[32], slIndex = 1;
1083 swapList[0] = PieceValue[MG][type_of(piece_on(to))];
1084 stm = color_of(piece_on(from));
1085 occupied = pieces() ^ from;
1087 // Castle moves are implemented as king capturing the rook so cannot be
1088 // handled correctly. Simply return 0 that is always the correct value
1089 // unless in the rare case the rook ends up under attack.
1090 if (type_of(m) == CASTLE)
1093 if (type_of(m) == ENPASSANT)
1095 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1096 swapList[0] = PieceValue[MG][PAWN];
1099 // Find all attackers to the destination square, with the moving piece
1100 // removed, but possibly an X-ray attacker added behind it.
1101 attackers = attackers_to(to, occupied) & occupied;
1103 // If the opponent has no attackers we are finished
1105 stmAttackers = attackers & pieces(stm);
1109 // The destination square is defended, which makes things rather more
1110 // difficult to compute. We proceed by building up a "swap list" containing
1111 // the material gain or loss at each stop in a sequence of captures to the
1112 // destination square, where the sides alternately capture, and always
1113 // capture with the least valuable piece. After each capture, we look for
1114 // new X-ray attacks from behind the capturing piece.
1115 captured = type_of(piece_on(from));
1118 assert(slIndex < 32);
1120 // Add the new entry to the swap list
1121 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1124 // Locate and remove the next least valuable attacker
1125 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1127 stmAttackers = attackers & pieces(stm);
1129 // Stop before processing a king capture
1130 if (captured == KING && stmAttackers)
1132 swapList[slIndex++] = QueenValueMg * 16;
1136 } while (stmAttackers);
1138 // If we are doing asymmetric SEE evaluation and the same side does the first
1139 // and the last capture, he loses a tempo and gain must be at least worth
1140 // 'asymmThreshold', otherwise we replace the score with a very low value,
1141 // before negamaxing.
1143 for (int i = 0; i < slIndex; i += 2)
1144 if (swapList[i] < asymmThreshold)
1145 swapList[i] = - QueenValueMg * 16;
1147 // Having built the swap list, we negamax through it to find the best
1148 // achievable score from the point of view of the side to move.
1150 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1156 /// Position::clear() erases the position object to a pristine state, with an
1157 /// empty board, white to move, and no castling rights.
1159 void Position::clear() {
1161 std::memset(this, 0, sizeof(Position));
1162 startState.epSquare = SQ_NONE;
1165 for (int i = 0; i < 8; i++)
1166 for (int j = 0; j < 16; j++)
1167 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1171 /// Position::compute_key() computes the hash key of the position. The hash
1172 /// key is usually updated incrementally as moves are made and unmade, the
1173 /// compute_key() function is only used when a new position is set up, and
1174 /// to verify the correctness of the hash key when running in debug mode.
1176 Key Position::compute_key() const {
1178 Key k = Zobrist::castle[st->castleRights];
1180 for (Bitboard b = pieces(); b; )
1182 Square s = pop_lsb(&b);
1183 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1186 if (ep_square() != SQ_NONE)
1187 k ^= Zobrist::enpassant[file_of(ep_square())];
1189 if (sideToMove == BLACK)
1196 /// Position::compute_pawn_key() computes the hash key of the position. The
1197 /// hash key is usually updated incrementally as moves are made and unmade,
1198 /// the compute_pawn_key() function is only used when a new position is set
1199 /// up, and to verify the correctness of the pawn hash key when running in
1202 Key Position::compute_pawn_key() const {
1206 for (Bitboard b = pieces(PAWN); b; )
1208 Square s = pop_lsb(&b);
1209 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1216 /// Position::compute_material_key() computes the hash key of the position.
1217 /// The hash key is usually updated incrementally as moves are made and unmade,
1218 /// the compute_material_key() function is only used when a new position is set
1219 /// up, and to verify the correctness of the material hash key when running in
1222 Key Position::compute_material_key() const {
1226 for (Color c = WHITE; c <= BLACK; c++)
1227 for (PieceType pt = PAWN; pt <= QUEEN; pt++)
1228 for (int cnt = 0; cnt < pieceCount[c][pt]; cnt++)
1229 k ^= Zobrist::psq[c][pt][cnt];
1235 /// Position::compute_psq_score() computes the incremental scores for the middle
1236 /// game and the endgame. These functions are used to initialize the incremental
1237 /// scores when a new position is set up, and to verify that the scores are correctly
1238 /// updated by do_move and undo_move when the program is running in debug mode.
1239 Score Position::compute_psq_score() const {
1241 Score score = SCORE_ZERO;
1243 for (Bitboard b = pieces(); b; )
1245 Square s = pop_lsb(&b);
1246 Piece pc = piece_on(s);
1247 score += psq[color_of(pc)][type_of(pc)][s];
1254 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1255 /// game material value for the given side. Material values are updated
1256 /// incrementally during the search, this function is only used while
1257 /// initializing a new Position object.
1259 Value Position::compute_non_pawn_material(Color c) const {
1261 Value value = VALUE_ZERO;
1263 for (PieceType pt = KNIGHT; pt <= QUEEN; pt++)
1264 value += pieceCount[c][pt] * PieceValue[MG][pt];
1270 /// Position::is_draw() tests whether the position is drawn by material,
1271 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1272 /// must be done by the search.
1273 bool Position::is_draw() const {
1275 // Draw by material?
1277 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1280 // Draw by the 50 moves rule?
1281 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1284 // Draw by repetition?
1285 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1289 StateInfo* stp = st->previous->previous;
1292 stp = stp->previous->previous;
1294 if (stp->key == st->key)
1306 /// Position::flip() flips position with the white and black sides reversed. This
1307 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1309 void Position::flip() {
1311 const Position pos(*this);
1315 sideToMove = ~pos.side_to_move();
1316 thisThread = pos.this_thread();
1317 nodes = pos.nodes_searched();
1318 chess960 = pos.is_chess960();
1319 gamePly = pos.game_ply();
1321 for (Square s = SQ_A1; s <= SQ_H8; s++)
1322 if (!pos.is_empty(s))
1324 Piece p = Piece(pos.piece_on(s) ^ 8);
1325 put_piece(~s, color_of(p), type_of(p));
1328 if (pos.can_castle(WHITE_OO))
1329 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, KING_SIDE));
1330 if (pos.can_castle(WHITE_OOO))
1331 set_castle_right(BLACK, ~pos.castle_rook_square(WHITE, QUEEN_SIDE));
1332 if (pos.can_castle(BLACK_OO))
1333 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, KING_SIDE));
1334 if (pos.can_castle(BLACK_OOO))
1335 set_castle_right(WHITE, ~pos.castle_rook_square(BLACK, QUEEN_SIDE));
1337 if (pos.st->epSquare != SQ_NONE)
1338 st->epSquare = ~pos.st->epSquare;
1340 st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove);
1342 st->key = compute_key();
1343 st->pawnKey = compute_pawn_key();
1344 st->materialKey = compute_material_key();
1345 st->psq = compute_psq_score();
1346 st->npMaterial[WHITE] = compute_non_pawn_material(WHITE);
1347 st->npMaterial[BLACK] = compute_non_pawn_material(BLACK);
1349 assert(pos_is_ok());
1353 /// Position::pos_is_ok() performs some consitency checks for the position object.
1354 /// This is meant to be helpful when debugging.
1356 bool Position::pos_is_ok(int* failedStep) const {
1358 int dummy, *step = failedStep ? failedStep : &dummy;
1360 // What features of the position should be verified?
1361 const bool all = false;
1363 const bool debugBitboards = all || false;
1364 const bool debugKingCount = all || false;
1365 const bool debugKingCapture = all || false;
1366 const bool debugCheckerCount = all || false;
1367 const bool debugKey = all || false;
1368 const bool debugMaterialKey = all || false;
1369 const bool debugPawnKey = all || false;
1370 const bool debugIncrementalEval = all || false;
1371 const bool debugNonPawnMaterial = all || false;
1372 const bool debugPieceCounts = all || false;
1373 const bool debugPieceList = all || false;
1374 const bool debugCastleSquares = all || false;
1378 if (sideToMove != WHITE && sideToMove != BLACK)
1381 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1384 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1387 if ((*step)++, debugKingCount)
1389 int kingCount[COLOR_NB] = {};
1391 for (Square s = SQ_A1; s <= SQ_H8; s++)
1392 if (type_of(piece_on(s)) == KING)
1393 kingCount[color_of(piece_on(s))]++;
1395 if (kingCount[0] != 1 || kingCount[1] != 1)
1399 if ((*step)++, debugKingCapture)
1400 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1403 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1406 if ((*step)++, debugBitboards)
1408 // The intersection of the white and black pieces must be empty
1409 if (pieces(WHITE) & pieces(BLACK))
1412 // The union of the white and black pieces must be equal to all
1414 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1417 // Separate piece type bitboards must have empty intersections
1418 for (PieceType p1 = PAWN; p1 <= KING; p1++)
1419 for (PieceType p2 = PAWN; p2 <= KING; p2++)
1420 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1424 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1427 if ((*step)++, debugKey && st->key != compute_key())
1430 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1433 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1436 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1439 if ((*step)++, debugNonPawnMaterial)
1440 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1441 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1444 if ((*step)++, debugPieceCounts)
1445 for (Color c = WHITE; c <= BLACK; c++)
1446 for (PieceType pt = PAWN; pt <= KING; pt++)
1447 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1450 if ((*step)++, debugPieceList)
1451 for (Color c = WHITE; c <= BLACK; c++)
1452 for (PieceType pt = PAWN; pt <= KING; pt++)
1453 for (int i = 0; i < pieceCount[c][pt]; i++)
1454 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1455 || index[pieceList[c][pt][i]] != i)
1458 if ((*step)++, debugCastleSquares)
1459 for (Color c = WHITE; c <= BLACK; c++)
1460 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1462 CastleRight cr = make_castle_right(c, s);
1464 if (!can_castle(cr))
1467 if ( (castleRightsMask[king_square(c)] & cr) != cr
1468 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1469 || castleRightsMask[castleRookSquare[c][s]] != cr)