Re: [Computer-go] Alphago and solving Go

[John Tromp]

> Shouldnt that number at most be 722^#positions? Since adding a black or a
> white stone is something fundamentally different?

The upper bound of 361^L(19,19) games is from Theorem 7 on page 31 of
http://tromp.github.io/go/gostate.pdf, where you will find a proof.
As the paragraph preceding that theorem explains, the difference from your
suggestion is due to the average position having only 361/3 empty points
available for play.

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Robert Jasiek]

On 09.08.2017 20:50, John Tromp wrote:

The number of games is at most 361^#positions.


This misses passes, rules distinguishing situations etc. and infinite 
sequences under some rulesets.


--
robert jasiek
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[uurtamo .]

Why do you think that there is a 3 in the denominator?

On Aug 9, 2017 2:29 PM, "Marc Landgraf"  wrote:

> I don't mind your terminology, in fact I feel like it is a good way to
> distinguish the two different things. It is just that I considiered one
> thing wrongly used instead of the other for the discussion here.
>
> But if we go with the link you are suggesting here:
> Shouldnt that number at most be 722^#positions? Since adding a black or a
> white stone is something fundamentally different?
>
> 2017-08-09 20:50 GMT+02:00 John Tromp :
>
>> > And what is the connection between the number of "positions" and the
>> number
>> > of games
>>
>> The number of games is at most 361^#positions.
>>
>> > or even solving games? In the game trees we do not care about
>> > positions, but about situations.
>>
>> We care about lots of things, including intersections, stones,
>> liberties, strings, positions, sets of previous positions.
>>
>> > I'm actually surprised that this "absurd" to you...
>>
>> I said that referring to a board configuration together with the set
>> of all previously occurring board configurations (and turn to move) as
>> "position" is absurd.
>> We need a simple word to denote a board configuration, and "position" fits
>> that requirement. A good word for all the relevant historical
>> information leading up to a position is "situation".
>>
>> -John
>> ___
>> Computer-go mailing list
>> Computer-go@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[uurtamo .]

It's trivial, dude.

On Aug 9, 2017 8:35 AM, "Marc Landgraf"  wrote:

> Under which ruleset is the 3^(n*n) a trivial upper bound for the number of
> legal positions?
> I'm sure there are rulesets, under which this bonds holds, but I doubt
> that this can be considered trivial.
>
> Under the in computer go more common rulesets this upper bound is simply
> wrong. Unless we talk about simply the visual aspect, but then this has
> absolutely nothing to do with the discussion abour solving games.
>
> 2017-08-09 14:34 GMT+02:00 Gunnar Farnebäck :
>
>> Except 361! (~10^768) couldn't plausibly be an estimate of the number of
>> legal positions, since ignoring the rules in that case gives the trivial
>> upper bound of 3^361 (~10^172).
>>
>> More likely it is a very, very bad attempt at estimating the number of
>> games. Even with the extremely unsharp bound given in
>> https://tromp.github.io/go/gostate.pdf
>>
>> 10^(10^48) < number of games < 10^(10^171)
>>
>> the 361! estimate comes nowhere close to that interval.
>>
>> /Gunnar
>>
>> On 08/07/2017 04:14 AM, David Doshay wrote:
>>
>>> Yes, that zeroth order number (the one you get to without any thinking
>>> about how the game’s rules affect the calculation) is outdated since early
>>> last year when this result gave us the exact number of legal board
>>> positions:
>>>
>>> https://tromp.github.io/go/legal.html
>>>
>>> So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170
>>> unique nodes (see the paper for all 171 digits) but some number of
>>> duplicates of those nodes for the different paths to each legal position.
>>>
>>> In an unfortunate bit of timing, it seems that many people missed this
>>> result because of the Alpha Go news.
>>>
>>> Cheers,
>>> David G Doshay
>>>
>>> ddos...@mac.com 
>>>
>>>
>>>
>>>
>>>
>>> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck > wrote:

 On 08/06/2017 04:39 PM, Vincent Richard wrote:

