Life-and-Death Problem Solver in Go

Abstract

The life-and-death problem in Go is a basic and essential problem to be overcome in implementing a computer Go program. This paper proposes a new heuristic searching model which can reduce the branching factor in a game tree. For constructing the first level of a game tree, we implement pattern clustering and eye shape analysis to get the set of the first moves, thereby reducing the branching factor of the game tree. The empirical result for game tree searching with these methods is promising. We also suggest several problems to address for making game tree searching more robust, such as: coping with situations where the number of legal moves in the surrounded group is more than 8, creating an accurate heuristic evaluation function, and dealing with ko fighting.