No, I don't do any node estimates. The nodes are completely unaware of anything. I just have a global counter that counts leave nodes:
Code: Select all
int accepted[10], rejected[10], count, nodes;
perft(n)
{
nodes++;
for(ALL_MOVES) {
if(n==1) count++; else
if(n <= SELECTIVITY && (random() & 31) != 0) rejected[n]++; else {
accepted[n]++;
MakeMove();
perft(n-1);
UnMake();
}
}
and afterwards I multiply count with (1 + rejected[n]/accepted[n]) for all n. As I never tried selectivity in the root, the chances that all moves are rejected at an entire level in astronomically small.
Btw, just to be sure I implemented Mersenne Twister (for again a20% slowdown)in stead of my crappy PRNG, and obtained the following empirical with 500M nodes:
Code: Select all
1/32 acceptace
3-ply full width:
14021. mean = 6.286692e+16 SD = 2.664580% ( 0.022503%) nodes=499991084
14022. mean = 6.286672e+16 SD = 2.664774% ( 0.022504%) nodes=500025967
4-ply full width:
587. mean = 6.284372e+16 SD = 0.424240% ( 0.017510%) nodes=499938176
588. mean = 6.284380e+16 SD = 0.423888% ( 0.017481%) nodes=500789873
5-ply full-width:
23. mean = 6.286163e+16 SD = 0.058986% ( 0.012299%) nodes=479736315
24. mean = 6.286130e+16 SD = 0.057748% ( 0.011788%) nodes=500595954
6-ply full-width:
1. mean = 6.284515e+16 SD = -nan% ( -nan%) nodes=510055595
SD is the empirical standard deviation in a single perft, in parenthesis the implied behind it the SD for the average of the entire run (so divided by sqrt(N) with N the number of runs, which is the first number on the line). The 6-ply full-width I did only once, so no empirical SD there.
As you can see, the randomness on the lower levels contributes significantly to the variance. If you force all moves at ply 4 to be picked equally often (by making that ply full-width), the SD drops from 0.0225% to 0.0175%, for same number of samples. That is a variance reduction of 37%.