# The huge game tree complexity of Go is meaningless

I played chess for many years before trying Go and since exploring the game I have noticed one point that Go enthusiasts love to go on about time and time and time again. The game tree complexity is estimated to be 10^700 (10 to the power 700 that is) possible games, while chess is estimated to be about 10^120. Thus, according to many Go players, Go is a far more complex game than chess

Stop. The number 10^120 is an unimaginably huge number, it’s 10 followed by 120 zeroes, or a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion (etc…) In fact not even current super computers have been able to accurately say how many possible games of chess there are.

To try to imagine the numbers involved, look at the tip of your little finger. It has trillions of atoms, and a trillion is far more games of chess anyone would play in their lifetime. And the tip of your little finger is only a tiny fraction of you as a person. And you are only a small part of the room you’re in. And the room is only a small part of the whole building. And the building is only a small part of the street.

And the street is only a small part of the local neighborhood. And the neighborhood is only a small part of your town or city. And your city is only a small part of your state/ province. And your province is only a small part of your country, and your country is only a small part of the planet.

Already, the tip of your little finger is an absolutely tiny part of the planet. If you go outside and look at your little and compare it to the rest of what you can see you can appreciate the numbers involved.

That’s the small part. Now take into account that the Earths’ place in the solar system, it’s a tiny fraction. And the solar system is a tiny fraction of our galaxy.

And there are billions of galaxies in the universe. The trillions of atoms in your little finger are looking very small indeed in the grand scheme of things.

The current estimate of umber of atoms in the observable universe is about 10^82, which is much smaller than the game tree complexity of chess, which is 10^120.

That’s why I feel that people who are so enamored of Go’s game tree complexity are missing the point.

In fact I don’t even know why Go players are continually comparing Go to chess. Apart from being very old strategy board games, they have no real similarities. What does chess have to do with Go?

That’s my point made. I happen to enjoy Go very much, but I get annoyed with the hardcore Go players who love to boast about Go’s complexity- they’re totally missing the point.

5 Likes

Was this post (partly) made in response to Go is better than chess because - #93 by Uberdude?

2 Likes

I love go and I don’t love chess but I don’t feel the need to say one is better than the other.

Some love to be parochialist.

4 Likes

That is, of course, because that goes without saying.

8 Likes

I don’t think my finger has a trillion atoms.

1 Like

You are completely correct, and I think (hope) most strong players would know better than to say something like this. For instance, Michael Redmond 9p mentioned in passing in a video that he believed that go, chess, and shogi are all about the same difficulty for humans. The number of legal moves in each position has very little effect on the gameplay, since most moves are nonsense. Anyone who has played any of these games at a high level would understand this.

But it’s so very easy to put “more positions than the number of atoms in the universe!” on a poster, and so very hard to explain the beauty of go to someone who has never played. So I fear we will have to live with this unfortunate trope for a long time.

I just thought that you might be comforted by the fact that there are plenty of go players who are just as annoyed as you

8 Likes

But it’s so very easy to put “more positions than the number of atoms in the universe!” on a poster, and so very hard to explain the beauty of go to someone who has never played. So I fear we will have to live with this unfortunate trope for a long time.

Some of the overenthusiastic advertising slogans are pretty laughable.

Consider:

“Go: Invented 4,000 (1) years ago, the oldest (2) and most popular (3) board game in the world!”

1. Probably false. Serious publications give lower bounds of 2,000 or 2,500 years.

2. Even at 4,000 years old, it would still be centuries younger than backgammon and / or similar games.

3. That is chess, then likely xiangqi. I’m not even sure Go is any more popular worldwide than draughts or even Scrabble.

6 Likes

If we start with assuming ideas for imaginary people like some “overenthusiastic” we go nowhere.

For me both games look difficult but the difficulty can come from different factors, like pieces different and moving or not.
So that’s why we can understand that computer programming got to offer a strong program for chess much earlier as for go. And yes it was much harder to explore all the tree branches of a go game and that stayed for a long time the main obstacle to programming, but that doesn’t say chess is easier.

So the “huge game tree is meaningless” is not what programmers were thinking for all this years. It was a real problem.

2 Likes

Indeed, the large branching factor is relevant to the difficulty for computers, but not so relevant to the difficulty for humans

5 Likes

First of all, chess and go are so complex that it is not their respective possibilites which limit human play but the limits of humans themselves. Which is also part of why they are so attractive to many people. You can explore in depth and reach your own frontiers of understanding far before you reach those of the game. They are both virtually limitless to humans.

Second, I don’t believe there are many go players who dismiss chess seriously on the ground of complexity. If that would be the case it would be stupid indeed.

Afaik it is just a running gag in the go community to bash chess. Many people enjoy both, myself included.

3 Likes

number of game trees is meaningless. But what is number of possible moves in chess?
(I mean on 1 next move, for Go its 362max (first move, pass included, 19x19 board))

this whole discussion is meanless

2 Likes

I think this topic confuses two things.

People who think that “Go is far more complex” has the meaning that “Go is a lot harder / more interesting / profound than chess” are misunderstanding what is really meant when it is stated that Go is more complex. Complexity in terms of game trees has not really much to do with how difficult the game is for humans, but instead just is the measure of how many possible games there are. In this sense, Go is indeed vastly more complex than chess, since there’s vastly more possible games. This doesn’t imply that it’s either more difficult for humans to learn, harder to solve (by finding a perfect strategy), or harder to write a strong algorithm for (like AlphaGo).

