One possible configuration of a Go board.

Go (not to be confused with the Sino-Japanese numeral for 5) 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 208,168,199,381,979,984,699,478,633,344,862,770,286,522,453,884,530,548,425,639,456,820,927,419,612,738,015,378,525,648,451,698,519,643,907,259,916,015,628,128,546,089,888,314,427,129,715,319,317,557,736,620,397,247,064,840,935, 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 \(386,356,909,593\). 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