History code rewrite (#1122)

Rearrange and rename all history heuristic code. Naming
is now based on chessprogramming.wikispaces.com conventions
and the relations among the various heuristics are now more
clear and consistent.

No functional change.

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 6b9f2be059c73cfcf62389a80bd0c5877a293681..55c685476dcdd481c898b32104a76e0f8c29044b 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -143,11 +143,11 @@ void MovePicker::score<CAPTURES>() {
 template<>
 void MovePicker::score<QUIETS>() {
 
 template<>
 void MovePicker::score<QUIETS>() {
 

-  const HistoryStats& history = pos.this_thread()->history;
+  const ButterflyHistory& history = pos.this_thread()->history;

 
 

-  const CounterMoveStats& cmh = *(ss-1)->counterMoves;
-  const CounterMoveStats& fmh = *(ss-2)->counterMoves;
-  const CounterMoveStats& fm2 = *(ss-4)->counterMoves;
+  const PieceToHistory& cmh = *(ss-1)->history;
+  const PieceToHistory& fmh = *(ss-2)->history;
+  const PieceToHistory& fm2 = *(ss-4)->history;

 
   Color c = pos.side_to_move();
 
 
   Color c = pos.side_to_move();
 


@@ -155,21 +155,21 @@ void MovePicker::score<QUIETS>() {
       m.value =  cmh[pos.moved_piece(m)][to_sq(m)]
                + fmh[pos.moved_piece(m)][to_sq(m)]
                + fm2[pos.moved_piece(m)][to_sq(m)]
       m.value =  cmh[pos.moved_piece(m)][to_sq(m)]
                + fmh[pos.moved_piece(m)][to_sq(m)]
                + fm2[pos.moved_piece(m)][to_sq(m)]

-               + history.get(c, m);
+               + history[c][from_to(m)];

 }
 
 template<>
 void MovePicker::score<EVASIONS>() {
   // Try captures ordered by MVV/LVA, then non-captures ordered by stats heuristics
 }
 
 template<>
 void MovePicker::score<EVASIONS>() {
   // Try captures ordered by MVV/LVA, then non-captures ordered by stats heuristics

-  const HistoryStats& history = pos.this_thread()->history;
+  const ButterflyHistory& history = pos.this_thread()->history;

   Color c = pos.side_to_move();
 
   for (auto& m : *this)
       if (pos.capture(m))
           m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]
   Color c = pos.side_to_move();
 
   for (auto& m : *this)
       if (pos.capture(m))
           m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]

-                   - Value(type_of(pos.moved_piece(m))) + HistoryStats::Max;
+                   - Value(type_of(pos.moved_piece(m))) + (1 << 28);

       else
       else

-          m.value = history.get(c, m);
+          m.value = history[c][from_to(m)];

 }
 
 
 }
 
 

diff --git a/src/movepick.h b/src/movepick.h
index 97b1b3abb7f1aaeded105cb068e47b6ceab15c69..34cac635cfb01d83d763e8bc55850b1eee15c91e 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -21,68 +21,70 @@
 #ifndef MOVEPICK_H_INCLUDED
 #define MOVEPICK_H_INCLUDED
 
 #ifndef MOVEPICK_H_INCLUDED
 #define MOVEPICK_H_INCLUDED
 

-#include <cstring>   // For std::memset
+#include <array>

 
 #include "movegen.h"
 #include "position.h"
 #include "types.h"
 
 
 #include "movegen.h"
 #include "position.h"
 #include "types.h"
 

+/// StatBoards is a generic 2-dimensional array used to store various statistics
+template<int Size1, int Size2, typename T = int>
+struct StatBoards : public std::array<std::array<T, Size2>, Size1> {

 
 

-/// HistoryStats records how often quiet moves have been successful or unsuccessful
-/// during the current search, and is used for reduction and move ordering decisions.
-struct HistoryStats {
+  void fill(const T& v) {
+    T* p = &(*this)[0][0];
+    std::fill(p, p + sizeof(*this) / sizeof(*p), v);
+  }
+};

 
 

-  static const int Max = 1 << 28;
+/// ButterflyBoards are 2 tables (one for each color) indexed by the move's from
+/// and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards
+typedef StatBoards<COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyBoards;

 
 

-  int get(Color c, Move m) const { return table[c][from_sq(m)][to_sq(m)]; }
-  void clear() { std::memset(table, 0, sizeof(table)); }
-  void update(Color c, Move m, int v) {
+/// PieceToBoards are addressed by a move's [piece][to] information
+typedef StatBoards<PIECE_NB, SQUARE_NB> PieceToBoards;

 
 

-    Square from = from_sq(m);
-    Square to = to_sq(m);
+/// ButterflyHistory records how often quiet moves have been successful or
+/// unsuccessful during the current search, and is used for reduction and move
+/// ordering decisions. It uses ButterflyBoards as backing store.
+struct ButterflyHistory : public ButterflyBoards {
+
+  void update(Color c, Move m, int v) {

 
     const int D = 324;
 
     const int D = 324;

+    int& entry = (*this)[c][from_to(m)];

 
     assert(abs(v) <= D); // Consistency check for below formula
 
 
     assert(abs(v) <= D); // Consistency check for below formula
 

-    table[c][from][to] -= table[c][from][to] * abs(v) / D;
-    table[c][from][to] += v * 32;
-  }
+    entry += v * 32 - entry * abs(v) / D;

 
 

-private:
-  int table[COLOR_NB][SQUARE_NB][SQUARE_NB];
+    assert(abs(entry) <= 32 * D);
+  }

 };
 
 };
 

+/// PieceToHistory is like ButterflyHistory, but is based on PieceToBoards
+struct PieceToHistory : public PieceToBoards {

 
 

-/// A template struct, used to generate MoveStats and CounterMoveHistoryStats:
-/// MoveStats store the move that refute a previous one.
-/// CounterMoveHistoryStats is like HistoryStats, but with two consecutive moves.
-/// Entries are stored using only the moving piece and destination square, hence
-/// two moves with different origin but same destination and piece will be
-/// considered identical.
-template<typename T>
-struct Stats {
-  const T* operator[](Piece pc) const { return table[pc]; }
-  T* operator[](Piece pc) { return table[pc]; }
-  void clear() { std::memset(table, 0, sizeof(table)); }
-  void update(Piece pc, Square to, Move m) { table[pc][to] = m; }

   void update(Piece pc, Square to, int v) {
 
     const int D = 936;
   void update(Piece pc, Square to, int v) {
 
     const int D = 936;

+    int& entry = (*this)[pc][to];

 
     assert(abs(v) <= D); // Consistency check for below formula
 
 
     assert(abs(v) <= D); // Consistency check for below formula
 

-    table[pc][to] -= table[pc][to] * abs(v) / D;
-    table[pc][to] += v * 32;
-  }
+    entry += v * 32 - entry * abs(v) / D;

 
 

-private:
-  T table[PIECE_NB][SQUARE_NB];
+    assert(abs(entry) <= 32 * D);
+  }

 };
 
 };
 

-typedef Stats<Move> MoveStats;
-typedef Stats<int> CounterMoveStats;
-typedef Stats<CounterMoveStats> CounterMoveHistoryStats;
+/// CounterMoveStat stores counter moves indexed by [piece][to] of the previous
+/// move, see chessprogramming.wikispaces.com/Countermove+Heuristic
+typedef StatBoards<PIECE_NB, SQUARE_NB, Move> CounterMoveStat;
+
+/// CounterMoveHistoryStat is like CounterMoveStat but instead of a move it
+/// stores a full history (based on PieceTo boards instead of ButterflyBoards).
+typedef StatBoards<PIECE_NB, SQUARE_NB, PieceToHistory> CounterMoveHistoryStat;

 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the
 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the

diff --git a/src/search.cpp b/src/search.cpp
index 2e8d5c6ff2ec3fbf530f78846822ad9805571eb6..aafbf80f94aef804009883e41bbfc8d28b96c3b6 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -193,14 +193,15 @@ void Search::clear() {
 
   for (Thread* th : Threads)
   {
 
   for (Thread* th : Threads)
   {

-      th->counterMoves.clear();
-      th->history.clear();
-      th->counterMoveHistory.clear();

       th->resetCalls = true;
       th->resetCalls = true;

+      th->counterMoves.fill(MOVE_NONE);
+      th->history.fill(0);

 
 

-      CounterMoveStats& cm = th->counterMoveHistory[NO_PIECE][0];
-      auto* t = &cm[NO_PIECE][0];
-      std::fill(t, t + sizeof(cm)/sizeof(*t), CounterMovePruneThreshold - 1);
+      for (auto& to : th->counterMoveHistory)
+          for (auto& h : to)
+              h.fill(0);
+
+      th->counterMoveHistory[NO_PIECE][0].fill(CounterMovePruneThreshold - 1);

   }
 
   Threads.main()->previousScore = VALUE_INFINITE;
   }
 
   Threads.main()->previousScore = VALUE_INFINITE;


@@ -334,7 +335,7 @@ void Thread::search() {
 
   std::memset(ss-4, 0, 7 * sizeof(Stack));
   for(int i = 4; i > 0; i--)
 
   std::memset(ss-4, 0, 7 * sizeof(Stack));
   for(int i = 4; i > 0; i--)

-     (ss-i)->counterMoves = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel
+     (ss-i)->history = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel

 
   bestValue = delta = alpha = -VALUE_INFINITE;
   beta = VALUE_INFINITE;
 
   bestValue = delta = alpha = -VALUE_INFINITE;
   beta = VALUE_INFINITE;


@@ -558,7 +559,7 @@ namespace {
     Thread* thisThread = pos.this_thread();
     inCheck = pos.checkers();
     moveCount = quietCount = ss->moveCount = 0;
     Thread* thisThread = pos.this_thread();
     inCheck = pos.checkers();
     moveCount = quietCount = ss->moveCount = 0;

-    ss->history = 0;
+    ss->statScore = 0;

     bestValue = -VALUE_INFINITE;
     ss->ply = (ss-1)->ply + 1;
 
     bestValue = -VALUE_INFINITE;
     ss->ply = (ss-1)->ply + 1;
 


@@ -607,7 +608,7 @@ namespace {
     assert(0 <= ss->ply && ss->ply < MAX_PLY);
 
     ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
     assert(0 <= ss->ply && ss->ply < MAX_PLY);
 
     ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;

-    ss->counterMoves = &thisThread->counterMoveHistory[NO_PIECE][0];
+    ss->history = &thisThread->counterMoveHistory[NO_PIECE][0];

     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
     Square prevSq = to_sq((ss-1)->currentMove);
 
     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
     Square prevSq = to_sq((ss-1)->currentMove);
 


@@ -750,7 +751,7 @@ namespace {
         Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY;
 
         ss->currentMove = MOVE_NULL;
         Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY;
 
         ss->currentMove = MOVE_NULL;

-        ss->counterMoves = &thisThread->counterMoveHistory[NO_PIECE][0];
+        ss->history = &thisThread->counterMoveHistory[NO_PIECE][0];

 
         pos.do_null_move(st);
         Value nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1)
 
         pos.do_null_move(st);
         Value nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1)


@@ -794,7 +795,7 @@ namespace {
             if (pos.legal(move))
             {
                 ss->currentMove = move;
             if (pos.legal(move))
             {
                 ss->currentMove = move;

-                ss->counterMoves = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)];
+                ss->history = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)];

 
                 pos.do_move(move, st);
                 value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode, false);
 
                 pos.do_move(move, st);
                 value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode, false);


@@ -818,9 +819,9 @@ namespace {
 
 moves_loop: // When in check search starts from here
 
 
 moves_loop: // When in check search starts from here
 

-    const CounterMoveStats& cmh = *(ss-1)->counterMoves;
-    const CounterMoveStats& fmh = *(ss-2)->counterMoves;
-    const CounterMoveStats& fm2 = *(ss-4)->counterMoves;
+    const PieceToHistory& cmh = *(ss-1)->history;
+    const PieceToHistory& fmh = *(ss-2)->history;
+    const PieceToHistory& fm2 = *(ss-4)->history;

 
     MovePicker mp(pos, ttMove, depth, ss);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
 
     MovePicker mp(pos, ttMove, depth, ss);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc


@@ -956,7 +957,7 @@ moves_loop: // When in check search starts from here
 
       // Update the current move (this must be done after singular extension search)
       ss->currentMove = move;
 
       // Update the current move (this must be done after singular extension search)
       ss->currentMove = move;

-      ss->counterMoves = &thisThread->counterMoveHistory[moved_piece][to_sq(move)];
+      ss->history = &thisThread->counterMoveHistory[moved_piece][to_sq(move)];

 
       // Step 14. Make the move
       pos.do_move(move, st, givesCheck);
 
       // Step 14. Make the move
       pos.do_move(move, st, givesCheck);


@@ -984,21 +985,21 @@ moves_loop: // When in check search starts from here
                        && !pos.see_ge(make_move(to_sq(move), from_sq(move))))
                   r -= 2 * ONE_PLY;
 
                        && !pos.see_ge(make_move(to_sq(move), from_sq(move))))
                   r -= 2 * ONE_PLY;
 

