[Computer-go] Alphago and solving Go

Álvaro Begué alvaro.begue at gmail.com
Sun Aug 6 15:09:41 PDT 2017


Eventually exploring the entire tree is what I would call "mathematically
sound", meaning that given enough time the algorithm is guaranteed to play
optimally. I would reserve "brute force" for algorithms that simply search
every possible variant exhaustively, like John Tromp's connect 4 program
Fhourstones does [very well, I may add].

But I do smell troll too, so I'll stop here. Enough feeding.

Álvaro.



On Sun, Aug 6, 2017 at 4:08 PM, Brian Sheppard via Computer-go <
computer-go at computer-go.org> wrote:

> Possibly you are answering a different question than the one posed?
> Possibly your interpretation is the one actually intended. I don’t know,
> and maybe you could be right about what was being asked.
>
>
>
> I do know the semantics of brute force, though, which you quoted below.
>
>
>
> Note that “brute force” != unintelligent. Inevitably, every brute force
> algorithm will incorporate intelligent heuristics. Consider the evolution
> of minimax, for example, via alpha-beta, selective extensions, LMR, etc.
>
>
>
>
>
>
>
> *From:* Steven Clark [mailto:steven.p.clark at gmail.com]
> *Sent:* Sunday, August 6, 2017 2:52 PM
> *To:* Brian Sheppard <sheppardco at aol.com>
> *Cc:* computer-go <computer-go at computer-go.org>
>
> *Subject:* Re: [Computer-go] Alphago and solving Go
>
>
>
> This is semantics. Yes, in the limit of infinite time, it is brute-force.
> Meanwhile, in the real world, AlphaGo chooses to balance its finite time
> budget between depth & width. The mere fact that the CNN policy network
> generates a score for each coordinate on the board in a given position,
> does not mean that all of those nodes will be expanded in any reasonable
> scenario.
>
>
>
> On Sun, Aug 6, 2017 at 2:20 PM, Brian Sheppard <sheppardco at aol.com> wrote:
>
> I understand why most people are saying that AlphaGo is not brute force,
> because it appears to be highly selective. But MCTS is a full width search.
> Read the AlphaGo papers, as one of the other respondents (rather
> sarcastically) suggested: AlphaGo will eventually search every move at
> every node.
>
>
>
> MCTS has the appearance of a selective search because time control
> terminates search while the tree is still ragged. In fact, it will search
> every continuation an infinite number of times.
>
>
>
> In order to have high performance, an MCTS implementation needs to search
> best moves as early as possible in each node. It is in this respect that
> AlphaGo truly excels. (AlphaGo also excels at whole board evaluation, but
> that is a separate topic.)
>
>
>
>
>
> *From:* Steven Clark [mailto:steven.p.clark at gmail.com]
> *Sent:* Sunday, August 6, 2017 1:14 PM
> *To:* Brian Sheppard <sheppardco at aol.com>; computer-go <
> computer-go at computer-go.org>
> *Subject:* Re: [Computer-go] Alphago and solving Go
>
>
>
> Why do you say AlphaGo is brute-force? Brute force is defined as: "In
> computer science, brute-force search or exhaustive search, also known as
> generate and test, is a very general problem-solving technique that
> consists of *systematically enumerating all possible candidates* for the
> solution and checking whether each candidate satisfies the problem's
> statement."
>
>
>
> The whole point of the policy network is to avoid brute-force search, by
> reducing the branching factor...
>
>
>
> On Sun, Aug 6, 2017 at 10:42 AM, Brian Sheppard via Computer-go <
> computer-go at computer-go.org> wrote:
>
> Yes, AlphaGo is brute force.
>
> No it is impossible to solve Go.
>
> Perfect play looks a lot like AlphaGo in that you would not be able to
> tell the difference. But I think that AlphaGo still has 0% win rate against
> perfect play.
>
>
>
> My own best guess is that top humans make about 12 errors per game. This
> is estimated based on the win rate of top pros in head-to-head games. The
> calculation starts by assuming that Go is a win at 6.5 komi for either
> Black (more likely) or White, so a perfect player would win 100% for Black.
> Actual championship caliber players win 51% to 52% for Black. In 9-dan play
> overall, I think the rate is 53% to 54% for Black. Then you can estimate
> how many errors each player has to make to bring about such a result. E.g.,
> If players made only one error on average, then Black would win the vast
> majority of games, so they must make more errors. I came up with 12 errors
> per game, but you can reasonably get other numbers based on your model.
>
>
>
> Best,
>
> Brian
>
>
>
> *From:* Computer-go [mailto:computer-go-bounces at computer-go.org] *On
> Behalf Of *Cai Gengyang
> *Sent:* Sunday, August 6, 2017 9:49 AM
> *To:* computer-go at computer-go.org
> *Subject:* [Computer-go] Alphago and solving Go
>
>
>
> Is Alphago brute force search?
>
> Is it possible to solve Go for 19x19 ?
>
> And what does perfect play in Go look like?
>
> How far are current top pros from perfect play?
>
>
>
> Gengyang
>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
>
>
>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20170806/5bf53dbb/attachment.html>


More information about the Computer-go mailing list