Martin Müller
Informatik, ETH Zürich
mueller@inf.ethz.ch
Determining whether stones are safe from capture, and whether territories are protected against an invasion, are two fundamental tasks in Go evaluation.
In general, safety cannot be proven by static evaluation; it must be decided by searching. However, good static evaluation functions can greatly speed up a search by making early evaluation possible. In addition, static analysis can decompose a search problem into independent subtasks, which yields an exponential speedup.
The new algorithms for proving safety developed in this paper are closely related to standard Life&Death search methods. However, there are two important differences. First, searches are local: they are restricted to a single enclosed region. Second, the search space for proving the safety of large territories is potentially huge. Therefore powerful static evaluation and search decomposition becomes very important.