See “complexity” simply as a measure of how much resources is needed for something.

• Complex things for humans (like Go, chess, playing the piano, learning a foreign language) need a lot of resources for humans to get good at.
• Game complexity measures how many possible games there are under the game rules, or how many board positions, etc., and is useful to determine upper bounds to how hard a game is to solve: if we want to find out which player wins the game under perfect play, we could consider all possible games and just compare all results.
• Strategic complexity measures how difficult it is to formulate a perfect strategy to win a game. If we have access to the whole game tree, we have access to a strategy, but it is not always necessary to compare the whole game tree. For example, the game Hex can be played on a board that is far larger than a go board, and thus for such boards has a far larger game complexity. But, by a strategy-stealing argument, it can be seen that the first player will win the game under perfect play, thus regardless of game complexity we know who wins.
• Computational complexity measures how resources increase as the problem gets larger. For example, in Go it would measure what the ratio is between the amount of time (or space) needed to solve an NxN board and to solve an (N+1)x(N+1) board. For example, the resources needed to let a computer solve a game of Go grows exponentially in time and space (and because the game is EXPSPACE-complete, it is quite likely that this is the best we can do, but this problem is very hard to solve and related to one of the largest open questions in mathematics / computing science). Similarly, solving a game of chess grows exponentially with board size, but Hex, for example, does only grow polynomially.

So to summarise, stating that Go is more complex than chess because the game tree is larger is just a fact: Go has a larger game complexity. Stating that Go is more difficult to solve strategically than chess is unknown, since neither chess nor Go have been solved strategically yet. Stating that Go is computationally more complex than chess is incorrect, since both are equally complex to generalise to larger board sizes.

Finally, saying that Go is more complex for humans to learn, is just an opinion. Considering that there is no definite point reached by any human for “having completed learning Go”, I think it’s a bit nonsense to think about how hard it is to learn Go. It’s as hard as you want it to be: in practice there’s always a stronger opponent waiting for you.

4 Likes

Extra example:

Consider the following extremely silly game, which I’ll call “first to claim the centre”.

• The game is played on a 99x99 board
• The players alternate between placing a stone on an empty intersection
• There’s no capturing mechanics, once a stone is placed it will remain there for the rest of the game.
• The game ends as soon as a stone is placed in the centre (tengen) intersection.
• After the game ends, the player wins who had the last turn (thus the first player who puts a stone on the centre intersection wins the game)

Now, it’s pretty easy to see that there are 99×99 -1 = 9800 intersections on the board that don’t matter. But, the players can alternatingly place stones on any of these intersections before either player attempts to place a stone in the centre, and thus there are already 9800 × 9799 × 9798 × … × 3 × 2 × 1 = 9800! (factorial) possible sequences in which the players could fill the entire board except the centre. That’s around 1034861 possible sequences. Hence the game complexity is far larger than that of Go.

Meanwhile, solving the game is easy: the first player just places their stone in the centre for their first move, and wins the game. Done.

6 Likes

I do understand your will to keep matters separated. OGS include a lot of chess players who sometimes like to digress on the differences, so a search will guide you to some related topics. (Link to one of them in @Uberdude answer to you)

To me chess has more as nothing to do but many times be a full opposite of go.

I invite you a book, in french maybe translated somewhere:
Lusson, P., Perec, G. et Roubaud, J. (1969). Petit traité invitant à la découverte de l’art subtile du go. Paris. Bourgois.

1 Like

Anyways, Monster Hunter is the better game. I actually had fun playing it.

1 Like

I don’t think so either, let’s do some Fermi estimation.

First, humans float in water, but only barely so, thus I’ll say that humans are about as dense as water is. An average finger is about 10cm long, and about 1cm x 1cm in diameter, so let’s say 10cm3 in volume, which is 10mL. 10mL of water weighs 10 grams, thus a finger weighs about 10 grams.

I’ve read somewhere that around 80% of human body weight is made from water, so let’s just round that and assume the finger is completely made of water (which are relatively light molecules, so probably the number of atoms in a finger is slightly less than my estimate). 10 grams of water is about half a mole of water, so that gives us about 3 × 1023 water molecules in a finger. Since water is made of 3 atoms, that means there are roughly 1024 atoms in a finger.

That’s a septillion.

3 Likes

Meanless like harmless?

As (ex)Chess player my self. I do like both of the game and i admit there are few toxic Go Player but, most of the time i see Go Player went toxic or bring up that tree complexity because Chess player brought that Chess better and more complex because of the same reasons or Go just one dimensional game with lack of depth without ever played Go even once the worst part is certain Chess Player played only few game just to find “weakness” of Go without even understanding Fundamental of Go. Toxic Chess Player are also often found on non Chess related Go topic especially Video on YT and i rarely see go player denounce chess on Non Go related Topics.

Why Comparing both when they’re “different”?
People have egos they’re really want to see their favorites things appear to be better. subconsciously you also will do the same, no matter.

Also It’s part of Advertising new Player to play, let’s face it. Go is lack really big advertisement on the west only AlphaGo. We don’t have influencer like big twitch streamer who played Go. I know it has side effects that made Chess player won’t touch Go because blind hatred, but it cant be done… No one could stop someone to bring this issues either

The Lacks of OP responds made this seems as Baiting or Just Venting, but well…

I apologize if my answer is out of topic and Hope you’ll keep Playing Go

Cheers…

3 Likes

So true, thanks!

1 Like