Benson's algorithm (Go)


In the game Go, Benson's algorithm 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.

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.