-              ss->history =  cmh[moved_piece][to_sq(move)]
-                           + fmh[moved_piece][to_sq(move)]
-                           + fm2[moved_piece][to_sq(move)]
-                           + thisThread->history.get(~pos.side_to_move(), move)
-                           - 4000; // Correction factor
+              ss->statScore =  cmh[moved_piece][to_sq(move)]
+                             + fmh[moved_piece][to_sq(move)]
+                             + fm2[moved_piece][to_sq(move)]
+                             + thisThread->history[~pos.side_to_move()][from_to(move)]
+                             - 4000; // Correction factor

 
               // Decrease/increase reduction by comparing opponent's stat score
 
               // Decrease/increase reduction by comparing opponent's stat score

-              if (ss->history > 0 && (ss-1)->history < 0)
+              if (ss->statScore > 0 && (ss-1)->statScore < 0)

                   r -= ONE_PLY;
 
                   r -= ONE_PLY;
 

-              else if (ss->history < 0 && (ss-1)->history > 0)
+              else if (ss->statScore < 0 && (ss-1)->statScore > 0)

                   r += ONE_PLY;
 
               // Decrease/increase reduction for moves with a good/bad history
                   r += ONE_PLY;
 
               // Decrease/increase reduction for moves with a good/bad history

-              r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->history / 20000) * ONE_PLY);
+              r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->statScore / 20000) * ONE_PLY);

           }
 
           Depth d = std::max(newDepth - r, ONE_PLY);
           }
 
           Depth d = std::max(newDepth - r, ONE_PLY);


