Improving the search

[Guetti]

I need some advice again. I just finished to implement a (very basic) transposition table in my engine and now I need to gather some statistics to see how it works, how to improve it, and how to measure the improvement of the TT on move sorting and the alphabeta search in general, before and while I continue to intergrate more stuff like killers, history heuristics etc.
So what I need is to extract some useful data from the search and the TT to have some values to compare. What are useful values to output.

read/writes to the TT, hits in the TT, misses in the TT?
fullness of the TT? (How can I measure that?)
Other useful output to make sure the TT is bugfree?
Some value for the quality of move ordering?

Other suggstions?

[Gerd Isenberg]

I suggest to implement a statistic struct/class for search as well as for hashtables.

Code: Select all

enum // counter indices
{
   e_NodeCount,    // always first
   e_QNodeCount, 
   e_CutOffs,
   e_CutOffOnFirst,
   e_CutOffOnHash,
   e_CutOffOnKiller,
   e_LeaveCut,
   e_Extensions,
   e_Mate,
   e_StaleMate,
   ....

   e_NumberOfCounters, // the last
}; 

class CStatistik
{
protected:
   int64 m_Count[e_NumberOfCounters];
public:
   CStatistik() {clear();}
   void clear();
   void printStatictics();
   void inc(unsigned int index) {m_Count[index]++;}
};

Embed it into your "search" object. And increment counter where appropriate. You may use some preprocessor macros to switch it on/off.

Code: Select all

#ifdef USETSTATS
#define INC(i) m_Stat.inc(i)

#define INCCUTOFF \
   m_Stat.inc(e_CutOffs); \
   if ( moveCount == 1 ) m_Stat.inc(e_CutOffOnFirst); \
   if ( move == pvMove ) m_Stat.inc(e_CutOffOnHash); \
   if ( move == killer1 ) m_Stat.inc(e_CutOffOnKiller);

#else
#define INC(i)
#define INCCUTOFF
#endif

int search(...) {
   ...
   m_Stat.inc(e_NodeCount); 
   ....
   if ( score >= beta ) {
      INCCUTOFF;
      ...
   }
}

To print the statistics, you simply use an array of strings to print the semantic of the counter. Simply based on a copy of the enums. Implementing new counters is very simple now.

Code: Select all

const char* strCounterName[] =
{
   "e_NodeCount", 
   "e_QNodeCount", 
   "e_CutOffs",
   "e_CutOffOnFirst",
   "e_CutOffOnHash",
   "e_CutOffOnKiller",
   "e_LeaveCut",
   "e_Extensions",
   "e_Mate",
   "e_StaleMate",
...
};

You may also use an int-array of enums to define the base of 100% values, so that you may print

Code: Select all

e_CutOffOnFirst nnnn, xx% of e_CutOffs

which should be > 90% or even 95% for most positions.

Code: Select all

#define PERCENT(A,B) ( (U32) ((10000*(A) + (B)/2 ) / (B)) )

