Go boards move > atoms.?

I just can’t get my head round this! It is claimed there are more moves on the Go board then there are atoms in the universe.

Just think, one blade of grass or a grain of sand. Look up how many atoms make one of these two. Now expand out to field, a beach etc. How, just how is this a fact?

2 Likes

Perhaps this will make the idea easier to understand:

4 Likes

Well, no, there are more possible games of Go than atoms in the universe. But at any moment, there’s at most 362 moves (1 move for each coordinate, and passing).


I wrote a bit about this over here:

and also an example why it’s not that interesting that there are that many games of Go:

7 Likes

Exponential complexity is just kind of amazing like that.

It is estimated that there are between 10^78 and 10^82 atoms in the observable universe (How Many Atoms Are There in the Universe? | Universe Today).

10^78 simply means a 1 followed 78 zeros, a number that one can easily write out in a minute or two on a piece of paper. Likewise, 10^82 just adds four more zeroes (while being 10000 times larger! Imagine 10 kilometers compared to a single meter, or 10 meters compared to a millimeter).

The number of legal positions on a Go board has been carefully worked out to be a number with 171 digits (see Counting Legal Positions in Go and Go and mathematics - Wikipedia). Although this number is only a little over twice as long as a 82 digit number, it is unfathomably larger. If every one of the 10^82 atoms in the universe was replaced with its own universe of 10^82 atoms, we still only have about 10 10^164 atoms, which is still 100000 times smaller than the number of legal Go positions.

