According to John Tromp et al at http://tromp.github.io/go/legal.html the number of legal 19x19 go positions is
P19 = 2081681993819799846 9947863334486277028 6522453884530548425 6394568209274196127 3801537852564845169 8519643907259916015 6281285460898883144 2712971531931755773 6620397247064840935 P19 ~ 2.081681994 * 10^170 *** The number G19 of legal games under a given go ruleset is unknown. We only know lower bounds and the following upper bound, where N = 19x19 = 361 is the number of intersections on the board: For positional superko (prohibition of recreation of the same position after completion of a move on the board), no passes, and no resignation, the number of possible games is smaller than N^P19 because P19 also restricts the maximal number of moves per game and there are at most N possible intersections per move. So approximately the upper bound for the number of legal games under the mentioned rules is G19 < 361^(2.081681994 * 10^170) Note that, changing the ko rules from positional superko to Japanese / Korean / Chinese style no-result ko rules, we get an infinite number of legal games with equivalence classes for as many different games as under positional superko. (For the sake of simplicity, let us ignore the impact of passes and resignations as technicalities for now.) *** Citation from my rec.games.go Rules FAQ: "Extremely modest estimates look like 10^N, which is based on an assumption of 10 reasonable intersections per move. A popular estimate for 19x19 go is 10^761, which must have originated from a typo and should be 10^361, if at all... These types of estimates are so popular because humans cannot even imagine the suggested number of atoms in the universe, 10^80. For comparison, 3^361 is ca. 10^172." In the AlphaGo research paper https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf the number of possible go games is estimated as approximately b^d, where b is the breadth (number of available intersections per move) and d is the depth (length of a game as its number of moves) and stated as approximately 250^150 by referencing to an earlier research article. This number is not completely meaningless: it is somehow related to empirical data. Even so, the number would be wrong because practically occurring games have been reported to last up to ca. 450 moves. Supposing 250 would be a reasonable average number of available intersections, we would get 250^450. I.e., already by correcting a minor mistake in the referenced number, we get a more meaningful number that already is astronomically larger than the stated 250^150. If we pretend the 250 in 250^450 to be reasonably correct, this more correct empirical number serves as an empirical lower bound. *** Therefore, under the made assumptions (such as permitting an empirical estimate for the lower bound), we know that the number G19 of legal go games is 250^450 < G19 < 361^(2.081681994 * 10^170). *** In various go blog messages and media articles, the same kinds of wrong (by astronomic factors too small) numbers are circulated for "the" complexity of go: 10^361, 10^170, 10^171, 250^150. The AlphaGo research paper, go players feeding journalists with information and journalists make the same mistake: they copy or cite without understanding the meaning of a particular number. The worst example has been a popular science journal's statement that ca. 10^170 would be the number of possible go games (when confusing it with the extremely smaller number of possible go positions). This leads us to types of complexities. There are the complexity of the number of legal positions, the complexity of the number of legal games (which is the actual complexity of go as a game because great applicable shorthands to a solution of perfect play are unknown) and the computational complexity of the generalised game on boards with N intersections (but go as a game is played on the 19x19 board with its fixed N = 361). -- robert jasiek _______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
