Department of Mathematics, UCI

The game of Go invites analysis. The rules seem few and simple, suggesting that the game may have helpful theorems. Tens of millions of people play and skill has developed over centuries to extraordinary levels. Thus, computer analysis can be tested against analysis by highly skilled human players.

We study M x N boards, rather than the usual 19 x 19. We begin with the computer-assisted complete tree calculation for the tiniest boards. The analysis extends to slightly larger boards with the aid of various lemmas and concepts of connectedness and symmetry. The usual rules are incomplete. Though difficulties rarely arise from this on a 19 x 19 board, they are frequent on small boards. We therefore extend and complete the rules in a way which, we believe, preserves their spirit.

We give bounds on the value of the game and on its combinatorial magnitude. We discuss a heuristic strategy based on potential. The flow chart for our computer program is included and may be easily modified for use in human-machine symbiosis. We offer conjectures about the optimal strategies and the value of the game, for somewhat larger boards than those solved.

We suggest small-board Go as a progressive testing ground, as M and N increase, for: (1) techniques to yield the complete solution, (2) the power of learning programs and of (positional) evaluation functions, (3) human-machine symbiosis, and (4) human-machine confrontation.