[Computer-go] AlphaGo rollout nakade patterns?

[Roel van Engelen]

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

[terry mcintyre via Computer-go]

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

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

[Brian Sheppard via Computer-go]

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.

[Robert Jasiek]

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

[Gian-Carlo Pascutto]

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

[Brian Sheppard via Computer-go]

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-...@computer-go.org] On Behalf Of Gian-Carlo Pascutto
Sent: Tuesday, January 24, 2017 3:05 AM
To: compu...@computer-go.org
Subject: Re: [Computer-go] AlphaGo rollout nakade patterns?

[Stefan Kaitschick]

Finally, somebody asks about the nature of those 8192 patterns.(pardon the Nature pun)

[Roel van Engelen]

@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

[Gian-Carlo Pascutto]

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

[Brian Sheppard via Computer-go]

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.

 

[Roel van Engelen]

@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

[Robert Jasiek]

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

[Brian Sheppard via Computer-go]

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.