Computer-assisted thermographic analysis of go endgames
William Fraser, Elwyn R. Berlekamp · 2002
In combinatorial game theory, the questions “Who is ahead, and by how much?” and “How much is the next move worth?” are answered precisely by value and incentive, represented as nested sets which can be quite complicated. Thermography replaces them with the numeric approximations mean and temperature, which retain sufficient information to find correct play in many situations. Environmental go, in which players have the choice of taking a coupon instead of making moves on the board, is described. Classical thermography, which is defined for finite, loop-free games, is not sufficient for handling go endgames, which may depend on kos. Extended thermographs, which are defined by the left score and right score of environmental go games, are shown to be equal to classical thermographs while covering a larger set of go positions. Several theorems, some original, are stated and proven concerning extended thermographs. Several models of kothreat environments are defined and discussed, including komaster, a model for a player who has “just a few” more kothreats than her opponent; komonster, a model for a player who has as strong a position as is possible with respect to kothreats; explicit kothreat environment, in which all kothreats are given explicitly in the game and neutral kothreat environment, in which each player is given an identical large set of kothreats spanning a wide range of temperatures. While thermography is a powerful tool, the bookkeeping required to compute correct thermographs for complex go positions can be overwhelming (several classes of go positions have been shown to be NP-complete). This thesis describes two powerful computer programs that I have written which embody some new algorithms for computing means, temperatures, and thermographs of go endgames. These programs are called BruteForce and GoSolver. BruteForce, as the name suggests, exhaustively searches an endgame region to calculate thermographs for every position. This is challenging because conventional recursive definitions of extended themographs could not accomodate the loopiness of many go game graphs. An alpha-beta like search is used to prune the analysis. The output of BruteForce is thermographs stored in a compact form and the program is capable of solving problems which are too large to fit into RAM. BruteForce uses this information to find means, temperatures, and orthodox lines of play. GoSolver, on the other hand restricts its attention to human-entered lines of play. By eliminating sub-optimal plays (especially sub-optimal loops), exponential explosion is reduced, allowing larger endgame regions to be analyzed. Additionally, since the human can make judgments about the value of moves which escape into enemy or neutral territory, positions with vague boundaries can be evaluated. In a typical go endgame, the board breaks into a number of small independent (or almost independent) subgames. GoSolver allows the user to separate the board into regions and examine them one at a time, in order to facilitate the analysis of whole board go positions. My entire thesis, as well as the software and some example files are available at http: //www.math.berkeley.edu/∼bfraser