When did the work start on beating each?
For Western Chess, at the end of the 1940s. Alan Turing wrote an algorithm to play chess. Of course, there were no computers that could run it, so Turing had to run the algorithm “by hand”.
Turing tested his algorithm playing against a friend of his in 1952. That is arguably the first “computer chess” game ever, although technically speaking there were no computers involved. For those interested, the game is here:
http://www.chessgames.com/perl/chessgame?gid=1356927
Chess was from that point on the permanent focus of a not insignificant amount of effort on the part of the AI community.
So, summing up: For chess, if we count the time from the beginnings with Alan Turing’s algorithm to 2005 (the last time a human being beat the best machine available), roughly 55+ years of effort were needed. However, for a real analogy with the present situation (the first victory of a computer playing Go against the world champion under standard tournament rules) we should be counting years until the first game won by a machine (Deep Blue) playing against the then world chess champion, Garry Kasparov, under standard tournament rules. That would be February 10, 1996. Thus, more like 45+ years in total.
For Go, the first program that could play Go was written in 1968. So, it has been 48 years to reach a situation like the one with Deep Blue in 1996 (the computer winning the first game against the top human player in a match under standard time controls).
Summing up: Getting an AI to win against the top human player in Chess and Go under standard time controls has taken roughly the same amount of time. Chess was first only because AI work on chess began earlier.
An excellent post, I would just take issue with the use of “only” in final sentence. I assume the vast increase in computing power between 1996 and 2016 is also a factor in Go programs now being competitive at the top level. You simply don’t need as much storage space for Chess. Or is this not an issue due to the way Go programs work? In any case, I stand by my comment.
It is not really much of an issue. Chess-playing programs and Go-playing programs use different approaches; it is a bit like comparing apples with oranges.
The most successful chess-playing programs go for a “brute-force” approach (mechanically explore the tree of moves to insane depths and choose the one that gives the best expected result at the end), combined with extensive libraries of openings and endgames that describe “perfect play” in those two situations.
This kind of approach for chess-playing programs is actually relatively recent: The “brute-force” thing was simply impossible until hardware capabilities reached a certain point that allowed for fast-enough processing (otherwise you would be waiting, like, 10 hours before the computer would make a move). This is actually a bit of a pity, because as soon as the hardware was fast and powerful enough, a lot of AI research on implementing the “feel of the board” was basically put aside. The “brute-force” approach is efficient, but it feels terribly clumsy to a certain type of romantic soul. I guess I am one of those romantic souls, at least a little 
But brute force is what defeated Garry Kasparov, and it is what chess-playing AIs are going to keep using.
Now, when it comes to Go, the “brute-force” approach is, as of now and for the foreseeable future, impractical. The tree of possible moves in Go explodes exponentially at a much higher rate than in chess.
Which is why, in the last few years, a lot of research was done in completely different directions, to wit: Using deep neural networks. Set up a huge multi-layer neural network, and train it to perform a given task. The revolutionary aspect of this Go-playing program is that they used a generic network, which potentially could be trained to do a bunch of different things, and gave it training to play Go.
(I am simplifying a LOT, but I hope I can convey how tremendously different those systems are from each other).
And the funny thing – Actually you can’t really understand why a neural network, in the end, behaves as it does… And very often it ends up displaying emergent behaviors that are totally unexpected.
(Example: In Google they took one of those deep neural networks and, without any particular preparation, began “showing” it YouTube videos and photos taken from the internet. After some time, the network, by itself, began identifying as “special” and reacting to a series of images… To wit, images and videos of cats.
The internet is made of cats, indeed).
Anyway, this is how AlphaGo works: Very deep neural network, coupled with libraries of josekis (standard sequences of play in Go) which has been trained by having it go through MILLIONS and MILLIONS of recorded Go games, and by having it play against clones of itself MILLIONS of times. This whole process induces changes in the internal weights of the connections between “neurons”, depending on whether a series of moves in the end lead to a win or a lose…
Another thing: In today’s game against Lee Sedol, AlphaGo played in a very different way than in the January match against the European champion. It actually played much better. In these few months, AlphaGo has “trained itself” to achieve a level of competence much higher than what it had in January. AlphaGo spent all this time playing go 24/7, reviewing thousands upon thousands of games at speed… And in barely three months improved its performance in ways that would take human players at least a couple of years to achieve.
I find this a little bit scary, as a matter of fact.
In any case, in my opinion, the most important aspect of AlphaGo is not how well it plays (and it plays mightily well, I may add) – it is that, at heart, it is just a generic neural network that has been trained to do a particular task… The same basic network can be trained to do other things.
I guess that this approached worked well to “crack” the game of Go because neural networks excel at pattern detection, and a big part of Go involves learning patterns.
I wonder whether this approach (pattern detection) would also work well with chess. It could be interesting to develop an “AlphaChess” and pit it against a brute-force system. I imagine that the brute-force system would win in the end… But I think that an hypothetical “AlphaChess” could put a good fight.
Fasinating.
I’m a keen chess player (in fact have to play a match in the Edinburgh League this evening) but must be one of the few with little interest in using computers to help me (which probably explains why I am not very strong).
I have read much about the strong human connections between ability in music and chess. I understand experts have put it down to pattern recognition as the main link. If that is correct, I would suspect there is something in your neural network chess programme - perhaps given enough time it could beat brute force programming?
Should have just called it a Go-Go Gadget
JoseB, I described your earlier post as “excellent” - your most recent one is fantastic. Many thanks for sharing your knowledge and fighting my ignorance.
Having said that, I still maintain that 20 (or perhaps 30) years ago, hardware limitations would have made it difficult or impossible for neural networks to work, at least at the speed you describe (e.g. they wouldn’t be able to play as many games against themselves in such a short space of time). Regardless of that, I totally understand your point and agree with what you say about chess. Tim Krabbe, a strong Dutch chess player (and creator of the amazing Chess Curiosities site) has said “computers don’t play chess”, which is exactly what you’re getting at. This article is now rather out of date and probably doesn’t apply to the latest programs, but it’s fun anyway.
I read an article about the match, and the human meatbag referred to AlphaGo’s play as “perfect.”
Pretty astonishing stuff.
My, you are going to make me blush, Dead Cat! Thanks for the compliments…
Just one comment to emphasize the difference between AlphaGo and current top chess programs: most of the training AlphaGo carries out is, basically, the same a human does-- study recorded games. The computer can do that extremely quickly. AlphaGo also.“trains” by solving Go problems and positions, and learning from that.
In contrast, chess-playing computers are fully programmed and cannot “learn” by themselves. Upgrades to their playing capabilities must be coded by their programmers. They do not adapt. They are the absolute best chess players since 2005, but they are essentially “frozen”.
To tell the truth, although I can’t help but finding it a little scary, I like the self-learning and self-improving ability of AlphaGo much more than the crystalline stasis of the top chess engines.
I believe (based on some of the videos put out by Google DeepMind) that AlphaGo actually uses two neural networks – one to suggest good potential moves at each step, and then another to evaluate the value of different positions. That way it can explore some number of moves forward (choosing only sequences of good potential moves) and see what puts it in the best position. This is, I think, similar to professional human Go players, who are looking several moves ahead but only considering the smart moves. A fully brute force approach (exploring all the possible moves at each step) isn’t possible because there are too many possible moves at each step. Apparently there are far more possible sequences of Go moves than there are atoms in the universe.
The other thing that evidently makes Go harder than chess (besides the larger number of possible moves) is that assigning value to different positions is trickier, since there aren’t any pieces that are inherently more valuable than others.
This is a really cool idea. 
Threads merged.
AlphaGo uses its neural nets as an approximation of the Q-value function in Monte-Carlo Tree Search, as well as a way to guess which move to try next in its search. In fact, the paper was on “Deep Q Networks”
What this essentially does is essentially pick a “promising looking” move, and then plays the rest of the game randomly as if a bunch of monkeys were doing it, down to a certain search depth (I think AlphaGo goes until the end of the game), and then estimates the overall “score” of those moves. This sounds dumb, but works surprisingly well for Go. It actually works surprisingly well even without the deep network.
I don’t want to undersell Alpha Go too much, they DID get an article in Nature, but their approach isn’t horribly… interesting if you understand the field. They basically took two well known methods (MCTS and Deep Networks) and glompf’d them together. It’s the kind of idea my adviser wouldn’t let me do because papers that do this generally aren’t well regarded unless they’re on very “hot” problems like Go.
The interesting bits are their approach to limited self-training, that is, training by playing against itself (which has theoretical problems but sometimes works in practice), and the engineering challenges. This is something that you pretty much need to be Google or IBM or Facebook to do, the vast majority of the work here is engineering work in making the Deep Network training and evaluation, and the MCTS, not take forever. MCTS is notoriously non-parallelizable, and they made a parallel evaluation of it work reasonably well, which is interesting. Still, the distributed server infrastructure you need for good (as opposed to merely reasonable) play is massive, even with all the crazy optimizations they did.
AlphaGo has won the second game of the series, with Lee Sedol playing first (black).
Both players ended up in time trouble, although Lee Sedol was in time trouble first, having to use extra time periods when AlphaGo still had 16 minutes left in the clock. However, the game went on, with Lee Sedol fighting tenaciously, and AlphaGo ended up having to use its own extra time periods.
At the end, however, Lee Sedol resigned. Will be checking the post-game press conference which should begin soon.
Link to a short article about today’s game:
Copypaste of a declaration of Lee Sedol during the press conference:
“Yesterday I was surprised but today it’s more than that — I am speechless”.
The score so far for this match is AlphaGo 2 - Lee Sedol 0. AlphaGo needs just one more win to take the match; Lee Sedol must win the three remaining games to get the prize.
Things are getting rea-a-a-ally interesting.
What could be really interesting would be to try to train a neural net AlphaChess against a brute-force system. I suppose that they might simply end up playing the same game over and over, but they figured out how to avoid that with the Go training, probably with some randomization of openings.
You think he even has a chance? I know nothing of Go or this grandmaster, but apparently this guy is (was) cocky, so I’m glad he’s getting his ass handed to him. From your article:
A reverse sweep after 2 losses seems like it would take a miracle.
Was he cocky or was he justified? All the literature makes it sound like he had every reason to believe that AlphaGo wouldn’t be able to play at a high level. His post-game remarks have been pretty humble, seems to me.
To be honest, I was also expecting Lee Sedol to win. He is the #1 player in the world, and recently he completely stomped over a challenger for his position. Besides, until, well, right now, all Go-playing computers have crashed and burned when confronted with truly high-level professional players. Some cockiness on his part is understandable.
His loss on the first day came as a shock to almost everybody, not least Lee Sedol himself. He may have thought that it was a fluke, and in the second game he changed tack, but ended up having to resign again (he also ended up in serious time trouble during the game – as I mentioned earlier, at a certain point, he was already in extra time while AlphaGo still had 16 minutes on the clock).
Now comes a rest day (the next game will be on saturday) and I am sure that Lee Sedol is going to be studying these two games like there is no tomorrow. He still has a chance, but if he wants to get the prize he MUST play perfectly from now on and win the last 3 games in a row. Possibly he underestimated AlphaGo in the beginning, but I think that he is doing that no longer. We will see.
There is a phenomenon that is particularly ironic, when we compare this tournament with the 1996 DeepBlue matches with Kasparov – When playing against chess computers, grandmasters usually tried to overwhelm the machine by using “strange” moves, unorthodox moves that led to really complex positions, hoping to drive the machine into a maze of possibilities. Kasparov did that against Deep Blue, and it worked for him in the end.
However, in these two games, the one making strange and unorthodox moves has been AlphaGo – more than once, AlphaGo made moves that either looked like mistakes or went against the received wisdom of the experts, and had the commenters scratching their heads. From this link, I copy-paste the relevant text:
Members of the Go community are as stunned with the inventive, aggressive way AlphaGo won as the fact that it did at all. “There were some moves at the beginning — what would you say about those three moves on the right on the fifth line?” American Go Association president Andy Okun asked VP of operations Andrew Jackson, who also happens to be a Google software engineer, at the venue following the match. “As it pushes from behind?” Jackson replied. “If I made those same moves…” Okun continued. “Our teachers would slap our wrists,” Jackson agreed. “They’d smack me!” says Okun.
And this may well introduce a new way of thinking about the game! Jackson and Okun continue, in the linked article:
- [But AlphaGo could also open up new avenues for the game] – “We’re absolutely in shock,” said Jackson. “There’s a real question, though. We’ve got this established Go orthodoxy, so what’s this going to reveal to us next? Is it going to shake things up? Are we going to find these things that we thought were true — these things you think you know and they just ain’t so?”*
The way AlphaGo is playing, it might show new ways of playing the game. In a way it feels a bit like the introduction of hypermodern openings in chess in the beginning of the 20th century, which also went against established wisdom.
As I said, things are getting rea-a-a-ally interesting.
I don’t know anything at all about Go beyond the most basic strategy involved - are AlphaGo’s strange strategies going to change the way the game is played, or is it only able to utilize such unorthodoxy because of its massive neural network and ability to see so much more depth than a human?
The commentators tend to remark on how puzzling and incomprehensible the moves are. So right now there’s no clear pathway towards the moves changing our theories of the game. But it’s early yet.