6 ms·

Can someone explain why this is more impressive than a computer beating top chess players over a decade ago? I'm not very familiar with Go, and while there were

Can someone explain why this is more impressive than a computer beating top chess players over a decade ago? I'm not very familiar with Go, and while there were far more squares on a Go board, it seems less sophisticated than chess to me. Maybe Go has way more moves possible and emergent strategies or something I'm not taking into account.

fcmk 11y ago
What do you mean by sophistication in this context?
- moonshinefe 11y ago
  In chess there are various pieces with differing powers, with Go it seems like they all have similar powers. Again, I don't really know the game and might be wrong, but that was my impression.
  - eru 11y ago
    Actually, that's the draw of Go over Chess for me. The different powers in chess seems arbitrary. We can easily imagine aliens coming up with Go by convergent evolution, but not Chess. Too many free parameters. Yes, the fascination lies in the strategies that emerge from the simple base.
  - kqr 11y ago
    One thing that's cool about Go is that the pieces get their value and power not from the rules, but from how they are used. In an actual game of Go, you will find groups of ten pieces that are casually thrown away, and you will find single pieces that the whole game revolve around. In the rulebook, they are the same piece, but in actual effort expended to save/attack them, you'll see they're valued vastly differently. This happens in chess too, of course, but in Go their value is decided only based on how they are used. The sophistication is about the same, but the rules are simpler.
    - eru 11y ago
      Go has many more sacrifices in a typical game than chess, too.
_xander 11y ago
"The game has long interested AI researchers because of its complexity...the average 150-move game contains more possible board configurations — 10^170 — than there are atoms in the Universe, so it can’t be solved by algorithms that search exhaustively for the best move." [Source: http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234 http://www.nature.com/news/google-ai-algorithm-masters-ancie...]
- moonshinefe 11y ago
  Yeah interesting, so mathematically there are more moves in Go than the other games AI players have solved so far. Thanks for the info.
- tromp 11y ago
  208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 to be precise. Which is more than even the square of the number of atoms in the universe, showing how silly that comparison is... Btw, the quoted "the average 150-move game contains" makes no sense at all, since such a game contains only 151 positions.
  - 1024core 11y ago
    Fold that friggin' number. It's causing everyone to scroll horizontally.
    - dang 11y ago
      We put two spaces ahead of it, which gives it 'pre' formatting that doesn't wrap.
    - awl130 11y ago
      +1
Lozzer 11y ago
Firstly there are vastly more positions in Go. Secondly, it's very hard to evaluate a Go position, especially at the start of the game when there are few stones on the board. In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1).
- slm_HN 11y ago
  >In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1). I guess it depends on your idea of a "long way". Using only your simple evaluation a program would be rated somewhere around 1000-1200. It would lose every single game to an average tournament player.
