Benson's algorithm (Go)
In the game Go, Benson's algorithm (named after David B. Benson) can be used to determine the stones which are safe from capture no matter how many turns in a row the opposing player gets, i.e. unconditionally alive.[1]
| Part of a series on |
| Go |
|---|
 |
| Game specifics |
|
| History and culture |
| Players and organizations |
| Computers and mathematics |
Algorithm
Without loss of generality, we describe Benson's algorithm for the Black player.
Let X be the set of all Black chains and R be the set of all Black-enclosed regions of X. Then Benson's algorithm requires iteratively applying the following two steps until neither is able to remove any more chains or regions:
- Remove from X all Black chains with less than two vital Black-enclosed regions in R, where a Black-enclosed region is vital to a Black chain in X if all its empty intersections are also liberties of the chain.
- Remove from R all Black-enclosed regions with a surrounding stone in a chain not in X.
The final set X is the set of all unconditionally alive Black chains.[2]
gollark: However, this would require more complex code and possibly make rendering generally slower.
gollark: So I would probably need to run through the AST and find all the wikilinks, then execute one query to fetch *all* the relevant information, which I think should be faster.
gollark: And pages may contain MANY links.
gollark: Well, yes, they complete in probably a millisecond at most, but the aim is for all sane operations to take under 40ms.
gollark: However, these are not *that* fast and on larger high-link-density pages could increase rendering time substantially, and good rendering performance important?!
See also
- Computer Go – Field of artificial intelligence dedicated to creating a computer program that plays Go
- Go strategy and tactics
References
- Tapani Raiko (May 5, 2005). "Benson's algorithm". Retrieved March 21, 2012.
- "Sensei's Library: Benson's Definition of Unconditional Life". Retrieved March 21, 2012.
- David B. Benson (1976). "Life in the game of Go" (pdf). Information Sciences. Elsevier. 10 (2): 17–29. doi:10.1016/s0020-0255(76)90554-5. Retrieved March 21, 2012.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.