[Computer-go] Alphago and solving Go

Steven Clark steven.p.clark at gmail.com
Sun Aug 6 13:18:02 PDT 2017


We've probably beat this horse to death, but here's David Silver (lead
programmer at top of alphago paper): "The search process itself is not
based on brute force, more on something akin to imagination…. "

On Aug 6, 2017 4:08 PM, "Brian Sheppard" <sheppardco at aol.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20170806/73788454/attachment-0001.html>


More information about the Computer-go mailing list