Benson's algorithm (Go)
Not to be confused with Benson's algorithm, a method for solving linear multi-objective optimization problems.
| Part of a series of articles on |
| Go |
|---|
 |
| Game specifics |
|
| History and culture |
| Players and organizations |
| Computers and mathematics |
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]
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]
See also
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 - version of the 5/13/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.