> > What we can say from experiments is that the scaling with time is very > > good > > with few simulations, but becomes less interesting with a lot of > > simulations. > > This is typical for statistical sampling. The variance of the sample mean > is a function of the square-root of the sampling size. > [....] > In case of UCT the sample-bias is on purpose. I do not know if this > accelerates convergence or introduces a systematic bias. A better > performance on a finite sample sizes does not mean that the sampling > converges in the limit to the true value. I also do not know if the result > measured at the end-position has some bias.
Here we don't have to forget that MC estimation is only at the leaf of the UCT tree. If there were no tree, of course, only few thousands of simulations would be enough to estimate the average. Here we don't try to estimate the expectation of a random variable using more sample, because after each simulation, the random variable is not the same. So, using UCT, the important thing is how deep is the tree, and if the predicted moves are the good ones, much more than variance analysis. If the MC returns bad values, the tree will go deeper, but will be meaningless. As said Magnus, at the end of the game, MC is quite good and then the tree gives good moves and with a lot of simulations becomes very good. At the beginning, if you give a lot of simulations, the tree can predict bad moves due to the bad MC evaluation. Of course, asymptotically it will converge towards the very best move, but we all know that we never are at the asymptotic :-). Sylvain _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
