Sums of hot and tepid combinatorial games
Kuo-Yuan Kao · 1997
In this dissertation, combinatorial games are the main objects of study. Games can be classified into hot, cold and tepid games according to their temperatures. Roughly speeking, the temperature of a game is a measure of the size of the next move in the game. The information about the temperatures of the games in a sum can be used to find out good moves in the sum. In the first part of this dissertation, we study hot games. A new method for calculating the mean/temperature of a game is presented. This new method improves the classical approach by ignoring unnecessary searches in the game tree. Two new game tree pruning techniques called M-cut and T-cut, analog to alpha-beta cut, are introduced. In the second part, we study tepid games. Tepid games are those games where the players fight for the last move, instead of points. The values of these games are called infinitesimals. We introduce several new classes of infinitesimals which are completely solved. As byproducts of the result, there are five games introduced in this disseration. Four of them are completely solved, the only unsolved one is an NP-hard game. The application of the result to computer Go is also discussed.