Code: Select all
perft(5) tot = 1499 mean = 19851211.416278 std = 59.598497% / sqrt(99.9M) = 0.00596% (cumulative 0.0107%) perft(4) tot = 1282 mean = 736316.900936 std = 47.666721% / sqrt(83.0M) = 0.00524% (cumulative 0.00900%) perft(3) tot = 1150 mean = 25486.833043 std = 41.495897% / sqrt(74.4M) = 0.00581% (cumulative 0.00732%) perft(2) tot = 1025 mean = 906.915122 std = 28.374558% / sqrt(66.1M) = 0.00349% (cumulative 0.00456%) perft(1) tot = 975 mean = 29.978462 std = 21.894053% / sqrt(62.5M) = 0.00277%
I then divide this std deviation of sub-tree size by the number of sub-trees I sample in the perft(12) estimation (which is the nr of nodes at that level, divided by the applicable power of 32). This gives the std deviation introduced by the sampling of that level.
Finally I quadratically add the standard deviations of all levels together, which leads to a total of 0.00107%.
Note that there is also an odd-even effect in the variances: the difference between a 2- and 3-ply tree-size variance is much larger than between 1- and 2-ply. This is of course because positions with high mobility (= perft(1)) tend to have daughters with high mobility as well, but not necessarily above-average opponent mobility.
Due to this depth-correlation of mobilities, it would make sense to select moves from nodes with high mobility with a larger probability. By how much would be dependent on the remaining depth. This could be implemented, but the accounting would become more complex: in stead of single accepted/rejected counters per level, you would have to keep such a counter for every mobility (ignoring checks). And you would have to weight the branches relative to each other, as Peter does, by their inverse acceptance probability).
Another remark is that the attenuation 1/32 seems pretty optimal: it more or less flattens out the increase in variance towards lower plies, because it puts more samples there. Perhaps a little bit could be gained by reducing the number of samples at the 10-th ply, and devoting them to the 7th or 9th. (Although samples at the 10th ply are cheaper than at the 7th, because the remaining path is shorter.)