OFFSET
1,2
COMMENTS
John Tromp wrote a small C program to compute the number for boards up to size 4 X 5, given in the rec.games.go posting below. Gunnar Farnebaeck (gunnar(AT)lysator.liu.se) wrote a pike script to compute the number by dynamic programming, which handles sizes up to 12 X 12 (available upon request).
LINKS
John Tromp, Table of n, a(n) for n = 1..19
British Go Association, Go
Sandy Harris, Number of Possible Outcomes of a Game
John Tromp, Complexity of Chess and Go
John Tromp, Number of legal Go positions
John Tromp and Gunnar Farnebäck, Combinatorics of Go (2016)
FORMULA
3^(n*n) is a trivial upper bound.
Tromp & Farnebäck prove that a(n) = (1 + o(1)) * L^(n^2), and conjecture that a(n) ~ A * B^(2n) * L^(n^2) * (1 + O(n*p^n)) for some constants A, B, L, and p < 1. - Charles R Greathouse IV, Feb 08 2016
EXAMPLE
The illegal 2 X 2 positions are the 2^4 with no empty points and the 4*2 having a stone adjacent to 2 opponent stones that share a liberty. That leaves 3^4-16-8 = 57 legal positions.
CROSSREFS
KEYWORD
nonn
AUTHOR
Jan Kristian Haugland, Jun 09 2004
EXTENSIONS
More terms from John Tromp, Jan 27 2005
a(10)-a(13) from John Tromp, Jun 23 2005
a(14)-a(15) from John Tromp, Sep 01 2005
a(16) from John Tromp, Oct 06 2005
Michal Koucky should be credited for carrying most of the computational load for computing the n=14, 15 and 16 results with his file-based implementation.
a(17)-a(18) from John Tromp, Mar 08 2015
a(19) from John Tromp, Jan 21 2016
STATUS
approved