Adversarial reasoning: A logical approach for computer Go

Go is a game with simple rules but complex strategy requiring ability in almost all aspects of human reasoning. A good Go player must be able to hypothesize moves and analyze their consequences; to judge which areas are relevant to the analysis at hand; to learn from successes and failures; to generalize that knowledge to other “similar” situations; and to make inferences from knowledge about a position. Unlike computer chess, which has seen steady progress since Shannon's and Turing's original papers on the subject, progress on computer Go remains in relative infancy. In computer chess, minimax search with alpha-beta pruning based on a simple evaluation function can beat a beginner handily. No such simple evaluation function is known for Go. To accurately evaluate a Go position requires knowledge of the life and death status of the points on the board. Since the player with the most live points at the end of the game wins, a small mistake in this analysis can be disastrous.; In this dissertation we describe the design, performance, and underlying logic of a knowledge-based program that solves life and death problems in the game of Go. Our algorithm applies life and death theory coupled with knowledge about which moves are reasonable for each relevant goal in that theory to restrict the search space to a tractable size. Our results show that simple depth-first search armed with a goal theory and heuristic move knowledge yields very positive results on standard life and death test problems—even without sophisticated move ordering heuristics.; In addition to a description of the program and its internals we present a modal logic useful for describing strategic theories in games and use it to give a life and death theory and to formally state the rules of Go. We also give an axiomatization for this logic using the modal mu-calculus and prove some basic theorems of the system.