Benson's algorithm (Go)

Part of a series on
Go
Game specifics
Rules Handicaps professional Proverbs List of terms Strategy and tactics Opening (theory; strategy) Fuseki (whole-board openings) Joseki (corner-based openings) Life and death Tsumego (Go puzzles)
History and culture
History Equipment Variants Four go houses List of games
Players and organizations
Players European Female Ranks and ratings Professionals Organizations Competitions
Computers and mathematics
Go and mathematics Computer Go Go software Internet Go servers AlphaGo versus Lee Sedol
v t

In the game Go, Benson's algorithm (named after ) 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:

1. 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.
2. 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[]

• Go and mathematics – Calculations of the game complexity of go
• Computer Go – Field of artificial intelligence dedicated to creating a computer program that plays Go
• Go strategy and tactics – Techniques for winning in the game of Go
• God's algorithm – Algorithm for solving a puzzle or game in the fewest possible moves

References[]

• 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.