X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitbase.cpp;h=fda5030d247e8dd82925151635886d57520dd93f;hp=0c3230f2aa9c0e9619fbe6f607eae4a77a1df066;hb=f3799aa750cd5d78ca5e253e4d1b7aa49d94284d;hpb=0fcda095df1caa860e8e3f3a714d5545ec9dc122 diff --git a/src/bitbase.cpp b/src/bitbase.cpp index 0c3230f2..fda5030d 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -28,157 +28,167 @@ namespace { RESULT_UNKNOWN, RESULT_INVALID, RESULT_WIN, - RESULT_LOSS, RESULT_DRAW }; struct KPKPosition { + Result classify_knowns(int index); + Result classify(int index, Result db[]); + + private: void from_index(int index); - bool is_legal() const; - bool is_immediate_draw() const; - bool is_immediate_win() const; - Bitboard wk_attacks() const { return NonSlidingAttacksBB[WK][whiteKingSquare]; } - Bitboard bk_attacks() const { return NonSlidingAttacksBB[BK][blackKingSquare]; } - Bitboard pawn_attacks() const { return NonSlidingAttacksBB[WP][pawnSquare]; } + Result classify_white(const Result db[]); + Result classify_black(const Result db[]); + Bitboard wk_attacks() const { return StepAttacksBB[WK][whiteKingSquare]; } + Bitboard bk_attacks() const { return StepAttacksBB[BK][blackKingSquare]; } + Bitboard pawn_attacks() const { return StepAttacksBB[WP][pawnSquare]; } Square whiteKingSquare, blackKingSquare, pawnSquare; Color sideToMove; }; - const int IndexMax = 2 * 24 * 64 * 64; + // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7 + const int IndexMax = 2 * 24 * 64 * 64; // color * wp_sq * wk_sq * bk_sq = 196608 + + // Each uint32_t stores results of 32 positions, one per bit + uint32_t KPKBitbase[IndexMax / 32]; - Result classify_wtm(const KPKPosition& pos, const Result bb[]); - Result classify_btm(const KPKPosition& pos, const Result bb[]); - int compute_index(Square wksq, Square bksq, Square psq, Color stm); + int compute_index(Square wksq, Square bksq, Square wpsq, Color stm); } -void generate_kpk_bitbase(uint8_t bitbase[]) { +uint32_t probe_kpk_bitbase(Square wksq, Square wpsq, Square bksq, Color stm) { + + int index = compute_index(wksq, bksq, wpsq, stm); + + return KPKBitbase[index / 32] & (1 << (index & 31)); +} + - bool repeat; - int i, j, b; +void kpk_bitbase_init() { + + Result db[IndexMax]; KPKPosition pos; - Result bb[IndexMax]; + int index, bit, repeat = 1; // Initialize table - for (i = 0; i < IndexMax; i++) - { - pos.from_index(i); - bb[i] = !pos.is_legal() ? RESULT_INVALID - : pos.is_immediate_draw() ? RESULT_DRAW - : pos.is_immediate_win() ? RESULT_WIN : RESULT_UNKNOWN; - } + for (index = 0; index < IndexMax; index++) + db[index] = pos.classify_knowns(index); // Iterate until all positions are classified (30 cycles needed) - do { - repeat = false; - - for (i = 0; i < IndexMax; i++) - if (bb[i] == RESULT_UNKNOWN) - { - pos.from_index(i); - - bb[i] = (pos.sideToMove == WHITE) ? classify_wtm(pos, bb) - : classify_btm(pos, bb); - if (bb[i] != RESULT_UNKNOWN) - repeat = true; - } - - } while (repeat); - - // Compress result and map into supplied bitbase parameter - for (i = 0; i < 24576; i++) - { - b = 0; - for (j = 0; j < 8; j++) - if (bb[8*i+j] == RESULT_WIN || bb[8*i+j] == RESULT_LOSS) - b |= (1 << j); - - bitbase[i] = (uint8_t)b; - } + while (repeat) + for (repeat = index = 0; index < IndexMax; index++) + if ( db[index] == RESULT_UNKNOWN + && pos.classify(index, db) != RESULT_UNKNOWN) + repeat = 1; + + // Map 32 position results into one KPKBitbase[] entry + for (index = 0; index < IndexMax / 32; index++) + for (bit = 0; bit < 32; bit++) + if (db[32 * index + bit] == RESULT_WIN) + KPKBitbase[index] |= (1 << bit); } namespace { - int compute_index(Square wksq, Square bksq, Square psq, Color stm) { + // A KPK bitbase index is an integer in [0, IndexMax] range + // + // Information is mapped in this way + // + // bit 0: side to move (WHITE or BLACK) + // bit 1- 6: black king square (from SQ_A1 to SQ_H8) + // bit 7-12: white king square (from SQ_A1 to SQ_H8) + // bit 13-14: white pawn file (from FILE_A to FILE_D) + // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1) + + int compute_index(Square wksq, Square bksq, Square wpsq, Color stm) { + + assert(square_file(wpsq) <= FILE_D); - int p = int(square_file(psq)) + (int(square_rank(psq)) - 1) * 4; - int r = int(stm) + 2 * int(bksq) + 128 * int(wksq) + 8192 * p; + int p = square_file(wpsq) + 4 * (square_rank(wpsq) - 1); + int r = stm + 2 * bksq + 128 * wksq + 8192 * p; - assert(r >= 0 && r < IndexMax); + assert(r >= 0 && r < IndexMax); - return r; + return r; } void KPKPosition::from_index(int index) { - int s = (index / 8192) % 24; - - sideToMove = Color(index % 2); - blackKingSquare = Square((index / 2) % 64); - whiteKingSquare = Square((index / 128) % 64); - pawnSquare = make_square(File(s % 4), Rank(s / 4 + 1)); + int s = index >> 13; + sideToMove = Color(index & 1); + blackKingSquare = Square((index >> 1) & 63); + whiteKingSquare = Square((index >> 7) & 63); + pawnSquare = make_square(File(s & 3), Rank((s >> 2) + 1)); } - bool KPKPosition::is_legal() const { + Result KPKPosition::classify_knowns(int index) { + + from_index(index); + // Check if two pieces are on the same square if ( whiteKingSquare == pawnSquare || whiteKingSquare == blackKingSquare - || pawnSquare == blackKingSquare) - return false; - - if (sideToMove == WHITE) - { - if ( bit_is_set(wk_attacks(), blackKingSquare) - || bit_is_set(pawn_attacks(), blackKingSquare)) - return false; - } - else if (bit_is_set(bk_attacks(), whiteKingSquare)) - return false; + || blackKingSquare == pawnSquare) + return RESULT_INVALID; - return true; - } + // Check if a king can be captured + if ( bit_is_set(wk_attacks(), blackKingSquare) + || (bit_is_set(pawn_attacks(), blackKingSquare) && sideToMove == WHITE)) + return RESULT_INVALID; - bool KPKPosition::is_immediate_draw() const { - - if (sideToMove == BLACK) - { - Bitboard wka = wk_attacks(); - Bitboard bka = bk_attacks(); - - // Case 1: Stalemate - if ((bka & ~(wka | pawn_attacks())) == EmptyBoardBB) - return true; - - // Case 2: King can capture pawn - if (bit_is_set(bka, pawnSquare) && !bit_is_set(wka, pawnSquare)) - return true; - } - else - { - // Case 1: Stalemate - if ( whiteKingSquare == SQ_A8 - && pawnSquare == SQ_A7 - && (blackKingSquare == SQ_C7 || blackKingSquare == SQ_C8)) - return true; - } - return false; + // The position is an immediate win if it is white to move and the + // white pawn can be promoted without getting captured. + if ( square_rank(pawnSquare) == RANK_7 + && sideToMove == WHITE + && whiteKingSquare != pawnSquare + DELTA_N + && ( square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1 + || bit_is_set(wk_attacks(), pawnSquare + DELTA_N))) + return RESULT_WIN; + + // Check for known draw positions + // + // Case 1: Stalemate + if ( sideToMove == BLACK + && (bk_attacks() & ~(wk_attacks() | pawn_attacks())) == EmptyBoardBB) + return RESULT_DRAW; + + // Case 2: King can capture pawn + if ( sideToMove == BLACK + && bit_is_set(bk_attacks(), pawnSquare) && !bit_is_set(wk_attacks(), pawnSquare)) + return RESULT_DRAW; + + // Case 3: Black king in front of white pawn + if ( blackKingSquare == pawnSquare + DELTA_N + && square_rank(pawnSquare) < RANK_7) + return RESULT_DRAW; + + // Case 4: White king in front of pawn and black has opposition + if ( whiteKingSquare == pawnSquare + DELTA_N + && blackKingSquare == pawnSquare + DELTA_N + DELTA_N + DELTA_N + && square_rank(pawnSquare) < RANK_5 + && sideToMove == WHITE) + return RESULT_DRAW; + + // Case 5: Stalemate with rook pawn + if ( blackKingSquare == SQ_A8 + && square_file(pawnSquare) == FILE_A) + return RESULT_DRAW; + + return RESULT_UNKNOWN; } - bool KPKPosition::is_immediate_win() const { + Result KPKPosition::classify(int index, Result db[]) { - // The position is an immediate win if it is white to move and the - // white pawn can be promoted without getting captured. - return sideToMove == WHITE - && square_rank(pawnSquare) == RANK_7 - && ( square_distance(blackKingSquare, pawnSquare + DELTA_N) > 1 - || bit_is_set(wk_attacks(), pawnSquare + DELTA_N)); + from_index(index); + db[index] = (sideToMove == WHITE ? classify_white(db) : classify_black(db)); + return db[index]; } - Result classify_wtm(const KPKPosition& pos, const Result bb[]) { + Result KPKPosition::classify_white(const Result db[]) { - // If one move leads to a position classified as RESULT_LOSS, the result + // If one move leads to a position classified as RESULT_WIN, the result // of the current position is RESULT_WIN. If all moves lead to positions // classified as RESULT_DRAW, the current position is classified RESULT_DRAW // otherwise the current position is classified as RESULT_UNKNOWN. @@ -186,120 +196,76 @@ namespace { bool unknownFound = false; Bitboard b; Square s; - int idx; + Result r; // King moves - b = pos.wk_attacks(); + b = wk_attacks(); while (b) { s = pop_1st_bit(&b); - idx = compute_index(s, pos.blackKingSquare, pos.pawnSquare, BLACK); + r = db[compute_index(s, blackKingSquare, pawnSquare, BLACK)]; - switch (bb[idx]) { - - case RESULT_LOSS: + if (r == RESULT_WIN) return RESULT_WIN; - case RESULT_UNKNOWN: + if (r == RESULT_UNKNOWN) unknownFound = true; - - case RESULT_DRAW: - case RESULT_INVALID: - break; - - default: - assert(false); - } } // Pawn moves - if (square_rank(pos.pawnSquare) < RANK_7) + if (square_rank(pawnSquare) < RANK_7) { - s = pos.pawnSquare + DELTA_N; - idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK); - - switch (bb[idx]) { + s = pawnSquare + DELTA_N; + r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)]; - case RESULT_LOSS: + if (r == RESULT_WIN) return RESULT_WIN; - case RESULT_UNKNOWN: + if (r == RESULT_UNKNOWN) unknownFound = true; - case RESULT_DRAW: - case RESULT_INVALID: - break; - - default: - assert(false); - } - // Double pawn push - if ( square_rank(s) == RANK_3 - && s != pos.whiteKingSquare - && s != pos.blackKingSquare) + if (square_rank(s) == RANK_3 && r != RESULT_INVALID) { s += DELTA_N; - idx = compute_index(pos.whiteKingSquare, pos.blackKingSquare, s, BLACK); + r = db[compute_index(whiteKingSquare, blackKingSquare, s, BLACK)]; - switch (bb[idx]) { - - case RESULT_LOSS: + if (r == RESULT_WIN) return RESULT_WIN; - case RESULT_UNKNOWN: + if (r == RESULT_UNKNOWN) unknownFound = true; - - case RESULT_DRAW: - case RESULT_INVALID: - break; - - default: - assert(false); - } } } return unknownFound ? RESULT_UNKNOWN : RESULT_DRAW; } - - Result classify_btm(const KPKPosition& pos, const Result bb[]) { + Result KPKPosition::classify_black(const Result db[]) { // If one move leads to a position classified as RESULT_DRAW, the result // of the current position is RESULT_DRAW. If all moves lead to positions - // classified as RESULT_WIN, the current position is classified as - // RESULT_LOSS. Otherwise, the current position is classified as - // RESULT_UNKNOWN. + // classified as RESULT_WIN, the position is classified as RESULT_WIN. + // Otherwise, the current position is classified as RESULT_UNKNOWN. bool unknownFound = false; Bitboard b; Square s; - int idx; + Result r; // King moves - b = pos.bk_attacks(); + b = bk_attacks(); while (b) { s = pop_1st_bit(&b); - idx = compute_index(pos.whiteKingSquare, s, pos.pawnSquare, WHITE); - - switch (bb[idx]) { + r = db[compute_index(whiteKingSquare, s, pawnSquare, WHITE)]; - case RESULT_DRAW: + if (r == RESULT_DRAW) return RESULT_DRAW; - case RESULT_UNKNOWN: + if (r == RESULT_UNKNOWN) unknownFound = true; - - case RESULT_WIN: - case RESULT_INVALID: - break; - - default: - assert(false); - } } - return unknownFound ? RESULT_UNKNOWN : RESULT_LOSS; + return unknownFound ? RESULT_UNKNOWN : RESULT_WIN; } }