On Wed, Jun 08, 2011 at 08:17:08PM +0800, Bojun Huang wrote:
> >So the question is, assuming memory is enough, or at a position (perhaps
> >near the end) in practice, does node-pruning harm the convergence?
>
> I think any kind of garbage collection will not harm the convergence of UCT,
> since UCT can converge to the optimal solution from exploration trees with
> any shape -- it's just a matter of how long it will converge.
One easy way to repair theoretical convergence should be probabilistic
pruning. E.g. if you want to prune 25% nodes, take 50% least visited
nodes, and prune each with probability proportional to its projected
merit (I can think of several ways right now) so that on average, you
prune half of them.
Pachi does very simplistic pruning (we just so far take the lazy way and
assume memory is quite cheap nowadays), but if I were to implement some
online pruning, I would certainly make it probabilistic not just because
of theoretical convergence, but because I have very good experience with
slight randomization within all MCTS aspects.
In other words, I think it depends on the pruning strategy.
--
Petr "Pasky" Baudis
UNIX is user friendly, it's just picky about who its friends are.
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
