AlphaGo beats Lee Sedol in game one

by admin on March 9, 2016

I am completely unqualified to talk about anything go-related, but still chess fans might relate to this news. In the first game of the match between AlphaGo (Google’s deep neural network-based AI) and Lee Sedol (generally considered the strongest go player in the world), the computer won by resignation. The commentary I read suggested that Sedol had played a little bit unorthodoxly in the opening, had managed to come back to a roughly equal position, but then made a mistake and got ground down in the endgame.

So many parallels to Deep Blue versus Kasparov, and also a few differences.

  • Kasparov lost his first game in the 1996 match, but came back to win the match, 4-2. If anything, coming back is easier in go because there are no draws. (Draws, or jigo, are ultra-rare anyway, and ruled out by the match rules concerning komi … see below.) Will we see a repeat?
  • On the other hand, Kasparov lost the second match in 1997 in part because he played very uncharacteristic openings, especially his disastrous Caro-Kann in game six. I hope that Lee Sedol will realize that there is nothing to be gained by departing from what he is comfortable with.
  • The shock of go players is very reminiscent of 1996 and 1997. Sedol said in interviews afterwards that he was completely taken aback by the computer’s strength. Even when he was behind, he still thought he was going to win, but the computer absolutely gave him no opportunities.
  • A big difference is the respect of both sides for each other. At least in their public statements. Instead of Kasparov’s bitter complaining that somebody must have been giving the computer moves behind the scenes, we have Sedol congratulating the programmers on their great accomplishment.
  • For any go experts out there: is the komi too much? This is the margin that the Black player (who goes first) has to win by. From what I read, typical komi range from 4.5 points to 7.5 points. This match is at the high end, with 7.5 points. Sedol was actually ahead on the board and would have probably won by 2 to 5 points, but resigned because he could not see any way to win by 8 points. This is troubling, because Sedol will play three games with Black, while AlphaGo is only playing two. The komi is supposed to even the playing field, but if it’s too high then it has just skewed the playing field in favor of AlphaGo.

Anyway, it’s fascinating to re-live history, and it will be interesting to see what the other four games have in store!

By the way, if anybody wants to read my pre-match article about the Lee Sedol – AlphaGo match, you can find it here. I was pleased to hear that it is currently the most-read story on the Science magazine website!

P.S. The editors’ decision to capitalize “Go” throughout the article is a little bit unorthodox. It’s unfortunate that the name of the game is such a common English word. I guess it’s too late to start calling it “baduk” (the Korean name) or “weiqi” (the Chinese name).

Print Friendly

{ 5 comments… read them below or add one }

Dan Schmidt March 9, 2016 at 12:20 pm

Many little comments:

– I see Go capitalized quite often, because as you note the English word is so common.

– You can still have draws even with non-integer komi, although they are exceedingly rare, due to a perpetual-check-like situation (search for “triple ko”).

– My understanding is that they will do nigiri again for the last game (“flipping a coin” for color) so Lee Sedol is not guaranteed to get three Blacks.

– The main current guesses for the proper komi are 6.5 and 7.5 (4.5 is clearly far too low), so I don’t think 7.5 is particularly high. I think at the absolute worst it would give White a 52-48 advantage or so. One does play with a different style as Black vs White, so it’s possible in theory that either Lee Sedol or AlphaGo is more vulnerable with one color or the other, but they’re both so good that I don’t think it should matter. It’s possible that Lee Sedol could feel more comfortable with one color or the other against the computer, though.

I look forward to the other four games; I think they should be very interesting. This one certainly was.

Reply

paul b. March 9, 2016 at 9:27 pm

It’s interesting that Kasparov played the Caro Kann against Big Blue. When he started to study chess under the Soviets, the Caro Kann was the first black opening that he was required to master, so it seems that he was going back to his roots.

I read Dana’s Science article and I find a disconnect: if poker is played over the internet then where is the human element? It would seem that the optimum poker strategy on the web is simply to play the hands using probability theory along with game theory; in short, a purely mathematical approach and that means letting the computer play everything. Decades ago I read a popularized explanation of game theory as it was developed by Neuman and Oskar Morgenstern and I came away with the idea that the mathematics of poker had been resolved. Seems that I’m wrong. I’m not a math so it would be great if Dana could provide some insights into the state of current poker strategy.

Reply

admin March 10, 2016 at 9:57 am

Excellent question! I did not have enough space to fully explain this in the article (since my main focus was computer go). It was explained to me very well by Nikolai Yakovenko, a former poker pro *and* a deep neural net researcher who used to work with Google. Yes, in the two-person game, game theory says that both players should play a Nash equilibrium strategy. But if everyone plays the optimal strategy, then poker becomes a game of luck. The skill in poker is recognizing the things that your opponent is doing wrong. If you can pin down your opponent’s faults, you can make much more money by exploiting them, *even though* that means playing a non-optimal strategy yourself. You’re like a casino — you don’t need to rely on luck at all.

To see why this matters, imagine a three-player table with Poker Pro, Computer Program, and Poker Novice. Poker Pro builds up a big lead in chips by taking advantage of Poker Novice’s blunders while Computer Program makes less money by playing its optimal strategy. After Poker Novice has been eliminated, now Poker Pro beats Computer Program by switching to an optimal strategy and capitalizing on his chip lead.

In the two-person game, I’m told that Fixed Limit Hold’Em has been close to solved, so computers can play close to a Nash equilibrium strategy and you can’t beat them. No Limit Hold’Em is not solved yet, I guess because the space of possible actions is much larger.

Reply

Dan Schmidt March 10, 2016 at 11:15 am

If you’re not intimidated by math (I know Dana isn’t!), The Mathematics of Poker by Chen and Ankenman is a very interesting exploration of the subject. They start with the simplest possible game (I think something like a three-card deck with fixed bets) and work their way up. It’s fascinating to see how it becomes game-theoretically optimal to bluff some fraction of the time.

Reply

paul b. March 10, 2016 at 10:23 am

John Von Neumann got into game theory after watching his college friends play poker. He determined that poker required more complex calculations than chess due to the unknowns in poker such as bluffing. Neumann said that true poker is played without limits on the maximum bet, therefore poker should be played only between players of equal financial means.

Reply

Leave a Comment

Previous post:

Next post: