The huge game tree complexity of Go is meaningless

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 :slight_smile:

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

I seriously doubt that Go is anything like 4000 years old. However, small shaped pieces of stone that are clearly playing pieces go back much older than that, all over the world and found by archaeologists. Go has a rich prehistory of various kinds of games played with markers and pits or boards, way before the current rules even began to be formulated. But I’ll bet that the present rules go back only 1000 to 2000 years, and only in certain regions, and were probably codified in stages by now-forgotten warriors, kings, or their advisors who loved games. My opinion only. And I agree with the OP: most board positions are nonsense, and when you subtract them out, 19-line Go is probably only moderately more complex than chess.

1 Like

Since your reasoning is brief, I will reply in kind: I don’t agree.

2 Likes

small shaped pieces of stone that are clearly playing pieces go back much older than that, all over the world and found by archaeologists. Go has a rich prehistory of various kinds of games played with markers and pits or boards

Just likely to be race games or mancalas as types of Go, wouldn’t you think?

Or a game like hasami shogi / ludus latrunculorum. I wouldn’t be surprised if “hasami shogi” (which isn’t a type of shogi whatsoever) had been a precursor of Go, seeing as it uses custodial (two-stone) capture.

Not a difficult jump, one would think, to shift from a game of undifferentiated moving pieces capturing custodially to one of undifferentiated non-moving pieces capturing in the “double custodial” manner of Go.

I know of two detailed speculations on the origins of the game, Claire’s thread and Shotwell’s book, both of which I can link if you’d like. Claire idea is especially interesting, that Go is a product of sedentary culture and represents disputes over irrigation.

On when “modern Go” emerged, I remember hearing it claimed that early references to Go speak only vaguely of achieving a certain goal, like perhaps making a certain shape as in gomoku – gomoku and other connect-N games are another good explanation for early stones – rather than specifically of surrounding territory. But I don’t know how accurate that claim is.

We also have to avoid being too absolutist.

If I have a chessboard, that doesn’t mean I’m playing chess; I could be only playing draughts, or both games.

Similarly, if I as an ancient Chinese nobleman have a “Go set”, I might be using it to play Go, or gomoku, or hasami shogi, or any mixture of the two depending on my mood or company.

The same analogy could be made to a pack of playing cards.

I don’t care

1 Like

I’ve heard many times that Americans are generally polite and positive, compared to the Dutch, who are generally blunt and cynical.
I suppose there are always exceptions to such generalizations
.

3 Likes

You were given misinfo

1 Like