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.

Google Advertise

Who's Online

We have 1239 guests online