> No, simply because there are way to many possibilities in the game,
> roughly (19x19)!
>

 Can we lay this particular number to rest? Not that "possibilities in
 the game" is very well defined (what does it even mean?) but the number of
 permutations of 19x19 points has no meaningful connection to the game of go
 at all, not even "roughly".

 /Gunnar
 ___
 Computer-go mailing list
 Computer-go@computer-go.org 
 http://computer-go.org/mailman/listinfo/computer-go

>>>
>>>
>>>
>>> ___
>>> Computer-go mailing list
>>> Computer-go@computer-go.org
>>> http://computer-go.org/mailman/listinfo/computer-go
>>>
>>>
>> ___
>> Computer-go mailing list
>> Computer-go@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Marc Landgraf]

I don't mind your terminology, in fact I feel like it is a good way to
distinguish the two different things. It is just that I considiered one
thing wrongly used instead of the other for the discussion here.

But if we go with the link you are suggesting here:
Shouldnt that number at most be 722^#positions? Since adding a black or a
white stone is something fundamentally different?

2017-08-09 20:50 GMT+02:00 John Tromp :

> > And what is the connection between the number of "positions" and the
> number
> > of games
>
> The number of games is at most 361^#positions.
>
> > or even solving games? In the game trees we do not care about
> > positions, but about situations.
>
> We care about lots of things, including intersections, stones,
> liberties, strings, positions, sets of previous positions.
>
> > I'm actually surprised that this "absurd" to you...
>
> I said that referring to a board configuration together with the set
> of all previously occurring board configurations (and turn to move) as
> "position" is absurd.
> We need a simple word to denote a board configuration, and "position" fits
> that requirement. A good word for all the relevant historical
> information leading up to a position is "situation".
>
> -John
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[John Tromp]

> And what is the connection between the number of "positions" and the number
> of games

The number of games is at most 361^#positions.

> or even solving games? In the game trees we do not care about
> positions, but about situations.

We care about lots of things, including intersections, stones,
liberties, strings, positions, sets of previous positions.

> I'm actually surprised that this "absurd" to you...

I said that referring to a board configuration together with the set
of all previously occurring board configurations (and turn to move) as
"position" is absurd.
We need a simple word to denote a board configuration, and "position" fits
that requirement. A good word for all the relevant historical
information leading up to a position is "situation".

-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Marc Landgraf]

And what is the connection between the number of "positions" and the number
of games or even solving games? In the game trees we do not care about
positions, but about situations. For the game tree it indeed matters whos
turn it is, which moves are legal, and if super-ko rules are used which
positions are legal and which aren't. It will be tough to solve the game
even for a single position without having this information.

I'm actually surprised that this "absurd" to you...

2017-08-09 17:48 GMT+02:00 John Tromp :

> > Under which ruleset is the 3^(n*n) a trivial upper bound for the number
> of
> > legal positions?
>
> Under all rulesets.
>
> > Unless we talk about simply the visual aspect
>
> Yes, we do.
>
> > but then this has
> > absolutely nothing to do with the discussion abour solving games.
>
> If you want the notion of "position" to encode everything needed to
> determine legality of future plays, then in the case of superko, you
> need the entire set of previous board configurations, which to me is
> rather absurd.
> Instead you should call that "situation".
> That's how we distinguish the two flavors of superko;
> positional vs situational...
>
> regards,
> -John
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[John Tromp]

> Under which ruleset is the 3^(n*n) a trivial upper bound for the number of
> legal positions?

Under all rulesets.

> Unless we talk about simply the visual aspect

Yes, we do.

> but then this has
> absolutely nothing to do with the discussion abour solving games.

If you want the notion of "position" to encode everything needed to
determine legality of future plays, then in the case of superko, you
need the entire set of previous board configurations, which to me is
rather absurd.
Instead you should call that "situation".
That's how we distinguish the two flavors of superko;
positional vs situational...

