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 700eea9892aa04819a4c27fd490bba36cd74d0a8..ef067c65bceca3bc809c5b977a8dd4610fcc4bc2 100644 (file)
--- 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<KPKPosition>& db)
-    { return stm == WHITE ? classify<WHITE>(db) : classify<BLACK>(db); }
-
     operator Result() const { return res; }
+    Result classify_leaf(unsigned idx);
+    Result classify(const std::vector<KPKPosition>& db)
+    { return us == WHITE ? classify<WHITE>(db) : classify<BLACK>(db); }
 
   private:
-    template<Color Us> Bitboard k_attacks() const
-    { return StepAttacksBB[KING][Us == WHITE ? wksq : bksq]; }
-
     template<Color Us> Result classify(const std::vector<KPKPosition>& 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<WHITE>() & 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<WHITE>() & (psq + DELTA_N))))
-        res = WIN;
-
-    // Check for known draw positions
-    //
-    // Case 1: Stalemate
-    else if (   stm == BLACK
-             && !(k_attacks<BLACK>() & ~(k_attacks<WHITE>() | StepAttacksBB[PAWN][psq])))
-        res = DRAW;
-
-    // Case 2: King can capture undefended pawn
-    else if (   stm == BLACK
-             && (k_attacks<BLACK>() & psq & ~k_attacks<WHITE>()))
-        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<Color Us>
   Result KPKPosition::classify(const std::vector<KPKPosition>& 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<Us>();
+    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 e3331bd440784c1e2bdec3154012c6f03d2a2c9f..90dec8165678811ae71f8efce50e11bbf400a5c6 100644 (file)
--- 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 ae29a71aba07d0faa77847e7045a31f1ef92b58c..8591676305f434ef8c10716058624d70d3dc32c5 100644 (file)
--- a/src/endgame.cpp
+++ b/src/endgame.cpp
@@ -199,21 +199,21 @@ Value Endgame<KPK>::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<KPK>::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<KPKP>::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<KPKP>::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;
 }