Go and mathematics
As computers become faster and more powerful their programmers continue to search for new challenges beyond computing pi or even playing chess. While most games can be won by a computer opponent, the complexity of go has proven to be beyond the reach of artificial intelligence and is seen as a new challenge. This is mainly because of the large number of possible plays at each move and the difficulty of evaluating them, which is addressed in the article computer go. This article addresses the mathematics of the complexity of go.
Allis notes that typical games between experts last about 150 moves, with an average of about 250 choices per move, suggesting a game-tree complexity of 10360. For the number of theoretically possible games, including ones impossible to play in practice, see John Tromp and Gunnar Farnebäck (2007). "Combinatorics of Go". This paper gives lower and upper bounds of 101048 and 1010171 respectively. It also shows that on a 19×19 board, about 1.196% of board setups are legal positions, which makes 3361×0.01196 = 2.082x10170 positions in total.
Sources
Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880.