[Bug-gnubg] Variance reduction efficiency

[Philippe Michel]

On Thu, 24 Aug 2017, tchow wrote:

> O.K., so let me rephrase my suggestion: What happens if we use n-ply variance 
> reduction for an n-ply rollout, at least for the first or second steps of a 
> rollout trial?

I don't have an answer to this specific question, but some (not 
statistically significant) data may give an idea.

Rolling out  some middle-game position at various plies gave (VR vs. 
no-VR) :

At 0-ply (VR at 0-ply) :
duration : x 21.3, SD : / 6.6, equivalent number of trials : x 44

At 1-ply (VR at 0-ply) :
duration : +45%, SD : / 6.4, equivalent number of trials : x 41

At 2-ply (VR at 1-ply) :
duration : +4.5%, SD : / 13.2, equivalent number of trials : x 174

At 3-ply (VR at 2-ply) :
duration : +3.7%, SD : / 17.4, equivalent number of trials : x 301

So, a higher ply for variance reduction helps (although the returns are 
diminishing with higher plies). On the other hand, using the same ply as 
the rollout itself, while better than no VR, is extremely expensive.

With your proposal used for the usual 2-ply rollouts the first few steps 
would be 20 times slower, the following ones unchanged. The total number 
of steps would depend of the position but the final cost may be in the
x 1.5 to x 2 range, similar to the gain in accuracy when *all* steps use 
2-ply variance reduction.