regards,
-John
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Marc Landgraf]

Under which ruleset is the 3^(n*n) a trivial upper bound for the number of
legal positions?
I'm sure there are rulesets, under which this bonds holds, but I doubt that
this can be considered trivial.

Under the in computer go more common rulesets this upper bound is simply
wrong. Unless we talk about simply the visual aspect, but then this has
absolutely nothing to do with the discussion abour solving games.

2017-08-09 14:34 GMT+02:00 Gunnar Farnebäck :

> Except 361! (~10^768) couldn't plausibly be an estimate of the number of
> legal positions, since ignoring the rules in that case gives the trivial
> upper bound of 3^361 (~10^172).
>
> More likely it is a very, very bad attempt at estimating the number of
> games. Even with the extremely unsharp bound given in
> https://tromp.github.io/go/gostate.pdf
>
> 10^(10^48) < number of games < 10^(10^171)
>
> the 361! estimate comes nowhere close to that interval.
>
> /Gunnar
>
> On 08/07/2017 04:14 AM, David Doshay wrote:
>
>> Yes, that zeroth order number (the one you get to without any thinking
>> about how the game’s rules affect the calculation) is outdated since early
>> last year when this result gave us the exact number of legal board
>> positions:
>>
>> https://tromp.github.io/go/legal.html
>>
>> So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170
>> unique nodes (see the paper for all 171 digits) but some number of
>> duplicates of those nodes for the different paths to each legal position.
>>
>> In an unfortunate bit of timing, it seems that many people missed this
>> result because of the Alpha Go news.
>>
>> Cheers,
>> David G Doshay
>>
>> ddos...@mac.com 
>>
>>
>>
>>
>>
>> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck >> > wrote:
>>>
>>> On 08/06/2017 04:39 PM, Vincent Richard wrote:
>>>
 No, simply because there are way to many possibilities in the game,
 roughly (19x19)!

>>>
>>> Can we lay this particular number to rest? Not that "possibilities in
>>> the game" is very well defined (what does it even mean?) but the number of
>>> permutations of 19x19 points has no meaningful connection to the game of go
>>> at all, not even "roughly".
>>>
>>> /Gunnar
>>> ___
>>> Computer-go mailing list
>>> Computer-go@computer-go.org 
>>> http://computer-go.org/mailman/listinfo/computer-go
>>>
>>
>>
>>
>> ___
>> Computer-go mailing list
>> Computer-go@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Erik van der Werf]

361! seems like an attempt to estimate an upper bound on the number of
games where nothing is captured.

On Wed, Aug 9, 2017 at 2:34 PM, Gunnar Farnebäck 
wrote:

> Except 361! (~10^768) couldn't plausibly be an estimate of the number of
> legal positions, since ignoring the rules in that case gives the trivial
> upper bound of 3^361 (~10^172).
>
> More likely it is a very, very bad attempt at estimating the number of
> games. Even with the extremely unsharp bound given in
> https://tromp.github.io/go/gostate.pdf
>
> 10^(10^48) < number of games < 10^(10^171)
>
> the 361! estimate comes nowhere close to that interval.
>
> /Gunnar
>
> On 08/07/2017 04:14 AM, David Doshay wrote:
>
>> Yes, that zeroth order number (the one you get to without any thinking
>> about how the game’s rules affect the calculation) is outdated since early
>> last year when this result gave us the exact number of legal board
>> positions:
>>
>> https://tromp.github.io/go/legal.html
>>
>> So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170
>> unique nodes (see the paper for all 171 digits) but some number of
>> duplicates of those nodes for the different paths to each legal position.
>>
>> In an unfortunate bit of timing, it seems that many people missed this
>> result because of the Alpha Go news.
>>
>> Cheers,
>> David G Doshay
>>
>> ddos...@mac.com 
>>
>>
>>
>>
>>
>> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck >> > wrote:
>>>
>>> On 08/06/2017 04:39 PM, Vincent Richard wrote:
>>>
 No, simply because there are way to many possibilities in the game,
 roughly (19x19)!