As for the number of a games, Walraet and Tromp (see https://matthieuw.github.io/go-games-number/AGoogolplexOfGoGames.pdf) have shown that there are at least a googolplex (10^10^100) legal games of Go.

10^100 (1 followed by one hundred zeros) is a “googol”.

10^10^100 is a googolplex and means 1 followed by a googol zeros, which is an absurdly large number. Given that there are only 10^82 atoms in the universe, it is impossible to even imaging all of these 10^100 zeros being written down, unless one somehow managed to pack 10^18 zeros (one billion billions) onto each and every atom!

7 Likes

There is approximately 1 billion grains of sand in a 1 foot cube, now consider how many 1 foot cubes you will fill out if the Sahara desert, each grain of sand contains 70,000,000,000 atoms

THAT’S JUST SAND!

Then do atoms in a drop of water/leaf/grass

Then consider the planets in our Solar system followed by the observable planets and stars outside our solar system

It just doesn’t seem plausible and I wonder how many people would believe the claim at face value alone

1 Like

Thanks for this, interesting, but not easy to understand at all. I am struggling still

1 Like

Would two games of go that end with identical finishes but completely different sequences were played count as separate games or not :thinking:

1 Like

Yeah, that’s a lot of sand!

Earth has roughly (and we’re speaking very roughly here) 7.5 x 10^18 grains of sand

And there are even more stars in the universe than grains of sand on Earth!

Now the population of stars jumps enormously, to 70 thousand million, million, million stars in the observable universe (a 2003 estimate), so that we’ve got multiple stars for every grain of sand — which means, sorry, grains, you are nowhere near as numerous as the stars.

70 thousand million, million, million is 7 x 10^22.

But all of these numbers of still much smaller than the 10^72 to 10^82 estimate of the number of atoms in the universe.

2 Likes

Yes they take into account all possible legal moves not just all possible finished board states.

1 Like

But if there are 7x10²² stars,
Just how many atoms would that make up in stars alone? How many atoms in 1 star times 7 X 10²².

It is said there are 10⁵⁷ atoms of hydrogen in just our sun alone. What about a red giant!!

Or number of atoms in a galaxy is 2 X 10⁶⁷… There are said to be hundreds of billions of galaxies !!

Thanks for the help but I’m just not getting my head around it.

Ok, so let’s explore these numbers a bit.

Suppose that I have a cup. I can either put a black stone in it, a white stone, or no stone at all. There’s three states that the cup can be in: containing a black stone, containing a white stone, or containing no stone.

Now, suppose I have two cups. Now there are 32=9 ways the two cups can be: black-black, black-white, black-empty, white-black, white-white, white-empty, empty-black, empty-white and empty-empty.

If I had three cups, there would be 33 ways the cups can be filled (or not).

Now, suppose I have 361 cups. Now there are 3361 ways to either place black stones or white stones in the cups, or leave them empty. In other words, there are 3361 ways I can place stones randomly on a goban. Not all of these are legitimate board positions in Go, (there could be groups without liberties for example), but this is a mindbogglingly large number, around 10172.

It turns out that about 1 in every 80 random board positions is actually a legal Go position. If you know a little bit about computer programming, you can easily check this yourself by generating boards filled with random stones, and seeing if there are any groups without liberties. I might make a simulation myself later to illustrate this.

So, to get some decent approximation of the number of legal Go positions, we have to divide 10172 by 80. To get, roughly, 10170

So, the number of legal Go positions is mostly huge because many Go positions are simply random stones thrown on a go board.


Now, let’s tackle the number of Go games.

If I have a Go position with 1 Black stone and 1 White stone, then there is only 1 possible way we can reach that position, by playing the black stone first, then the white stone.

If we have a position with 2 Black stones (a and b) and 2 White stones (c and d), then we reach that position in 4 ways: a-c-b-d, a-d-b-c, b-c-a-d and b-d-a-c. In particular, there are 2 possibilities for the first black stone, and in each of those possibilities only 1 possibility for the last black stone, and similar for white. So in total there are 2 x 1 x 2 x 1 ways to reach our board state.

If we have a position with 3 Black stones and 3 White stones, there are 3 x 2 x 1 x 3 x 2 x 1 ways to reach this position. Usually this is written as (3!) x (3!).

Now suppose I have a random Go position, then I can expect about 1/3 of the stones to be Black, 1/3 to be White, and 1/3 to be empty, since it’s random. So that’s 120 Black stones, 120 White stones. In total, that gives me (120!) x (120!) different ways to reach that end position.

This in itself is around 10397! And that’s just one of the 10170 random board positions.

That means that the total number of possible games of Go, is at least somewhere around 10397 x 10170 = 10577. Why at least? Because we’re currently only counting games where none of the stones are captured. There’s no long ko fights, no filling the entire board and then capturing everything and start over again, etc.


Anyways, I hope that explains a bit why these numbers are so large.

6 Likes

The 10^78 to 10^82 estimate of number of atoms in the universe is actually based on a calculation just like this. Let’s round up the number of stars to 10^23. If the average mass of the stars is roughly the same as our sun, then the average number of atoms per star is also roughly 10^57. Multiplying 10^57 times 10^23 yields 10^80. Even if we conservatively assume that our sun is 100 times smaller than the average star, that only changes the calculation to 10^82.

There are certainly much, much more massive stars than our sun, but they are also rarer, and probably don’t skew the average that much.

It is worth noting that while a red giant can have a much, much large diameter than our sun, it might not necessarily be significantly more massive. Eventually, our sun will become a red giant (see Sun - Wikipedia) while expanding its diameter by several orders of magnitude to probably engulf the orbit of Earth. However, at that point it will actually have slightly less mass than it currently does (since it is gradually losing mass in its solar wind), and there will be significantly fewer individual atoms (since much of the hydrogen will have fused by pairs into helium).

8 Likes

Vsotvep and yebellz very informative posts to a question I presume must get asked a lot on here, good work and easy to understand :+1:t2:

5 Likes

Note the word “observable”. We don’t know how big the universe actually is.

6 Likes

Thank you for this. Just one issue, isn’t black-empty and empty-black the same thing? Besides that this has helped me a lot. Thanks again.

Permutations and perturbations?? I remember covering a similar situation with red blue and green counters, and those two words changed how many variations are counted, been a while so I’m rusty.

1 Like

Agreed, I read that as we can only observe a small percentage of the universe, that would mean it is finite as the light in the universe would have had infinite time to light up space had it’d be infinitely large.

1 Like

black-empty is a black stone in the first cup, and an empty second cup. empty-black is an empty first cup, and a black stone in the second cup.

For the sake of my argument these are different. But you’ve got a point here: generally we don’t count a Go game differently if it’s rotated or mirrored. So, we have to divide our total by 8 again to compensate for symmetries (4 ways to rotate the board, times 2 for mirroring). However, dividing by 8 is not really going to change the magnitude of the numbers.

I mean, this doesn’t change anything: the colour of the stones don’t affect how many different options there are :wink:

4 Likes

Thanks for clarifying!

1 Like