X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fposition.cpp;h=87067ea56f644187cf52bf4c4adce75900da9d78;hb=HEAD;hp=cb0701524af47239812f12e887fa502e3c807438;hpb=1d1b7df7c6b3496d1a3fe926cadf25d91e1558f6;p=stockfish diff --git a/src/position.cpp b/src/position.cpp index cb070152..c45dd7b2 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -1,7 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2014 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -17,166 +16,152 @@ along with this program. If not, see . */ +#include "position.h" + #include +#include #include +#include +#include #include +#include #include +#include #include +#include +#include -#include "bitcount.h" +#include "bitboard.h" +#include "misc.h" #include "movegen.h" -#include "notation.h" -#include "position.h" -#include "psqtab.h" -#include "rkiss.h" +#include "nnue/nnue_common.h" +#include "syzygy/tbprobe.h" #include "thread.h" #include "tt.h" +#include "uci.h" using std::string; -static const string PieceToChar(" PNBRQK pnbrqk"); - -CACHE_LINE_ALIGNMENT - -Score psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB]; -Value PieceValue[PHASE_NB][PIECE_NB] = { -{ VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg }, -{ VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } }; +namespace Stockfish { namespace Zobrist { - Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB]; - Key enpassant[FILE_NB]; - Key castling[CASTLING_RIGHT_NB]; - Key side; - Key exclusion; +Key psq[PIECE_NB][SQUARE_NB]; +Key enpassant[FILE_NB]; +Key castling[CASTLING_RIGHT_NB]; +Key side, noPawns; } -Key Position::exclusion_key() const { return st->key ^ Zobrist::exclusion;} - namespace { -// min_attacker() is a helper function used by see() to locate the least -// valuable attacker for the side to move, remove the attacker we just found -// from the bitboards and scan for new X-ray attacks behind it. - -template FORCE_INLINE -PieceType min_attacker(const Bitboard* bb, const Square& to, const Bitboard& stmAttackers, - Bitboard& occupied, Bitboard& attackers) { +constexpr std::string_view PieceToChar(" PNBRQK pnbrqk"); - Bitboard b = stmAttackers & bb[Pt]; - if (!b) - return min_attacker(bb, to, stmAttackers, occupied, attackers); +constexpr Piece Pieces[] = {W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING, + B_PAWN, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING}; +} // namespace - occupied ^= b & ~(b - 1); - if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN) - attackers |= attacks_bb(to, occupied) & (bb[BISHOP] | bb[QUEEN]); +// Returns an ASCII representation of the position +std::ostream& operator<<(std::ostream& os, const Position& pos) { - if (Pt == ROOK || Pt == QUEEN) - attackers |= attacks_bb(to, occupied) & (bb[ROOK] | bb[QUEEN]); + os << "\n +---+---+---+---+---+---+---+---+\n"; - attackers &= occupied; // After X-ray that may add already processed pieces - return (PieceType)Pt; -} + for (Rank r = RANK_8; r >= RANK_1; --r) + { + for (File f = FILE_A; f <= FILE_H; ++f) + os << " | " << PieceToChar[pos.piece_on(make_square(f, r))]; -template<> FORCE_INLINE -PieceType min_attacker(const Bitboard*, const Square&, const Bitboard&, Bitboard&, Bitboard&) { - return KING; // No need to update bitboards: it is the last cycle -} + os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n"; + } -} // namespace + os << " a b c d e f g h\n" + << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase << std::setfill('0') + << std::setw(16) << pos.key() << std::setfill(' ') << std::dec << "\nCheckers: "; + for (Bitboard b = pos.checkers(); b;) + os << UCI::square(pop_lsb(b)) << " "; -/// CheckInfo c'tor + if (int(Tablebases::MaxCardinality) >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING)) + { + StateInfo st; + ASSERT_ALIGNED(&st, Eval::NNUE::CacheLineSize); -CheckInfo::CheckInfo(const Position& pos) { + Position p; + p.set(pos.fen(), pos.is_chess960(), &st, pos.this_thread()); + Tablebases::ProbeState s1, s2; + Tablebases::WDLScore wdl = Tablebases::probe_wdl(p, &s1); + int dtz = Tablebases::probe_dtz(p, &s2); + os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")" + << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")"; + } - Color them = ~pos.side_to_move(); - ksq = pos.king_square(them); - - pinned = pos.pinned_pieces(pos.side_to_move()); - dcCandidates = pos.discovered_check_candidates(); - - checkSq[PAWN] = pos.attacks_from(ksq, them); - checkSq[KNIGHT] = pos.attacks_from(ksq); - checkSq[BISHOP] = pos.attacks_from(ksq); - checkSq[ROOK] = pos.attacks_from(ksq); - checkSq[QUEEN] = checkSq[BISHOP] | checkSq[ROOK]; - checkSq[KING] = 0; + return os; } -/// Position::init() initializes at startup the various arrays used to compute -/// hash keys and the piece square tables. The latter is a two-step operation: -/// Firstly, the white halves of the tables are copied from PSQT[] tables. -/// Secondly, the black halves of the tables are initialized by flipping and -/// changing the sign of the white scores. - -void Position::init() { - - RKISS rk; - - for (Color c = WHITE; c <= BLACK; ++c) - for (PieceType pt = PAWN; pt <= KING; ++pt) - for (Square s = SQ_A1; s <= SQ_H8; ++s) - Zobrist::psq[c][pt][s] = rk.rand(); - - for (File f = FILE_A; f <= FILE_H; ++f) - Zobrist::enpassant[f] = rk.rand(); - - for (int cf = NO_CASTLING; cf <= ANY_CASTLING; ++cf) - { - Bitboard b = cf; - while (b) - { - Key k = Zobrist::castling[1ULL << pop_lsb(&b)]; - Zobrist::castling[cf] ^= k ? k : rk.rand(); - } - } - - Zobrist::side = rk.rand(); - Zobrist::exclusion = rk.rand(); - - for (PieceType pt = PAWN; pt <= KING; ++pt) - { - PieceValue[MG][make_piece(BLACK, pt)] = PieceValue[MG][pt]; - PieceValue[EG][make_piece(BLACK, pt)] = PieceValue[EG][pt]; - - Score v = make_score(PieceValue[MG][pt], PieceValue[EG][pt]); - - for (Square s = SQ_A1; s <= SQ_H8; ++s) - { - psq[WHITE][pt][ s] = (v + PSQT[pt][s]); - psq[BLACK][pt][~s] = -(v + PSQT[pt][s]); - } - } -} - +// Implements Marcel van Kervinck's cuckoo algorithm to detect repetition of positions +// for 3-fold repetition draws. The algorithm uses two hash tables with Zobrist hashes +// to allow fast detection of recurring positions. For details see: +// http://web.archive.org/web/20201107002606/https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf -/// Position::operator=() creates a copy of 'pos'. We want the new born Position -/// object to not depend on any external data so we detach state pointer from -/// the source one. +// First and second hash functions for indexing the cuckoo tables +inline int H1(Key h) { return h & 0x1fff; } +inline int H2(Key h) { return (h >> 16) & 0x1fff; } -Position& Position::operator=(const Position& pos) { +// Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves +Key cuckoo[8192]; +Move cuckooMove[8192]; - std::memcpy(this, &pos, sizeof(Position)); - startState = *st; - st = &startState; - nodes = 0; - assert(pos_is_ok()); +// Initializes at startup the various arrays used to compute hash keys +void Position::init() { - return *this; + PRNG rng(1070372); + + for (Piece pc : Pieces) + for (Square s = SQ_A1; s <= SQ_H8; ++s) + Zobrist::psq[pc][s] = rng.rand(); + + for (File f = FILE_A; f <= FILE_H; ++f) + Zobrist::enpassant[f] = rng.rand(); + + for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr) + Zobrist::castling[cr] = rng.rand(); + + Zobrist::side = rng.rand(); + Zobrist::noPawns = rng.rand(); + + // Prepare the cuckoo tables + std::memset(cuckoo, 0, sizeof(cuckoo)); + std::memset(cuckooMove, 0, sizeof(cuckooMove)); + [[maybe_unused]] int count = 0; + for (Piece pc : Pieces) + for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) + for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2) + if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2)) + { + Move move = make_move(s1, s2); + Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side; + int i = H1(key); + while (true) + { + std::swap(cuckoo[i], key); + std::swap(cuckooMove[i], move); + if (move == MOVE_NONE) // Arrived at empty slot? + break; + i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot + } + count++; + } + assert(count == 3668); } -/// Position::set() initializes the position object with the given FEN string. -/// This function is not very robust - make sure that input FENs are correct, -/// this is assumed to be the responsibility of the GUI. - -void Position::set(const string& fenStr, bool isChess960, Thread* th) { -/* +// Initializes the position object with the given FEN string. +// This function is not very robust - make sure that input FENs are correct, +// this is assumed to be the responsibility of the GUI. +Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Thread* th) { + /* A FEN string defines a particular position using only the ASCII character set. A FEN string contains six fields separated by a space. The fields are: @@ -199,8 +184,9 @@ void Position::set(const string& fenStr, bool isChess960, Thread* th) { 4) En passant target square (in algebraic notation). If there's no en passant target square, this is "-". If a pawn has just made a 2-square move, this - is the position "behind" the pawn. This is recorded regardless of whether - there is a pawn in position to make an en passant capture. + is the position "behind" the pawn. Following X-FEN standard, this is recorded + only if there is a pawn in position to make an en passant capture, and if + there really is a pawn that might have advanced two squares. 5) Halfmove clock. This is the number of halfmoves since the last pawn advance or capture. This is used to determine if a draw can be claimed under the @@ -210,1198 +196,1101 @@ void Position::set(const string& fenStr, bool isChess960, Thread* th) { incremented after Black's move. */ - char col, row, token; - size_t idx; - Square sq = SQ_A8; - std::istringstream ss(fenStr); - - clear(); - ss >> std::noskipws; - - // 1. Piece placement - while ((ss >> token) && !isspace(token)) - { - if (isdigit(token)) - sq += Square(token - '0'); // Advance the given number of files - - else if (token == '/') - sq -= Square(16); - - else if ((idx = PieceToChar.find(token)) != string::npos) - { - put_piece(sq, color_of(Piece(idx)), type_of(Piece(idx))); - ++sq; - } - } - - // 2. Active color - ss >> token; - sideToMove = (token == 'w' ? WHITE : BLACK); - ss >> token; - - // 3. Castling availability. Compatible with 3 standards: Normal FEN standard, - // Shredder-FEN that uses the letters of the columns on which the rooks began - // the game instead of KQkq and also X-FEN standard that, in case of Chess960, - // if an inner rook is associated with the castling right, the castling tag is - // replaced by the file letter of the involved rook, as for the Shredder-FEN. - while ((ss >> token) && !isspace(token)) - { - Square rsq; - Color c = islower(token) ? BLACK : WHITE; - - token = char(toupper(token)); - - if (token == 'K') - for (rsq = relative_square(c, SQ_H1); type_of(piece_on(rsq)) != ROOK; --rsq) {} - - else if (token == 'Q') - for (rsq = relative_square(c, SQ_A1); type_of(piece_on(rsq)) != ROOK; ++rsq) {} - - else if (token >= 'A' && token <= 'H') - rsq = File(token - 'A') | relative_rank(c, RANK_1); - - else - continue; - - set_castling_right(c, rsq); - } - - // 4. En passant square. Ignore if no pawn capture is possible - if ( ((ss >> col) && (col >= 'a' && col <= 'h')) - && ((ss >> row) && (row == '3' || row == '6'))) - { - st->epSquare = File(col - 'a') | Rank(row - '1'); - - if (!(attackers_to(st->epSquare) & pieces(sideToMove, PAWN))) - st->epSquare = SQ_NONE; - } - - // 5-6. Halfmove clock and fullmove number - ss >> std::skipws >> st->rule50 >> gamePly; - - // Convert from fullmove starting from 1 to ply starting from 0, - // handle also common incorrect FEN with fullmove = 0. - gamePly = std::max(2 * (gamePly - 1), 0) + int(sideToMove == BLACK); - - st->key = compute_key(); - st->pawnKey = compute_pawn_key(); - st->materialKey = compute_material_key(); - st->psq = compute_psq_score(); - st->npMaterial[WHITE] = compute_non_pawn_material(WHITE); - st->npMaterial[BLACK] = compute_non_pawn_material(BLACK); - st->checkersBB = attackers_to(king_square(sideToMove)) & pieces(~sideToMove); - chess960 = isChess960; - thisThread = th; - - assert(pos_is_ok()); + unsigned char col, row, token; + size_t idx; + Square sq = SQ_A8; + std::istringstream ss(fenStr); + + std::memset(this, 0, sizeof(Position)); + std::memset(si, 0, sizeof(StateInfo)); + st = si; + + ss >> std::noskipws; + + // 1. Piece placement + while ((ss >> token) && !isspace(token)) + { + if (isdigit(token)) + sq += (token - '0') * EAST; // Advance the given number of files + + else if (token == '/') + sq += 2 * SOUTH; + + else if ((idx = PieceToChar.find(token)) != string::npos) + { + put_piece(Piece(idx), sq); + ++sq; + } + } + + // 2. Active color + ss >> token; + sideToMove = (token == 'w' ? WHITE : BLACK); + ss >> token; + + // 3. Castling availability. Compatible with 3 standards: Normal FEN standard, + // Shredder-FEN that uses the letters of the columns on which the rooks began + // the game instead of KQkq and also X-FEN standard that, in case of Chess960, + // if an inner rook is associated with the castling right, the castling tag is + // replaced by the file letter of the involved rook, as for the Shredder-FEN. + while ((ss >> token) && !isspace(token)) + { + Square rsq; + Color c = islower(token) ? BLACK : WHITE; + Piece rook = make_piece(c, ROOK); + + token = char(toupper(token)); + + if (token == 'K') + for (rsq = relative_square(c, SQ_H1); piece_on(rsq) != rook; --rsq) + {} + + else if (token == 'Q') + for (rsq = relative_square(c, SQ_A1); piece_on(rsq) != rook; ++rsq) + {} + + else if (token >= 'A' && token <= 'H') + rsq = make_square(File(token - 'A'), relative_rank(c, RANK_1)); + + else + continue; + + set_castling_right(c, rsq); + } + + // 4. En passant square. + // Ignore if square is invalid or not on side to move relative rank 6. + bool enpassant = false; + + if (((ss >> col) && (col >= 'a' && col <= 'h')) + && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3')))) + { + st->epSquare = make_square(File(col - 'a'), Rank(row - '1')); + + // En passant square will be considered only if + // a) side to move have a pawn threatening epSquare + // b) there is an enemy pawn in front of epSquare + // c) there is no piece on epSquare or behind epSquare + enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN) + && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))) + && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove)))); + } + + if (!enpassant) + st->epSquare = SQ_NONE; + + // 5-6. Halfmove clock and fullmove number + ss >> std::skipws >> st->rule50 >> gamePly; + + // Convert from fullmove starting from 1 to gamePly starting from 0, + // handle also common incorrect FEN with fullmove = 0. + gamePly = std::max(2 * (gamePly - 1), 0) + (sideToMove == BLACK); + + chess960 = isChess960; + thisThread = th; + set_state(); + + assert(pos_is_ok()); + + return *this; } -/// Position::set_castling_right() is a helper function used to set castling -/// rights given the corresponding color and the rook starting square. - +// Helper function used to set castling +// rights given the corresponding color and the rook starting square. void Position::set_castling_right(Color c, Square rfrom) { - Square kfrom = king_square(c); - CastlingSide cs = kfrom < rfrom ? KING_SIDE : QUEEN_SIDE; - CastlingRight cr = (c | cs); - - st->castlingRights |= cr; - castlingRightsMask[kfrom] |= cr; - castlingRightsMask[rfrom] |= cr; - castlingRookSquare[cr] = rfrom; + Square kfrom = square(c); + CastlingRights cr = c & (kfrom < rfrom ? KING_SIDE : QUEEN_SIDE); - Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1); - Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1); + st->castlingRights |= cr; + castlingRightsMask[kfrom] |= cr; + castlingRightsMask[rfrom] |= cr; + castlingRookSquare[cr] = rfrom; - for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s) - if (s != kfrom && s != rfrom) - castlingPath[cr] |= s; + Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1); + Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1); - for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s) - if (s != kfrom && s != rfrom) - castlingPath[cr] |= s; + castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto)) & ~(kfrom | rfrom); } -/// Position::fen() returns a FEN representation of the position. In case of -/// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function. +// Sets king attacks to detect if a move gives check +void Position::set_check_info() const { -const string Position::fen() const { + update_slider_blockers(WHITE); + update_slider_blockers(BLACK); - int emptyCnt; - std::ostringstream ss; + Square ksq = square(~sideToMove); - for (Rank rank = RANK_8; rank >= RANK_1; --rank) - { - for (File file = FILE_A; file <= FILE_H; ++file) - { - for (emptyCnt = 0; file <= FILE_H && empty(file | rank); ++file) - ++emptyCnt; + st->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq); + st->checkSquares[KNIGHT] = attacks_bb(ksq); + st->checkSquares[BISHOP] = attacks_bb(ksq, pieces()); + st->checkSquares[ROOK] = attacks_bb(ksq, pieces()); + st->checkSquares[QUEEN] = st->checkSquares[BISHOP] | st->checkSquares[ROOK]; + st->checkSquares[KING] = 0; +} - if (emptyCnt) - ss << emptyCnt; - if (file <= FILE_H) - ss << PieceToChar[piece_on(file | rank)]; - } +// Computes the hash keys of the position, and other +// data that once computed is updated incrementally as moves are made. +// The function is only used when a new position is set up +void Position::set_state() const { - if (rank > RANK_1) - ss << '/'; - } + st->key = st->materialKey = 0; + st->pawnKey = Zobrist::noPawns; + st->nonPawnMaterial[WHITE] = st->nonPawnMaterial[BLACK] = VALUE_ZERO; + st->checkersBB = attackers_to(square(sideToMove)) & pieces(~sideToMove); - ss << (sideToMove == WHITE ? " w " : " b "); + set_check_info(); - if (can_castle(WHITE_OO)) - ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | KING_SIDE)), false) : 'K'); + for (Bitboard b = pieces(); b;) + { + Square s = pop_lsb(b); + Piece pc = piece_on(s); + st->key ^= Zobrist::psq[pc][s]; - if (can_castle(WHITE_OOO)) - ss << (chess960 ? to_char(file_of(castling_rook_square(WHITE | QUEEN_SIDE)), false) : 'Q'); + if (type_of(pc) == PAWN) + st->pawnKey ^= Zobrist::psq[pc][s]; - if (can_castle(BLACK_OO)) - ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | KING_SIDE)), true) : 'k'); + else if (type_of(pc) != KING) + st->nonPawnMaterial[color_of(pc)] += PieceValue[pc]; + } - if (can_castle(BLACK_OOO)) - ss << (chess960 ? to_char(file_of(castling_rook_square(BLACK | QUEEN_SIDE)), true) : 'q'); + if (st->epSquare != SQ_NONE) + st->key ^= Zobrist::enpassant[file_of(st->epSquare)]; - if (!can_castle(WHITE) && !can_castle(BLACK)) - ss << '-'; + if (sideToMove == BLACK) + st->key ^= Zobrist::side; - ss << (ep_square() == SQ_NONE ? " - " : " " + to_string(ep_square()) + " ") - << st->rule50 << " " << 1 + (gamePly - int(sideToMove == BLACK)) / 2; + st->key ^= Zobrist::castling[st->castlingRights]; - return ss.str(); + for (Piece pc : Pieces) + for (int cnt = 0; cnt < pieceCount[pc]; ++cnt) + st->materialKey ^= Zobrist::psq[pc][cnt]; } -/// Position::pretty() returns an ASCII representation of the position to be -/// printed to the standard output together with the move's san notation. +// Overload to initialize the position object with the given endgame code string +// like "KBPKN". It's mainly a helper to get the material key out of an endgame code. +Position& Position::set(const string& code, Color c, StateInfo* si) { -const string Position::pretty(Move move) const { + assert(code[0] == 'K'); - const string dottedLine = "\n+---+---+---+---+---+---+---+---+"; - const string twoRows = dottedLine + "\n| | . | | . | | . | | . |" - + dottedLine + "\n| . | | . | | . | | . | |"; + string sides[] = {code.substr(code.find('K', 1)), // Weak + code.substr(0, std::min(code.find('v'), code.find('K', 1)))}; // Strong - string brd = twoRows + twoRows + twoRows + twoRows + dottedLine; + assert(sides[0].length() > 0 && sides[0].length() < 8); + assert(sides[1].length() > 0 && sides[1].length() < 8); - for (Bitboard b = pieces(); b; ) - { - Square s = pop_lsb(&b); - brd[513 - 68 * rank_of(s) + 4 * file_of(s)] = PieceToChar[piece_on(s)]; - } + std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower); - std::ostringstream ss; + string fenStr = "8/" + sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/" + sides[1] + + char(8 - sides[1].length() + '0') + "/8 w - - 0 10"; - if (move) - ss << "\nMove: " << (sideToMove == BLACK ? ".." : "") - << move_to_san(*const_cast(this), move); + return set(fenStr, false, si, nullptr); +} - ss << brd << "\nFen: " << fen() << "\nKey: " << std::hex << std::uppercase - << std::setfill('0') << std::setw(16) << st->key << "\nCheckers: "; - for (Bitboard b = checkers(); b; ) - ss << to_string(pop_lsb(&b)) << " "; +// Returns a FEN representation of the position. In case of +// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function. +string Position::fen() const { - ss << "\nLegal moves: "; - for (MoveList it(*this); *it; ++it) - ss << move_to_san(*const_cast(this), *it) << " "; + int emptyCnt; + std::ostringstream ss; - return ss.str(); -} + for (Rank r = RANK_8; r >= RANK_1; --r) + { + for (File f = FILE_A; f <= FILE_H; ++f) + { + for (emptyCnt = 0; f <= FILE_H && empty(make_square(f, r)); ++f) + ++emptyCnt; + if (emptyCnt) + ss << emptyCnt; -/// Position::check_blockers() returns a bitboard of all the pieces with color -/// 'c' that are blocking check on the king with color 'kingColor'. A piece -/// blocks a check if removing that piece from the board would result in a -/// position where the king is in check. A check blocking piece can be either a -/// pinned or a discovered check piece, according if its color 'c' is the same -/// or the opposite of 'kingColor'. + if (f <= FILE_H) + ss << PieceToChar[piece_on(make_square(f, r))]; + } -Bitboard Position::check_blockers(Color c, Color kingColor) const { + if (r > RANK_1) + ss << '/'; + } - Bitboard b, pinners, result = 0; - Square ksq = king_square(kingColor); + ss << (sideToMove == WHITE ? " w " : " b "); - // Pinners are sliders that give check when a pinned piece is removed - pinners = ( (pieces( ROOK, QUEEN) & PseudoAttacks[ROOK ][ksq]) - | (pieces(BISHOP, QUEEN) & PseudoAttacks[BISHOP][ksq])) & pieces(~kingColor); + if (can_castle(WHITE_OO)) + ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO))) : 'K'); - while (pinners) - { - b = between_bb(ksq, pop_lsb(&pinners)) & pieces(); + if (can_castle(WHITE_OOO)) + ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q'); - if (!more_than_one(b)) - result |= b & pieces(c); - } - return result; -} + if (can_castle(BLACK_OO)) + ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO))) : 'k'); + if (can_castle(BLACK_OOO)) + ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q'); -/// Position::attackers_to() computes a bitboard of all pieces which attack a -/// given square. Slider attacks use the occ bitboard to indicate occupancy. + if (!can_castle(ANY_CASTLING)) + ss << '-'; -Bitboard Position::attackers_to(Square s, Bitboard occ) const { + ss << (ep_square() == SQ_NONE ? " - " : " " + UCI::square(ep_square()) + " ") << st->rule50 + << " " << 1 + (gamePly - (sideToMove == BLACK)) / 2; - return (attacks_from(s, BLACK) & pieces(WHITE, PAWN)) - | (attacks_from(s, WHITE) & pieces(BLACK, PAWN)) - | (attacks_from(s) & pieces(KNIGHT)) - | (attacks_bb(s, occ) & pieces(ROOK, QUEEN)) - | (attacks_bb(s, occ) & pieces(BISHOP, QUEEN)) - | (attacks_from(s) & pieces(KING)); + return ss.str(); } +// Calculates st->blockersForKing[c] and st->pinners[~c], +// which store respectively the pieces preventing king of color c from being in check +// and the slider pieces of color ~c pinning pieces of color c to the king. +void Position::update_slider_blockers(Color c) const { + + Square ksq = square(c); + + st->blockersForKing[c] = 0; + st->pinners[~c] = 0; + + // Snipers are sliders that attack 's' when a piece and other snipers are removed + Bitboard snipers = ((attacks_bb(ksq) & pieces(QUEEN, ROOK)) + | (attacks_bb(ksq) & pieces(QUEEN, BISHOP))) + & pieces(~c); + Bitboard occupancy = pieces() ^ snipers; + + while (snipers) + { + Square sniperSq = pop_lsb(snipers); + Bitboard b = between_bb(ksq, sniperSq) & occupancy; + + if (b && !more_than_one(b)) + { + st->blockersForKing[c] |= b; + if (b & pieces(c)) + st->pinners[~c] |= sniperSq; + } + } +} -/// Position::legal() tests whether a pseudo-legal move is legal - -bool Position::legal(Move m, Bitboard pinned) const { - - assert(is_ok(m)); - assert(pinned == pinned_pieces(sideToMove)); - Color us = sideToMove; - Square from = from_sq(m); +// Computes a bitboard of all pieces which attack a given square. +// Slider attacks use the occupied bitboard to indicate occupancy. +Bitboard Position::attackers_to(Square s, Bitboard occupied) const { - assert(color_of(moved_piece(m)) == us); - assert(piece_on(king_square(us)) == make_piece(us, KING)); + return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN)) + | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN)) + | (attacks_bb(s) & pieces(KNIGHT)) + | (attacks_bb(s, occupied) & pieces(ROOK, QUEEN)) + | (attacks_bb(s, occupied) & pieces(BISHOP, QUEEN)) + | (attacks_bb(s) & pieces(KING)); +} - // En passant captures are a tricky special case. Because they are rather - // uncommon, we do it simply by testing whether the king is attacked after - // the move is made. - if (type_of(m) == ENPASSANT) - { - Color them = ~us; - Square to = to_sq(m); - Square capsq = to + pawn_push(them); - Square ksq = king_square(us); - Bitboard b = (pieces() ^ from ^ capsq) | to; - assert(to == ep_square()); - assert(moved_piece(m) == make_piece(us, PAWN)); - assert(piece_on(capsq) == make_piece(them, PAWN)); - assert(piece_on(to) == NO_PIECE); +// Tests whether a pseudo-legal move is legal +bool Position::legal(Move m) const { + + assert(is_ok(m)); + + Color us = sideToMove; + Square from = from_sq(m); + Square to = to_sq(m); + + assert(color_of(moved_piece(m)) == us); + assert(piece_on(square(us)) == make_piece(us, KING)); + + // En passant captures are a tricky special case. Because they are rather + // uncommon, we do it simply by testing whether the king is attacked after + // the move is made. + if (type_of(m) == EN_PASSANT) + { + Square ksq = square(us); + Square capsq = to - pawn_push(us); + Bitboard occupied = (pieces() ^ from ^ capsq) | to; + + assert(to == ep_square()); + assert(moved_piece(m) == make_piece(us, PAWN)); + assert(piece_on(capsq) == make_piece(~us, PAWN)); + assert(piece_on(to) == NO_PIECE); + + return !(attacks_bb(ksq, occupied) & pieces(~us, QUEEN, ROOK)) + && !(attacks_bb(ksq, occupied) & pieces(~us, QUEEN, BISHOP)); + } + + // Castling moves generation does not check if the castling path is clear of + // enemy attacks, it is delayed at a later time: now! + if (type_of(m) == CASTLING) + { + // After castling, the rook and king final positions are the same in + // Chess960 as they would be in standard chess. + to = relative_square(us, to > from ? SQ_G1 : SQ_C1); + Direction step = to > from ? WEST : EAST; + + for (Square s = to; s != from; s += step) + if (attackers_to(s) & pieces(~us)) + return false; + + // In case of Chess960, verify if the Rook blocks some checks. + // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1. + return !chess960 || !(blockers_for_king(us) & to_sq(m)); + } + + // If the moving piece is a king, check whether the destination square is + // attacked by the opponent. + if (type_of(piece_on(from)) == KING) + return !(attackers_to(to, pieces() ^ from) & pieces(~us)); + + // A non-king move is legal if and only if it is not pinned or it + // is moving along the ray towards or away from the king. + return !(blockers_for_king(us) & from) || aligned(from, to, square(us)); +} - return !(attacks_bb< ROOK>(ksq, b) & pieces(them, QUEEN, ROOK)) - && !(attacks_bb(ksq, b) & pieces(them, QUEEN, BISHOP)); - } - // If the moving piece is a king, check whether the destination - // square is attacked by the opponent. Castling moves are checked - // for legality during move generation. - if (type_of(piece_on(from)) == KING) - return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us)); +// Takes a random move and tests whether the move is +// pseudo-legal. It is used to validate moves from TT that can be corrupted +// due to SMP concurrent access or hash position key aliasing. +bool Position::pseudo_legal(const Move m) const { - // A non-king move is legal if and only if it is not pinned or it - // is moving along the ray towards or away from the king. - return !pinned - || !(pinned & from) - || aligned(from, to_sq(m), king_square(us)); + Color us = sideToMove; + Square from = from_sq(m); + Square to = to_sq(m); + Piece pc = moved_piece(m); + + // Use a slower but simpler function for uncommon cases + // yet we skip the legality check of MoveList(). + if (type_of(m) != NORMAL) + return checkers() ? MoveList(*this).contains(m) + : MoveList(*this).contains(m); + + // Is not a promotion, so the promotion piece must be empty + assert(promotion_type(m) - KNIGHT == NO_PIECE_TYPE); + + // If the 'from' square is not occupied by a piece belonging to the side to + // move, the move is obviously not legal. + if (pc == NO_PIECE || color_of(pc) != us) + return false; + + // The destination square cannot be occupied by a friendly piece + if (pieces(us) & to) + return false; + + // Handle the special case of a pawn move + if (type_of(pc) == PAWN) + { + // We have already handled promotion moves, so destination cannot be on the 8th/1st rank + if ((Rank8BB | Rank1BB) & to) + return false; + + if (!(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture + && !((from + pawn_push(us) == to) && empty(to)) // Not a single push + && !((from + 2 * pawn_push(us) == to) // Not a double push + && (relative_rank(us, from) == RANK_2) && empty(to) && empty(to - pawn_push(us)))) + return false; + } + else if (!(attacks_bb(type_of(pc), from, pieces()) & to)) + return false; + + // Evasions generator already takes care to avoid some kind of illegal moves + // and legal() relies on this. We therefore have to take care that the same + // kind of moves are filtered out here. + if (checkers()) + { + if (type_of(pc) != KING) + { + // Double check? In this case, a king move is required + if (more_than_one(checkers())) + return false; + + // Our move must be a blocking interposition or a capture of the checking piece + if (!(between_bb(square(us), lsb(checkers())) & to)) + return false; + } + // In case of king moves under check we have to remove the king so as to catch + // invalid moves like b1a1 when opposite queen is on c1. + else if (attackers_to(to, pieces() ^ from) & pieces(~us)) + return false; + } + + return true; } -/// Position::pseudo_legal() takes a random move and tests whether the move is -/// pseudo legal. It is used to validate moves from TT that can be corrupted -/// due to SMP concurrent access or hash position key aliasing. +// Tests whether a pseudo-legal move gives a check +bool Position::gives_check(Move m) const { -bool Position::pseudo_legal(const Move m) const { + assert(is_ok(m)); + assert(color_of(moved_piece(m)) == sideToMove); - Color us = sideToMove; - Square from = from_sq(m); - Square to = to_sq(m); - Piece pc = moved_piece(m); - - // Use a slower but simpler function for uncommon cases - if (type_of(m) != NORMAL) - return MoveList(*this).contains(m); - - // Is not a promotion, so promotion piece must be empty - if (promotion_type(m) - 2 != NO_PIECE_TYPE) - return false; - - // If the 'from' square is not occupied by a piece belonging to the side to - // move, the move is obviously not legal. - if (pc == NO_PIECE || color_of(pc) != us) - return false; - - // The destination square cannot be occupied by a friendly piece - if (pieces(us) & to) - return false; - - // Handle the special case of a pawn move - if (type_of(pc) == PAWN) - { - // Move direction must be compatible with pawn color - int direction = to - from; - if ((us == WHITE) != (direction > 0)) - return false; - - // We have already handled promotion moves, so destination - // cannot be on the 8th/1st rank. - if (rank_of(to) == RANK_8 || rank_of(to) == RANK_1) - return false; - - // Proceed according to the square delta between the origin and - // destination squares. - switch (direction) - { - case DELTA_NW: - case DELTA_NE: - case DELTA_SW: - case DELTA_SE: - // Capture. The destination square must be occupied by an enemy - // piece (en passant captures was handled earlier). - if (piece_on(to) == NO_PIECE || color_of(piece_on(to)) != ~us) - return false; - - // From and to files must be one file apart, avoids a7h5 - if (abs(file_of(from) - file_of(to)) != 1) - return false; - break; - - case DELTA_N: - case DELTA_S: - // Pawn push. The destination square must be empty. - if (!empty(to)) - return false; - break; - - case DELTA_NN: - // Double white pawn push. The destination square must be on the fourth - // rank, and both the destination square and the square between the - // source and destination squares must be empty. - if ( rank_of(to) != RANK_4 - || !empty(to) - || !empty(from + DELTA_N)) - return false; - break; - - case DELTA_SS: - // Double black pawn push. The destination square must be on the fifth - // rank, and both the destination square and the square between the - // source and destination squares must be empty. - if ( rank_of(to) != RANK_5 - || !empty(to) - || !empty(from + DELTA_S)) - return false; - break; - - default: - return false; - } - } - else if (!(attacks_from(pc, from) & to)) - return false; - - // Evasions generator already takes care to avoid some kind of illegal moves - // and pl_move_is_legal() relies on this. We therefore have to take care that - // the same kind of moves are filtered out here. - if (checkers()) - { - if (type_of(pc) != KING) - { - // Double check? In this case a king move is required - if (more_than_one(checkers())) - return false; - - // Our move must be a blocking evasion or a capture of the checking piece - if (!((between_bb(lsb(checkers()), king_square(us)) | checkers()) & to)) - return false; - } - // In case of king moves under check we have to remove king so as to catch - // invalid moves like b1a1 when opposite queen is on c1. - else if (attackers_to(to, pieces() ^ from) & pieces(~us)) - return false; - } - - return true; -} + Square from = from_sq(m); + Square to = to_sq(m); + // Is there a direct check? + if (check_squares(type_of(piece_on(from))) & to) + return true; -/// Position::gives_check() tests whether a pseudo-legal move gives a check - -bool Position::gives_check(Move m, const CheckInfo& ci) const { - - assert(is_ok(m)); - assert(ci.dcCandidates == discovered_check_candidates()); - assert(color_of(moved_piece(m)) == sideToMove); - - Square from = from_sq(m); - Square to = to_sq(m); - PieceType pt = type_of(piece_on(from)); - - // Is there a direct check? - if (ci.checkSq[pt] & to) - return true; - - // Is there a discovered check? - if ( unlikely(ci.dcCandidates) - && (ci.dcCandidates & from) - && !aligned(from, to, ci.ksq)) - return true; - - // Can we skip the ugly special cases? - if (type_of(m) == NORMAL) - return false; - - switch (type_of(m)) - { - case PROMOTION: - return attacks_bb(Piece(promotion_type(m)), to, pieces() ^ from) & ci.ksq; - - // En passant capture with check? We have already handled the case - // of direct checks and ordinary discovered check, so the only case we - // need to handle is the unusual case of a discovered check through - // the captured pawn. - case ENPASSANT: - { - Square capsq = file_of(to) | rank_of(from); - Bitboard b = (pieces() ^ from ^ capsq) | to; - - return (attacks_bb< ROOK>(ci.ksq, b) & pieces(sideToMove, QUEEN, ROOK)) - | (attacks_bb(ci.ksq, b) & pieces(sideToMove, QUEEN, BISHOP)); - } - case CASTLING: - { - Square kfrom = from; - Square rfrom = to; // Castling is encoded as 'King captures the rook' - Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1); - Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1); - - return (PseudoAttacks[ROOK][rto] & ci.ksq) - && (attacks_bb(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & ci.ksq); - } - default: - assert(false); - return false; - } -} + // Is there a discovered check? + if (blockers_for_king(~sideToMove) & from) + return !aligned(from, to, square(~sideToMove)) || type_of(m) == CASTLING; + switch (type_of(m)) + { + case NORMAL : + return false; -/// Position::do_move() makes a move, and saves all information necessary -/// to a StateInfo object. The move is assumed to be legal. Pseudo-legal -/// moves should be filtered out before this function is called. + case PROMOTION : + return attacks_bb(promotion_type(m), to, pieces() ^ from) & square(~sideToMove); -void Position::do_move(Move m, StateInfo& newSt) { + // En passant capture with check? We have already handled the case of direct + // checks and ordinary discovered check, so the only case we need to handle + // is the unusual case of a discovered check through the captured pawn. + case EN_PASSANT : { + Square capsq = make_square(file_of(to), rank_of(from)); + Bitboard b = (pieces() ^ from ^ capsq) | to; - CheckInfo ci(*this); - do_move(m, newSt, ci, gives_check(m, ci)); -} + return (attacks_bb(square(~sideToMove), b) & pieces(sideToMove, QUEEN, ROOK)) + | (attacks_bb(square(~sideToMove), b) + & pieces(sideToMove, QUEEN, BISHOP)); + } + default : //CASTLING + { + // Castling is encoded as 'king captures the rook' + Square rto = relative_square(sideToMove, to > from ? SQ_F1 : SQ_D1); -void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveIsCheck) { - - assert(is_ok(m)); - assert(&newSt != st); - - ++nodes; - Key k = st->key; - - // Copy some fields of the old state to our new StateInfo object except the - // ones which are going to be recalculated from scratch anyway and then switch - // our state pointer to point to the new (ready to be updated) state. - std::memcpy(&newSt, st, StateCopySize64 * sizeof(uint64_t)); - - newSt.previous = st; - st = &newSt; - - // Update side to move - k ^= Zobrist::side; - - // Increment ply counters. In particular, rule50 will be reset to zero later on - // in case of a capture or a pawn move. - ++gamePly; - ++st->rule50; - ++st->pliesFromNull; - - Color us = sideToMove; - Color them = ~us; - Square from = from_sq(m); - Square to = to_sq(m); - Piece pc = piece_on(from); - PieceType pt = type_of(pc); - PieceType captured = type_of(m) == ENPASSANT ? PAWN : type_of(piece_on(to)); - - assert(color_of(pc) == us); - assert(piece_on(to) == NO_PIECE || color_of(piece_on(to)) == them || type_of(m) == CASTLING); - assert(captured != KING); - - if (type_of(m) == CASTLING) - { - assert(pc == make_piece(us, KING)); - - bool kingSide = to > from; - Square rfrom = to; // Castling is encoded as "king captures friendly rook" - Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1); - to = relative_square(us, kingSide ? SQ_G1 : SQ_C1); - captured = NO_PIECE_TYPE; - - do_castling(from, to, rfrom, rto); - - st->psq += psq[us][ROOK][rto] - psq[us][ROOK][rfrom]; - k ^= Zobrist::psq[us][ROOK][rfrom] ^ Zobrist::psq[us][ROOK][rto]; - } - - if (captured) - { - Square capsq = to; - - // If the captured piece is a pawn, update pawn hash key, otherwise - // update non-pawn material. - if (captured == PAWN) - { - if (type_of(m) == ENPASSANT) - { - capsq += pawn_push(them); - - assert(pt == PAWN); - assert(to == st->epSquare); - assert(relative_rank(us, to) == RANK_6); - assert(piece_on(to) == NO_PIECE); - assert(piece_on(capsq) == make_piece(them, PAWN)); - - board[capsq] = NO_PIECE; - } - - st->pawnKey ^= Zobrist::psq[them][PAWN][capsq]; - } - else - st->npMaterial[them] -= PieceValue[MG][captured]; - - // Update board and piece lists - remove_piece(capsq, them, captured); - - // Update material hash key and prefetch access to materialTable - k ^= Zobrist::psq[them][captured][capsq]; - st->materialKey ^= Zobrist::psq[them][captured][pieceCount[them][captured]]; - prefetch((char*)thisThread->materialTable[st->materialKey]); - - // Update incremental scores - st->psq -= psq[them][captured][capsq]; - - // Reset rule 50 counter - st->rule50 = 0; - } - - // Update hash key - k ^= Zobrist::psq[us][pt][from] ^ Zobrist::psq[us][pt][to]; - - // Reset en passant square - if (st->epSquare != SQ_NONE) - { - k ^= Zobrist::enpassant[file_of(st->epSquare)]; - st->epSquare = SQ_NONE; - } - - // Update castling rights if needed - if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to])) - { - int cr = castlingRightsMask[from] | castlingRightsMask[to]; - k ^= Zobrist::castling[st->castlingRights & cr]; - st->castlingRights &= ~cr; - } - - // Prefetch TT access as soon as we know the new hash key - prefetch((char*)TT.first_entry(k)); - - // Move the piece. The tricky Chess960 castling is handled earlier - if (type_of(m) != CASTLING) - move_piece(from, to, us, pt); - - // If the moving piece is a pawn do some special extra work - if (pt == PAWN) - { - // Set en-passant square if the moved pawn can be captured - if ( (int(to) ^ int(from)) == 16 - && (attacks_from(from + pawn_push(us), us) & pieces(them, PAWN))) - { - st->epSquare = Square((from + to) / 2); - k ^= Zobrist::enpassant[file_of(st->epSquare)]; - } - - if (type_of(m) == PROMOTION) - { - PieceType promotion = promotion_type(m); - - assert(relative_rank(us, to) == RANK_8); - assert(promotion >= KNIGHT && promotion <= QUEEN); - - remove_piece(to, us, PAWN); - put_piece(to, us, promotion); - - // Update hash keys - k ^= Zobrist::psq[us][PAWN][to] ^ Zobrist::psq[us][promotion][to]; - st->pawnKey ^= Zobrist::psq[us][PAWN][to]; - st->materialKey ^= Zobrist::psq[us][promotion][pieceCount[us][promotion]-1] - ^ Zobrist::psq[us][PAWN][pieceCount[us][PAWN]]; - - // Update incremental score - st->psq += psq[us][promotion][to] - psq[us][PAWN][to]; - - // Update material - st->npMaterial[us] += PieceValue[MG][promotion]; - } - - // Update pawn hash key and prefetch access to pawnsTable - st->pawnKey ^= Zobrist::psq[us][PAWN][from] ^ Zobrist::psq[us][PAWN][to]; - prefetch((char*)thisThread->pawnsTable[st->pawnKey]); - - // Reset rule 50 draw counter - st->rule50 = 0; - } - - // Update incremental scores - st->psq += psq[us][pt][to] - psq[us][pt][from]; - - // Set capture piece - st->capturedType = captured; - - // Update the key with the final value - st->key = k; - - // Update checkers bitboard: piece must be already moved - st->checkersBB = 0; - - if (moveIsCheck) - { - if (type_of(m) != NORMAL) - st->checkersBB = attackers_to(king_square(them)) & pieces(us); - else - { - // Direct checks - if (ci.checkSq[pt] & to) - st->checkersBB |= to; - - // Discovered checks - if (ci.dcCandidates && (ci.dcCandidates & from)) - { - if (pt != ROOK) - st->checkersBB |= attacks_from(king_square(them)) & pieces(us, QUEEN, ROOK); - - if (pt != BISHOP) - st->checkersBB |= attacks_from(king_square(them)) & pieces(us, QUEEN, BISHOP); - } - } - } - - sideToMove = ~sideToMove; - - assert(pos_is_ok()); + return check_squares(ROOK) & rto; + } + } } -/// Position::undo_move() unmakes a move. When it returns, the position should -/// be restored to exactly the same state as before the move was made. +// Makes a move, and saves all information necessary +// to a StateInfo object. The move is assumed to be legal. Pseudo-legal +// moves should be filtered out before this function is called. +void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { + + assert(is_ok(m)); + assert(&newSt != st); + + thisThread->nodes.fetch_add(1, std::memory_order_relaxed); + Key k = st->key ^ Zobrist::side; + + // Copy some fields of the old state to our new StateInfo object except the + // ones which are going to be recalculated from scratch anyway and then switch + // our state pointer to point to the new (ready to be updated) state. + std::memcpy(&newSt, st, offsetof(StateInfo, key)); + newSt.previous = st; + st = &newSt; + + // Increment ply counters. In particular, rule50 will be reset to zero later on + // in case of a capture or a pawn move. + ++gamePly; + ++st->rule50; + ++st->pliesFromNull; + + // Used by NNUE + st->accumulator.computed[WHITE] = false; + st->accumulator.computed[BLACK] = false; + auto& dp = st->dirtyPiece; + dp.dirty_num = 1; + + Color us = sideToMove; + Color them = ~us; + Square from = from_sq(m); + Square to = to_sq(m); + Piece pc = piece_on(from); + Piece captured = type_of(m) == EN_PASSANT ? make_piece(them, PAWN) : piece_on(to); + + assert(color_of(pc) == us); + assert(captured == NO_PIECE || color_of(captured) == (type_of(m) != CASTLING ? them : us)); + assert(type_of(captured) != KING); + + if (type_of(m) == CASTLING) + { + assert(pc == make_piece(us, KING)); + assert(captured == make_piece(us, ROOK)); + + Square rfrom, rto; + do_castling(us, from, to, rfrom, rto); + + k ^= Zobrist::psq[captured][rfrom] ^ Zobrist::psq[captured][rto]; + captured = NO_PIECE; + } + + if (captured) + { + Square capsq = to; + + // If the captured piece is a pawn, update pawn hash key, otherwise + // update non-pawn material. + if (type_of(captured) == PAWN) + { + if (type_of(m) == EN_PASSANT) + { + capsq -= pawn_push(us); + + assert(pc == make_piece(us, PAWN)); + assert(to == st->epSquare); + assert(relative_rank(us, to) == RANK_6); + assert(piece_on(to) == NO_PIECE); + assert(piece_on(capsq) == make_piece(them, PAWN)); + } + + st->pawnKey ^= Zobrist::psq[captured][capsq]; + } + else + st->nonPawnMaterial[them] -= PieceValue[captured]; + + dp.dirty_num = 2; // 1 piece moved, 1 piece captured + dp.piece[1] = captured; + dp.from[1] = capsq; + dp.to[1] = SQ_NONE; + + // Update board and piece lists + remove_piece(capsq); + + // Update material hash key and prefetch access to materialTable + k ^= Zobrist::psq[captured][capsq]; + st->materialKey ^= Zobrist::psq[captured][pieceCount[captured]]; + + // Reset rule 50 counter + st->rule50 = 0; + } + + // Update hash key + k ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to]; + + // Reset en passant square + if (st->epSquare != SQ_NONE) + { + k ^= Zobrist::enpassant[file_of(st->epSquare)]; + st->epSquare = SQ_NONE; + } + + // Update castling rights if needed + if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to])) + { + k ^= Zobrist::castling[st->castlingRights]; + st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]); + k ^= Zobrist::castling[st->castlingRights]; + } + + // Move the piece. The tricky Chess960 castling is handled earlier + if (type_of(m) != CASTLING) + { + dp.piece[0] = pc; + dp.from[0] = from; + dp.to[0] = to; + + move_piece(from, to); + } + + // If the moving piece is a pawn do some special extra work + if (type_of(pc) == PAWN) + { + // Set en passant square if the moved pawn can be captured + if ((int(to) ^ int(from)) == 16 + && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN))) + { + st->epSquare = to - pawn_push(us); + k ^= Zobrist::enpassant[file_of(st->epSquare)]; + } + + else if (type_of(m) == PROMOTION) + { + Piece promotion = make_piece(us, promotion_type(m)); + + assert(relative_rank(us, to) == RANK_8); + assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN); + + remove_piece(to); + put_piece(promotion, to); + + // Promoting pawn to SQ_NONE, promoted piece from SQ_NONE + dp.to[0] = SQ_NONE; + dp.piece[dp.dirty_num] = promotion; + dp.from[dp.dirty_num] = SQ_NONE; + dp.to[dp.dirty_num] = to; + dp.dirty_num++; + + // Update hash keys + k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to]; + st->pawnKey ^= Zobrist::psq[pc][to]; + st->materialKey ^= + Zobrist::psq[promotion][pieceCount[promotion] - 1] ^ Zobrist::psq[pc][pieceCount[pc]]; + + // Update material + st->nonPawnMaterial[us] += PieceValue[promotion]; + } + + // Update pawn hash key + st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to]; + + // Reset rule 50 draw counter + st->rule50 = 0; + } + + // Set capture piece + st->capturedPiece = captured; + + // Update the key with the final value + st->key = k; + + // Calculate checkers bitboard (if move gives check) + st->checkersBB = givesCheck ? attackers_to(square(them)) & pieces(us) : 0; + + sideToMove = ~sideToMove; + + // Update king attacks used for fast check detection + set_check_info(); + + // Calculate the repetition info. It is the ply distance from the previous + // occurrence of the same position, negative in the 3-fold case, or zero + // if the position was not repeated. + st->repetition = 0; + int end = std::min(st->rule50, st->pliesFromNull); + if (end >= 4) + { + StateInfo* stp = st->previous->previous; + for (int i = 4; i <= end; i += 2) + { + stp = stp->previous->previous; + if (stp->key == st->key) + { + st->repetition = stp->repetition ? -i : i; + break; + } + } + } + + assert(pos_is_ok()); +} + +// Unmakes a move. When it returns, the position should +// be restored to exactly the same state as before the move was made. void Position::undo_move(Move m) { - assert(is_ok(m)); - - sideToMove = ~sideToMove; - - Color us = sideToMove; - Color them = ~us; - Square from = from_sq(m); - Square to = to_sq(m); - PieceType pt = type_of(piece_on(to)); - PieceType captured = st->capturedType; - - assert(empty(from) || type_of(m) == CASTLING); - assert(captured != KING); - - if (type_of(m) == PROMOTION) - { - PieceType promotion = promotion_type(m); - - assert(promotion == pt); - assert(relative_rank(us, to) == RANK_8); - assert(promotion >= KNIGHT && promotion <= QUEEN); - - remove_piece(to, us, promotion); - put_piece(to, us, PAWN); - pt = PAWN; - } - - if (type_of(m) == CASTLING) - { - bool kingSide = to > from; - Square rfrom = to; // Castling is encoded as "king captures friendly rook" - Square rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1); - to = relative_square(us, kingSide ? SQ_G1 : SQ_C1); - captured = NO_PIECE_TYPE; - pt = KING; - do_castling(to, from, rto, rfrom); - } - else - move_piece(to, from, us, pt); // Put the piece back at the source square - - if (captured) - { - Square capsq = to; - - if (type_of(m) == ENPASSANT) - { - capsq -= pawn_push(us); - - assert(pt == PAWN); - assert(to == st->previous->epSquare); - assert(relative_rank(us, to) == RANK_6); - assert(piece_on(capsq) == NO_PIECE); - } - - put_piece(capsq, them, captured); // Restore the captured piece - } - - // Finally point our state pointer back to the previous state - st = st->previous; - --gamePly; - - assert(pos_is_ok()); + assert(is_ok(m)); + + sideToMove = ~sideToMove; + + Color us = sideToMove; + Square from = from_sq(m); + Square to = to_sq(m); + Piece pc = piece_on(to); + + assert(empty(from) || type_of(m) == CASTLING); + assert(type_of(st->capturedPiece) != KING); + + if (type_of(m) == PROMOTION) + { + assert(relative_rank(us, to) == RANK_8); + assert(type_of(pc) == promotion_type(m)); + assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN); + + remove_piece(to); + pc = make_piece(us, PAWN); + put_piece(pc, to); + } + + if (type_of(m) == CASTLING) + { + Square rfrom, rto; + do_castling(us, from, to, rfrom, rto); + } + else + { + move_piece(to, from); // Put the piece back at the source square + + if (st->capturedPiece) + { + Square capsq = to; + + if (type_of(m) == EN_PASSANT) + { + capsq -= pawn_push(us); + + assert(type_of(pc) == PAWN); + assert(to == st->previous->epSquare); + assert(relative_rank(us, to) == RANK_6); + assert(piece_on(capsq) == NO_PIECE); + assert(st->capturedPiece == make_piece(~us, PAWN)); + } + + put_piece(st->capturedPiece, capsq); // Restore the captured piece + } + } + + // Finally point our state pointer back to the previous state + st = st->previous; + --gamePly; + + assert(pos_is_ok()); } -/// Position::do_castling() is a helper used to do/undo a castling move. This -/// is a bit tricky, especially in Chess960. - -void Position::do_castling(Square kfrom, Square kto, Square rfrom, Square rto) { - - // Remove both pieces first since squares could overlap in Chess960 - remove_piece(kfrom, sideToMove, KING); - remove_piece(rfrom, sideToMove, ROOK); - board[kfrom] = board[rfrom] = NO_PIECE; // Since remove_piece doesn't do it for us - put_piece(kto, sideToMove, KING); - put_piece(rto, sideToMove, ROOK); +// Helper used to do/undo a castling move. This is a bit +// tricky in Chess960 where from/to squares can overlap. +template +void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto) { + + bool kingSide = to > from; + rfrom = to; // Castling is encoded as "king captures friendly rook" + rto = relative_square(us, kingSide ? SQ_F1 : SQ_D1); + to = relative_square(us, kingSide ? SQ_G1 : SQ_C1); + + if (Do) + { + auto& dp = st->dirtyPiece; + dp.piece[0] = make_piece(us, KING); + dp.from[0] = from; + dp.to[0] = to; + dp.piece[1] = make_piece(us, ROOK); + dp.from[1] = rfrom; + dp.to[1] = rto; + dp.dirty_num = 2; + } + + // Remove both pieces first since squares could overlap in Chess960 + remove_piece(Do ? from : to); + remove_piece(Do ? rfrom : rto); + board[Do ? from : to] = board[Do ? rfrom : rto] = + NO_PIECE; // remove_piece does not do this for us + put_piece(make_piece(us, KING), Do ? to : from); + put_piece(make_piece(us, ROOK), Do ? rto : rfrom); } -/// Position::do(undo)_null_move() is used to do(undo) a "null move": It flips -/// the side to move without executing any move on the board. - +// Used to do a "null move": it flips +// the side to move without executing any move on the board. void Position::do_null_move(StateInfo& newSt) { - assert(!checkers()); + assert(!checkers()); + assert(&newSt != st); - std::memcpy(&newSt, st, sizeof(StateInfo)); // Fully copy here + std::memcpy(&newSt, st, offsetof(StateInfo, accumulator)); - newSt.previous = st; - st = &newSt; + newSt.previous = st; + st = &newSt; - if (st->epSquare != SQ_NONE) - { - st->key ^= Zobrist::enpassant[file_of(st->epSquare)]; - st->epSquare = SQ_NONE; - } + st->dirtyPiece.dirty_num = 0; + st->dirtyPiece.piece[0] = NO_PIECE; // Avoid checks in UpdateAccumulator() + st->accumulator.computed[WHITE] = false; + st->accumulator.computed[BLACK] = false; - st->key ^= Zobrist::side; - prefetch((char*)TT.first_entry(st->key)); + if (st->epSquare != SQ_NONE) + { + st->key ^= Zobrist::enpassant[file_of(st->epSquare)]; + st->epSquare = SQ_NONE; + } - ++st->rule50; - st->pliesFromNull = 0; + st->key ^= Zobrist::side; + ++st->rule50; + prefetch(TT.first_entry(key())); - sideToMove = ~sideToMove; + st->pliesFromNull = 0; - assert(pos_is_ok()); -} + sideToMove = ~sideToMove; -void Position::undo_null_move() { + set_check_info(); - assert(!checkers()); + st->repetition = 0; - st = st->previous; - sideToMove = ~sideToMove; + assert(pos_is_ok()); } -/// Position::see() is a static exchange evaluator: It tries to estimate the -/// material gain or loss resulting from a move. - -Value Position::see_sign(Move m) const { - - assert(is_ok(m)); +// Must be used to undo a "null move" +void Position::undo_null_move() { - // Early return if SEE cannot be negative because captured piece value - // is not less then capturing one. Note that king moves always return - // here because king midgame value is set to 0. - if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))]) - return VALUE_KNOWN_WIN; + assert(!checkers()); - return see(m); + st = st->previous; + sideToMove = ~sideToMove; } -Value Position::see(Move m) const { - - Square from, to; - Bitboard occupied, attackers, stmAttackers; - Value swapList[32]; - int slIndex = 1; - PieceType captured; - Color stm; - - assert(is_ok(m)); - - from = from_sq(m); - to = to_sq(m); - swapList[0] = PieceValue[MG][piece_on(to)]; - stm = color_of(piece_on(from)); - occupied = pieces() ^ from; - - // Castling moves are implemented as king capturing the rook so cannot be - // handled correctly. Simply return 0 that is always the correct value - // unless in the rare case the rook ends up under attack. - if (type_of(m) == CASTLING) - return VALUE_ZERO; - - if (type_of(m) == ENPASSANT) - { - occupied ^= to - pawn_push(stm); // Remove the captured pawn - swapList[0] = PieceValue[MG][PAWN]; - } - - // Find all attackers to the destination square, with the moving piece - // removed, but possibly an X-ray attacker added behind it. - attackers = attackers_to(to, occupied) & occupied; - - // If the opponent has no attackers we are finished - stm = ~stm; - stmAttackers = attackers & pieces(stm); - if (!stmAttackers) - return swapList[0]; - - // The destination square is defended, which makes things rather more - // difficult to compute. We proceed by building up a "swap list" containing - // the material gain or loss at each stop in a sequence of captures to the - // destination square, where the sides alternately capture, and always - // capture with the least valuable piece. After each capture, we look for - // new X-ray attacks from behind the capturing piece. - captured = type_of(piece_on(from)); - - do { - assert(slIndex < 32); - - // Add the new entry to the swap list - swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][captured]; - - // Locate and remove the next least valuable attacker - captured = min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); - - // Stop before processing a king capture - if (captured == KING) - { - if (stmAttackers == attackers) - ++slIndex; - - break; - } - - stm = ~stm; - stmAttackers = attackers & pieces(stm); - ++slIndex; - - } while (stmAttackers); - - // Having built the swap list, we negamax through it to find the best - // achievable score from the point of view of the side to move. - while (--slIndex) - swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]); - - return swapList[0]; -} +// Computes the new hash key after the given move. Needed +// for speculative prefetch. It doesn't recognize special moves like castling, +// en passant and promotions. +Key Position::key_after(Move m) const { -/// Position::clear() erases the position object to a pristine state, with an -/// empty board, white to move, and no castling rights. + Square from = from_sq(m); + Square to = to_sq(m); + Piece pc = piece_on(from); + Piece captured = piece_on(to); + Key k = st->key ^ Zobrist::side; -void Position::clear() { + if (captured) + k ^= Zobrist::psq[captured][to]; - std::memset(this, 0, sizeof(Position)); - startState.epSquare = SQ_NONE; - st = &startState; + k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[pc][from]; - for (int i = 0; i < PIECE_TYPE_NB; ++i) - for (int j = 0; j < 16; ++j) - pieceList[WHITE][i][j] = pieceList[BLACK][i][j] = SQ_NONE; + return (captured || type_of(pc) == PAWN) ? k : adjust_key50(k); } -/// Position::compute_key() computes the hash key of the position. The hash -/// key is usually updated incrementally as moves are made and unmade. The -/// compute_key() function is only used when a new position is set up, and -/// to verify the correctness of the hash key when running in debug mode. - -Key Position::compute_key() const { - - Key k = Zobrist::castling[st->castlingRights]; - - for (Bitboard b = pieces(); b; ) - { - Square s = pop_lsb(&b); - k ^= Zobrist::psq[color_of(piece_on(s))][type_of(piece_on(s))][s]; - } - - if (ep_square() != SQ_NONE) - k ^= Zobrist::enpassant[file_of(ep_square())]; - - if (sideToMove == BLACK) - k ^= Zobrist::side; - - return k; +// Tests if the SEE (Static Exchange Evaluation) +// value of move is greater or equal to the given threshold. We'll use an +// algorithm similar to alpha-beta pruning with a null window. +bool Position::see_ge(Move m, Value threshold) const { + + assert(is_ok(m)); + + // Only deal with normal moves, assume others pass a simple SEE + if (type_of(m) != NORMAL) + return VALUE_ZERO >= threshold; + + Square from = from_sq(m), to = to_sq(m); + + int swap = PieceValue[piece_on(to)] - threshold; + if (swap < 0) + return false; + + swap = PieceValue[piece_on(from)] - swap; + if (swap <= 0) + return true; + + assert(color_of(piece_on(from)) == sideToMove); + Bitboard occupied = pieces() ^ from ^ to; // xoring to is important for pinned piece logic + Color stm = sideToMove; + Bitboard attackers = attackers_to(to, occupied); + Bitboard stmAttackers, bb; + int res = 1; + + while (true) + { + stm = ~stm; + attackers &= occupied; + + // If stm has no more attackers then give up: stm loses + if (!(stmAttackers = attackers & pieces(stm))) + break; + + // Don't allow pinned pieces to attack as long as there are + // pinners on their original square. + if (pinners(~stm) & occupied) + { + stmAttackers &= ~blockers_for_king(stm); + + if (!stmAttackers) + break; + } + + res ^= 1; + + // Locate and remove the next least valuable attacker, and add to + // the bitboard 'attackers' any X-ray attackers behind it. + if ((bb = stmAttackers & pieces(PAWN))) + { + if ((swap = PawnValue - swap) < res) + break; + occupied ^= least_significant_square_bb(bb); + + attackers |= attacks_bb(to, occupied) & pieces(BISHOP, QUEEN); + } + + else if ((bb = stmAttackers & pieces(KNIGHT))) + { + if ((swap = KnightValue - swap) < res) + break; + occupied ^= least_significant_square_bb(bb); + } + + else if ((bb = stmAttackers & pieces(BISHOP))) + { + if ((swap = BishopValue - swap) < res) + break; + occupied ^= least_significant_square_bb(bb); + + attackers |= attacks_bb(to, occupied) & pieces(BISHOP, QUEEN); + } + + else if ((bb = stmAttackers & pieces(ROOK))) + { + if ((swap = RookValue - swap) < res) + break; + occupied ^= least_significant_square_bb(bb); + + attackers |= attacks_bb(to, occupied) & pieces(ROOK, QUEEN); + } + + else if ((bb = stmAttackers & pieces(QUEEN))) + { + if ((swap = QueenValue - swap) < res) + break; + occupied ^= least_significant_square_bb(bb); + + attackers |= (attacks_bb(to, occupied) & pieces(BISHOP, QUEEN)) + | (attacks_bb(to, occupied) & pieces(ROOK, QUEEN)); + } + + else // KING + // If we "capture" with the king but the opponent still has attackers, + // reverse the result. + return (attackers & ~pieces(stm)) ? res ^ 1 : res; + } + + return bool(res); } +// Tests whether the position is drawn by 50-move rule +// or by repetition. It does not detect stalemates. +bool Position::is_draw(int ply) const { -/// Position::compute_pawn_key() computes the hash key of the position. The -/// hash key is usually updated incrementally as moves are made and unmade. -/// The compute_pawn_key() function is only used when a new position is set -/// up, and to verify the correctness of the pawn hash key when running in -/// debug mode. - -Key Position::compute_pawn_key() const { + if (st->rule50 > 99 && (!checkers() || MoveList(*this).size())) + return true; - Key k = 0; - - for (Bitboard b = pieces(PAWN); b; ) - { - Square s = pop_lsb(&b); - k ^= Zobrist::psq[color_of(piece_on(s))][PAWN][s]; - } - - return k; + // Return a draw score if a position repeats once earlier but strictly + // after the root, or repeats twice before or at the root. + return st->repetition && st->repetition < ply; } -/// Position::compute_material_key() computes the hash key of the position. -/// The hash key is usually updated incrementally as moves are made and unmade. -/// The compute_material_key() function is only used when a new position is set -/// up, and to verify the correctness of the material hash key when running in -/// debug mode. - -Key Position::compute_material_key() const { - - Key k = 0; +// Tests whether there has been at least one repetition +// of positions since the last capture or pawn move. +bool Position::has_repeated() const { - for (Color c = WHITE; c <= BLACK; ++c) - for (PieceType pt = PAWN; pt <= KING; ++pt) - for (int cnt = 0; cnt < pieceCount[c][pt]; ++cnt) - k ^= Zobrist::psq[c][pt][cnt]; + StateInfo* stc = st; + int end = std::min(st->rule50, st->pliesFromNull); + while (end-- >= 4) + { + if (stc->repetition) + return true; - return k; + stc = stc->previous; + } + return false; } -/// Position::compute_psq_score() computes the incremental scores for the middlegame -/// and the endgame. These functions are used to initialize the incremental scores -/// when a new position is set up, and to verify that the scores are correctly -/// updated by do_move and undo_move when the program is running in debug mode. +// Tests if the position has a move which draws by repetition, +// or an earlier position has a move that directly reaches the current position. +bool Position::has_game_cycle(int ply) const { -Score Position::compute_psq_score() const { + int j; - Score score = SCORE_ZERO; + int end = std::min(st->rule50, st->pliesFromNull); - for (Bitboard b = pieces(); b; ) - { - Square s = pop_lsb(&b); - Piece pc = piece_on(s); - score += psq[color_of(pc)][type_of(pc)][s]; - } - - return score; -} + if (end < 3) + return false; + Key originalKey = st->key; + StateInfo* stp = st->previous; -/// Position::compute_non_pawn_material() computes the total non-pawn middlegame -/// material value for the given side. Material values are updated incrementally -/// during the search. This function is only used when initializing a new Position -/// object. + for (int i = 3; i <= end; i += 2) + { + stp = stp->previous->previous; -Value Position::compute_non_pawn_material(Color c) const { + Key moveKey = originalKey ^ stp->key; + if ((j = H1(moveKey), cuckoo[j] == moveKey) || (j = H2(moveKey), cuckoo[j] == moveKey)) + { + Move move = cuckooMove[j]; + Square s1 = from_sq(move); + Square s2 = to_sq(move); - Value value = VALUE_ZERO; + if (!((between_bb(s1, s2) ^ s2) & pieces())) + { + if (ply > i) + return true; - for (PieceType pt = KNIGHT; pt <= QUEEN; ++pt) - value += pieceCount[c][pt] * PieceValue[MG][pt]; + // For nodes before or at the root, check that the move is a + // repetition rather than a move to the current position. + // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in + // the same location, so we have to select which square to check. + if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move()) + continue; - return value; + // For repetitions before or at the root, require one more + if (stp->repetition) + return true; + } + } + } + return false; } -/// Position::is_draw() tests whether the position is drawn by material, 50 moves -/// rule or repetition. It does not detect stalemates. +// Flips position with the white and black sides reversed. This +// is only useful for debugging e.g. for finding evaluation symmetry bugs. +void Position::flip() { -bool Position::is_draw() const { + string f, token; + std::stringstream ss(fen()); - if ( !pieces(PAWN) - && (non_pawn_material(WHITE) + non_pawn_material(BLACK) <= BishopValueMg)) - return true; + for (Rank r = RANK_8; r >= RANK_1; --r) // Piece placement + { + std::getline(ss, token, r > RANK_1 ? '/' : ' '); + f.insert(0, token + (f.empty() ? " " : "/")); + } - if (st->rule50 > 99 && (!checkers() || MoveList(*this).size())) - return true; + ss >> token; // Active color + f += (token == "w" ? "B " : "W "); // Will be lowercased later - StateInfo* stp = st; - for (int i = 2, e = std::min(st->rule50, st->pliesFromNull); i <= e; i += 2) - { - stp = stp->previous->previous; + ss >> token; // Castling availability + f += token + " "; - if (stp->key == st->key) - return true; // Draw at first repetition - } + std::transform(f.begin(), f.end(), f.begin(), + [](char c) { return char(islower(c) ? toupper(c) : tolower(c)); }); - return false; -} + ss >> token; // En passant square + f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3")); + std::getline(ss, token); // Half and full moves + f += token; -/// Position::flip() flips position with the white and black sides reversed. This -/// is only useful for debugging e.g. for finding evaluation symmetry bugs. + set(f, is_chess960(), st, this_thread()); -static char toggle_case(char c) { - return char(islower(c) ? toupper(c) : tolower(c)); + assert(pos_is_ok()); } -void Position::flip() { - - string f, token; - std::stringstream ss(fen()); - for (Rank rank = RANK_8; rank >= RANK_1; --rank) // Piece placement - { - std::getline(ss, token, rank > RANK_1 ? '/' : ' '); - f.insert(0, token + (f.empty() ? " " : "/")); - } +// Performs some consistency checks for the position object +// and raise an assert if something wrong is detected. +// This is meant to be helpful when debugging. +bool Position::pos_is_ok() const { - ss >> token; // Active color - f += (token == "w" ? "B " : "W "); // Will be lowercased later + constexpr bool Fast = true; // Quick (default) or full check? - ss >> token; // Castling availability - f += token + " "; + if ((sideToMove != WHITE && sideToMove != BLACK) || piece_on(square(WHITE)) != W_KING + || piece_on(square(BLACK)) != B_KING + || (ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6)) + assert(0 && "pos_is_ok: Default"); - std::transform(f.begin(), f.end(), f.begin(), toggle_case); + if (Fast) + return true; - ss >> token; // En passant square - f += (token == "-" ? token : token.replace(1, 1, token[1] == '3' ? "6" : "3")); + if (pieceCount[W_KING] != 1 || pieceCount[B_KING] != 1 + || attackers_to(square(~sideToMove)) & pieces(sideToMove)) + assert(0 && "pos_is_ok: Kings"); - std::getline(ss, token); // Half and full moves - f += token; + if ((pieces(PAWN) & (Rank1BB | Rank8BB)) || pieceCount[W_PAWN] > 8 || pieceCount[B_PAWN] > 8) + assert(0 && "pos_is_ok: Pawns"); - set(f, is_chess960(), this_thread()); + if ((pieces(WHITE) & pieces(BLACK)) || (pieces(WHITE) | pieces(BLACK)) != pieces() + || popcount(pieces(WHITE)) > 16 || popcount(pieces(BLACK)) > 16) + assert(0 && "pos_is_ok: Bitboards"); - assert(pos_is_ok()); -} + for (PieceType p1 = PAWN; p1 <= KING; ++p1) + for (PieceType p2 = PAWN; p2 <= KING; ++p2) + if (p1 != p2 && (pieces(p1) & pieces(p2))) + assert(0 && "pos_is_ok: Bitboards"); -/// Position::pos_is_ok() performs some consistency checks for the position object. -/// This is meant to be helpful when debugging. + for (Piece pc : Pieces) + if (pieceCount[pc] != popcount(pieces(color_of(pc), type_of(pc))) + || pieceCount[pc] != std::count(board, board + SQUARE_NB, pc)) + assert(0 && "pos_is_ok: Pieces"); -bool Position::pos_is_ok(int* failedStep) const { + for (Color c : {WHITE, BLACK}) + for (CastlingRights cr : {c & KING_SIDE, c & QUEEN_SIDE}) + { + if (!can_castle(cr)) + continue; - int dummy, *step = failedStep ? failedStep : &dummy; + if (piece_on(castlingRookSquare[cr]) != make_piece(c, ROOK) + || castlingRightsMask[castlingRookSquare[cr]] != cr + || (castlingRightsMask[square(c)] & cr) != cr) + assert(0 && "pos_is_ok: Castling"); + } - // What features of the position should be verified? - const bool all = false; - - const bool debugBitboards = all || false; - const bool debugKingCount = all || false; - const bool debugKingCapture = all || false; - const bool debugCheckerCount = all || false; - const bool debugKey = all || false; - const bool debugMaterialKey = all || false; - const bool debugPawnKey = all || false; - const bool debugIncrementalEval = all || false; - const bool debugNonPawnMaterial = all || false; - const bool debugPieceCounts = all || false; - const bool debugPieceList = all || false; - const bool debugCastlingSquares = all || false; - - *step = 1; - - if (sideToMove != WHITE && sideToMove != BLACK) - return false; - - if ((*step)++, piece_on(king_square(WHITE)) != W_KING) - return false; - - if ((*step)++, piece_on(king_square(BLACK)) != B_KING) - return false; - - if ((*step)++, debugKingCount) - { - int kingCount[COLOR_NB] = {}; - - for (Square s = SQ_A1; s <= SQ_H8; ++s) - if (type_of(piece_on(s)) == KING) - ++kingCount[color_of(piece_on(s))]; - - if (kingCount[0] != 1 || kingCount[1] != 1) - return false; - } - - if ((*step)++, debugKingCapture) - if (attackers_to(king_square(~sideToMove)) & pieces(sideToMove)) - return false; - - if ((*step)++, debugCheckerCount && popcount(st->checkersBB) > 2) - return false; - - if ((*step)++, debugBitboards) - { - // The intersection of the white and black pieces must be empty - if (pieces(WHITE) & pieces(BLACK)) - return false; - - // The union of the white and black pieces must be equal to all - // occupied squares - if ((pieces(WHITE) | pieces(BLACK)) != pieces()) - return false; - - // Separate piece type bitboards must have empty intersections - for (PieceType p1 = PAWN; p1 <= KING; ++p1) - for (PieceType p2 = PAWN; p2 <= KING; ++p2) - if (p1 != p2 && (pieces(p1) & pieces(p2))) - return false; - } - - if ((*step)++, ep_square() != SQ_NONE && relative_rank(sideToMove, ep_square()) != RANK_6) - return false; - - if ((*step)++, debugKey && st->key != compute_key()) - return false; - - if ((*step)++, debugPawnKey && st->pawnKey != compute_pawn_key()) - return false; - - if ((*step)++, debugMaterialKey && st->materialKey != compute_material_key()) - return false; - - if ((*step)++, debugIncrementalEval && st->psq != compute_psq_score()) - return false; - - if ((*step)++, debugNonPawnMaterial) - if ( st->npMaterial[WHITE] != compute_non_pawn_material(WHITE) - || st->npMaterial[BLACK] != compute_non_pawn_material(BLACK)) - return false; - - if ((*step)++, debugPieceCounts) - for (Color c = WHITE; c <= BLACK; ++c) - for (PieceType pt = PAWN; pt <= KING; ++pt) - if (pieceCount[c][pt] != popcount(pieces(c, pt))) - return false; - - if ((*step)++, debugPieceList) - for (Color c = WHITE; c <= BLACK; ++c) - for (PieceType pt = PAWN; pt <= KING; ++pt) - for (int i = 0; i < pieceCount[c][pt]; ++i) - if ( board[pieceList[c][pt][i]] != make_piece(c, pt) - || index[pieceList[c][pt][i]] != i) - return false; - - if ((*step)++, debugCastlingSquares) - for (Color c = WHITE; c <= BLACK; ++c) - for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1)) - { - if (!can_castle(c | s)) - continue; - - if ( (castlingRightsMask[king_square(c)] & (c | s)) != (c | s) - || piece_on(castlingRookSquare[c | s]) != make_piece(c, ROOK) - || castlingRightsMask[castlingRookSquare[c | s]] != (c | s)) - return false; - } - - *step = 0; - return true; + return true; } + +} // namespace Stockfish