If AlphaGo actually used hard (e.g. permanent) pruning, then it would not be 
brute force. But it doesn’t operate that way, so it is brute force.


BTW, AlphaGo’s papers reports benefiting from search and RAVE. That suggests 
that hard pruning is a risky business.


From: David Wu [mailto:lightvec...@gmail.com] 
Sent: Sunday, August 6, 2017 2:54 PM
To: Brian Sheppard <sheppar...@aol.com>; computer-go@computer-go.org
Cc: Steven Clark <steven.p.cl...@gmail.com>
Subject: Re: [Computer-go] Alphago and solving Go


Saying in an unqualified way that AlphaGo is brute force is wrong in the spirit 
of the question. Assuming AlphaGo uses a typical variant of MCTS, it is 
technically correct. The reason it's technically correct uninteresting is 
because the bias introduced by a policy net is so extreme that it might as well 
be a selective search. 


Or put another way, imagine one were to set a threshold on the policy net 
output past a certain point in the tree such that moves below the threshold 
would be hard-pruned, and that threshold were set to a level that would prune, 
say, 70% of the legal moves in an average position. In technical sense, the 
search would no longer be full-width, and therefore it would suddenly become 
"not brute force" according to the definition earlier in the thread. But this 
distinction is not very useful, because moves in the tree that fall below such 
a threshold would receive zero simulations under any reasonable time controls 
anyways, so there would be no practical observable difference in the program's 
search or its play.


So - spirit of the question - no AlphaGo is not brute force, its search is 
selective to an extreme due to the policy net, the vast majority of 
possibilities will never be in practice given any attention or time whatsoever.


Technical answer - yes, AlphaGo is brute force, in that in the limit of having 
enormously vastly many more orders of magnitude of search time than we would 
ever devote to it and unbounded memory, it will theoretically eventually search 
everything (maybe, it would still depend on the actual details of its 



On Sun, Aug 6, 2017 at 2:20 PM, Brian Sheppard via Computer-go 
<computer-go@computer-go.org <mailto:computer-go@computer-go.org> > 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.cl...@gmail.com 
<mailto:steven.p.cl...@gmail.com> ] 
Sent: Sunday, August 6, 2017 1:14 PM
To: Brian Sheppard <sheppar...@aol.com <mailto:sheppar...@aol.com> >; 
computer-go <computer-go@computer-go.org <mailto:computer-go@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@computer-go.org <mailto:computer-go@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.





From: Computer-go [mailto:computer-go-boun...@computer-go.org 
<mailto:computer-go-boun...@computer-go.org> ] On Behalf Of Cai Gengyang
Sent: Sunday, August 6, 2017 9:49 AM
To: computer-go@computer-go.org <mailto:computer-go@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?



Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 


Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 


Computer-go mailing list

Reply via email to