>>>
>>> Can we lay this particular number to rest? Not that "possibilities in
>>> the game" is very well defined (what does it even mean?) but the number of
>>> permutations of 19x19 points has no meaningful connection to the game of go
>>> at all, not even "roughly".
>>>
>>> /Gunnar
>>> ___
>>> Computer-go mailing list
>>> Computer-go@computer-go.org 
>>> http://computer-go.org/mailman/listinfo/computer-go
>>>
>>
>>
>>
>> ___
>> Computer-go mailing list
>> Computer-go@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Gunnar Farnebäck]

Except 361! (~10^768) couldn't plausibly be an estimate of the number of 
legal positions, since ignoring the rules in that case gives the trivial 
upper bound of 3^361 (~10^172).


More likely it is a very, very bad attempt at estimating the number of 
games. Even with the extremely unsharp bound given in 
https://tromp.github.io/go/gostate.pdf


10^(10^48) < number of games < 10^(10^171)

the 361! estimate comes nowhere close to that interval.

/Gunnar

On 08/07/2017 04:14 AM, David Doshay wrote:
Yes, that zeroth order number (the one you get to without any thinking 
about how the game’s rules affect the calculation) is outdated since 
early last year when this result gave us the exact number of legal board 
positions:


https://tromp.github.io/go/legal.html

So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170 
unique nodes (see the paper for all 171 digits) but some number of 
duplicates of those nodes for the different paths to each legal position.


In an unfortunate bit of timing, it seems that many people missed this 
result because of the Alpha Go news.


Cheers,
David G Doshay

ddos...@mac.com 





On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck > wrote:


On 08/06/2017 04:39 PM, Vincent Richard wrote:
No, simply because there are way to many possibilities in the game, 
roughly (19x19)!


Can we lay this particular number to rest? Not that "possibilities in 
the game" is very well defined (what does it even mean?) but the 
number of permutations of 19x19 points has no meaningful connection to 
the game of go at all, not even "roughly".


/Gunnar
___
Computer-go mailing list
Computer-go@computer-go.org 
http://computer-go.org/mailman/listinfo/computer-go




___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go



___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Erik van der Werf]

On Mon, Aug 7, 2017 at 12:52 PM, Darren Cook  wrote:

> > https://en.wikipedia.org/wiki/Brute-force_search explains it as
> > "systematically enumerating all possible candidates for the
> > solution".
> >
> > There is nothing systematic about the pseudo random variation
> > selection in MCTS;
>
> More semantics, but as it is pseudo-random, isn't that systematic? It
> only looks like it is jumping around because we are looking at it from
> the wrong angle.
>
> (Systematic pseudo-random generation gets very hard over a cluster, of
> course...)
>
>
The selection should be quite deterministic. Randomness is in the playouts,
so it only comes in indirectly. With a value net there will be even less
variance.



> > it may not even have sufficient entropy to guarantee full
> > enumeration...
>
> That is the most interesting idea in this thread. Is there any way to
> prove it one way or the other? I'm looking at you here, John - sounds
> right up your street :-)
>

Full enumeration may occur with infinite time & memory, and a growing
exploration term for unexplored nodes. Randomness has little to do with it.

Anyway, IMO the whole argument is silly and even a bit disrespectful. I
don't consider AlphaGo a brute force solution. However, if some
hard-pruning would turn AlphaGo from brute force into non-brute force then
just implement some provably correct hard pruning rules and you're done
(e.g., don't play in unconditional territory, stop the playouts when the
position is statically solved, etc.). I have things like that in
Steenvreter, but it doesn't feel like that changes the nature of the beast.

E.
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Darren Cook]