gjm11 11y ago
Chess is quite tactical and brute-force-y -- the board is quite small, games are quite short, and there aren't all that many possible moves at any given point. A program can play pretty good chess on modern hardware just by alpha-beta searching with a fairly simple evaluation function for the leaves of the search tree. The best programs are cleverer than that; they have sophisticated evaluation functions, they prune and extend their searches, etc. But at heart, what makes them so strong is that they can search deeply. That approach doesn't work so well for go. The board is 6x the size, games are 4x as long, the "branching factor" (number of moves available in a given position) is 10x as large. (All figures very crudely approximate.) If you try to make a fairly-dumb searcher in go, it will play very badly. So how do humans manage to play well in go? By smarter searching, with a better idea of what moves are worth considering; by thinking strategically; by having a feel for the shape of a position ("moving here is likely to be very valuable"). Those are all things that feel like they are harder to make a computer do, and come closer to actual intelligence, than doing well at chess just by doing an enormous search. The first of those is certainly correct. AlphaGo (like most modern go programs) organizes its searches in quite a different way from a typical chess program. It's not clear how far it deserves to be called smarter, though, since a lot of what it's doing is playing out lots of games fairly stupidly[1] and seeing how they go on average. [1] Compared with how it actually plays. One of the achievements of AlphaGo, I think, is that it can reasonably quickly select moves for its playouts that are actually pretty good. The second is more debatable. But, e.g., AlphaGo selects and evaluates moves using neural networks trained on a large amount of high-quality play, and the effect of this is that given a position it can quickly "see" how good it thinks the position is and what moves might be effective, without doing any searching, as a result of feeding the position through a big neural network that does some mysterious calculation we don't understand well. Which is, at that level of abstraction, pretty similar to what you might say about a human go player. Whether any of this has any bearing on more general artificial intelligence is an entirely different question, which I will not attempt to get into.
gjm11 11y ago
Here's a way to measure the sophistication of a game of skill. Consider two players A and Z. A is a ten-year-old who has just been told the rules; Z is God. Now, in between them, put a series of other players B, ..., Y, where B beats A 2/3 of the time, C beats B 2/3 of the time, ..., Z beats Y 2/3 of the time. (We assume God doesn't use his magical divine powers to cheat by, e.g., making Y play bad moves.) Unfortunately, God is not readily available for comparison, so we'll use the best human players instead. How many links are there in that chain? The more there are, the more there is to learn about the game, and hence the deeper and more sophisticated the game is. (So you might think, anyway.) If you rate players using the Elo system, beating someone 2/3 of the time corresponds to being about 150 points stronger. A complete beginner at chess might have an Elo rating of 500, compared with the world champion somewhere around 2900, giving 16 links in the chain. In go, beating someone 2/3 of the time corresponds to being about one kyu/dan rank stronger. A complete beginner might be 30 kyu; the best players are stronger than 9 amateur dan, so that's at least 40 links in the chain. (Lower-numbered kyu ranks are stronger; after 1 kyu comes 1 dan, and then higher-numbered dan ranks are stronger.) So by this measure -- which you may or may not find convincing -- go is a more sophisticated game than chess. Here is the best argument I know against this definition. Define the game of "tenchess" as follows. To play a game of tenchess, you play ten games of chess and the winner is whoever wins more games (a draw if the same number). Then it's easy to see that tenchess has a longer chain, as defined above, than chess; if I win 2/3 of my chess games then I win 79% of my tenchess games, so I can win 2/3 of my tenchess games with a smaller advantage. (I am ignoring the existence of draws for this calculation, just for simplicity.) But surely tenchess isn't a deeper game than chess; it's just longer. Perhaps go's longer chain is just the result of its being a longer game.
- cthor 11y ago
  The tenchess counterargument doesn't work in the context of Elo (from which chain lengths are derived). A has 150 more Elo rating than B in chess. Elo says A has a 2/3 EV on the game result, and B has 1/3. In tenchess, A will get 20/3 points on average and B will get 10/3 points. A will have more points than B in 79% of tenchess games, but the Elo ratings will not change. Elo doesn't consider winning and losing as binary. (This is why draws behave sensibly.) Just as a tie between these players cause A to lose rating, so too would a marginal win from A.

fcmk 11y ago

What do you mean by sophistication in this context?

moonshinefe 11y ago
In chess there are various pieces with differing powers, with Go it seems like they all have similar powers. Again, I don't really know the game and might be wrong, but that was my impression.
- eru 11y ago
  Actually, that's the draw of Go over Chess for me. The different powers in chess seems arbitrary. We can easily imagine aliens coming up with Go by convergent evolution, but not Chess. Too many free parameters. Yes, the fascination lies in the strategies that emerge from the simple base.
- kqr 11y ago
  One thing that's cool about Go is that the pieces get their value and power not from the rules, but from how they are used. In an actual game of Go, you will find groups of ten pieces that are casually thrown away, and you will find single pieces that the whole game revolve around. In the rulebook, they are the same piece, but in actual effort expended to save/attack them, you'll see they're valued vastly differently. This happens in chess too, of course, but in Go their value is decided only based on how they are used. The sophistication is about the same, but the rules are simpler.
  - eru 11y ago
    Go has many more sacrifices in a typical game than chess, too.

_xander 11y ago

