X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fposition.cpp;h=6abef5b47bcb42c764901fdc0cb7a871d7e80039;hb=a1c02815ccc5824fe8737d1d6fab8aef09874a07;hp=35e2627634ed2f9f0926dfc9216bb6e9382f3dfd;hpb=e6376d9b8daae0aa0dcda618ec6330bda2dcfaf7;p=stockfish diff --git a/src/position.cpp b/src/position.cpp index 35e26276..6abef5b4 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -31,11 +31,11 @@ #include #include "bitcount.h" -#include "mersenne.h" #include "movegen.h" #include "movepick.h" #include "position.h" #include "psqtab.h" +#include "rkiss.h" #include "san.h" #include "tt.h" #include "ucioption.h" @@ -44,9 +44,54 @@ using std::string; using std::cout; using std::endl; -static inline bool isZero(char c) { return c == '0'; } -struct PieceLetters : std::map { +//// +//// Position's static data definitions +//// + +Key Position::zobrist[2][8][64]; +Key Position::zobEp[64]; +Key Position::zobCastle[16]; +Key Position::zobSideToMove; +Key Position::zobExclusion; + +Score Position::PieceSquareTable[16][64]; + +// Material values arrays, indexed by Piece +const Value Position::PieceValueMidgame[17] = { + VALUE_ZERO, + PawnValueMidgame, KnightValueMidgame, BishopValueMidgame, + RookValueMidgame, QueenValueMidgame, VALUE_ZERO, + VALUE_ZERO, VALUE_ZERO, + PawnValueMidgame, KnightValueMidgame, BishopValueMidgame, + RookValueMidgame, QueenValueMidgame +}; + +const Value Position::PieceValueEndgame[17] = { + VALUE_ZERO, + PawnValueEndgame, KnightValueEndgame, BishopValueEndgame, + RookValueEndgame, QueenValueEndgame, VALUE_ZERO, + VALUE_ZERO, VALUE_ZERO, + PawnValueEndgame, KnightValueEndgame, BishopValueEndgame, + RookValueEndgame, QueenValueEndgame +}; + +// Material values array used by SEE, indexed by PieceType +const Value Position::seeValues[] = { + VALUE_ZERO, + PawnValueMidgame, KnightValueMidgame, BishopValueMidgame, + RookValueMidgame, QueenValueMidgame, QueenValueMidgame*10 +}; + + +namespace { + + // Bonus for having the side to move (modified by Joona Kiiski) + const Score TempoValue = make_score(48, 22); + + bool isZero(char c) { return c == '0'; } + + struct PieceLetters : public std::map { PieceLetters() { @@ -69,24 +114,11 @@ struct PieceLetters : std::map { assert(false); return 0; } -}; - -//// -//// Variables -//// - -Key Position::zobrist[2][8][64]; -Key Position::zobEp[64]; -Key Position::zobCastle[16]; -Key Position::zobSideToMove; -Key Position::zobExclusion; - -Score Position::PieceSquareTable[16][64]; - -static PieceLetters pieceLetters; + } pieceLetters; +} -/// Constructors +/// CheckInfo c'tor CheckInfo::CheckInfo(const Position& pos) { @@ -109,13 +141,12 @@ CheckInfo::CheckInfo(const Position& pos) { /// or the FEN string, we want the new born Position object do not depend /// on any external data so we detach state pointer from the source one. -Position::Position(int th) : threadID(th) {} - Position::Position(const Position& pos, int th) { memcpy(this, &pos, sizeof(Position)); detach(); // Always detach() in copy c'tor to avoid surprises threadID = th; + nodes = 0; } Position::Position(const string& fen, int th) { @@ -182,7 +213,7 @@ void Position::from_fen(const string& fen) { { if (isdigit(token)) { - file += token - '0'; // Skip the given number of files + file += File(token - '0'); // Skip the given number of files continue; } else if (token == '/') @@ -240,6 +271,10 @@ void Position::from_fen(const string& fen) { castleRightsMask[make_square(initialQRFile, RANK_1)] ^= WHITE_OOO; castleRightsMask[make_square(initialQRFile, RANK_8)] ^= BLACK_OOO; + isChess960 = initialKFile != FILE_E + || initialQRFile != FILE_A + || initialKRFile != FILE_H; + find_checkers(); st->key = compute_key(); @@ -346,21 +381,17 @@ const string Position::to_fen() const { if (st->castleRights != CASTLES_NONE) { - const bool Chess960 = initialKFile != FILE_E - || initialQRFile != FILE_A - || initialKRFile != FILE_H; - if (can_castle_kingside(WHITE)) - fen += Chess960 ? char(toupper(file_to_char(initialKRFile))) : 'K'; + fen += isChess960 ? char(toupper(file_to_char(initialKRFile))) : 'K'; if (can_castle_queenside(WHITE)) - fen += Chess960 ? char(toupper(file_to_char(initialQRFile))) : 'Q'; + fen += isChess960 ? char(toupper(file_to_char(initialQRFile))) : 'Q'; if (can_castle_kingside(BLACK)) - fen += Chess960 ? file_to_char(initialKRFile) : 'k'; + fen += isChess960 ? file_to_char(initialKRFile) : 'k'; if (can_castle_queenside(BLACK)) - fen += Chess960 ? file_to_char(initialQRFile) : 'q'; + fen += isChess960 ? file_to_char(initialQRFile) : 'q'; } else fen += '-'; @@ -370,7 +401,7 @@ const string Position::to_fen() const { /// Position::print() prints an ASCII representation of the position to -/// the standard output. If a move is given then also the san is print. +/// the standard output. If a move is given then also the san is printed. void Position::print(Move move) const { @@ -511,6 +542,7 @@ bool Position::move_attacks_square(Move m, Square s) const { assert(move_is_ok(m)); assert(square_is_ok(s)); + Bitboard occ, xray; Square f = move_from(m), t = move_to(m); assert(square_is_occupied(f)); @@ -519,12 +551,11 @@ bool Position::move_attacks_square(Move m, Square s) const { return true; // Move the piece and scan for X-ray attacks behind it - Bitboard occ = occupied_squares(); - Color us = color_of_piece_on(f); - clear_bit(&occ, f); - set_bit(&occ, t); - Bitboard xray = ( (rook_attacks_bb(s, occ) & pieces(ROOK, QUEEN)) - |(bishop_attacks_bb(s, occ) & pieces(BISHOP, QUEEN))) & pieces_of_color(us); + occ = occupied_squares(); + do_move_bb(&occ, make_move_bb(f, t)); + xray = ( (rook_attacks_bb(s, occ) & pieces(ROOK, QUEEN)) + |(bishop_attacks_bb(s, occ) & pieces(BISHOP, QUEEN))) + & pieces_of_color(color_of_piece_on(f)); // If we have attacks we need to verify that are caused by our move // and are not already existent ones. @@ -740,6 +771,7 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI assert(is_ok()); assert(move_is_ok(m)); + nodes++; Key key = st->key; // Copy some fields of old state to our new StateInfo object except the @@ -753,7 +785,9 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI Value npMaterial[2]; }; - memcpy(&newSt, st, sizeof(ReducedStateInfo)); + if (&newSt != st) + memcpy(&newSt, st, sizeof(ReducedStateInfo)); + newSt.previous = st; st = &newSt; @@ -839,8 +873,9 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI // Reset rule 50 draw counter st->rule50 = 0; - // Update pawn hash key + // Update pawn hash key and prefetch in L1/L2 cache st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to]; + prefetchPawn(st->pawnKey, threadID); // Set en passant square, only if moved pawn can be captured if ((to ^ from) == 16) @@ -889,7 +924,7 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI st->value += pst(us, promotion, to); // Update material - st->npMaterial[us] += piece_value_midgame(promotion); + st->npMaterial[us] += PieceValueMidgame[promotion]; } } @@ -962,7 +997,7 @@ void Position::do_capture_move(Key& key, PieceType capture, Color them, Square t st->pawnKey ^= zobrist[them][PAWN][capsq]; } else - st->npMaterial[them] -= piece_value_midgame(capture); + st->npMaterial[them] -= PieceValueMidgame[capture]; // Remove captured piece clear_bit(&(byColorBB[them]), capsq); @@ -1332,12 +1367,6 @@ void Position::undo_null_move() { /// move, and one which takes a 'from' and a 'to' square. The function does /// not yet understand promotions captures. -int Position::see(Square to) const { - - assert(square_is_ok(to)); - return see(SQ_NONE, to); -} - int Position::see(Move m) const { assert(move_is_ok(m)); @@ -1362,82 +1391,50 @@ int Position::see_sign(Move m) const { int Position::see(Square from, Square to) const { - // Material values - static const int seeValues[18] = { - 0, PawnValueMidgame, KnightValueMidgame, BishopValueMidgame, - RookValueMidgame, QueenValueMidgame, QueenValueMidgame*10, 0, - 0, PawnValueMidgame, KnightValueMidgame, BishopValueMidgame, - RookValueMidgame, QueenValueMidgame, QueenValueMidgame*10, 0, - 0, 0 - }; + Bitboard occ, attackers, stmAttackers, b; + int swapList[32], slIndex = 1; + PieceType capturedType, pt; + Color stm; - Bitboard attackers, stmAttackers, b; - - assert(square_is_ok(from) || from == SQ_NONE); + assert(square_is_ok(from)); assert(square_is_ok(to)); - // Initialize colors - Color us = (from != SQ_NONE ? color_of_piece_on(from) : opposite_color(color_of_piece_on(to))); - Color them = opposite_color(us); - - // Initialize pieces - Piece piece = piece_on(from); - Piece capture = piece_on(to); - Bitboard occ = occupied_squares(); + capturedType = type_of_piece_on(to); // King cannot be recaptured - if (type_of_piece(piece) == KING) - return seeValues[capture]; + if (capturedType == KING) + return seeValues[capturedType]; + + occ = occupied_squares(); // Handle en passant moves if (st->epSquare == to && type_of_piece_on(from) == PAWN) { - assert(capture == PIECE_NONE); + Square capQq = (side_to_move() == WHITE) ? (to - DELTA_N) : (to - DELTA_S); - Square capQq = (side_to_move() == WHITE)? (to - DELTA_N) : (to - DELTA_S); - capture = piece_on(capQq); + assert(capturedType == PIECE_TYPE_NONE); assert(type_of_piece_on(capQq) == PAWN); // Remove the captured pawn clear_bit(&occ, capQq); + capturedType = PAWN; } - while (true) - { - // Find all attackers to the destination square, with the moving piece - // removed, but possibly an X-ray attacker added behind it. - clear_bit(&occ, from); - attackers = (rook_attacks_bb(to, occ) & pieces(ROOK, QUEEN)) - | (bishop_attacks_bb(to, occ) & pieces(BISHOP, QUEEN)) - | (attacks_from(to) & pieces(KNIGHT)) - | (attacks_from(to) & pieces(KING)) - | (attacks_from(to, WHITE) & pieces(PAWN, BLACK)) - | (attacks_from(to, BLACK) & pieces(PAWN, WHITE)); - - if (from != SQ_NONE) - break; - - // If we don't have any attacker we are finished - if ((attackers & pieces_of_color(us)) == EmptyBoardBB) - return 0; - - // Locate the least valuable attacker to the destination square - // and use it to initialize from square. - stmAttackers = attackers & pieces_of_color(us); - PieceType pt; - for (pt = PAWN; !(stmAttackers & pieces(pt)); pt++) - assert(pt < KING); - - from = first_1(stmAttackers & pieces(pt)); - piece = piece_on(from); - } + // Find all attackers to the destination square, with the moving piece + // removed, but possibly an X-ray attacker added behind it. + clear_bit(&occ, from); + attackers = (rook_attacks_bb(to, occ) & pieces(ROOK, QUEEN)) + | (bishop_attacks_bb(to, occ) & pieces(BISHOP, QUEEN)) + | (attacks_from(to) & pieces(KNIGHT)) + | (attacks_from(to) & pieces(KING)) + | (attacks_from(to, WHITE) & pieces(PAWN, BLACK)) + | (attacks_from(to, BLACK) & pieces(PAWN, WHITE)); // If the opponent has no attackers we are finished - stmAttackers = attackers & pieces_of_color(them); + stm = opposite_color(color_of_piece_on(from)); + stmAttackers = attackers & pieces_of_color(stm); if (!stmAttackers) - return seeValues[capture]; - - attackers &= occ; // Remove the moving piece + return seeValues[capturedType]; // The destination square is defended, which makes things rather more // difficult to compute. We proceed by building up a "swap list" containing @@ -1445,12 +1442,8 @@ int Position::see(Square from, Square to) const { // 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. - int lastCapturingPieceValue = seeValues[piece]; - int swapList[32], n = 1; - Color c = them; - PieceType pt; - - swapList[0] = seeValues[capture]; + swapList[0] = seeValues[capturedType]; + capturedType = type_of_piece_on(from); do { // Locate the least valuable attacker for the side to move. The loop @@ -1463,35 +1456,35 @@ int Position::see(Square from, Square to) const { // and scan for new X-ray attacks behind the attacker. b = stmAttackers & pieces(pt); occ ^= (b & (~b + 1)); - attackers |= (rook_attacks_bb(to, occ) & pieces(ROOK, QUEEN)) + attackers |= (rook_attacks_bb(to, occ) & pieces(ROOK, QUEEN)) | (bishop_attacks_bb(to, occ) & pieces(BISHOP, QUEEN)); - attackers &= occ; + attackers &= occ; // Cut out pieces we've already done // Add the new entry to the swap list - assert(n < 32); - swapList[n] = -swapList[n - 1] + lastCapturingPieceValue; - n++; + assert(slIndex < 32); + swapList[slIndex] = -swapList[slIndex - 1] + seeValues[capturedType]; + slIndex++; // Remember the value of the capturing piece, and change the side to move // before beginning the next iteration - lastCapturingPieceValue = seeValues[pt]; - c = opposite_color(c); - stmAttackers = attackers & pieces_of_color(c); + capturedType = pt; + stm = opposite_color(stm); + stmAttackers = attackers & pieces_of_color(stm); // Stop after a king capture if (pt == KING && stmAttackers) { - assert(n < 32); - swapList[n++] = QueenValueMidgame*10; + assert(slIndex < 32); + swapList[slIndex++] = QueenValueMidgame*10; break; } } 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 (--n) - swapList[n-1] = Min(-swapList[n], swapList[n-1]); + while (--slIndex) + swapList[slIndex-1] = Min(-swapList[slIndex], swapList[slIndex-1]); return swapList[0]; } @@ -1506,6 +1499,7 @@ void Position::clear() { memset(st, 0, sizeof(StateInfo)); st->epSquare = SQ_NONE; startPosPlyCounter = 0; + nodes = 0; memset(byColorBB, 0, sizeof(Bitboard) * 2); memset(byTypeBB, 0, sizeof(Bitboard) * 8); @@ -1590,7 +1584,7 @@ void Position::allow_ooo(Color c) { Key Position::compute_key() const { - Key result = Key(0ULL); + Key result = 0; for (Square s = SQ_A1; s <= SQ_H8; s++) if (square_is_occupied(s)) @@ -1615,7 +1609,7 @@ Key Position::compute_key() const { Key Position::compute_pawn_key() const { - Key result = Key(0ULL); + Key result = 0; Bitboard b; Square s; @@ -1640,7 +1634,7 @@ Key Position::compute_pawn_key() const { Key Position::compute_material_key() const { - Key result = Key(0ULL); + Key result = 0; for (Color c = WHITE; c <= BLACK; c++) for (PieceType pt = PAWN; pt <= QUEEN; pt++) { @@ -1658,7 +1652,7 @@ Key Position::compute_material_key() const { /// updated by do_move and undo_move when the program is running in debug mode. Score Position::compute_value() const { - Score result = make_score(0, 0); + Score result = SCORE_ZERO; Bitboard b; Square s; @@ -1686,7 +1680,7 @@ Score Position::compute_value() const { Value Position::compute_non_pawn_material(Color c) const { - Value result = Value(0); + Value result = VALUE_ZERO; for (PieceType pt = KNIGHT; pt <= QUEEN; pt++) { @@ -1694,8 +1688,9 @@ Value Position::compute_non_pawn_material(Color c) const { while (b) { assert(piece_on(first_1(b)) == piece_of_color_and_type(c, pt)); + pop_1st_bit(&b); - result += piece_value_midgame(pt); + result += PieceValueMidgame[pt]; } } return result; @@ -1705,7 +1700,6 @@ Value Position::compute_non_pawn_material(Color c) const { /// Position::is_draw() tests whether the position is drawn by material, /// repetition, or the 50 moves rule. It does not detect stalemates, this /// must be done by the search. -// FIXME: Currently we are not handling 50 move rule correctly when in check bool Position::is_draw() const { @@ -1715,7 +1709,7 @@ bool Position::is_draw() const { return true; // Draw by the 50 moves rule? - if (st->rule50 > 100 || (st->rule50 == 100 && !is_check())) + if (st->rule50 > 99 && (st->rule50 > 100 || !is_mate())) return true; // Draw by repetition? @@ -1732,83 +1726,81 @@ bool Position::is_draw() const { bool Position::is_mate() const { - MoveStack moves[256]; - return is_check() && (generate_moves(*this, moves, false) == moves); + MoveStack moves[MOVES_MAX]; + return is_check() && (generate_moves(*this, moves) == moves); } -/// Position::has_mate_threat() tests whether a given color has a mate in one -/// from the current position. +/// Position::has_mate_threat() tests whether the side to move is under +/// a threat of being mated in one from the current position. -bool Position::has_mate_threat(Color c) { +bool Position::has_mate_threat() { + MoveStack mlist[MOVES_MAX], *last, *cur; StateInfo st1, st2; - Color stm = side_to_move(); + bool mateFound = false; + // If we are under check it's up to evasions to do the job if (is_check()) return false; - // If the input color is not equal to the side to move, do a null move - if (c != stm) - do_null_move(st1); + // First pass the move to our opponent doing a null move + do_null_move(st1); - MoveStack mlist[120]; - bool result = false; - Bitboard pinned = pinned_pieces(sideToMove); - - // Generate pseudo-legal non-capture and capture check moves - MoveStack* last = generate_non_capture_checks(*this, mlist); + // Then generate pseudo-legal moves that give check + last = generate_non_capture_checks(*this, mlist); last = generate_captures(*this, last); - // Loop through the moves, and see if one of them is mate - for (MoveStack* cur = mlist; cur != last; cur++) + // Loop through the moves, and see if one of them gives mate + Bitboard pinned = pinned_pieces(sideToMove); + CheckInfo ci(*this); + for (cur = mlist; cur != last && !mateFound; cur++) { Move move = cur->move; - if (!pl_move_is_legal(move, pinned)) + if ( !pl_move_is_legal(move, pinned) + || !move_is_check(move, ci)) continue; - do_move(move, st2); + do_move(move, st2, ci, true); + if (is_mate()) - result = true; + mateFound = true; undo_move(move); } - // Undo null move, if necessary - if (c != stm) - undo_null_move(); - - return result; + undo_null_move(); + return mateFound; } -/// Position::init_zobrist() is a static member function which initializes the -/// various arrays used to compute hash keys. +/// Position::init_zobrist() is a static member function which initializes at +/// startup the various arrays used to compute hash keys. void Position::init_zobrist() { - for (int i = 0; i < 2; i++) - for (int j = 0; j < 8; j++) - for (int k = 0; k < 64; k++) - zobrist[i][j][k] = Key(genrand_int64()); + RKISS RKiss; + int i,j, k; - for (int i = 0; i < 64; i++) - zobEp[i] = Key(genrand_int64()); + for (i = 0; i < 2; i++) for (j = 0; j < 8; j++) for (k = 0; k < 64; k++) + zobrist[i][j][k] = RKiss.rand(); + + for (i = 0; i < 64; i++) + zobEp[i] = RKiss.rand(); - for (int i = 0; i < 16; i++) - zobCastle[i] = genrand_int64(); + for (i = 0; i < 16; i++) + zobCastle[i] = RKiss.rand(); - zobSideToMove = genrand_int64(); - zobExclusion = genrand_int64(); + zobSideToMove = RKiss.rand(); + zobExclusion = RKiss.rand(); } /// Position::init_piece_square_tables() initializes the piece square tables. -/// This is a two-step operation: -/// First, the white halves of the tables are -/// copied from the MgPST[][] and EgPST[][] arrays. -/// Second, the black halves of the tables are initialized by mirroring -/// and changing the sign of the corresponding white scores. +/// This is a two-step operation: First, the white halves of the tables are +/// copied from the MgPST[][] and EgPST[][] arrays. Second, the black halves +/// of the tables are initialized by mirroring and changing the sign of the +/// corresponding white scores. void Position::init_piece_square_tables() { @@ -1949,7 +1941,7 @@ bool Position::is_ok(int* failedStep) const { // Is there more than 2 checkers? if (failedStep) (*failedStep)++; - if (debugCheckerCount && count_1s(st->checkersBB) > 2) + if (debugCheckerCount && count_1s(st->checkersBB) > 2) return false; // Bitboards OK? @@ -2018,7 +2010,7 @@ bool Position::is_ok(int* failedStep) const { if (debugPieceCounts) for (Color c = WHITE; c <= BLACK; c++) for (PieceType pt = PAWN; pt <= KING; pt++) - if (pieceCount[c][pt] != count_1s(pieces(pt, c))) + if (pieceCount[c][pt] != count_1s(pieces(pt, c))) return false; if (failedStep) (*failedStep)++;