Computer Science/Discrete Mathematics Seminar I

Decomposition and modularity are fundamental issues in many fields, including mathematics, biology, engineering, and management. How can large systems be broken into subsystems which interact enough to meet the overall system goals, but not so much as to inhibit the efficient specialized local functions? This talk addresses these issues in the context of certain popular board games, where we have found just enough structure to get some interesting quantitive results. In order to quantify the sizes of various moves in the game of Go, in the mid 1990s I devised a new variation of the game, now called "Coupon Go". This game compels the players to make quantitative decisions. The initially empty Go board is accompanied by a stack of coupons. The values of these coupons are uniformly spaced, and they are sorted with the most valuable coupons first. One set of values which has been used on several occasions consists of 40 coupons with values 20, 19.5, 19, 18.5, etc. White also receives an initial komi which typically is approximately half of the value of the top coupon. At each turn, a player may choose to take the top coupon, which is then added to his score. OR he may instead elect to place a stone onto the board. As usual, the game ends when all coupons are taken and neither player wants to play any more stones onto the board. Then both players pass and the game ends. Each player's final score is equal to his score on the board, plus the total of all of the coupons he has taken, plus the initial komi. At every move in a coupon game, each player must decide whether he prefers to play on the board or to take the top coupon. In 1998-2000, we sponsored several full-day coupon games between two famous 9-dan professionals, Jujo Jiang and Naiwei Rui. The records of these games provide documentation of expert opinions bounding the sizes of the moves they played. For positions early in the game, such expert opinions and judgments are likely to be as near to the truth as anyone can now learn. However, in the late-stage endgames, we have devised a collection of techniques and theorems that enable us to do rigorous and mathematically precise calculations. In some cases, these results provide new information not previously known to the experts. The same idea has also shed new light on certain other games, most notably Amazons. This talk will review some of the results of this research in combinatorial game theory.