[Computer-go] quiescence in UCT search

Olivier Teytaud teytaud at lri.fr
Wed Nov 9 02:32:49 PST 2011


Hi Dave.
I agree there is a point here, and that UCB does not do it. UCB does not
use the limited thinking time,
whereas you want to use this additional information.
We got 54% improvement by rules such as
"remove all children of the root for which getting more simulations than
the root is impossible",
or criterion of that form. Only this...
Other alternative solution: you get save up time by stopping thinking when
one child is sure of being the winner (i.e. if it is the winner whenever
the second best is almost simulated from now on). No change on the result,
and sometimes you save up some time.
Best regards,
OIivier

Le 9 novembre 2011 09:11:08 UTC+8, Dave Dyer <ddyer at real-me.net> a écrit :

>
> My starting point is that the root node is different from all
> other nodes.  The purpose of any particular search is to select
> the next move.  Once a particular child is far enough behind
> the leaders, it's effectively eliminated, and any additional
> effort spent to investigate it is a waste.
>
> For example, suppose we're going to search for 10 seconds, 5 seconds
> have passed, the leading node has 10,000 visits, and some other node
> has 100.  It's mathematically impossible for the weak node to ever
> replace the strong one.
>
> I'm looking for a mathematical framework for making that kind of
> decision on an ongoing basis.  Ideally, the top level nodes will
> be eliminated one by one, as the probability that they would have
> eventually been the winning choice falls below a chosen threshold.
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>



-- 
=========================================================
Olivier Teytaud -- olivier.teytaud at inria.fr
TAO, LRI, UMR 8623(CNRS - Universite Paris-Sud),
bat 490 Universite Paris-Sud F-91405 Orsay Cedex France http://0z.fr/EJm0g
(one of the 56.5 % of french who did not vote for Sarkozy in 2007)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20111109/57bb7ba8/attachment.html>


More information about the Computer-go mailing list