[tromp]

> Go is a deeply complex strategic game — famously far more complicated than chess, with 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible board configurations.

The correct number of legal Go positions is over twice as much, or to be exact [1]:

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

Indeed far larger than the ~ 4.8 x 10^44 legal chess positions [2], that is in between the number of legal 9x9 and 10x10 Go positions.

[1] https://tromp.github.io/go/legal.html

[2] https://tromp.github.io/chess/chess.htm

[HackerThemAll]

All these digits are only making it more obfuscated. Using the order of magnitude it's 10^44 for chess versus 10^170 for Go. Thus, Go is 10^126 times more complex than chess.

For reference, the estimated number of individual atoms in the universe is thought to be between mere 10^80 and 10^83.

[kibwen]

> All these digits are only making it more obfuscated.

I think that using these numbers as as stand-ins for difficulty is itself a form of obfuscation.

The truth is that, despite the massive number of potential board states, Chess and Go are some of the easier games to solve, thanks to their nature (perfect information, zero randomness, alternating turns where each player plays exactly one move). And trying to use board states as a proxy for complexity and complexity as a proxy for difficulty doesn't generalize to other categories of games. Compared to Go, what's the complexity of Sid Meier's Civilization? If I devise a game of Candyland with 10^180 squares, is that harder to devise an optimal strategy for than Go just because it has more board states?

The reason that we're still using board states as a proxy for difficulty is because historically our metric of "this is difficult for a computer to play" was based on the size of the decision tree and thus the feasibility of locally searching it up to a given depth. In the age of machine learning, surely we can come up with a more interesting metric?

[btilly]

We have more theory for deterministic games. That doesn't mean that it is harder to solve them to a human level.

Computers got to being better than humans in both Go and poker in 2016. The difference is that https://www.deepstack.ai/ was solvable by academics with normal research grants. The training for the final version of AlphaGo is estimated at about $35 million. And who knows how many other versions were created?

Yes, actually solving Go and Civilization are both impossible. But I would be shocked if playing Civilization at a human level was too hard for us to solve with current machine learning techniques.

[banannaise]

Number of possible game states is a poor measure of complexity. How many game states does soccer or basketball have, when you consider flight of ball and movement of players? Does that tell us anything about whether basketball is more complex than Go?

[btilly]

Every measure of complexity is limited in some way. So they are all poor in various ways. That doesn't make them not worthwhile.

Total game states is one measure. What does it take to solve the game?

You can also look at the branching factor, how many moves are there to make on average. For chess, it's 20. For go, it's something like 300.

You can also look at how long it takes from a move to seeing its negative consequences. A bad move in chess is frequently visible in very few moves. You lose a piece. You lose an exchange. Often these sequences are virtually forced. By contrast, the consequences of a bad move in Go are usually not visible for 50 moves or more. And there is nothing forced about the sequence that gets there.

You can also look at how likely good players are to play similar games. Many chess games have been played over and over again. People sometimes play half the game out of a memorized opening sequence. By contrast, it is plausible that no Go game has ever been played twice on a 9x9 board. It is very unlikely that any Go gamme has been played twice on a 13x13 or 21x21 board.

You can also look at how big the skill gaps between humans get. In my experience, a 1 stone difference in Go is roughly a similar skill gap to 200 points of Elo in chess. A rank beginner who barely moves the pieces may have a 400 rating. No human has ever reached a 2900 rating. That's 12.5 levels. By contrast Go has 30 levels of amateur (kyo), another 9 for serious players (dan), and then the skill range among professionals is about another 3. That's 42 levels of fairly recognizable skill differences between humans. Which speaks to how much more there is to learn about Go than chess. (Even more so when you realize how much of advancing in chess is a matter of making fewer mistakes. By contrast advancing in Go is much more about integrating better principles.)

No matter how you look at it, Go is much more complex than chess.

[bluecalm]

One good measure is how much resources a computer program needs to have to play optimally. This is hard to measure as we don't have optimal programs but maybe "how much resources is needed to play better than the best human" is a sensible measure as well. Go wins on this one but only marginally.

[frutiger]

> For reference, the estimated number of individual atoms in the universe is thought to be between mere 10^80 and 10^83.

Yes, but what are the estimated number of states of all these atoms?

[karakot]

is it even countable?

[tromp]

Or one could say that Go is about as complex as 4 simultaneous games of go, with the number of positions being about the 4th power.

[bluecalm]

Complexity of the game has nothing to do with the number of legal positions. It's very easy to design a game with arbitrary number of positions which is very simple. While go might be more complex than chess using a more reasonable measure this argument was used to for arguing nonsense in scientific papers in the past (that some poker games are more complicated than chess because they have more possible states).

[falserum]

I have a further nitpick regarding terminology.

Wording like “game is more complex” overal seems incorrect. Game is not complex by itself (for example go rules are extreemly simple), all the difficulty and challenge depends on the skill of your oponent. Game only allows the opponent to demonstrate the skill.

[tromp]

Beyond rule complexity, there are at least 5 measures of game complexity in Combinatorial game theory [1]:

    State-space complexity
    Game tree size
    Decision complexity
    Game-tree complexity
    Computational complexity

[1] https://en.wikipedia.org/wiki/Game_complexity

[Kranar]

Those are all meaningful measures of complexity, but it's worth noting that all of them are a function of the number of legal positions (among other things as well).

[tromp]

That would be quite a strange function. For example, Tic-Tac-Toe has 26830 possible games on 5478 possible positions, while 2x2 Go has 386356909593 possible games on only 57 possible positions.

The major difference of course being that Go allows stones to be captured.

[Kranar]

I don't see what's strange about that, different functions grow at different rates. That's like saying it's strange that exp(x) is a billion for x = 21 while sqrt(x) is merely ~4 when x = 21.

Go's complexity grows much faster than tic tac toe's complexity as a function of legal positions, but the complexity is still a function of the number of legal positions (among other things, as I pointed out).

[Kranar]

Are you sure that the complexity of a game has absolutely nothing to do with the number of legal positions?

I mean I am open to hear the justification for this, but I was fairly certain that all measures of game complexity are a function of the number of legal positions. Now certainly there are other factors, namely the cost of computing the transition from one legal move to another legal move so a simple game might have a very low cost transition function while a complex game has a very complex transition function, but I can't conceive of a game where the number of legal positions bears no weight on the game's complexity.

[jan_Inkepa]

Take a game where you get to pick a single number between one and a billion. If you pick 10 you win. This has a billion states, but it's trivial. I can increase the bound above a billion, it doesn't matter.

State count gives an upper bound, though, to how complex a game can be, for sure.

[nurettin]

Those position counts don't account for blunders or bad tactics which the players will take advantage of in order to simplify and win. In go, any move that lets your opponent cut you off is highly likely a blunder, so counting every other move other than the obvious one you have to play in order to not lose is pretty useless. You can also call it a bad move if you are not under an immediate threat and you are not invading. (this is a guess, I am not a go player) So counting the rest of the moves developing in your territory is also useless.

[bluecalm]

Yes, for example no limit Rock Paper Scissors where you bet an arbitrary amount and your opponent might call or fold is a game that:

1)has infinitely many legal states/positions

2)imperfect information (another argument often used to argue that game is more complex)

And is:

3)dead simple to play optimally

It's also easy to design a board game with arbitrary number of legal positions that is dead simple to play optimally.

[lp4vn]

Go is played in a a bigger board though and has this kind of recursive nature where a subset of a go game is also a go game while chess is more ad-hoc.

[anon84873628]

For extra fun, use the "Listen to article" feature on that paragraph...