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 // Remove both pieces first since squares could overlap in Chess960
993 remove_piece(kfrom, sideToMove, KING);
994 remove_piece(rfrom, sideToMove, ROOK);
995 board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us
996 put_piece(kto, sideToMove, KING);
997 put_piece(rto, sideToMove, ROOK);
1001 /// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips
1002 /// the side to move without executing any move on the board.
1004 void Position::do_null_move(StateInfo& newSt) {
1006 assert(!checkers());
1008 std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here
1010 newSt.previous = st;
1013 if (st->epSquare != SQ_NONE)
1015 st->key ^= Zobrist::enpassant[file_of(st->epSquare)];
1016 st->epSquare = SQ_NONE;
1019 st->key ^= Zobrist::side;
1020 prefetch((char*)TT.first_entry(st->key));
1023 st->pliesFromNull = 0;
1025 sideToMove = ~sideToMove;
1027 assert(pos_is_ok());
1030 void Position::undo_null_move() {
1032 assert(!checkers());
1035 sideToMove = ~sideToMove;
1039 /// Position::see() is a static exchange evaluator: It tries to estimate the
1040 /// material gain or loss resulting from a move. Parameter 'asymmThreshold' takes
1041 /// tempi into account. If the side who initiated the capturing sequence does the
1042 /// last capture, he loses a tempo and if the result is below 'asymmThreshold'
1043 /// the capturing sequence is considered bad.
1045 int Position::see_sign(Move m) const {
1049 // Early return if SEE cannot be negative because captured piece value
1050 // is not less then capturing one. Note that king moves always return
1051 // here because king midgame value is set to 0.
1052 if (PieceValue[MG][piece_moved(m)] <= PieceValue[MG][piece_on(to_sq(m))])
1058 int Position::see(Move m, int asymmThreshold) const {
1061 Bitboard occupied, attackers, stmAttackers;
1062 int swapList[32], slIndex = 1;
1070 swapList[0] = PieceValue[MG][type_of(piece_on(to))];
1071 stm = color_of(piece_on(from));
1072 occupied = pieces() ^ from;
1074 // Castle moves are implemented as king capturing the rook so cannot be
1075 // handled correctly. Simply return 0 that is always the correct value
1076 // unless in the rare case the rook ends up under attack.
1077 if (type_of(m) == CASTLE)
1080 if (type_of(m) == ENPASSANT)
1082 occupied ^= to - pawn_push(stm); // Remove the captured pawn
1083 swapList[0] = PieceValue[MG][PAWN];
1086 // Find all attackers to the destination square, with the moving piece
1087 // removed, but possibly an X-ray attacker added behind it.
1088 attackers = attackers_to(to, occupied) & occupied;
1090 // If the opponent has no attackers we are finished
1092 stmAttackers = attackers & pieces(stm);
1096 // The destination square is defended, which makes things rather more
1097 // difficult to compute. We proceed by building up a "swap list" containing
1098 // the material gain or loss at each stop in a sequence of captures to the
1099 // destination square, where the sides alternately capture, and always
1100 // capture with the least valuable piece. After each capture, we look for
1101 // new X-ray attacks from behind the capturing piece.
1102 captured = type_of(piece_on(from));
1105 assert(slIndex < 32);
1107 // Add the new entry to the swap list
1108 swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured];
1111 // Locate and remove the next least valuable attacker
1112 captured = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
1114 stmAttackers = attackers & pieces(stm);
1116 // Stop before processing a king capture
1117 if (captured == KING && stmAttackers)
1119 swapList[slIndex++] = QueenValueMg * 16;
1123 } while (stmAttackers);
1125 // If we are doing asymmetric SEE evaluation and the same side does the first
1126 // and the last capture, he loses a tempo and gain must be at least worth
1127 // 'asymmThreshold', otherwise we replace the score with a very low value,
1128 // before negamaxing.
1130 for (int i = 0; i < slIndex; i += 2)
1131 if (swapList[i] < asymmThreshold)
1132 swapList[i] = - QueenValueMg * 16;
1134 // Having built the swap list, we negamax through it to find the best
1135 // achievable score from the point of view of the side to move.
1137 swapList[slIndex-1] = std::min(-swapList[slIndex], swapList[slIndex-1]);
1143 /// Position::clear() erases the position object to a pristine state, with an
1144 /// empty board, white to move, and no castling rights.
1146 void Position::clear() {
1148 std::memset(this, 0, sizeof(Position));
1149 startState.epSquare = SQ_NONE;
1152 for (int i = 0; i < PIECE_TYPE_NB; i++)
1153 for (int j = 0; j < 16; j++)
1154 pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE;
1158 /// Position::compute_key() computes the hash key of the position. The hash
1159 /// key is usually updated incrementally as moves are made and unmade, the
1160 /// compute_key() function is only used when a new position is set up, and
1161 /// to verify the correctness of the hash key when running in debug mode.
1163 Key Position::compute_key() const {
1165 Key k = Zobrist::castle[st->castleRights];
1167 for (Bitboard b = pieces(); b; )
1169 Square s = pop_lsb(&b);
1170 k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s];
1173 if (ep_square() != SQ_NONE)
1174 k ^= Zobrist::enpassant[file_of(ep_square())];
1176 if (sideToMove == BLACK)
1183 /// Position::compute_pawn_key() computes the hash key of the position. The
1184 /// hash key is usually updated incrementally as moves are made and unmade,
1185 /// the compute_pawn_key() function is only used when a new position is set
1186 /// up, and to verify the correctness of the pawn hash key when running in
1189 Key Position::compute_pawn_key() const {
1193 for (Bitboard b = pieces(PAWN); b; )
1195 Square s = pop_lsb(&b);
1196 k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s];
1203 /// Position::compute_material_key() computes the hash key of the position.
1204 /// The hash key is usually updated incrementally as moves are made and unmade,
1205 /// the compute_material_key() function is only used when a new position is set
1206 /// up, and to verify the correctness of the material hash key when running in
1209 Key Position::compute_material_key() const {
1213 for (Color c = WHITE; c <= BLACK; ++c)
1214 for (PieceType pt = PAWN; pt <= QUEEN; ++pt)
1215 for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt)
1216 k ^= Zobrist::psq[c][pt][cnt];
1222 /// Position::compute_psq_score() computes the incremental scores for the middle
1223 /// game and the endgame. These functions are used to initialize the incremental
1224 /// scores when a new position is set up, and to verify that the scores are correctly
1225 /// updated by do_move and undo_move when the program is running in debug mode.
1227 Score Position::compute_psq_score() const {
1229 Score score = SCORE_ZERO;
1231 for (Bitboard b = pieces(); b; )
1233 Square s = pop_lsb(&b);
1234 Piece pc = piece_on(s);
1235 score += psq[color_of(pc)][type_of(pc)][s];
1242 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1243 /// game material value for the given side. Material values are updated
1244 /// incrementally during the search, this function is only used while
1245 /// initializing a new Position object.
1247 Value Position::compute_non_pawn_material(Color c) const {
1249 Value value = VALUE_ZERO;
1251 for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt)
1252 value += pieceCount[c][pt] * PieceValue[MG][pt];
1258 /// Position::is_draw() tests whether the position is drawn by material,
1259 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1260 /// must be done by the search.
1261 bool Position::is_draw() const {
1263 // Draw by material?
1265 && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg))
1268 // Draw by the 50 moves rule?
1269 if (st->rule50 > 99 && (!checkers() || MoveList<LEGAL>(*this).size()))
1272 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
1276 StateInfo* stp = st->previous->previous;
1279 stp = stp->previous->previous;
1281 if (stp->key == st->key)
1282 return true; // Draw after first repetition
1293 /// Position::flip() flips position with the white and black sides reversed. This
1294 /// is only useful for debugging especially for finding evaluation symmetry bugs.
1296 static char toggle_case(char c) {
1297 return char(islower(c) ? toupper(c) : tolower(c));
1300 void Position::flip() {
1303 std::stringstream ss(fen());
1305 for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement
1307 std::getline(ss, token, rank > RANK_1 ? '/' : ' ');
1308 f.insert(0, token + (f.empty() ? " " : "/"));
1311 ss >> token; // Active color
1312 f += (token == "w" ? "B " : "W "); // Will be lowercased later
1314 ss >> token; // Castling availability
1317 std::transform(f.begin(), f.end(), f.begin(), toggle_case);
1319 ss >> token; // En passant square
1320 f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3"));
1322 std::getline(ss, token); // Half and full moves
1325 set(f, is_chess960(), this_thread());
1327 assert(pos_is_ok());
1331 /// Position::pos_is_ok() performs some consitency checks for the position object.
1332 /// This is meant to be helpful when debugging.
1334 bool Position::pos_is_ok(int* failedStep) const {
1336 int dummy, *step = failedStep ? failedStep : &dummy;
1338 // What features of the position should be verified?
1339 const bool all = false;
1341 const bool debugBitboards = all || false;
1342 const bool debugKingCount = all || false;
1343 const bool debugKingCapture = all || false;
1344 const bool debugCheckerCount = all || false;
1345 const bool debugKey = all || false;
1346 const bool debugMaterialKey = all || false;
1347 const bool debugPawnKey = all || false;
1348 const bool debugIncrementalEval = all || false;
1349 const bool debugNonPawnMaterial = all || false;
1350 const bool debugPieceCounts = all || false;
1351 const bool debugPieceList = all || false;
1352 const bool debugCastleSquares = all || false;
1356 if (sideToMove != WHITE && sideToMove != BLACK)
1359 if ((*step)++, piece_on(king_square(WHITE)) != W_KING)
1362 if ((*step)++, piece_on(king_square(BLACK)) != B_KING)
1365 if ((*step)++, debugKingCount)
1367 int kingCount[COLOR_NB] = {};
1369 for (Square s = SQ_A1; s <= SQ_H8; ++s)
1370 if (type_of(piece_on(s)) == KING)
1371 kingCount[color_of(piece_on(s))]++;
1373 if (kingCount[0] != 1 || kingCount[1] != 1)
1377 if ((*step)++, debugKingCapture)
1378 if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove))
1381 if ((*step)++, debugCheckerCount && popcount<Full>(st->checkersBB) > 2)
1384 if ((*step)++, debugBitboards)
1386 // The intersection of the white and black pieces must be empty
1387 if (pieces(WHITE) & pieces(BLACK))
1390 // The union of the white and black pieces must be equal to all
1392 if ((pieces(WHITE) | pieces(BLACK)) != pieces())
1395 // Separate piece type bitboards must have empty intersections
1396 for (PieceType p1 = PAWN; p1 <= KING; ++p1)
1397 for (PieceType p2 = PAWN; p2 <= KING; ++p2)
1398 if (p1 != p2 && (pieces(p1) & pieces(p2)))
1402 if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)
1405 if ((*step)++, debugKey && st->key != compute_key())
1408 if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key())
1411 if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key())
1414 if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score())
1417 if ((*step)++, debugNonPawnMaterial)
1418 if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE)
1419 || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK))
1422 if ((*step)++, debugPieceCounts)
1423 for (Color c = WHITE; c <= BLACK; ++c)
1424 for (PieceType pt = PAWN; pt <= KING; ++pt)
1425 if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
1428 if ((*step)++, debugPieceList)
1429 for (Color c = WHITE; c <= BLACK; ++c)
1430 for (PieceType pt = PAWN; pt <= KING; ++pt)
1431 for (int i = 0; i < pieceCount[c][pt]; i++)
1432 if ( board[pieceList[c][pt][i]] != make_piece(c, pt)
1433 || index[pieceList[c][pt][i]] != i)
1436 if ((*step)++, debugCastleSquares)
1437 for (Color c = WHITE; c <= BLACK; ++c)
1438 for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1))
1440 CastleRight cr = make_castle_right(c, s);
1442 if (!can_castle(cr))
1445 if ( (castleRightsMask[king_square(c)] & cr) != cr
1446 || piece_on(castleRookSquare[c][s]) != make_piece(c, ROOK)
1447 || castleRightsMask[castleRookSquare[c][s]] != cr)