Some basic search stats

[hgm]

Writing a new engine from scratch was a good opportunity to take some basic statistics on how much various search techniques contribute in a simple search. (No extensions or reductions yet.) I was particularly interested in how IID would help 'breaking new ground', i.e. extending a search branch into an erea where no hash information exists. Testing before I had implemented the hash table made this visible more clearly.

I tried various forms of IID: only in 'PV nodes' (defined as the first daughter of a PV node or the root, in this context), in steps of 2, in every node, or (which tested as best), in PV nodes in steps of 2, and in all other nodes with a remaining search depth d>=3 by preceeding it by a d=1 search. Only a single move of every iteration was moved to the front of the move list. (Even if there would be multiple non-fail-lows.) The static sorting initally was: hash move (if enabled and available), captures in MVV/LVA order, killers (if enabled) and non-captures in unspecified order.

Measurements were done by searching a single selected position. (Yes, I know it is better to average over a hundred or so, but I was a bit in a hurry.) I tried hash tables of 16M entries, firt with always-replace, and then ('dual hash') with shallowest-of-two replacement.

Code: Select all

No null move, no killers, no hash, no IID
 1     20      0         55 g3g4
 2      0      0        612 g3g4
 3     20      0       7198 c3c4
 4     16      7      52718 c3c4
 5     16     32     435366 c3c4
 6     16    511    4010125 c3c4
 7     28   2327   27357019 c3c4
 8     16  24585  204553953 c3c4
No null move, no killers, no hash, IID(+=2) in PV
 1     20      0         55 g3g4
 2      0      1        612 g3g4
 3     20      1       7198 c3c4
 4     16      7      51906 c3c4
 5     16     31     429695 c3c4
 6     16    507    3933810 c3c4
 7     28   2307   26846804 c3c4
 8     16  24416  201059835 c3c4
No null move, no killers, no hash, IID(+=2) in PV, IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      0        612 g3g4
 3     20      0       7198 c3c4
 4     16      7      52398 c3c4
 5     16     27     419872 c3c4
 6     16    492    3836356 c3c4
 7     28   2044   24761801 c3c4
 8     16  22500  188502161 c3c4
No null move, no killers, no hash, IID(+=2) everywhere
 1     20      0         55 g3g4
 2      0      0        612 g3g4
 3     20      1       7198 c3c4
 4     16      7      52398 c3c4
 5     16     27     424057 c3c4
 6     16    492    3906797 c3c4
 7     28   2057   25721828 c3c4
 8     16  23434  198910229 c3c4
No null move, killers, no hash, no IID
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      1       6625 c3c4
 4     16      5      38059 c3c4
 5     16     21     308866 c3c4
 6     16    245    2030363 c3c4
 7     28   1165   15261167 c3c4
 8     16  10844   95512145 c3c4
No null move, killers, no hash, IID(+=2) in PV
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      0       6625 c3c4
 4     16      5      38080 c3c4
 5     16     23     324286 c3c4
 6     16    252    2088716 c3c4
 7     28   1214   16228090 c3c4
 8     16  12833  112098161 c3c4
No null move, killers, no hash, IID(+=2) in PV, IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      1        614 g3g4
 3     20      1       6625 c3c4
 4     16      5      37967 c3c4
 5     16     18     304952 c3c4
 6     16    265    2211838 c3c4
 7     28    914   13595721 c3c4
 8     16  10815   93815081 c3c4
No null move, no killers, no hash, IID(+=2) everywhere
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      0       6625 c3c4
 4     16      4      37967 c3c4
 5     16     18     299292 c3c4
 6     16    278    2251734 c3c4
 7     28    976   14452768 c3c4
 8     16  11832  102647822 c3c4
No null move, killers, hash:move, IID(+=2) in PV, IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      1       4284 c3c4
 4     16      5      24549 c3c4
 5     16     11     137942 c3c4
 6     16    122     825418 c3c4
 7     28    363    5517338 c3c4
 8     16   4087   31004728 c3c4
No null move, killers, hash:move, IID only if no hash move: in PV(+=2), IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      1       4284 c3c4
 4     16      6      24554 c3c4
 5     16     11     135014 c3c4
 6     16    117     806378 c3c4
 7     28    353    5336942 c3c4
 8     16   4401   32994567 c3c4
No null move, killers, hash:move+(xd)cuts, IID only if no hash move: in PV(+=2), IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      1        614 g3g4
 3     20      1       4284 c3c4
 4     16      4      22765 c3c4
 5     16      9      98459 c3c4
 6     16     79     588490 c3c4
 7     28    225    2775964 c3c4
 8     16   2361   17542280 c3c4
 9     24  11508  151970543 c3c4
No null move, killers, dual-hash:move+(xd)cuts, IID only if no hash move: in PV(+=2), IID(1,d) in non-PV d>2
 1     20      0         55 g3g4
 2      0      0        614 g3g4
 3     20      0       4284 c3c4
 4     16      5      22765 c3c4
 5     16     10      98331 c3c4
 6     16     79     583223 c3c4
 7     28    217    2655804 c3c4
 8     16   1721   13070630 c3c4
 9     24   4519   58541231 c3c4

When enabling hash cutoffs, I only accepted them for exact depth, to make sure the scores would not be affected by hash hits through grafting. In the real engine will of course not keep that restriction, but it seemed a fairer and more reliabe way to take the stats.

For some reason, I can't get null-move runing to work yet. (i.e. it hardly seems to have any impact. Perhaps the position is to blame for this.)

[Dann Corbit]

Quite an interesting table. What happens when you factor in null move?

[Aleks Peshkov]

It will be interesting to compare different IID strategies with TT, but without killers.

[hgm]

I am not sure the difference would be observable. With TT the data become intrinsically noisy, depending on how positions collide (i.e. a different set of Zobrist keys will in general produce different node counts). And in most nodes you would have hash hits, so you would not do IID there with any strategy. (Even if you would attempt it, the earlier iterations would all be hash cuts, and nothng would be searched in parctice.) So IID would only happen in a small fraction of the nodes, and the difference the strategy would make would only be a very minor fraction of those sub-trees. This would drown in the noise caused by TT replacement.

Perhaps it could be done using an asymptotically large hash table, with a 'lossless' replacement scheme. I was heavily overloading the table in the fnal iterations, and the replacement scheme was primitive, so that even in a 1% loaded table a large fraction of the entries would get overwritten. But I don't feel like writing a special re-hashing scheme for this, which would be useless for a real engine.

[Aleks Peshkov]

I did not understand you at all. If, as you say, we have TT hits in most nodes, we need not any other move heuristics. Is it really so? What is special with rehashing and why it is useless in real engine?