Life In 19x19

I know that the total number of moves in a 19x19 game of go is calculated to be 10x10 into 170th power. But can anyone tell me what this number is for 9x9 go games? Thanks.

Alberich wrote:I know that the total number of moves in a 19x19 game of go is calculated to be 10x10 into 170th power. But can anyone tell me what this number is for 9x9 go games? Thanks.

If we are just plonking stones on a board with no regard for captures, the the total number of possible sequences of doing so is 81 possibilities for the first move, then 80 possible places to play the second move, the 79 for the third, etc, or 81! That is about 5.8 x 10^120.

On the first move, due to rotation and flipping, there are really only 15 unique moves, not 81, so the refined guess is about 10^120.

Then there are captures, and that opens up a whole bunch of new possibilities. I have no idea how to calculate that,

Search for John Tromp's research, else read the rec.games.go Rules FAQ, section 5.12:

http://home.snafu.de/jasiek/rulesfaq.txt

There is a good article about this on wikipedia:

http://en.wikipedia.org/wiki/Go_and_mathematics

For even more details, you can follow the links to the referenced sources there.

I looked through the wikipedia article and it says "3x10x38th power". I take it to mean it's 30 plus 38 zeroes following. So a 9x9 board game of go has less possible combinations than chess, which I think is 10x120th power. A 13x13 board of go is 10x89th power while the standard 19x19 board version is 10x170th power. That would be 10 followed by 170 zeroes. So 19x19 go beats western chess by 50 zeroes. I love the fact that computers won't be able to solve 19x19 go.

Numbers depend on the used ruleset.

Alberich wrote:I looked through the wikipedia article and it says "3x10x38th power". I take it to mean it's 30 plus 38 zeroes following. So a 9x9 board game of go has less possible combinations than chess, which I think is 10x120th power. A 13x13 board of go is 10x89th power while the standard 19x19 board version is 10x170th power. That would be 10 followed by 170 zeroes. So 19x19 go beats western chess by 50 zeroes. I love the fact that computers won't be able to solve 19x19 go.

No, you are confusing number of possible board positions with number of possible games. Games are sequences of positions.

On 19x19, there are about 10¹⁷⁰ possible positions, but a rough estimate of 361! gives us about 10⁷⁶⁸ possible games.

On 9x9, there are 10³⁸ possible positions, and a rough estimate of 81! gives us about 10¹²⁰ games.

Chess has about 10⁴³ positions, and a rough estimate of about 10¹²⁰ games. (See Shannon number)

Those numbers on possible positions are pretty accurate. The numbers on possible games are really only rough estimates. Tromp and Farnebäck have proven that it is theoretically possible to play a game of at least 10⁴⁸ moves without repeating any position, putting a lower bound on the game tree complexity of about 10^{₁₀ 48}. That is a 1 with 10⁴⁸ zero's behind it...

Of course, playing a game with 10⁴⁸ moves is practically impossible. Suppose we built a computer that is capable of playing 1,000,000,000,000 (1 trillion) moves per second. It would still take that computer over 1,000,000,000,000,000,000 times the current age of the universe (which is about 15 billion years) to finish the game...

HermanHiddema wrote: rough estimate [...] rough estimate
[...] at least 10⁴⁸

Since those are related to estimating lower bounds, theoretically possible numbers can be very much greater.

To (hopefully) get more practical numbers, one can ask for the minimally necessary size of a tree that explains all choices necessary for perfect play. Anyone..?:)

HermanHiddema wrote:the current age of the universe (which is about 15 billion years)

13.7 billion years.

RobertJasiek wrote:...one can ask for the minimally necessary size of a tree that explains all choices necessary for perfect play. Anyone..?:)

The size of that tree depends heavily on the evaluation algorithm used to determine its leaves. In the most extreme case, one could let the tree grow so that all leaves are finished games, and a counting algorith is used. In such a case, the majority of the tree would be games that a 10k could evaluate as clearly decided.
A good evaluation algorithm could take several orders of magnitute off of that tree.

RobertJasiek wrote:
Since those are related to estimating lower bounds, theoretically possible numbers can be very much greater.

To (hopefully) get more practical numbers, one can ask for the minimally necessary size of a tree that explains all choices necessary for perfect play. Anyone..?:)

Upper bound on the size of the game tree is 10^{₁₀ 170}

RobertJasiek wrote:

HermanHiddema wrote:the current age of the universe (which is about 15 billion years)

13.7 billion years.

Which is about 15 billion years.