> https://en.wikipedia.org/wiki/Brute-force_search explains it as 
> "systematically enumerating all possible candidates for the
> solution".
> 
> There is nothing systematic about the pseudo random variation 
> selection in MCTS;

More semantics, but as it is pseudo-random, isn't that systematic? It
only looks like it is jumping around because we are looking at it from
the wrong angle.

(Systematic pseudo-random generation gets very hard over a cluster, of
course...)

> it may not even have sufficient entropy to guarantee full
> enumeration...

That is the most interesting idea in this thread. Is there any way to
prove it one way or the other? I'm looking at you here, John - sounds
right up your street :-)

Darren
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Petr Baudis]

  BTW, if anyone is wondering about the "roughly" part,
361! = 1.438 * 10^768 while L19 = 2.081681994 * 10^170.

On Sun, Aug 06, 2017 at 07:14:42PM -0700, David Doshay wrote:
> Yes, that zeroth order number (the one you get to without any thinking about 
> how the game’s rules affect the calculation) is outdated since early last 
> year when this result gave us the exact number of legal board positions:
> 
> https://tromp.github.io/go/legal.html 
> 
> So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170 
> unique nodes (see the paper for all 171 digits) but some number of duplicates 
> of those nodes for the different paths to each legal position. 
> 
> In an unfortunate bit of timing, it seems that many people missed this result 
> because of the Alpha Go news.
> 
> Cheers,
> David G Doshay
> 
> ddos...@mac.com
> 
> 
> 
> 
> 
> > On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck  wrote:
> > 
> > On 08/06/2017 04:39 PM, Vincent Richard wrote:
> >> No, simply because there are way to many possibilities in the game, 
> >> roughly (19x19)!
> > 
> > Can we lay this particular number to rest? Not that "possibilities in the 
> > game" is very well defined (what does it even mean?) but the number of 
> > permutations of 19x19 points has no meaningful connection to the game of go 
> > at all, not even "roughly".
> > 
> > /Gunnar
> > ___
> > Computer-go mailing list
> > Computer-go@computer-go.org
> > http://computer-go.org/mailman/listinfo/computer-go
> 

> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go


-- 
Petr Baudis, Rossum
Run before you walk! Fly before you crawl! Keep moving forward!
If we fail, I'd rather fail really hugely.  -- Moist von Lipwig
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[David Doshay]

Yes, that zeroth order number (the one you get to without any thinking about 
how the game’s rules affect the calculation) is outdated since early last year 
when this result gave us the exact number of legal board positions:

https://tromp.github.io/go/legal.html 

So, a complete game tree for 19x19 Go would contain about 2.08 * 10^170 unique 
nodes (see the paper for all 171 digits) but some number of duplicates of those 
nodes for the different paths to each legal position. 

In an unfortunate bit of timing, it seems that many people missed this result 
because of the Alpha Go news.

Cheers,
David G Doshay

ddos...@mac.com





> On 6, Aug 2017, at 3:17 PM, Gunnar Farnebäck  wrote:
> 
> On 08/06/2017 04:39 PM, Vincent Richard wrote:
>> No, simply because there are way to many possibilities in the game, roughly 
>> (19x19)!
> 
> Can we lay this particular number to rest? Not that "possibilities in the 
> game" is very well defined (what does it even mean?) but the number of 
> permutations of 19x19 points has no meaningful connection to the game of go 
> at all, not even "roughly".
> 
> /Gunnar
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Gunnar Farnebäck]

On 08/06/2017 04:39 PM, Vincent Richard wrote:
No, simply because there are way to many possibilities in the game, 
roughly (19x19)!


Can we lay this particular number to rest? Not that "possibilities in 
the game" is very well defined (what does it even mean?) but the number 
of permutations of 19x19 points has no meaningful connection to the game 
of go at all, not even "roughly".


