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