What this document is
This paper by computer scientist John Tromp and Gunnar Farnebäck works through the mathematics of how many legal positions and games are possible on a Go board of a given size, a question that has interested both Go players and computer scientists because of the game's enormous branching complexity compared with games like chess.
The authors derive a recurrence relation for the number of legal positions on an m-by-n board and describe a dynamic programming algorithm for computing it, which they use to work out the exact count for the standard 19-by-19 board, a number famous in Go circles for its sheer size. They also establish a growth constant, roughly 2.9757, that describes how the count of legal positions grows as the board expands.
A later revision described reducing the hardest part of the 19-by-19 calculation to a matrix operation involving a matrix with 363 billion rows and columns, illustrating just how far outside ordinary intuition the combinatorics of a 19-by-19 Go board really sit. The paper builds on Tromp's long-running public project counting and verifying figures related to Go's legal positions and game count.
Where to find it
Available from John Tromp.