void CStatistic::printStatistics()
{
   printf("Search Statistics:\n");
   printf("%s:%10I64d\n", strCounterName[0], m_Count[0]); // node count
   if ( m_Count[0] )
   {
      for &#40;int i = 1; i < e_NumberOfCounters; i++) &#123;
         if ( m_Count&#91;i&#93; == 0 ) continue;
         if ( m_Count&#91;dependend&#91;i&#93;&#93; == 0 ) continue;
         U32 per = PERCENT&#40;m_Count&#91;i&#93;, m_Count&#91;dependend&#91;i&#93;&#93;);
         printf&#40;"%s&#58;%10I64d %3d.%02d%% of %s\n", 
                strCounterName&#91;i&#93;, 
                m_Count&#91;i&#93;, 
                per/100, 
                per%100, 
                strCounterName&#91;dependend&#91;i&#93;&#93;);
      &#125;
      printf&#40;"\n");
   &#125;
&#125;

You may even index counters by some depth measure for horizon-, below horizon-, (pre,pre) frontier-nodes etc., to really get the "inner eye" of your engine.

For hashtables, you may use similar objects. If you replace an entry, you increment one counter. If the former entry was empty (null) you may increment another counter, to measure fillstate. Otherwise you'll count each kind of hit depending on your implementation, with or without sufficient draft and upper/lower/exact states or whatever.

Gerd

[Guetti]

Thanks, Gerd. I implemented/rewrote the statistics part as you suggested. But, I need some more explanations about this part:

Embed it into your "search" object. And increment counter where appropriate. You may use some preprocessor macros to switch it on/off.

Code: Select all

#ifdef USETSTATS
#define INC(i) m_Stat.inc(i)

#define INCCUTOFF \
   m_Stat.inc(e_CutOffs); \
   if ( moveCount == 1 ) m_Stat.inc(e_CutOffOnFirst); \
   if ( move == pvMove ) m_Stat.inc(e_CutOffOnHash); \
   if ( move == killer1 ) m_Stat.inc(e_CutOffOnKiller);

#else
#define INC(i)
#define INCCUTOFF
#endif

int search(...) {
   ...
   m_Stat.inc(e_NodeCount); 
   ....
   if ( score >= beta ) {
      INCCUTOFF;
      ...
   }
}

Ok, CutOffOnFirst is when I cut off on the first move. But what do you mean by CutOffOnHash? Isn't it the first move too, since we try the Hashmove first?
And should I also count CutOffs when I probe the TT and return immediately at the beginning of the search to CutOffOnFirst?
Or count this to CutOffs at all?

[Gerd Isenberg]

Ok, CutOffOnFirst is when I cut off on the first move. But what do you mean by CutOffOnHash? Isn't it the first move too, since we try the Hashmove first?

If you store cuts from null-move or standing pat in qnodes in TT, you have hashentries at cut-nodes with no move at all, where you fail high with first move anyway. Also former all-nodes with no move stored, may become cut-nodes up and then with more depth left. You may also maintain expected node types to store distinct statistics there. May be it is a good idea to produce some csv-file, where you may append your search statistics (together with pv and scores) after each move searched or even between iterations, to analyse all the values with some spreadsheet program like excel, to print some nice charts.

And should I also count CutOffs when I probe the TT and return immediately at the beginning of the search to CutOffOnFirst?
Or count this to CutOffs at all?

Yes, you should count your early exits like repetitions and TT hits as well, key-hits, upper/lower/exact hits with sufficient depth, hits with and without move, Nullmove tries, cuts and fails, leaf-standpat cuts at or below horizon, how often you prune at frontier nodes and all kind of stuff you are interested in.

Each time I enter nullmove or IID i increment a counter, if I leave, I decrement. Now I count how many of the total nodes are inside Null or IID.

Code: Select all

m_Stat.inc(e_NodeCount);
if ( m_InNull ) m_Stat.inc(e_NodeCountInNull);
if ( m_InIIDl ) m_Stat.inc(e_NodeCountInIID);
...
makeNull(ply);
m_InNull++;
val = -zeroWindowSearch (depth - R - 1, 1-beta);
m_InNull--;
unmakeNull();
...

Cheers,
Gerd

[Guetti]

Oha, I completely forgot about the CutOffs in qsearch. Damn, now I was already happy to get such a good ratio of CutOffOnFirst.

I got a bit distracted with an issue in my TT. Maybe I have to explain first. As I said it is a very basic approach and I know it's is not the best method but I wanted to keep it simple at first. I basically split the TT in two, and one slot represents a depth prefer entry and the other slot is replace always.
Now, apparently I made a mistake when retrieving an Entry from the TT. I should try the replace always first (if it does exist), because this entries are more recent, shoulnd't I? And if there is no hit in the replace always I should go with the one in depth prefer, if it exists. Is this Correct?

[Gerd Isenberg]

You may also define a conditional increment macro for that stuff as well:

Code: Select all

#define INC(i) m_Stat.inc(i)
#define INC_ON_CONDITION(cond, i) if (cond) INC(i)

   INC_ON_CONDITION(m_InNull != 0, e_NodeCountInNull);

[Gerd Isenberg]

Oha, I completely forgot about the CutOffs in qsearch. Damn, now I was already happy to get such a good ratio of CutOffOnFirst.

I got a bit distracted with an issue in my TT. Maybe I have to explain first. As I said it is a very basic approach and I know it's is not the best method but I wanted to keep it simple at first. I basically split the TT in two, and one slot represents a depth prefer entry and the other slot is replace always.
Now, apparently I made a mistake when retrieving an Entry from the TT. I should try the replace always first (if it does exist), because this entries are more recent, shoulnd't I? And if there is no hit in the replace always I should go with the one in depth prefer, if it exists. Is this Correct?

Hmm... no idea, I would probe the depth preferred table first because hits may more valuable. But if your replace always is smaller and faster it might be better the other way around, or exclusively probe in qnodes. I actually use only one four-slot, depth preferred table - also in qsearch.

Of course memory latency + TLB-miss penalty of huge GByte tables is an issue, where you burn hundreds of cycles. I recommend a prefetch at the beginning of the node to do some stuff you'll likely need in eval and movegen before you actually probe. Otherwise you may rely on hyperthreading.

Gerd

[Guetti]

Oha, I completely forgot about the CutOffs in qsearch. Damn, now I was already happy to get such a good ratio of CutOffOnFirst.

I got a bit distracted with an issue in my TT. Maybe I have to explain first. As I said it is a very basic approach and I know it's is not the best method but I wanted to keep it simple at first. I basically split the TT in two, and one slot represents a depth prefer entry and the other slot is replace always.
Now, apparently I made a mistake when retrieving an Entry from the TT. I should try the replace always first (if it does exist), because this entries are more recent, shoulnd't I? And if there is no hit in the replace always I should go with the one in depth prefer, if it exists. Is this Correct?

Hmm... no idea, I would probe the depth preferred table first because hits may more valuable. But if your replace always is smaller and faster it might be better the other way around, or exclusively probe in qnodes. I actually use only one four-slot, depth preferred table - also in qsearch.

Of course memory latency + TLB-miss penalty of huge GByte tables is an issue, where you burn hundreds of cycles. I recommend a prefetch at the beginning of the node to do some stuff you'll likely need in eval and movegen before you actually probe. Otherwise you may rely on hyperthreading.

Gerd

You're probably right. The strange thing is, I played a bit around with Fine 70, and get wildly different results by changing which of the two tables (depth-preferred or always-replace) I probe (nothing else changed).

Here is depth-preferred first:

Code: Select all

 ply   score     time       nodes    pv
   1     137        0           3    a1b2 
   2     125        0          14    a1b2 a7b6 
   3     129        0          87    a1b2 a7b6 b2c3 
   4     129        0         221    a1b2 a7b6 b2c3 b6c7 
   5     133        0         423    a1b2 a7b6 b2c3 b6c7 c3d3 
   6     131        0         657    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 
   7     131        0        1093    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 d3e3 
   8     133        0        1891    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 
   9     133        0        2467    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3c4 
  10     133        0        3342    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3e3 a6b6 
  11     133        0        4230    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 
  12     133        1        5324    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6c7 
  13     133        1        7042    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6c7 d3c4 
  14     133        1        9647    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6a6 d3e3 a6b6 
  15     133        2       12528    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6a6 d3c2 a6b6 c2d3 
  16     133        2       15928    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6a6 d3c2 a6b6 c2d3 b6c7 
  17     133        3       21276    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6a6 d3c2 a6b6 c2d3 b6a6 d3c2 a6b6 c2d3 b6c7 d3c4 
  18     133       16      240639    a1b2 a7b6 b2c3 b6b7 c3d3 b7c7 d3c4 
  19     133       26      517390    a1b2 a7b6 b2c3 b6b7 c3d3 b7c7 d3c4 
  20     133      104     2463829    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 
  21     133      219     5672789    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 
  22     133      236     6094914    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 c3b2 b7a8 
  23     133      298     7801707    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 c3b2 b7a8 
  24     133      452    11823094    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 c3b2 b7a8 
  25     133      891    23887937    a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 c3b2 b7a8 

25 (3/3) 1.33  60.00  160400783  a1b2 a7a8 b2c2 a8b8 c2c3 b8b7 c3b2 b7a8 
Nodes: 160400783  NPS: 2673k  Ply: 25/29
Qnodes:    532197   0.33% of Nodes
CutOffs: 114196103  71.19% of Nodes
CutOffOnFirst: 113084544  99.03% of CutOffs
Evals:  84117611
LazyEvals:  46397587  55.16% of Evals
Evasions:  10766898
TT-Writes:   69725815, TT-Hits:  159131866,  TT-Full: 100.0%
move a1b2 

And here is the always replace:

Code: Select all

 ply   score     time       nodes    pv
   1     137        0           3    a1b2 
   2     125        0          14    a1b2 a7b6 
   3     129        0          87    a1b2 a7b6 b2c3 
   4     129        0         218    a1b2 a7b6 b2c3 b6c7 
   5     133        0         589    a1b2 a7b6 b2c3 b6c7 c3d3 
   6     131        0        1103    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 
   7     131        0        1752    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 d3e3 
   8     133        0        2914    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 
   9     133        0        4481    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3e3 
  10     133        1        5940    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3c4 
  11     133        1        8215    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3c4 
  12     133        1       11952    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3c3 c7b6 c3d3 
  13     133        2       15325    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6b7 d3c2 b7a6 c2b2 a6b6 
  14     133        2       18990    a1b2 a7b6 b2c3 b6c7 c3b2 c7b6 
  15     133        2       22546    a1b2 a7b6 b2c3 b6c7 c3b2 c7b6 
  16     133        3       28695    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4b3 b6a6 b3a2 a6b6 a2a1 b6a6 a1b2 a6b6 
  17     133        4       35613    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4b3 b6a6 b3a2 a6b6 a2a1 b6a6 a1b1 a6b6 b1a1 b6a7 a1b2 
  18     133        5       46210    a1b2 a7b6 b2c3 b6b7 c3b2 b7a6 b2a1 a6b6 a1b1 b6a6 b1a1 a6b6 a1b1 b6a6 b1a1 a6b6 a1b2 b6b7 
  19     133        6       59627    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7a6 a1b1 
  20     133        7       69591    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7a6 a1b1 a6a7 b1a1 a7a6 a1b1 a6a7 b1a1 a7a6 a1b1 a6a7 b1b2 
  21     133        8       82806    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7a6 a1b1 a6a7 b1a1 a7a6 a1b1 a6a7 b1a1 a7a6 a1b1 a6a7 b1b2 
  22     135       10      101031    a1b1 a7b7 b1c1 b7c7 c1b2 c7c8 b2b3 c8c7 b3b2 c7c8 b2b3 c8c7 b3b2 c7c8 b2b3 c8c7 
  23     135       12      125255    a1b1 a7b7 b1c1 b7c7 c1b2 c7b6 b2c2 b6b7 c2c1 
  24     135       14      169780    a1b1 a7b7 b1c1 b7c7 c1b2 c7c8 b2a2 c8b7 a2b1 
>>25     185       16      202340    *
  25     252       19      256345    a1b1 a7b7 b1c1 b7c7 c1d1 c7b6 d1e1 b6a6 e1f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4g5 d7e7 g5f5 e7f7 f5g5 f7e7 
  26     252       21      288039    a1b1 a7a6 b1c2 a6b6 c2b2 b6a6 b2c2 a6b6 c2b2 b6a6 b2c2 a6b6 c2b2 b6a6 b2c2 a6b6 c2b2 b6a6 b2c2 a6b6 c2d2 b6a6 d2d1 a6b6 
  27     252       25      380546    a1b1 a7a8 b1b2 a8a7 b2b3 a7a6 b3c2 
  28     257       28      472692    a1b1 a7a6 b1c2 a6b6 c2d2 b6a6 d2e1 a6b6 e1f2 b6b7 f2g3 b7c7 g3h4 c7d7 h4g5 d7e7 g5f5 e7f7 f5g5 f7g7 f4f5 g7f7 
  29     257       33      573635    a1b1 a7a8 b1b2 a8a7 b2b3 a7a6 b3c2 a6b6 c2d2 
  30     258       39      736310    a1b1 a7a6 b1c2 a6b6 c2d2 b6b7 d2e2 b7c7 e2d1 c7d7 d1c2 d7c7 c2b1 c7b7 b1c1 b7b6 c1c2 b6a6 c2d1 
  31     258       43      839771    a1b1 a7a8 b1b2 a8a7 b2b3 a7a6 b3c2 a6b6 c2d2 b6b7 
  32     258       52     1049624    a1b1 a7a6 b1c2 a6b6 c2d2 b6b7 d2c1 b7a6 c1d1 a6b6 d1c2 b6a6 c2b2 a6a7 b2b1 
  33     258       63     1299726    a1b1 a7a8 b1b2 a8a7 b2b3 a7a6 b3b2 a6a7 
  34     258       90     1944561    a1b1 a7a6 b1c2 a6b6 c2d2 b6c7 d2d3 c7b6 d3c2 b6a6 c2d1 
  35     258      170     3529250    a1b1 a7a8 b1b2 a8a7 b2b1 
  36     259      432     8666791    a1b1 a7a6 b1c2 a6b6 c2d2 b6c7 d2d3 c7b6 d3e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4g5 e8f8 g5f4 f8e8 f4g5 
  37     263      462     9356322    a1b1 a7a8 b1b2 a8a7 b2b3 a7a6 b3b2 a6b6 b2c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 g5f5 
  38     263      512    10413599    a1b1 a7a6 b1b2 a6b6 b2c2 b6a6 c2d1 a6b6 d1d2 b6b7 d2e1 b7c7 e1d1 c7b6 

38 (3/3) 2.63  60.00  114797551  a1b1 a7a6 b1b2 a6b6 b2c2 b6a6 c2d1 a6b6 d1d2 b6b7 d2e1 b7c7 e1d1 c7b6 
Nodes: 114797551  NPS: 1913k  Ply: 38/50
Qnodes:   8174329   7.12% of Nodes
CutOffs:  97451618  84.89% of Nodes
CutOffOnFirst:  93172032  95.61% of CutOffs
Evals:  37908801
LazyEvals:  34979713  92.27% of Evals
Evasions:  15495627
TT-Writes:   27269589, TT-Hits:   55186605,  TT-Full: 99.9%
move a1b1 

Now I wonder, does the depth-prefer table perform so much worse? I smell a bug somewhere.

[Harald Johnsen]

Your pv is cut in your depth prefered search.
And why are you doing lazy evals in pawn endgame positions (or is that cached evals) ?

HJ.

[Guetti]

Your pv is cut in your depth prefered search.

Exactly. How can I prevent that?

And why are you doing lazy evals in pawn endgame positions (or is that cached evals) ?

HJ.

Hm, I guess I'm to lazy doing a full eval if one side ends up with a queen surplus?