@@ -1399,7 +1400,7 @@ moves_loop: // When in check search starts from here
 
     for (int i : {1, 2, 4})
         if (is_ok((ss-i)->currentMove))
 
     for (int i : {1, 2, 4})
         if (is_ok((ss-i)->currentMove))

-            (ss-i)->counterMoves->update(pc, s, bonus);
+            (ss-i)->history->update(pc, s, bonus);

   }
 
 
   }
 
 


@@ -1422,7 +1423,7 @@ moves_loop: // When in check search starts from here
     if (is_ok((ss-1)->currentMove))
     {
         Square prevSq = to_sq((ss-1)->currentMove);
     if (is_ok((ss-1)->currentMove))
     {
         Square prevSq = to_sq((ss-1)->currentMove);

-        thisThread->counterMoves.update(pos.piece_on(prevSq), prevSq, move);
+        thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]=move;

     }
 
     // Decrease all the other played quiet moves
     }
 
     // Decrease all the other played quiet moves

diff --git a/src/search.h b/src/search.h
index 94b59d2bfac712be92d3559cf44e02912d55fd12..55a1bf6b3e1874754821e778bb85edffc5984673 100644 (file)
--- a/src/search.h
+++ b/src/search.h
@@ -38,13 +38,13 @@ namespace Search {
 
 struct Stack {
   Move* pv;
 
 struct Stack {
   Move* pv;

-  CounterMoveStats* counterMoves;
+  PieceToHistory* history;

   int ply;
   Move currentMove;
   Move excludedMove;
   Move killers[2];
   Value staticEval;
   int ply;
   Move currentMove;
   Move excludedMove;
   Move killers[2];
   Value staticEval;

-  int history;
+  int statScore;

   int moveCount;
 };
 
   int moveCount;
 };
 

diff --git a/src/thread.h b/src/thread.h
index 86e5565f2e3363667bbf07a34a777fdec56f5b70..7666a34fbaba39110c181de72eb1e584f435a462 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -68,9 +68,9 @@ public:
   Depth rootDepth;
   Depth completedDepth;
   std::atomic_bool resetCalls;
   Depth rootDepth;
   Depth completedDepth;
   std::atomic_bool resetCalls;

-  MoveStats counterMoves;
-  HistoryStats history;
-  CounterMoveHistoryStats counterMoveHistory;
+  CounterMoveStat counterMoves;
+  ButterflyHistory history;
+  CounterMoveHistoryStat counterMoveHistory;

 };
 
 
 };
 
 

diff --git a/src/types.h b/src/types.h
index 2709d77ffea70c3a39276bc62d45883c6f5d3be8..c24f22090882b443d15618defc7fc0dd436630cb 100644 (file)
--- a/src/types.h
+++ b/src/types.h
@@ -421,6 +421,10 @@ inline Square to_sq(Move m) {
   return Square(m & 0x3F);
 }
 
   return Square(m & 0x3F);
 }
 

+inline int from_to(Move m) {
+ return m & 0xFFF;
+}
+

 inline MoveType type_of(Move m) {
   return MoveType(m & (3 << 14));
 }
 inline MoveType type_of(Move m) {
   return MoveType(m & (3 << 14));
 }