[Computer-go] convergence in UCT search

Brian Sheppard sheppardco at aol.com
Mon Nov 14 14:47:20 PST 2011

The assumptions under which UCT converges are the same as alpha-beta,
minimax, state-space search, A*, etc.

"Converges" has a definition. You cannot redefine "converges" to preclude
large (but finite) amounts of resources.

-----Original Message-----
From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org] On Behalf Of Dave Dyer
Sent: Monday, November 14, 2011 5:13 PM
To: computer-go at dvandva.org; computer-go at dvandva.org
Subject: Re: [Computer-go] convergence in UCT search

At 12:40 PM 11/14/2011, Brian Sheppard wrote:
>My understanding is the opposite: UCT search with random playouts converges
>to best play in every two-player game.

That is true with infinite time and memory.  In practice,
even very obviously non-optimum moves persist with any reasonable
amount of search resources.

Computer-go mailing list
Computer-go at dvandva.org

More information about the Computer-go mailing list