4 ms·
Let's compare Go and Chess. We all know that Go is more complex that Chess, but how much more? There's 10^50 atoms in the planet Earth. That's a lot. Let's pu
by davelondon 11y ago
Let's compare Go and Chess. We all know that Go is more complex that Chess, but how much more?
There's 10^50 atoms in the planet Earth. That's a lot.
Let's put a chess board in each of them. We'll count each possible permutation of each of the chess boards as a separate position. That's a lot, right? There's 10^50 atoms, and 10^40 positions in each chess board so that gives us 10^90 total positions.
That's a lot of positions, but we're not quite there yet.
What we do now is we shrink this planet Earth full of chess board atoms down to the size of an atom itself, and make a whole universe out of these atoms.
So each atom in the universe is a planet Earth, and each atom in this planet Earth is a separate chess board. There's 10^80 atoms in the universe, and 10^90 positions in each of these atoms.
That makes 10^170 positions in total, which is the same as a single Go board.
Chess positions: 10^40 (https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number)
Go positions: 10^170 (https://en.wikipedia.org/wiki/Go_and_mathematics https://en.wikipedia.org/wiki/Go_and_mathematics)
Atoms in the universe: 10^80 (https://en.wikipedia.org/wiki/Observable_universe#Matter_content https://en.wikipedia.org/wiki/Observable_universe#Matter_con...)
Atoms in the world: 10^50 (http://education.jlab.org/qa/mathatom_05.html http://education.jlab.org/qa/mathatom_05.html)
- justsaysmthng 11y agoWhy am I feeling a bit scared of all this ?
- __john 11y agoThe oldest and strongest emotion of mankind is fear, and the oldest and strongest kind of fear is fear of the unknown. -- H.P. Lovecraft
- ekianjo 11y agoI am not sure that calculating the raw number of positions is a good indication of complexity at a given point. What if most positions are obviously junk in go while they are more difficult to assess in chess? Not saying this is the case in this particular example but thats a possibility in theory.
- masklinn 11y ago> What if most positions are obviously junk in go while they are more difficult to assess in chess? I wouldn't go with most (because I don't know about that), but many of these boards would also be either impossible to achieve (in a normal game) or illegal.
- aardvark179 11y agoThe 10^170 figure is legal positions. It's about 1% of possible board positions. How many of those are sensible is another matter.
- eru 11y agoTo illustrate your point: you can just add rows to a game of Nim (https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim) to get a truly enormous state space, without changing the simple winning strategy.
- pavelrub 11y agoThis doesn't seem to be the main reason why Go is harder than chess for computers. It was noted that even in 9x9 Go, with a comparable branching factor to Chess, traditional Go programs are still no stronger than on big boards. The main difficulty for Go is that it is much harder to evaluate board positions. So in Chess the depth of the search can be significantly reduced by using a reasonable evaluation function, whereas in Go no such function seems to exist.
- kotach 11y agoAlphaGo has a learned evaluation function for each move. Evaluation function exists but it is not as simple as it can be for chess.
- liviu- 11y ago>It was noted that even in 9x9 Go, with a comparable branching factor to Chess, traditional Go programs are still no stronger than on big boards. Are they not? MoGo beat pros of 9 Dan on 9x9 in 2011: https://www.lri.fr/~teytaud/mogo.html https://www.lri.fr/~teytaud/mogo.html
- pavelrub 11y agoWell, I guess it was more true before the advent of Monte Carlo Tree Search. Even so, note that even in the case of MoGoTW in 2011, it played blind Go (this helps the computer), and out of 4 games, won two games against a 9p player, and lost 1 game to a 5p player. Though it is perhaps better than MoGo's performance on 19x19, it still isn't very good, doesn't seem much better than MoGo on 13x13, and performs much worse than computer Chess, despite a similar branching factor.
- iopq 11y agoThe branching factor is much larger, around 75 legal moves after the opening, while chess has at most like 30. Fuego beat a pro in 2008 using MCTS actually.
- 11y ago
- deleted 11y ago[deleted]
- no_wave 11y agoStarcraft has way more possible board states
- taneq 11y agoThere's a Starcraft AI League (http://sscaitournament.com/ http://sscaitournament.com/) you might be interested in.
- claudius 11y agoOn the other hand, 2^565 is already slightly larger than 10^170. In other words, a couple of hydrogen atoms as quantum bits can perfectly well encode every possible position.