Legal positions
Since each location on the board can be either empty, black, or white, there are a total of 3N possible board positions on a board with N intersections. Tromp and Farneb?ck show that on a 19?19 board, about 1.2% of board positions are legal (no stones without liberties exist on the board), which makes for 3361?0.012... = 2.1 ?10170 legal positions "of which we can expect all digits to be correct" (i.e. because the convergence is so fast). As the board gets larger, the percentage of the positions that is legal decreases. Go (with Japanese ko rules) is a two player un-bounded EXPTIME-complete game. Rule variations that places a polynomial bound on the length of the game produces a PSPACE-complete game. The complexity of Go with superko rules remains an open question.
Game size |
Board size N |
3N |
Percent legal |
Maximum legal game positions |
2?2 |
4 |
81 |
70% |
57 |
3?3 |
9 |
19,683 |
64% |
12,675 |
4?4 |
16 |
43,046,721 |
56% |
24,318,165 |
5?5 |
25 |
8.47?1011 |
49% |
4.1?1011 |
9?9 |
81 |
4.4?1038 |
23.4% |
1.039?1038 |
13?13 |
169 |
4.3?1080 |
8.66% |
3.72497923?1079 |
19?19 |
361 |
1.74?10172 |
1.196% |
2.08168199382?10170 |
21?21 |
441 |
2.57?10210 |
? |
? |
?