/Gunnar
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Álvaro Begué]

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@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.cl...@gmail.com]
> *Sent:* Sunday, August 6, 2017 2:52 PM
> *To:* Brian Sheppard <sheppar...@aol.com>
> *Cc:* computer-go <computer-go@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 <sheppar...@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.cl...@gmail.com]
> *Sent:* Sunday, August 6, 2017 1:14 PM
> *To:* Brian Sheppard <sheppar...@aol.com>; computer-go <
> 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> 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-boun...@computer-go.org] *On
> Behalf Of *Cai Gengyang
> *Sent:* Sunday, August 

Re: [Computer-go] Alphago and solving Go

[Brian Sheppard via Computer-go]

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.cl...@gmail.com] 
Sent: Sunday, August 6, 2017 2:52 PM
To: Brian Sheppard <sheppar...@aol.com>
Cc: computer-go <computer-go@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 <sheppar...@aol.com 
<mailto:sheppar...@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.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.

 

Best,

Brian

 

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?

 

Gengyang


___
Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 
http://computer-go.org/mailman/listinfo/computer-go

 

 

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Ian Davis]

Aren't you a little bit too old now to be troling this list?

On Sun, Aug 6, 2017 at 3:49 PM, Cai Gengyang  wrote:

> 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@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Brian Sheppard via Computer-go]

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 
implementation).

 

 

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

Re: [Computer-go] Alphago and solving Go

[Brian Sheppard via Computer-go]

There is a definition of “brute force” on Wikipedia. Seems to me that MCTS 
fits. Deep Blue fits.

 

From: Álvaro Begué [mailto:alvaro.be...@gmail.com] 
Sent: Sunday, August 6, 2017 2:56 PM
To: Brian Sheppard <sheppar...@aol.com>; computer-go 
<computer-go@computer-go.org>
Subject: Re: [Computer-go] Alphago and solving Go

 

It was already a stretch when people said that Deep Blue was a brute-force 
searcher. If we apply it to AlphaGo as well, the term just means nothing. 
Full-width and brute-force are most definitely not the same thing.

 

Álvaro.

 

 

 

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.

 

Best,

Brian

 

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?

 

Gengyang


___
Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 
http://computer-go.org/mailman/listinfo/computer-go

 


___
Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 
http://computer-go.org/mailman/listinfo/computer-go

 

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[David Wu]

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 implementation).


On Sun, Aug 6, 2017 at 2:20 PM, Brian Sheppard via Computer-go <
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]
> *Sent:* Sunday, August 6, 2017 1:14 PM
> *To:* Brian Sheppard <sheppar...@aol.com>; computer-go <
> 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> 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-boun...@computer-go.org] *On
> Behalf Of *Cai Gengyang
> *Sent:* Sunday, August 6, 2017 9:49 AM
> *To:* computer-go@computer-go.org
> *Subject:* [Computer-go] Alphago and solving Go
>
>
>
> Is Alphago brute force search?
>
> Is it possib

Re: [Computer-go] Alphago and solving Go

[Steven Clark]

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 <sheppar...@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.cl...@gmail.com]
> *Sent:* Sunday, August 6, 2017 1:14 PM
> *To:* Brian Sheppard <sheppar...@aol.com>; computer-go <
> 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> 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-boun...@computer-go.org] *On
> Behalf Of *Cai Gengyang
> *Sent:* Sunday, August 6, 2017 9:49 AM
> *To:* 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?
>
>
>
> Gengyang
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
>
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Brian Sheppard via Computer-go]

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] 
Sent: Sunday, August 6, 2017 1:14 PM
To: Brian Sheppard <sheppar...@aol.com>; computer-go 
<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.

 

Best,

Brian

 

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?

 

Gengyang


___
Computer-go mailing list
Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> 
http://computer-go.org/mailman/listinfo/computer-go

 

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Steven Clark]

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> 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-boun...@computer-go.org] *On
> Behalf Of *Cai Gengyang
> *Sent:* Sunday, August 6, 2017 9:49 AM
> *To:* 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?
>
>
>
> Gengyang
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Brian Sheppard via Computer-go]

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

 

