Lee Sedol wins Game 4! (1-3 vs AlphaGo)

Lee Sedol took home the victory late last night/early this morning.  He started the game very copying his opening moves from Game 2, expecting AlphaGo to follow suit, which it did.  Lee didn't follow his old moves for very long, however.  From reading some commentary on GoGameGuru, it sounds like he went for a tough all-or-nothing strategy instead of letting the field get divided up into lots of little battles that AlphaGo could weigh and evaluate well. 

Around 78 moves in, he made a move that was really highly regarded by others, and 10 moves later, AlphaGo started making a bunch of moves that onlookers thought were very bad.  Is it because there's an inherent weakness in algorithms that utilize Monte Carlo Tree Search?  Or is it because AlphaGo couldn't properly see the strength in Lee's move at 78?  If that move only works if a few other exact plays get made, then perhaps AlphaGo never tried those paths and didn't see what was coming. 

I am really excited to see that Lee, representing Team Humans, managed to recognize and exploit a weakness in AlphaGo.  Although he might not have another winning strategy to employ in the next game (as he'll be playing as Black instead of White) I still hope he can manage to push out a win.

AlphaGo 3-0 (vs Lee Sedol)

AlphaGo sealed the match against Lee Sedol with a third straight win.  Wow.  YouTube link to the game. 

Is this the end of humans competing with computers in Go?  Not exactly.  I just read a great reddit post about Chess after Garry Kasparov vs. Deep Blue in 1997.   Humans certainly didn't give up and only six years later, Kasparov drew against a more powerful Deep Junior.

I expect that humans will get more used to playing computer opponents and perhaps tip the scales back.  As more games with strong computer players are played, the new strategies can be studied and humans can adapt to them.

It'll be interesting to see how that plays out.  The next two games between AlphaGo and Lee might be indicative of how quickly humans can adapt to the new Go gamescape.

SmartGo article: AlphaGo Don't Care

Bob Hearn shared this wonderful article on smartgo.com by Anders Kierulf: AlphaGo don't care. 

I loved this piece, mostly because it really hits on an important aspect of the theoretical study of combinatorial games.  There is a real "psychology" aspect to a lot of the strategies.  I am not familiar with the Go terminology of the different move/structure types in the article (e.g. "tenuki", "extend at the bottom", and "peep").  These are human ways to describe different strategies and patterns. 

As the article reiterates: "AlphaGo don't care."  It doesn't lose universal focus to get stuck in local duels.  Each turn, it reevaluates the gameboard as a whole.  It doesn't care about the order of the previous plays, data that doesn't change the outcome of the game.

The same is true in CGT.  The options from a position depend only on the information of that position, not the history of plays nor the psychological battle between the two players.  The value of the game is irrelevant (though it may be very hard to calculate exactly).

From the article:

Lee Sedol threatens the territory at the top with 166? AlphaGo don’t care, it just secures points in the center instead. Points are points, it doesn’t matter where on the board they are.

It doesn't matter that Lee Sedol last moved near the top, AlphaGo just goes wherever it thinks it can amass the most points, not where it thinks the other player is going to focus their efforts.  The actual temperature of the regions is more important than which pieces were the most recent plays.

The third game is tonight!

AlphaGo 2-0 (vs Lee Sedol)

AlphaGo defeated Lee Sedol again last night.  BBC has a nice story about the game.  It looks like AlphaGo's moves in this game were a bit less shocking to the 9-dan champion Lee.  My second-hand perspective on this is a bit dire; I'll admit that I'm rooting for humanity here.  If Lee has a hard time reviewing this game and figuring out where he might have made some grand mistakes, the likelihood of improvement in the next two days (before the next game) is low.  Unless he can spot a weakness in AlphaGo's play, the Holy Grail of Go might fall.

YouTube has a video of the second game.

Good luck to Lee in the next game!

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.

2016 Portuguese CG Tournaments

Yesterday, Ludus ran the annual Math Games tournament for elementary, middle, and high school students.

Here's the English version of the site with lots of pictures: http://www.di.fc.ul.pt/~jpn/cnjm12/  (I'm only familiar with two of the games they played.)

Swiss Museum of Games

Planning a trip to Switzerland soon?  If you're on Lake Geneva near Montreux, you might be surprised to find a museum dedicated to board games!  The Swiss Museum of Games (Musee Suisse de Jeu) occupies a castle directly on the lake and it looks like they have great exhibits and activities!

I hope someday I can get over there and check things out first-hand.  It looks like right now they're doing a cool exhibition on Mahjong that ends this month.  Their permanent collection has a potpourri of games from many different cultures.