4 ms·

> 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,0

by tromp 3y ago

> 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 https://tromp.github.io/go/legal.html [2] https://tromp.github.io/chess/chess.htm https://tromp.github.io/chess/chess.htm

HackerThemAll 3y ago
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.
- tromp 3y ago
  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.
- kibwen 3y ago
  > 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 3y ago
    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/ 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 3y ago
  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 3y ago
    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 3y ago
      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 3y ago
  > 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 3y ago
    is it even countable?
lp4vn 3y ago
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.
bluecalm 3y ago
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 3y ago
  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 3y ago
    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 https://en.wikipedia.org/wiki/Game_complexity
    - Kranar 3y ago
      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 3y ago
        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.
anon84873628 3y ago
For extra fun, use the "Listen to article" feature on that paragraph...

by tromp 3y ago

HackerThemAll 3y ago

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.

tromp 3y ago
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.
kibwen 3y ago
> 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 3y ago
  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/ 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 3y ago
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 3y ago
  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 3y ago
    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 3y ago
> 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 3y ago
  is it even countable?

lp4vn 3y ago

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.

bluecalm 3y ago

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 3y ago
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 3y ago
  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 https://en.wikipedia.org/wiki/Game_complexity
  - Kranar 3y ago
    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 3y ago
      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.

anon84873628 3y ago

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