Experiments in Computer Go Endgames
Martin Müller, Ralph Gasser · 1997
Recently, the mathematical theory of games has been applied to late-stage Go endgames [Berlekamp and Wolfe 1994; Wolfe 1991]. Based upon this theory, we developed a tool to solve local Go endgames. We verified all exact game values in [Wolfe 1991] and analyzed some more complex positions. We extended our method to calculate bounds for positions where optimal play depends on Ko. Our program Explorer uses this tool to play full board endgames. It plays a nontrivial class of endgame positions perfectly. In a last section we discuss heuristic play for a wider range of endgames. 1. Go Endgames Towards the end of a Go game, the board position usually breaks down into several local fights that can be analyzed individually (Figure 1). To find an optimal move globally, one needs to consider relations between these local subgames: There is a conflict between maximizing the local score and gaining the initiative to play in another part of the board. These relationships can be very complex, even surpassing the abilities of professional Go players. Exhaustive analysis of full board endgames is only feasible for the most trivial problems, because of exponential explosion of the search. The mathematical theory of games [Conway 1976; Berlekamp et al. 1982] can handle such complexity by divide and conquer: It defines an operation called a sum of games that builds up a game from its subgames (if no Ko fights exist, as explained below). This theory gives us algorithms to prune bad moves, compare the value of games and find an optimal move without exhaustive search on the full board.