Generalized Thermography: Algorithms, Implementation, and Application to Go Endgames

Martin Müller, Elwyn Berlekamp and Bill Spight
TR 96-030, ICSI, Berkeley
October 1996

Thermography is a powerful method for analyzing combinatorial games. It has been extended to games that contain loops in their game graph by Berlekamp. We survey the main ideas of this method and discuss how it applies to Go endgames. After a brief review of the methodology, we develop an algorithm for generalized thermography and describe its implementation.

To illustrate the power and scope of the resulting program, we give an extensive catalog of examples of Ko positions and their thermographs.

We introduce a new method related to thermography for analyzing ko in the context of a specific ko threat situation. We comment on some well-known Go techniques, terminology, and ``exotic'' Go positions from a thermography point of view. Our analysis shows that a framework based on generalized thermography can be useful for the opening and midgame as well. We suggest that such a framework will serve as the basis for future strong Go programs.