pruning statistics

[jdart]

I have been looking into how much various engines actually use their pruning and extension heuristics.

For pruning that is done when entering a node, including static null pruning, razoring and null move pruning, my measurement is what % of nodes are pruned. Nodes are counted by incrementing a counter every time the search enters a new regular node (not quiescence node).

For pruning, reduction and extensions that are done on a per move basis, my measurement is based on what % of moves have these operations done on them. Every time a new move is produced from the move generator (even if later determined to be illegal) I increment the move counter, again only in the regular search, not the q-search.

I have only done this measurement so far for a few programs that are easy to modify.

I ran each engine single-threaded for 60 seconds on this position:

2q2r2/3n1p2/p2p2k1/3PpRp1/P1n1P3/2P2QB1/1rB1R1P1/6K1 w - - bm Rxg5+; id "arasan16.3";

Here are some results (note: MinkoChess has no extensions):

Protector 1.5:

< ENGINE 58.43% futility pruning
> ENGINE stop
< ENGINE 10.16% static null pruning
> ENGINE stop
< ENGINE 15.60% razoring
> ENGINE stop
< ENGINE 15.99% null cutoff
> ENGINE stop
< ENGINE 33.23% lmp
> ENGINE stop
< ENGINE 8.49% check extensions
> ENGINE stop
< ENGINE 0.42% evasion extensions
> ENGINE stop
< ENGINE 0.00% pawn extensions
> ENGINE stop
< ENGINE 0.00% capture extensions
> ENGINE stop
< ENGINE 5.25% reduced
> ENGINE stop

MinkoChess 1.3:

< ENGINE 13% static null pruning
> ENGINE stop
< ENGINE 6% razored
> ENGINE stop
< ENGINE 4.2% null cuts
> ENGINE stop
< ENGINE 13% futility pruning
> ENGINE stop
< ENGINE 2% see pruning
> ENGINE stop
< ENGINE 24% reduced
> ENGINE stop

and Arasan, latest dev version:

pre-search pruning:
4.17% razoring
19.12% static null pruning
5.67% null cuts
search pruning:
34.70% futility
1.33% history
12.00% lmp
6.33% SEE
7.96% reduced
extensions: 4.64% check, 1.75% evasions, 0.00% capture, 0.14% pawn
0 tablebase probes, 0 tablebase hits

[jdart]

And here is DiscoCheck 5.2:

< ENGINE 16% static null pruning
< ENGINE 8.4% razoring
< ENGINE 9.9% null cuts
< ENGINE 28% futility pruning
< ENGINE 23% lmp
< ENGINE 2.3% SEE pruning
< ENGINE 3.4% check extensions
< ENGINE 0.52% evasion extensions
< ENGINE 65% reduced

[ZirconiumX]

And here is DiscoCheck 5.2:

< ENGINE 16% static null pruning
< ENGINE 8.4% razoring
< ENGINE 9.9% null cuts
< ENGINE 28% futility pruning
< ENGINE 23% lmp
< ENGINE 2.3% SEE pruning
< ENGINE 3.4% check extensions
< ENGINE 0.52% evasion extensions
< ENGINE 65% reduced

Knowing Lucas, I was expecting this to be a big figure.

Maybe you could also add information about how often the first move was the best move (i.e. how close to optimal move ordering is).

It's certainly interesting to see the comparison between engines - maybe other engine authors could join in?

Matthew:out

[jdart]

Here are some statistics for Arasan, on the same position:

move ordering: 1st 95.57% 2nd 2.52% 3rd 0.90% 4th 0.48%

So about 95% of the time the first move is the best move.

--Jon

[cetormenter]

I did the same thing with Nirvanachess. Here are my results.
I am not sure how you are counting LMR since most of the moves that would be reduced will most likely be pruned there is even the chance to reduce them. However I simply moved where I calculated the reductions to beginning of the search.

Results:

Check Extensions: 3.12%
Late Move Pruning: 21.51%
Futility Pruning: 21.31%
See Pruning: 1.24%
Late move Reduction: 30.96%

Razored: 13.50%
Static Nullmove Pruning: 10.76%
Nullmove Pruning: 15.07%

First Move: 86.14%
Second Move: 5.42%
Third Move: 2.83%

[jdart]

My engine does reduction after pruning. Some engines do the reverse and also use the reduced depth in pruning decisions so moves that have reducing are more likely to be pruned.

I am counting as reduced any moves that get a non-zero reduction of depth regardless of where that occurs.

--Jon