From: Marco Costalba Date: Fri, 15 Feb 2013 07:56:04 +0000 (+0100) Subject: Further speed up bitbase generation X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=e0dfb0bc34dfd6bdb055a7f5779e7a61e2d76dd6 Further speed up bitbase generation Another trick, along the same lines of previous patch. This time we first check positions with white side to move that, becuase we start with pawn on rank 7, are easily classified as wins, then black ones. Number of cycles reduced to 15 ! Becuase now it is faster we can remove a lot of code to detect theoretical draws. We will calculate them anyhow, although a bit slower, but the speed up trick more than compensates it. Verified that generated bitbases match original ones. No functional change. --- diff --git a/src/bitbase.cpp b/src/bitbase.cpp index 700eea98..ef067c65 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -26,22 +26,22 @@ namespace { // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7 - const unsigned IndexMax = 24*64*64*2; // wp_sq * wk_sq * bk_sq * stm = 196608 + const unsigned IndexMax = 2*24*64*64; // stm * psq * wksq * bksq = 196608 // Each uint32_t stores results of 32 positions, one per bit uint32_t KPKBitbase[IndexMax / 32]; // A KPK bitbase index is an integer in [0, IndexMax] range // - // Information is mapped in this way + // Information is mapped in a way that minimizes number of iterations: // - // 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 0- 5: white king square (from SQ_A1 to SQ_H8) + // bit 6-11: black king square (from SQ_A1 to SQ_H8) + // bit 12: side to move (WHITE or BLACK) // bit 13-14: white pawn file (from FILE_A to FILE_D) // bit 15-17: white pawn 6 - rank (from 6 - RANK_7 to 6 - RANK_2) - unsigned index(Color stm, Square bksq, Square wksq, Square psq) { - return stm + (bksq << 1) + (wksq << 7) + (file_of(psq) << 13) + ((6 - rank_of(psq)) << 15); + unsigned index(Color us, Square bksq, Square wksq, Square psq) { + return wksq + (bksq << 6) + (us << 12) + (file_of(psq) << 13) + ((6 - rank_of(psq)) << 15); } enum Result { @@ -55,20 +55,15 @@ namespace { struct KPKPosition { - void classify_leaf(unsigned idx); - - Result classify(const std::vector& db) - { return stm == WHITE ? classify(db) : classify(db); } - operator Result() const { return res; } + Result classify_leaf(unsigned idx); + Result classify(const std::vector& db) + { return us == WHITE ? classify(db) : classify(db); } private: - template Bitboard k_attacks() const - { return StepAttacksBB[KING][Us == WHITE ? wksq : bksq]; } - template Result classify(const std::vector& db); - Color stm; + Color us; Square bksq, wksq, psq; Result res; }; @@ -76,12 +71,12 @@ namespace { } // namespace -bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm) { +bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color us) { assert(file_of(wpsq) <= FILE_D); - unsigned idx = index(stm, bksq, wksq, wpsq); - return KPKBitbase[idx / 32] & (1 << (idx & 31)); + unsigned idx = index(us, bksq, wksq, wpsq); + return KPKBitbase[idx / 32] & (1 << (idx & 0x1F)); } @@ -94,7 +89,7 @@ void Bitbases::init_kpk() { for (idx = 0; idx < IndexMax; idx++) db[idx].classify_leaf(idx); - // Iterate until all positions are classified (26 cycles needed) + // Iterate until all positions are classified (15 cycles needed) while (repeat) for (repeat = idx = 0; idx < IndexMax; idx++) if (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN) @@ -103,101 +98,61 @@ void Bitbases::init_kpk() { // Map 32 results into one KPKBitbase[] entry for (idx = 0; idx < IndexMax; idx++) if (db[idx] == WIN) - KPKBitbase[idx / 32] |= 1 << (idx & 31); + KPKBitbase[idx / 32] |= 1 << (idx & 0x1F); } namespace { - void KPKPosition::classify_leaf(unsigned idx) { + Result KPKPosition::classify_leaf(unsigned idx) { - stm = Color(idx & 1); - bksq = Square((idx >> 1) & 0x3F); - wksq = Square((idx >> 7) & 0x3F); + wksq = Square((idx >> 0) & 0x3F); + bksq = Square((idx >> 6) & 0x3F); + us = Color((idx >> 12) & 0x01); psq = File((idx >> 13) & 3) | Rank(6 - (idx >> 15)); // Check if two pieces are on the same square or if a king can be captured if ( wksq == psq || wksq == bksq || bksq == psq - || (k_attacks() & bksq) - || (stm == WHITE && (StepAttacksBB[PAWN][psq] & bksq))) - res = INVALID; - - // The position is an immediate win if it is white to move and the white - // pawn can be promoted without getting captured. - else if ( rank_of(psq) == RANK_7 - && stm == WHITE - && wksq != psq + DELTA_N - && ( square_distance(bksq, psq + DELTA_N) > 1 - ||(k_attacks() & (psq + DELTA_N)))) - res = WIN; - - // Check for known draw positions - // - // Case 1: Stalemate - else if ( stm == BLACK - && !(k_attacks() & ~(k_attacks() | StepAttacksBB[PAWN][psq]))) - res = DRAW; - - // Case 2: King can capture undefended pawn - else if ( stm == BLACK - && (k_attacks() & psq & ~k_attacks())) - res = DRAW; - - // Case 3: Black king in front of white pawn - else if ( bksq == psq + DELTA_N - && rank_of(psq) < RANK_7) - res = DRAW; - - // Case 4: White king in front of pawn and black has opposition - else if ( stm == WHITE - && wksq == psq + DELTA_N - && bksq == wksq + DELTA_N + DELTA_N - && rank_of(psq) < RANK_5) - res = DRAW; - - // Case 5: Stalemate with rook pawn - else if ( bksq == SQ_A8 - && file_of(psq) == FILE_A) - res = DRAW; - - // Case 6: White king trapped on the rook file - else if ( file_of(wksq) == FILE_A - && file_of(psq) == FILE_A - && rank_of(wksq) > rank_of(psq) - && bksq == wksq + 2) - res = DRAW; + || (StepAttacksBB[KING][wksq] & bksq) + || (us == WHITE && (StepAttacksBB[PAWN][psq] & bksq))) + return res = INVALID; - else - res = UNKNOWN; + if (us == WHITE) + { + // Immediate win if pawn can be promoted without getting captured + if ( rank_of(psq) == RANK_7 + && wksq != psq + DELTA_N + && ( square_distance(bksq, psq + DELTA_N) > 1 + ||(StepAttacksBB[KING][wksq] & (psq + DELTA_N)))) + return res = WIN; + } + // Immediate draw if is stalemate or king captures undefended pawn + else if ( !(StepAttacksBB[KING][bksq] & ~(StepAttacksBB[KING][wksq] | StepAttacksBB[PAWN][psq])) + || (StepAttacksBB[KING][bksq] & psq & ~StepAttacksBB[KING][wksq])) + return res = DRAW; + + return res = UNKNOWN; } template Result KPKPosition::classify(const std::vector& db) { - // White to Move: 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. + // White to Move: If one move leads to a position classified as WIN, the result + // of the current position is WIN. If all moves lead to positions classified + // as DRAW, the current position is classified DRAW otherwise the current + // position is classified as UNKNOWN. // - // Black to Move: 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 position is classified RESULT_WIN. - // Otherwise, the current position is classified as RESULT_UNKNOWN. + // Black to Move: If one move leads to a position classified as DRAW, the result + // of the current position is DRAW. If all moves lead to positions classified + // as WIN, the position is classified WIN otherwise the current position is + // classified UNKNOWN. Result r = INVALID; - Bitboard b = k_attacks(); + Bitboard b = StepAttacksBB[KING][Us == WHITE ? wksq : bksq]; while (b) - { - r |= Us == WHITE ? db[index(BLACK, bksq, pop_lsb(&b), psq)] - : db[index(WHITE, pop_lsb(&b), wksq, psq)]; - - if (Us == WHITE && (r & WIN)) - return res = WIN; - - if (Us == BLACK && (r & DRAW)) - return res = DRAW; - } + r |= Us == WHITE ? db[index(~Us, bksq, pop_lsb(&b), psq)] + : db[index(~Us, pop_lsb(&b), wksq, psq)]; if (Us == WHITE && rank_of(psq) < RANK_7) { @@ -206,12 +161,12 @@ namespace { if (rank_of(s) == RANK_3 && s != wksq && s != bksq) r |= db[index(BLACK, bksq, wksq, s + DELTA_N)]; // Double push - - if (r & WIN) - return res = WIN; } - return res = r & UNKNOWN ? UNKNOWN : Us == WHITE ? DRAW : WIN; + if (Us == WHITE) + return res = r & WIN ? WIN : r & UNKNOWN ? UNKNOWN : DRAW; + else + return res = r & DRAW ? DRAW : r & UNKNOWN ? UNKNOWN : WIN; } -} +} // namespace diff --git a/src/bitboard.h b/src/bitboard.h index e3331bd4..90dec816 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -33,7 +33,7 @@ void print(Bitboard b); namespace Bitbases { void init_kpk(); -bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm); +bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color us); } diff --git a/src/endgame.cpp b/src/endgame.cpp index ae29a71a..85916763 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -199,21 +199,21 @@ Value Endgame::operator()(const Position& pos) const { assert(pos.piece_count(weakerSide, PAWN) == 0); Square wksq, bksq, wpsq; - Color stm; + Color us; if (strongerSide == WHITE) { wksq = pos.king_square(WHITE); bksq = pos.king_square(BLACK); wpsq = pos.piece_list(WHITE, PAWN)[0]; - stm = pos.side_to_move(); + us = pos.side_to_move(); } else { wksq = ~pos.king_square(BLACK); bksq = ~pos.king_square(WHITE); wpsq = ~pos.piece_list(BLACK, PAWN)[0]; - stm = ~pos.side_to_move(); + us = ~pos.side_to_move(); } if (file_of(wpsq) >= FILE_E) @@ -223,7 +223,7 @@ Value Endgame::operator()(const Position& pos) const { wpsq = mirror(wpsq); } - if (!Bitbases::probe_kpk(wksq, wpsq, bksq, stm)) + if (!Bitbases::probe_kpk(wksq, wpsq, bksq, us)) return VALUE_DRAW; Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(wpsq)); @@ -920,14 +920,14 @@ ScaleFactor Endgame::operator()(const Position& pos) const { Square wksq = pos.king_square(strongerSide); Square bksq = pos.king_square(weakerSide); Square wpsq = pos.piece_list(strongerSide, PAWN)[0]; - Color stm = pos.side_to_move(); + Color us = pos.side_to_move(); if (strongerSide == BLACK) { wksq = ~wksq; bksq = ~bksq; wpsq = ~wpsq; - stm = ~stm; + us = ~us; } if (file_of(wpsq) >= FILE_E) @@ -945,5 +945,5 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // Probe the KPK bitbase with the weakest side's pawn removed. If it's a draw, // it's probably at least a draw even with the pawn. - return Bitbases::probe_kpk(wksq, wpsq, bksq, stm) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; + return Bitbases::probe_kpk(wksq, wpsq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; }