Gengyang

___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[David Wu]

Actually, a better Go-God for handicap games would probably be one that
ignores score margin as long as it's behind and simply maximizes the
entropy measure for the lowest-entropy proof tree that proves that Black is
winning. (And only counts the entropy for the black moves, not the white
moves in that tree). Once ahead, of course it can do whatever it wants that
preserves the win.

On Sun, Aug 6, 2017 at 10:31 AM, David Wu  wrote:

> * A little but not really.
> * No, and as far as we can tell, never. Even 7x7 is not rigorously solved.
> * Unknown.
> * Against Go-God (plays move that maximizes score margin, breaking ties by
> some measure of the entropy needed to build the proof tree relative to a
> human-pro-level policy net), I guess upper bound at 5 stones, likely less.
> Against Go-Devil (plays moves that maximizes win chance against *you*, has
> omniscient knowledge of all your weaknesses and perfect ability to forecast
> when you would have a brainfart and blunder), unknown, probably a bit more
> than vs Go-God.
>
> On Sun, Aug 6, 2017 at 9:49 AM, Cai Gengyang 
> wrote:
>
>> 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@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Vincent Richard]

*Is Alphago **brute **force search? *

No, simply because there are way to many possibilities in the game, 
roughly (19x19)!


Alphago tries to consider the game like the human do: it evaluates the 
board from only a limited set of moves, based on its "instinct". This 
instinct is generated from deep convolutionnal neural network (see 
alphago's aper for details 
http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html?foxtrotcallback=true)


*Is it possible to solve Go for 19x19 ? *
If I remember correctly, I pretty sure a team has solved go for 5x5 
boards. I let you guess reaching 19x19 is quite impossible. It is often 
said there are ore games of go than atoms in the universe


*And what does perfect play in Go look like? *
=> Alphago is currently the best players, hence the closest to a perfect 
play. Google Deepmind has published 50 self played games alphago 
https://deepmind.com/research/alphago/alphago-vs-alphago-self-play-games/. 
Some reviews by Michael Redmond have been published on youtube: 
https://www.youtube.com/watch?v=vjsN9BRInys


*How far are current top pros from perfect play?*
=> Difficult to say, even if Alphago is strong, some pros feel it still 
does some mistakes.



Vincent Richard


Le 06-Aug-17 à 10:49 PM, Cai Gengyang a écrit :

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@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go


___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[David Wu]

* A little but not really.
* No, and as far as we can tell, never. Even 7x7 is not rigorously solved.
* Unknown.
* Against Go-God (plays move that maximizes score margin, breaking ties by
some measure of the entropy needed to build the proof tree relative to a
human-pro-level policy net), I guess upper bound at 5 stones, likely less.
Against Go-Devil (plays moves that maximizes win chance against *you*, has
omniscient knowledge of all your weaknesses and perfect ability to forecast
when you would have a brainfart and blunder), unknown, probably a bit more
than vs Go-God.

On Sun, Aug 6, 2017 at 9:49 AM, Cai Gengyang  wrote:

> 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@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Steven Clark]

No (have you read any of the papers about it?)
No
We don't know
We don't know (pros used to claim they were 2-3 stones away from God, but
AlphaGo might have encouraged them to be a bit more humble)

On Sun, Aug 6, 2017 at 9:49 AM, Cai Gengyang  wrote:

> 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@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Alphago and solving Go

[Álvaro Begué]

No, it is not possible to solve go on a 19x19 board. The closest we have is
5x5, I believe. We have a pretty good idea what optimal play looks like on
7x7. The difficulty of finding optimal play on large boards is
unfathomable.

Álvaro.


On Sun, Aug 6, 2017 at 10:06 AM Cai Gengyang  wrote:

> 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@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go