

A094777


Number of legal positions in Go played on an n X n grid (each group must have at least one liberty).


7



1, 57, 12675, 24318165, 414295148741, 62567386502084877, 83677847847984287628595, 990966953618170260281935463385, 103919148791293834318983090438798793469, 96498428501909654589630887978835098088148177857, 793474866816582266820936671790189132321673383112185151899, 57774258489513238998237970307483999327287210756991189655942651331169, 37249792307686396442294904767024517674249157948208717533254799550970595875237705, 212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^4168 = 57 legal positions.


CROSSREFS

Sequence in context: A219077 A091749 A218425 * A218662 A093257 A210148
Adjacent sequences: A094774 A094775 A094776 * A094778 A094779 A094780


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 filebased implementation.
a(17)a(18) from John Tromp, Mar 08 2015
a(19) from John Tromp, Jan 21 2016


STATUS

approved



