## FANDOM

10,841 Pages

Go is a popular board game whose analysis leads to some large numbers.

In this game two players alternate to put white and black stones on the crossings on a board containing $$19$$ vertical and $$19$$ horizontal lines (so that there are $$19^2=361$$ possible positions) with a goal of surrounding more territory than the opponent. Variants of the game exist in which the number of lines, and hence of possible positions, varies.

## Number of legal positionsEdit

The number of possible ways to put stones on some (but possibly not all) crossings on the board is equal to $$3^{361}$$ (about $$1.74\cdot 10^{172}$$), but due to capture rules in the game not all of them can arise during a game of Go. The exact number of legal positions in Go took 10 years to find precisely and on January 20, 2016, it was determined to be equal to 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935, or roughly $$2.08\cdot 10^{170}$$.[1]

This can be generalized to a function $$L(n)$$, which is equal to the number of possible legal positions on a board consisting of crossings of $$n$$ vertical and $$n$$ horizontal lines. Values of $$L(n)$$ have been determined up to $$n=19$$.

This can be generalized further to a two-variable function $$L(m,n)$$, the number of legal positions when there are $$m$$ vertical and $$n$$ horizontal lines. For every fixed $$m$$ there exists a linear recurrence for the function $$L_m(n)=L(m,n)$$, which helps to find the values of a function for small $$m$$ and arbitrary $$n$$. However, the complexity of the recurrence formulas rapidly increases and they become useless for large $$m$$.

The known values of $$L(m,n)$$ suggest an approximation

$L(m,n) \approx ab^{m+n}c^{mn}$

where $$a = 0.85064,\,b = 0.96554,\,c = 2.97573$$.

## Number of possible gamesEdit

Another function to be considered is the number of possible games to be played on a board of a given size. It was calculated that for a board with $$4$$ crossings arranged in a square the number of possible games is precisely $$386356909593$$. The number of possible games on a board of standard size has not been determined, but it was shown to be equal to at least googolplex,[1] and can easily be shown to be much less than $$L! \approx 10^{3.54\times10^{172}}$$, where $$L$$ is the number of legal moves (defined above).

1. 1.0 1.1 http://tromp.github.io/go/legal19.html