[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.