Game tree complexity - 2
The total number of possible games can be estimated from the board size in a number of ways, some more rigorous than others. The simplest, a permutation of the board size, (N)L, fails to include illegal captures and positions. Taking N as the board size (19?19=361) and L as the longest game, NL forms an upper limit. A more accurate limit is presented in the Tromp/Farneb?ck paper.
Longest game L (19?19) |
(N)L |
Lower Limit of games |
Upper Limit of games |
Notes |
1 |
1 |
361 |
361 |
White resigns after first move |
50 |
2.1?10126 |
? |
7.5?10127 |
? |
100 |
1.4?10249 |
? |
5.6?10255 |
? |
150 |
6.4?10367 |
? |
4.2?10383 |
? |
200 |
1.9?10481 |
? |
3.2?10511 |
? |
250 |
8.2?10587 |
? |
2.4?10639 |
? |
300 |
2.8?10684 |
? |
7.8?10766 |
? |
350 |
3.6?10760 |
? |
1.3?10895 |
? |
361 |
1.4?10768 |
? |
1.8?10923 |
Longest game using 181 black and 180 white stones |
400 |
n/a |
? |
1.0?101023 |
Longest professional games |
500 |
n/a |
? |
5.7?101278 |
? |
1000 |
n/a |
? |
3.2?102557 |
? |
47 million |
n/a |
? |
10108 |
361^3 moves |
1048 |
n/a |
101048 |
1010171 |
Longest game |
From this table, we can see that 10700 is an overestimate of the number of possible games that can be played in 200 moves and an underestimate of the number of games that can be played in 361 moves. It can also be noted that since there are about 31 million seconds in a year, it would take about 2? years, playing 16 hours a day at one move per second, to play 47 million moves. As to 1048, since the future age of the universe is projected to be less than 1000 trillion years and no computer is projected to compute anything close to a trillion Teraflops, any number higher than 1039 is beyond possibility of being played.