"The game has long interested AI researchers because of its complexity...the average 150-move game contains more possible board configurations — 10^170 — than there are atoms in the Universe, so it can’t be solved by algorithms that search exhaustively for the best move." [Source: http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234 http://www.nature.com/news/google-ai-algorithm-masters-ancie...]

moonshinefe 11y ago
Yeah interesting, so mathematically there are more moves in Go than the other games AI players have solved so far. Thanks for the info.
tromp 11y ago
208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 to be precise. Which is more than even the square of the number of atoms in the universe, showing how silly that comparison is... Btw, the quoted "the average 150-move game contains" makes no sense at all, since such a game contains only 151 positions.
- 1024core 11y ago
  Fold that friggin' number. It's causing everyone to scroll horizontally.
  - dang 11y ago
    We put two spaces ahead of it, which gives it 'pre' formatting that doesn't wrap.
  - awl130 11y ago
    +1

Lozzer 11y ago

Firstly there are vastly more positions in Go. Secondly, it's very hard to evaluate a Go position, especially at the start of the game when there are few stones on the board. In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1).

slm_HN 11y ago
>In chess you can get a long way using a simple evaluation (K=99, Q=9, R=5, B=3, N=3, P=1). I guess it depends on your idea of a "long way". Using only your simple evaluation a program would be rated somewhere around 1000-1200. It would lose every single game to an average tournament player.

gjm11 11y ago

Chess is quite tactical and brute-force-y -- the board is quite small, games are quite short, and there aren't all that many possible moves at any given point. A program can play pretty good chess on modern hardware just by alpha-beta searching with a fairly simple evaluation function for the leaves of the search tree. The best programs are cleverer than that; they have sophisticated evaluation functions, they prune and extend their searches, etc. But at heart, what makes them so strong is that they can search deeply. That approach doesn't work so well for go. The board is 6x the size, games are 4x as long, the "branching factor" (number of moves available in a given position) is 10x as large. (All figures very crudely approximate.) If you try to make a fairly-dumb searcher in go, it will play very badly. So how do humans manage to play well in go? By smarter searching, with a better idea of what moves are worth considering; by thinking strategically; by having a feel for the shape of a position ("moving here is likely to be very valuable"). Those are all things that feel like they are harder to make a computer do, and come closer to actual intelligence, than doing well at chess just by doing an enormous search. The first of those is certainly correct. AlphaGo (like most modern go programs) organizes its searches in quite a different way from a typical chess program. It's not clear how far it deserves to be called smarter, though, since a lot of what it's doing is playing out lots of games fairly stupidly[1] and seeing how they go on average. [1] Compared with how it actually plays. One of the achievements of AlphaGo, I think, is that it can reasonably quickly select moves for its playouts that are actually pretty good. The second is more debatable. But, e.g., AlphaGo selects and evaluates moves using neural networks trained on a large amount of high-quality play, and the effect of this is that given a position it can quickly "see" how good it thinks the position is and what moves might be effective, without doing any searching, as a result of feeding the position through a big neural network that does some mysterious calculation we don't understand well. Which is, at that level of abstraction, pretty similar to what you might say about a human go player. Whether any of this has any bearing on more general artificial intelligence is an entirely different question, which I will not attempt to get into.

gjm11 11y ago

Here's a way to measure the sophistication of a game of skill. Consider two players A and Z. A is a ten-year-old who has just been told the rules; Z is God. Now, in between them, put a series of other players B, ..., Y, where B beats A 2/3 of the time, C beats B 2/3 of the time, ..., Z beats Y 2/3 of the time. (We assume God doesn't use his magical divine powers to cheat by, e.g., making Y play bad moves.) Unfortunately, God is not readily available for comparison, so we'll use the best human players instead. How many links are there in that chain? The more there are, the more there is to learn about the game, and hence the deeper and more sophisticated the game is. (So you might think, anyway.) If you rate players using the Elo system, beating someone 2/3 of the time corresponds to being about 150 points stronger. A complete beginner at chess might have an Elo rating of 500, compared with the world champion somewhere around 2900, giving 16 links in the chain. In go, beating someone 2/3 of the time corresponds to being about one kyu/dan rank stronger. A complete beginner might be 30 kyu; the best players are stronger than 9 amateur dan, so that's at least 40 links in the chain. (Lower-numbered kyu ranks are stronger; after 1 kyu comes 1 dan, and then higher-numbered dan ranks are stronger.) So by this measure -- which you may or may not find convincing -- go is a more sophisticated game than chess. Here is the best argument I know against this definition. Define the game of "tenchess" as follows. To play a game of tenchess, you play ten games of chess and the winner is whoever wins more games (a draw if the same number). Then it's easy to see that tenchess has a longer chain, as defined above, than chess; if I win 2/3 of my chess games then I win 79% of my tenchess games, so I can win 2/3 of my tenchess games with a smaller advantage. (I am ignoring the existence of draws for this calculation, just for simplicity.) But surely tenchess isn't a deeper game than chess; it's just longer. Perhaps go's longer chain is just the result of its being a longer game.

cthor 11y ago
The tenchess counterargument doesn't work in the context of Elo (from which chain lengths are derived). A has 150 more Elo rating than B in chess. Elo says A has a 2/3 EV on the game result, and B has 1/3. In tenchess, A will get 20/3 points on average and B will get 10/3 points. A will have more points than B in 79% of tenchess games, but the Elo ratings will not change. Elo doesn't consider winning and losing as binary. (This is why draws behave sensibly.) Just as a tie between these players cause A to lose rating, so too would a marginal win from A.