Counting Legal Positions in Go

The computation uses dynamic programming to count the number of paths through a graph consisting of 18^2=324 layers with up to 81 billion nodes each. Each node corresponds to a set of partial board (e.g. the top 7 rows plus 6 points on the 8th row) positions that are equivalent in their set of valid completions. Our paper explains the algorithm in detail, and also explains how the resulting exact counts allow derivation of the approximation formula

L(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n} * 2.97573419204335724938^{m*n}

which gives us the approximate number of legal positions on a standard board size

L(19,19) ~ 2.08168199381982*10^170

via Counting Legal Positions in Go.

Thanks to the Chinese Remainder Theorem, the work of computing L(19,19) can be split up into 9 jobs that each compute 64 bits of the 566-bit result. Allowing for some redundancy, we need from 10 to 13 servers, each with at least 8 cores, 512GB RAM, and ample disk space (10-15TB), running for about 5-9 months.