Re: [Computer-go] AlphaGo rollout nakade patterns?
Rollout policy is a black art. Lots of trial and error. That said, you are on
the right path if you use the published papers as the starting point for your
own experiments.
Two board representation details are very important. If your board
representation has these capabilities then you can represent an astounding
amount of Go theory. In Pebbles, the following properties are incrementally
updated as part of the make-move operation:
- the number of liberties for any string
- the index of the 3x3 neighborhood of every point.
Best,
Brian
-Original Message-
From: Roel van Engelen <ich.bun...@gmail.com>
To: computer-go <computer-go@computer-go.org>
Sent: Tue, Jan 31, 2017 12:55 pm
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
@Gian-Carlo Pascutto, thanks! but identifying the shapes is not the problem=)
@Brain Sheppard, Sorry it was not my goal to make you start guessing any
implementation details, somehow from your first explanation i got the
impression that you where familiar with it and i was wondering whether anybody
wrote something about it.
right now i am sticking to the paper as much as possible and reading, trying to
understand how others improve their rollouts. I hope that i will be able to
improve the rollouts at some point.
Roel
On 31 January 2017 at 17:21, Brian Sheppard via Computer-go
<computer-go@computer-go.org> wrote:
If a "diamond" pattern is centered on a 5x5 square, then you have 13 points.
The diagram below will give the idea.
__+__
_+++_
+
_+++_
__+__
At one bit per cell, this would be 8192 patterns, so this is why I am guessing
that this is the pattern set. (You would set one bit for each captured stone,
then look up in a table.)
I feel like I am engaging in a lot of guesswork regarding implementation
details. I want to emphasize that the implementation details are not
particularly important. The important point is that you can add this capability
("reply on the vital point after the capture of a nakade group, provided that
the opponent's surrounding stones have no additional eyes") to your rollout,
and the implementation should take less than 1% of total time. Any
implementation that achieves that goal will make a noticeable difference to
strength.
-Original Message-
From: Roel van Engelen <ich.bun...@gmail.com>
To: computer-go <computer-go@computer-go.org>
Sent: Tue, Jan 31, 2017 10:42 am
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
@Brain Sheppard
Thanks that is a really useful explanation!
the way you state: "and therefore a 8192-sized pattern set will identify all
potential nakade." seems to indicate this is a known pattern set? could i find
some more information on it somewhere? also i was unable to find Pebbles, is it
open source?
@Robert Jasiek
what definitions/papers/publications are you referring to?
m.v.g. Roel
On 24 January 2017 at 12:57, Brian Sheppard via Computer-go
<computer-go@computer-go.org> wrote:
There are two issues: one is the shape and the other is the policy that the
search should follow.
Of course the vital point is a killing move whether or not a group was just
captured. So it is possible to detect such shapes on the board and then play
the vital point.
It is an entirely different thing to say when a rollout should look for such
features. Rollouts are complicated; playing the "best" play does not always
make your search engine stronger. Of course, there is a question of the time
required for analysis. And then there is the question of "balance".
"Balance" means that the rollout should play "equally well" for both sides,
with the goal that the terminal nodes of the rollout are accurate evaluations
of the leafs of the tree. If you incorporate all moves that punish tactical
errors then sometimes you can get unbalanced results because you do not have
rules that prevent tactical errors from happening.
A common rule for nakade is to only check after a group is captured. The point
is that the vital point is otherwise not motivated by any heuristics, whereas
most other moves in capturing races are suggested by local patterns. My
understanding of Alpha Go's policy is that they were only checking for nakade
after captures.
The "center of a group of three" rule is a separate issue. My recollection is
that this pattern should be checked after every move, and that was a discovery
by the Mogo team.
Note that there are often subtle differences for your program compared to the
published papers.
Best,
Brian
-Original Message-
From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf Of
Gian-Carlo Pascutto
Sent: Tuesday, January 24, 2017 3:05 AM
To: computer-go@computer-go.org
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
On 23-01-17 20:10, Brian Sheppard via Computer
Re: [Computer-go] AlphaGo rollout nakade patterns?
On 31.01.2017 16:39, Gian-Carlo Pascutto wrote: http://senseis.xmp.net/?BasicLivingEyeShapes Warning: these do not include any living eye shapes with inside stones, nor specialities on the edge or in the corner. -- robert jasiek ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo rollout nakade patterns?
@Gian-Carlo Pascutto, thanks! but identifying the shapes is not the
problem=)
@Brain Sheppard, Sorry it was not my goal to make you start guessing any
implementation details, somehow from your first explanation i got the
impression that you where familiar with it and i was wondering whether
anybody wrote something about it.
right now i am sticking to the paper as much as possible and reading,
trying to understand how others improve their rollouts. I hope that i will
be able to improve the rollouts at some point.
Roel
On 31 January 2017 at 17:21, Brian Sheppard via Computer-go <
computer-go@computer-go.org> wrote:
> If a "diamond" pattern is centered on a 5x5 square, then you have 13
> points. The diagram below will give the idea.
>
> __+__
> _+++_
> +
> _+++_
> __+__
>
>
> At one bit per cell, this would be 8192 patterns, so this is why I am
> guessing that this is the pattern set. (You would set one bit for each
> captured stone, then look up in a table.)
>
> I feel like I am engaging in a lot of guesswork regarding implementation
> details. I want to emphasize that the implementation details are not
> particularly important. The important point is that you can add this
> capability ("reply on the vital point after the capture of a nakade group,
> provided that the opponent's surrounding stones have no additional eyes")
> to your rollout, and the implementation should take less than 1% of total
> time. Any implementation that achieves that goal will make a noticeable
> difference to strength.
>
>
> -Original Message-
> From: Roel van Engelen <ich.bun...@gmail.com>
> To: computer-go <computer-go@computer-go.org>
> Sent: Tue, Jan 31, 2017 10:42 am
> Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
>
> @Brain Sheppard
> Thanks that is a really useful explanation!
> the way you state: "and therefore a 8192-sized pattern set will identify
> all potential nakade." seems to indicate this is a known pattern set?
> could i find some more information on it somewhere? also i was unable to
> find Pebbles, is it open source?
>
> @Robert Jasiek
> what definitions/papers/publications are you referring to?
>
> m.v.g. Roel
>
> On 24 January 2017 at 12:57, Brian Sheppard via Computer-go <
> computer-go@computer-go.org> wrote:
>
>> There are two issues: one is the shape and the other is the policy that
>> the search should follow.
>>
>> Of course the vital point is a killing move whether or not a group was
>> just captured. So it is possible to detect such shapes on the board and
>> then play the vital point.
>>
>> It is an entirely different thing to say when a rollout should look for
>> such features. Rollouts are complicated; playing the "best" play does not
>> always make your search engine stronger. Of course, there is a question of
>> the time required for analysis. And then there is the question of "balance".
>>
>> "Balance" means that the rollout should play "equally well" for both
>> sides, with the goal that the terminal nodes of the rollout are accurate
>> evaluations of the leafs of the tree. If you incorporate all moves that
>> punish tactical errors then sometimes you can get unbalanced results
>> because you do not have rules that prevent tactical errors from happening.
>>
>> A common rule for nakade is to only check after a group is captured. The
>> point is that the vital point is otherwise not motivated by any heuristics,
>> whereas most other moves in capturing races are suggested by local
>> patterns. My understanding of Alpha Go's policy is that they were only
>> checking for nakade after captures.
>>
>> The "center of a group of three" rule is a separate issue. My
>> recollection is that this pattern should be checked after every move, and
>> that was a discovery by the Mogo team.
>>
>> Note that there are often subtle differences for your program compared to
>> the published papers.
>>
>> Best,
>> Brian
>>
>> -Original Message-
>> From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf
>> Of Gian-Carlo Pascutto
>> Sent: Tuesday, January 24, 2017 3:05 AM
>> To: computer-go@computer-go.org
>> Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
>>
>> On 23-01-17 20:10, Brian Sheppard via Computer-go wrote:
>> > only captures of up to 9 stones can be nakade.
>>
>> I don't really understand this.
>>
>> http://senseis.xmp.net/?StraightThree
>>
>> Both constructing this shape and playing the vital point are not
>
Re: [Computer-go] AlphaGo rollout nakade patterns?
If a "diamond" pattern is centered on a 5x5 square, then you have 13 points.
The diagram below will give the idea.
__+__
_+++_
+
_+++_
__+__
At one bit per cell, this would be 8192 patterns, so this is why I am guessing
that this is the pattern set. (You would set one bit for each captured stone,
then look up in a table.)
I feel like I am engaging in a lot of guesswork regarding implementation
details. I want to emphasize that the implementation details are not
particularly important. The important point is that you can add this capability
("reply on the vital point after the capture of a nakade group, provided that
the opponent's surrounding stones have no additional eyes") to your rollout,
and the implementation should take less than 1% of total time. Any
implementation that achieves that goal will make a noticeable difference to
strength.
-Original Message-
From: Roel van Engelen <ich.bun...@gmail.com>
To: computer-go <computer-go@computer-go.org>
Sent: Tue, Jan 31, 2017 10:42 am
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
@Brain Sheppard
Thanks that is a really useful explanation!
the way you state: "and therefore a 8192-sized pattern set will identify all
potential nakade." seems to indicate this is a known pattern set? could i find
some more information on it somewhere? also i was unable to find Pebbles, is it
open source?
@Robert Jasiek
what definitions/papers/publications are you referring to?
m.v.g. Roel
On 24 January 2017 at 12:57, Brian Sheppard via Computer-go
<computer-go@computer-go.org> wrote:
There are two issues: one is the shape and the other is the policy that the
search should follow.
Of course the vital point is a killing move whether or not a group was just
captured. So it is possible to detect such shapes on the board and then play
the vital point.
It is an entirely different thing to say when a rollout should look for such
features. Rollouts are complicated; playing the "best" play does not always
make your search engine stronger. Of course, there is a question of the time
required for analysis. And then there is the question of "balance".
"Balance" means that the rollout should play "equally well" for both sides,
with the goal that the terminal nodes of the rollout are accurate evaluations
of the leafs of the tree. If you incorporate all moves that punish tactical
errors then sometimes you can get unbalanced results because you do not have
rules that prevent tactical errors from happening.
A common rule for nakade is to only check after a group is captured. The point
is that the vital point is otherwise not motivated by any heuristics, whereas
most other moves in capturing races are suggested by local patterns. My
understanding of Alpha Go's policy is that they were only checking for nakade
after captures.
The "center of a group of three" rule is a separate issue. My recollection is
that this pattern should be checked after every move, and that was a discovery
by the Mogo team.
Note that there are often subtle differences for your program compared to the
published papers.
Best,
Brian
-Original Message-
From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf Of
Gian-Carlo Pascutto
Sent: Tuesday, January 24, 2017 3:05 AM
To: computer-go@computer-go.org
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?
On 23-01-17 20:10, Brian Sheppard via Computer-go wrote:
> only captures of up to 9 stones can be nakade.
I don't really understand this.
http://senseis.xmp.net/?StraightThree
Both constructing this shape and playing the vital point are not captures. How
can you detect the nakade (and play at a in time) if you only check captures?
--
GCP
___
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
listComputer-go@computer-go.orghttp://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 rollout nakade patterns?
On 31-01-17 16:32, Roel van Engelen wrote: > @Brain Sheppard > Thanks that is a really useful explanation! > the way you state: "and therefore a 8192-sized pattern set will identify > all potential nakade." seems to indicate this is a known pattern set? > could i find some more information on it somewhere? http://senseis.xmp.net/?BasicLivingEyeShapes -- GCP ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo rollout nakade patterns?
@Brain Sheppard Thanks that is a really useful explanation! the way you state: "and therefore a 8192-sized pattern set will identify all potential nakade." seems to indicate this is a known pattern set? could i find some more information on it somewhere? also i was unable to find Pebbles, is it open source? @Robert Jasiek what definitions/papers/publications are you referring to? m.v.g. Roel On 24 January 2017 at 12:57, Brian Sheppard via Computer-go < computer-go@computer-go.org> wrote: > There are two issues: one is the shape and the other is the policy that > the search should follow. > > Of course the vital point is a killing move whether or not a group was > just captured. So it is possible to detect such shapes on the board and > then play the vital point. > > It is an entirely different thing to say when a rollout should look for > such features. Rollouts are complicated; playing the "best" play does not > always make your search engine stronger. Of course, there is a question of > the time required for analysis. And then there is the question of "balance". > > "Balance" means that the rollout should play "equally well" for both > sides, with the goal that the terminal nodes of the rollout are accurate > evaluations of the leafs of the tree. If you incorporate all moves that > punish tactical errors then sometimes you can get unbalanced results > because you do not have rules that prevent tactical errors from happening. > > A common rule for nakade is to only check after a group is captured. The > point is that the vital point is otherwise not motivated by any heuristics, > whereas most other moves in capturing races are suggested by local > patterns. My understanding of Alpha Go's policy is that they were only > checking for nakade after captures. > > The "center of a group of three" rule is a separate issue. My recollection > is that this pattern should be checked after every move, and that was a > discovery by the Mogo team. > > Note that there are often subtle differences for your program compared to > the published papers. > > Best, > Brian > > -Original Message- > From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf > Of Gian-Carlo Pascutto > Sent: Tuesday, January 24, 2017 3:05 AM > To: computer-go@computer-go.org > Subject: Re: [Computer-go] AlphaGo rollout nakade patterns? > > On 23-01-17 20:10, Brian Sheppard via Computer-go wrote: > > only captures of up to 9 stones can be nakade. > > I don't really understand this. > > http://senseis.xmp.net/?StraightThree > > Both constructing this shape and playing the vital point are not captures. > How can you detect the nakade (and play at a in time) if you only check > captures? > > -- > GCP > ___ > 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 rollout nakade patterns?
Finally, somebody asks about the nature of those 8192 patterns.(pardon the Nature pun) ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo rollout nakade patterns?
There are two issues: one is the shape and the other is the policy that the search should follow. Of course the vital point is a killing move whether or not a group was just captured. So it is possible to detect such shapes on the board and then play the vital point. It is an entirely different thing to say when a rollout should look for such features. Rollouts are complicated; playing the "best" play does not always make your search engine stronger. Of course, there is a question of the time required for analysis. And then there is the question of "balance". "Balance" means that the rollout should play "equally well" for both sides, with the goal that the terminal nodes of the rollout are accurate evaluations of the leafs of the tree. If you incorporate all moves that punish tactical errors then sometimes you can get unbalanced results because you do not have rules that prevent tactical errors from happening. A common rule for nakade is to only check after a group is captured. The point is that the vital point is otherwise not motivated by any heuristics, whereas most other moves in capturing races are suggested by local patterns. My understanding of Alpha Go's policy is that they were only checking for nakade after captures. The "center of a group of three" rule is a separate issue. My recollection is that this pattern should be checked after every move, and that was a discovery by the Mogo team. Note that there are often subtle differences for your program compared to the published papers. Best, Brian -Original Message- From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf Of Gian-Carlo Pascutto Sent: Tuesday, January 24, 2017 3:05 AM To: computer-go@computer-go.org Subject: Re: [Computer-go] AlphaGo rollout nakade patterns? On 23-01-17 20:10, Brian Sheppard via Computer-go wrote: > only captures of up to 9 stones can be nakade. I don't really understand this. http://senseis.xmp.net/?StraightThree Both constructing this shape and playing the vital point are not captures. How can you detect the nakade (and play at a in time) if you only check captures? -- GCP ___ 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 rollout nakade patterns?
On 23-01-17 20:10, Brian Sheppard via Computer-go wrote: > only captures of up to 9 stones can be nakade. I don't really understand this. http://senseis.xmp.net/?StraightThree Both constructing this shape and playing the vital point are not captures. How can you detect the nakade (and play at a in time) if you only check captures? -- GCP ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo rollout nakade patterns?
On 23.01.2017 19:00, terry mcintyre via Computer-go wrote: nakade involves creating a shape (such as three in a row or a bulky five) such that, if captured, it would only form one eye, given the proper placement. Nakade has been defined (e.g., several times by me) reasonably well, but for computer purposes some sort of simplifying (implicit) definition is often necessary according to a study purpose. (Your attempt is too naive, worse than ca. 68 years ago. See my texts for progress or else be naive with determination, i.e., keep things simple strictly without any "such that", "would", "eye", "proper", "involves".) -- robert jasiek ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo rollout nakade patterns?
A capturing move has a potential nakade if the string that was removed is among a limited set of possibilities. Probably Alpha Go has a 13-point bounding region (e.g., the 13-point star) that it uses as a positional index, and therefore a 8192-sized pattern set will identify all potential nakade. It is also easy and inexpensive to identify nakade by if/the/else rules. Very few moves in a Go game are captures, and only captures of up to 9 stones can be nakade. The captured stones must also fit in a 3x3 bounding box, so code can rapidly eliminate non-nakade situations. The point is that using much less than 1% of your CPU time, you can identify potential nakade moves. And since you reach this stage very rarely, you can invest a lot of time trying to do precise analysis. In Pebbles, I concluded that it was worthwhile to also test that the surrounding strings likely did not have another potential eye. That is a pretty expensive calculation, but the code path was executed only when it was critical to success. Nakade are enormously valuable because they are cheap to calculate and a playout would otherwise have close to 0% chance of following the right path. -Original Message- From: terry mcintyre via Computer-go <computer-go@computer-go.org> To: computer-go <computer-go@computer-go.org> Sent: Mon, Jan 23, 2017 1:14 pm Subject: Re: [Computer-go] AlphaGo rollout nakade patterns? I speculate: nakade involves creating a shape (such as three in a row or a bulky five) such that, if captured, it would only form one eye, given the proper placement. I can imagine a set of patterns which enumerate the possibilities. Some examples exist, however, which are quite complex. Sent from Yahoo Mail for iPad On Monday, January 23, 2017, 11:45 AM, Roel van Engelen <ich.bun...@gmail.com> wrote: I am trying to re-create the fast rollout policy as described by deepMind but got stuck on the nakade patterns: "Nakade, # of patterns 8192: Move matches a nakade pattern at captured stone" the "at captured stone" confuses me, my first thought is: "this is only computed if stones have been captured recently" but i don't think that is correct. how should i read it? since they say "# of patterns 8192" i imagine they found some way to hash them just like the 3x3 and 12point diamond shapes but so far i have not found a way to do so. I found that other engines use heuristics to find nakade patterns so my question is does AlphaGo use patterns and does somebody know how this works? Thanks! Roel ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___Computer-go mailing listComputer-go@computer-go.orghttp://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 rollout nakade patterns?
blockquote, div.yahoo_quoted { margin-left: 0 !important; border-left:1px
#715FFA solid !important; padding-left:1ex !important; background-color:white
!important; } I speculate: nakade involves creating a shape (such as three in a
row or a bulky five) such that, if captured, it would only form one eye, given
the proper placement. I can imagine a set of patterns which enumerate the
possibilities. Some examples exist, however, which are quite complex.
Sent from Yahoo Mail for iPad
On Monday, January 23, 2017, 11:45 AM, Roel van Engelen
wrote:
I am trying to re-create the fast rollout policy as described by deepMind but
got stuck on the nakade patterns:
"Nakade, # of patterns 8192: Move matches a nakade pattern at captured stone"
the "at captured stone" confuses me, my first thought is: "this is only
computed if stones have been captured recently" but i don't think that is
correct. how should i read it?
since they say "# of patterns 8192" i imagine they found some way to hash them
just like the 3x3 and 12point diamond shapes but so fari have not found a way
to do so. I found that other engines use heuristics to find nakade patterns so
my question is does AlphaGo use patterns and does somebody know how this works?
Thanks!
Roel___
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] AlphaGo rollout nakade patterns?
I am trying to re-create the fast rollout policy as described by deepMind but got stuck on the nakade patterns: "Nakade, # of patterns 8192: Move matches a nakade pattern at captured stone" the "at captured stone" confuses me, my first thought is: "this is only computed if stones have been captured recently" but i don't think that is correct. how should i read it? since they say "# of patterns 8192" i imagine they found some way to hash them just like the 3x3 and 12point diamond shapes but so far i have not found a way to do so. I found that other engines use heuristics to find nakade patterns so my question is does AlphaGo use patterns and does somebody know how this works? Thanks! Roel ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
