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.
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.
> In go, beating someone 2/3 of the time corresponds to being about one kyu/dan rank stronger
This isn't true. One kyu/dan rank stronger means being 1 stone stronger (so winning 50% of the time when playing White with reverse komi). In practice this may correspond to winning 2/3 of the time with normal komi for high dan players, but that doesn't hold for low kyu players. A 29k has maybe a 51% chance of winning against a 30k because both will make huge mistakes. So although the 29k can score on average 13-15 more points than the 30k in a given game, this advantage is swamped by the large standard deviation of scores in beginner games, turning the win/loss outcome into essentially a coin flip.
Fair comment about very weak players. My impression is that the element of chance goes way down well before you get to high dan level, though. How sure are you that I'm wrong?
Quite sure. 17k players still make many huge mistakes, and at the other extreme, God (say 13d) would win 100% of the time against a 12d player. Given that the win ratio for a one rank difference starts at 50% for extreme beginners and ends at 100% for God, maybe you should be the one explaining why you'd expect a significant plateau at 2/3 instead of a smooth increase.
I agree. In particular, I wasn't arguing for anything special to happen at p=2/3. I was hopeful, though, that p=2/3 might be a tolerable approximation over a reasonable range of skill levels.
Having played a bit with some toy models, I've changed my mind a bit; my guess is that p=2/3 is a reasonable approximation for few-dan and few-kyu amateurs, but that outside, say, the 5k-5d range it's far enough off to make a substantial difference.
So, what does this do to those (anyway fairly bogus) "depth" figures? My crappy toy model suggests that for a 2/3 win probability you need a 3-rank difference around 24k, a 2-rank difference around 12k, a 1-rank difference around 2d, a 0.5-rank difference around 8d. And I estimate God at 15 amateur dan (if Cho Chikun is 9p and needs 4 stones from God then God is 21p; if, handwavily, 9d=3p and one p-step is 1/3 the size of one d-step, then God is 21p = (3+18)p = (9+6)d = 15d). So we need maybe 20 steps from God to 5d, then maybe 10 from there to 5k, then maybe 5 from there to 15k, then maybe 5 from there to 30k. That's 40 steps -- not so very different from what we get just by pretending one rank = one "2/3 win probability" step, as it happens.
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.
I think I wasn't clear enough. Here is how you play a game of tenchess. (1) Play ten games of chess. (2) You get 0 points if you won fewer chess games than your opponent, 1 point if you won more, 1/2 a point if you won the same number.
In particular, you don't get the total number of points you'd have got by playing the chess games individually. You get 0, 1/2, or 1. In particularly particular, A doesn't get any fewer points from a marginal win than from a blowout. (Just as, when playing chess, you don't get fewer points from taking 100 moves to grind out a tiny positional advantage than from a 20-move brilliancy.)
So A and B don't get 20/3 and 10/3 points on average from a game of tenchess; that's the number of "chess points" they get on average, but the average of the number of chess points isn't a thing that actually matters when they're playing tenchess.
(If A wins 2/3 of the time at chess and they never draw, then it turns out that A gets about 0.855 points per tenchess game.)
"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."
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.
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).
>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.
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.
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.
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.
Maybe Go has way more moves possible and emergent strategies or something I'm not taking into account.