I don't know if the worst could be worse; UCT convergence for a 1-ply search is a probabilistic function with an exponential bound. The bound for an N-ply search is a tower of N exponentials: Exp(Exp(Exp(...Exp()))). Ugh.
Because of this bound, guessing good moves quickly is absolutely vital for strong play from UCT. Which calls into question why I haven't taken MM and Sim Balancing more seriously. :-) -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Petr Baudis Sent: Monday, April 04, 2011 10:27 PM To: [email protected] Subject: Re: [Computer-go] 7.0 Komi and weird deep search result On Mon, Apr 04, 2011 at 12:56:54PM -0400, Brian Sheppard wrote: > >> MCTS using RAVE prioritization *does* converge to game theoretic values > in a > >> binary-valued space. > > >Can you reference some more detailed analysis claiming this? > > > > Theorem: In a binary-valued game of finite length, the RAVE score of all > winning moves converges to 1, provided that 0 < FPU < 1. Oh of course, it is obvious. Sorry for being slow and confused. But it seems it should be possible to prove that even theoretical convergence in case of RAVE discrepecancies is much slower than with plain UCT... Might be a fun exercise. Petr "Pasky" Baudis _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
