AlphaGo 1-0 (AlphaGo vs Lee Sedol)

Last night, the computer program AlphaGo defeated professional 9-dan Go player Lee Sedol in the first game of a five-game match.  This is the first time a computer player has defeated a 9-dan player without a handicap.  The second game occurs tonight.  YouTube has the video of the first game and Wikipedia has a good article for the entire 5-game challenge.

This match is highly anticipated after AlphaGo defeated 2-dan Fan Hui back in October.  That was the first time a computer defeated a professional Go player on a full sized (19 x 19) board.  It was at this point that it became clear that AlphaGo had a chance against even the strongest human opponent.  The hype was set for the challenge with Lee Sedol.  The New York Times published a good article in the aftermath of the victory over Fan Hui.  They brought in some experts (including my colleague Bob Hearn) to explain better how AlphaGo works.

AlphaGo uses a combination of Monte Carlo Tree Search (MCTS) algorithms and newer Deep Learning techniques to win.  The MCTS algorithms have been around for about a decade or so, and brought about the first victories by computer players on 9x9 boards.  The basic idea behind this is that it randomly plays a bunch of complete games to their end, using the win/loss result of the last game to decide which game to explore next.  By playing a few thousand games and intelligently choosing which game to try next, the search can help narrow down which move to make.

Deep Learning comes in to play in two ways in AlphaGo.  First, it can approximate the win/loss value of each game early enough that the entire thing doesn't need to be played out.  (This may sound like a bad idea, but the game played by a pure MCTS algorithm is an approximation anyways, as the later moves are chosen completely at random.)  Second, it helps choose which of the games to simulate.  I don't know enough about deep learning (yet) to better describe the details of how it solves each of these problems.

This match is very reminiscent of Garry Kasparov's loss against Deep Blue in 1997.  That was the first time the reigning human world Chess champion lost to a computer.  At that time, Go was still unreachable by computer players, a Holy Grail that would require stronger computers and more sophisticated algorithms to attain.  After AlphaGo's win yesterday, perhaps the Grail will be captured soon.

As Bob Hearn points out in the NYT article:

Go was the last bastion of human superiority at what’s historically been viewed as quintessentially intellectual. This is it. We’re out of games now. This is seen by some as a harbinger of the approaching singularity.

I'm very anxious to see what happens over the course of the next week!

Update: post about the second game.