Transposition Table and nps drop

[hgm]

If I use a small hash table of 4Kb (256 entries), the search for my test positions takes 34.4s at 8.5M nps searching 293M nodes.

If I use a 32Mb hash table the search takes 22.6s at 5M nps searching 112M nodes

I have never seen such a drop in NPS, unless you are either (a) so small that everything fits into cache until you start probing the hash which causes things to get replaced frequently; (b) using a hash implementation that is too slow, perhaps using multiple probes or something...

Then you can add now:

(c) When you enlarge the hash table so that it no longer fits in cache.

[hgm]

You pin pointed the issue. Before I added the TT code in my Minimax function at depth=0, I was returning Eval() wich is really fast since it only return an incrementally updated value. When I added my TT code, I did a probe _before_ I checked for depth=0, So I was doing an extra probe at each leaf nodes.

When your eval gets more complicated, and even more when at depth=0 nodes you can still be doing a Quiescense Search, it is not so obvious that you can drop the probe at the leave nodes. I tried this in Joker and micro-Max, and both actually slow down (not in nps, but in over-all search time) when I probe (and store) only depth >= 1. In Crafty it seems to be about even. So you would have to keep testing what is better when you develop your engine further, and you might just have to live with the lower nps.

[Tony]

Hi,

My engine is actually using a simple minimax (no AlphaBeta) function for the moment. I want to get it completely functional before I write the AB search and all the other improvements.

This week I implemented a transposition table, because I want to be able to retrieve the principal variation from it. So I implemented it into my Minimax function and I get confused by the results.

If I use a small hash table of 4Kb (256 entries), the search for my test positions takes 34.4s at 8.5M nps searching 293M nodes.

If I use a 32Mb hash table the search takes 22.6s at 5M nps searching 112M nodes

and if I use a 256Mb the search takes 25.2s at 4.3M nps searching 107M nodes.

I was expecting a drop in nodes per seconds, but it seems that with a 256Mb hash tables, the nps drop by about 50% making the search even slower than with a 32 Mo hash table.

However, when I profile my engine, the profiling code seems to use only <1% of the total cpu time. What does that means? Do I have a bug or is this due the cache miss the huge table will inevitably cause?

It's normal.

Implement alpha beta (and move ordering) and it will drop even more.

There are several reasons:

- additional processing time
- additional cache misses
- less nodes searched (ie even if I only spend 0.1% additional time to reduce the tree by 90%, my nodes/sec drop)

Every searchimprovement slows the engine down compared to plain minimax. But overal time to solution should become better. Hence the term improvement

Tony