AlphaGo versus Lee Sedol

Go match between AlphaGo and Lee Sedol
AlphaGo versus Lee Sedol
4–1
Seoul, South Korea, 9–15 March 2016
Game one AlphaGo won.
Game two AlphaGo won.
Game three AlphaGo won.
Game four Lee Sedol won.
Game five AlphaGo won.

AlphaGo versus Lee Sedol, or Google DeepMind Challenge Match, was a five-game Go match between 18-time world champion Lee Sedol and AlphaGo, a computer Go program developed by Google DeepMind, played in Seoul, South Korea between 9 and 15 March 2016. AlphaGo won all but the fourth game;[1] all games were won by resignation.[2] The match has been compared with the historic chess match between Deep Blue and Garry Kasparov in 1997.

The winner of the match was slated to win $1 million. Since AlphaGo won, Google DeepMind stated that the prize will be donated to charities, including UNICEF, and Go organisations.[3] Lee received $170,000 ($150,000 for participating in the five games and an additional $20,000 for winning one game).[4]

After the match, The Korea Baduk Association awarded AlphaGo the highest Go grandmaster rank – an "honorary 9 dan". It was given in recognition of AlphaGo's "sincere efforts" to master Go.[5] This match was chosen by Science as one of the Breakthrough of the Year runners-up on 22 December 2016.[6]

Contents

BackgroundEdit

Difficult challenge in artificial intelligenceEdit

Main article: Computer Go
External video
  Machine trains self to beat humans at world's hardest game, Retro Report, 2:51, Retro Report[7]

Go is a complex board game that requires intuition, creative and strategic thinking.[8][9] It has long been considered a difficult challenge in the field of artificial intelligence (AI) and is considerably more difficult[10] to solve than chess. Many in the field of artificial intelligence consider Go to require more elements that mimic human thought than chess.[11] Mathematician I. J. Good wrote in 1965:[12]

Go on a computer? – In order to programme a computer to play a reasonable game of Go, rather than merely a legal game – it is necessary to formalise the principles of good strategy, or to design a learning programme. The principles are more qualitative and mysterious than in chess, and depend more on judgment. So I think it will be even more difficult to programme a computer to play a reasonable game of Go than of chess.

Prior to 2015,[13] the best Go programs only managed to reach amateur dan level.[14] On the small 9×9 board, the computer fared better, and some programs managed to win a fraction of their 9×9 games against professional players. Prior to AlphaGo, some researchers had claimed that computers would never defeat top humans at Go.[15] Elon Musk, an early investor of Deepmind, said in 2016 that experts in the field thought AI was 10 years away from achieving a victory against a Go top professional player.[16]

The match AlphaGo versus Lee Sedol is comparable to the 1997 chess match Deep Blue versus Garry Kasparov. There IBM's Deep Blue computer's defeat of reigning champion Kasparov is seen as the symbolic point where computers became better than humans at chess.[17]

AlphaGo is most significantly different from previous AI efforts in that it applies neural networks, in which evaluation heuristics are not hard-coded by human beings, but instead to a large extent learned by the program itself, through tens of millions of past Go matches as well as its own matches with itself. Not even AlphaGo's developer team are able to point out how AlphaGo evaluates the game position and picks its next move. These networks guide a Monte Carlo tree search which explores many moves into the future.

Related research results are being applied to fields such as cognitive science, pattern recognition and machine learning.[18]

Match against Fan HuiEdit

 
Fan Hui vs AlphaGo – Game 5

AlphaGo defeated European champion Fan Hui, a 2 dan professional, 5–0 in October 2015, the first time an AI had beaten a human professional player at the game on a full-sized board without a handicap.[19][20] Some commentators stressed the gulf between Fan and Lee, who is ranked 9 dan professional.[21] Computer programs Zen and Crazy Stone have previously defeated human players ranked 9 dan professional with handicaps of four or five stones.[22][23] Canadian AI specialist Jonathan Schaeffer, commenting after the win against Fan, compared AlphaGo with a "child prodigy" that lacked experience, and considered, "the real achievement will be when the program plays a player in the true top echelon." He then believed that Lee would win the match in March 2016.[20] Hajin Lee, a professional Go player and the International Go Federation's secretary-general, commented that she was "very excited" at the prospect of an AI challenging Lee, and thought the two players had an equal chance of winning.[20]

In the aftermath of his match against AlphaGo, Fan Hui noted that the game had taught him to be a better player, and to see things he had not previously seen. By March 2016, Wired reported that his ranking had risen from around 633 to the 300s.[24]

PreparationEdit

Go experts found errors in AlphaGo's play against Fan, in particular relating to a lack of awareness of the entire board, but before the opening game against Lee, it was unknown how much the program had improved its game since its October match.[21][25] AlphaGo was not tailored to play against Lee Sedol, which would anyways be hard to do because training AlphaGo requires tens of millions of games, and a few hundred or thousand games from a particular player would not be enough to alter AlphaGo's play. Instead, AlphaGo's training was started with games of strong amateur players from internet Go servers, after which AlphaGo trained by playing against itself; there were no Lee Sedol games in AlphaGo's training data.[26][27]

PlayersEdit

AlphaGoEdit

Main article: AlphaGo
 
AlphaGo logo

AlphaGo is a computer program developed by Google DeepMind to play the board game Go. AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play. The system's neural networks were initially bootstrapped from human game-play expertise. AlphaGo was initially trained to mimic human play by attempting to match the moves of expert players from recorded historical games, using a KGS Go Server database of around 30 million moves from 160,000 games by KGS 6 to 9 dan human players.[13][28] Once it had reached a certain degree of proficiency, it was trained further by being set to play large numbers of games against other instances of itself, using reinforcement learning to improve its play.[29] The system doesn't use a "database" of moves to play. As one of the creators of AlphaGo explained:[30]

Although we have programmed this machine to play, we have no idea what moves it will come up with. Its moves are an emergent phenomenon from the training. We just create the data sets and the training algorithms. But the moves it then comes up with are out of our hands—and much better than we, as Go players, could come up with.

The version of AlphaGo that played against Lee used a similar amount of computing power as in the match against Fan Hui,[31] where it used 1,202 CPUs and 176 GPUs.[13] The Economist reported that it used 1,920 CPUs and 280 GPUs.[32] Google has also stated that its proprietary tensor processing units were used in the match against Lee Sedol.[33]

Lee SedolEdit

Main article: Lee Sedol
 
Lee Sedol in 2012

Lee Sedol is a professional Go player of 9 dan rank[34] and is one of the strongest players in the history of Go. He started his career in 1996 (promoted to professional dan rank at the age of 12), winning 18 world championships since then.[35] He is a "national hero" in his native South Korea, known for his unconventional and creative play.[36] Lee Sedol initially predicted he would defeat AlphaGo in a "landslide".[36] Some weeks before the match he won the Korean Myungin title, a major championship.[37]

GamesEdit

The match was a five-game match with 1 million US dollars as the grand prize,[3] using Chinese rules with a 7.5-point komi.[4] For each game there was a 2-hour set time limit for each player followed by three 60-second byo-yomi overtime periods.[4] Each game started at 13:00 KST (04:00 GMT).[38]

The match was played at the Four Seasons Hotel in Seoul, South Korea in March 2016 and was video-streamed live with commentary by Michael Redmond (9-dan professional) and Chris Garlock.[39][40][41] Aja Huang, a DeepMind team member and amateur 6-dan Go player, placed stones on the Go board for AlphaGo, which ran through the Google Cloud Platform with its server located in the United States.[42]

SummaryEdit

Game Date Black White Result Moves
1 9 March 2016 Lee Sedol AlphaGo Lee Sedol resigned 186 Game 1
2 10 March 2016 AlphaGo Lee Sedol Lee Sedol resigned 211 Game 2
3 12 March 2016 Lee Sedol AlphaGo Lee Sedol resigned 176 Game 3
4 13 March 2016 AlphaGo Lee Sedol AlphaGo resigned 180 Game 4
5 15 March 2016 Lee Sedol[note 1] AlphaGo Lee Sedol resigned 280 Game 5
Result:
AlphaGo 4 – 1 Lee Sedol
^ note 1: For Game Five, under the official rules, it was intended that the colour assignments would be done at random.[43] However, during the press conference after the fourth match, Lee requested "... since I won with white, I really do hope that in the fifth match I could win with black because winning with black is much more valuable."[44] Hassabis agreed to his proposition.

Game 1Edit

AlphaGo (white) won the first game. Lee appeared to be in control throughout much of the match, but AlphaGo gained the advantage in the final 20 minutes and Lee resigned.[45] Lee stated afterwards that he had made a critical error at the beginning of the match; he said that the computer's strategy in the early part of the game was "excellent" and that the AI had made one unusual move that no human Go player would have made.[45] David Ormerod, commenting on the game at Go Game Guru, described Lee's seventh stone as "a strange move to test AlphaGo's strength in the opening", characterising the move as a mistake and AlphaGo's response as "accurate and efficient". He described AlphaGo's position as favourable in the first part of the game, considering that Lee started to come back with move 81, before making "questionable" moves at 119 and 123, followed by a "losing" move at 129.[46] Professional Go player Cho Hanseung commented that AlphaGo's game had greatly improved from when it beat Fan Hui in October 2015.[46] Michael Redmond described the computer's game as being more aggressive than against Fan.[47]

According to 9-dan Go grandmaster Kim Seong-ryong, Lee seemed stunned by AlphaGo's strong play on the 102nd stone.[48] After watching AlphaGo make the game's 102nd move, Lee mulled over his options for more than 10 minutes.[48]

                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
First 99 moves
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
Moves 100–186

Game 2Edit

AlphaGo (black) won the second game. Lee stated afterwards that "AlphaGo played a nearly perfect game",[49] "from very beginning of the game I did not feel like there was a point that I was leading".[50] One of the creators of AlphaGo, Demis Hassabis, said that the system was confident of victory from the midway point of the game, even though the professional commentators could not tell which player was ahead.[50]

Michael Redmond (9p) noted that AlphaGo's 19th stone (move 37) was "creative" and "unique".[30] Lee took an unusually long time to respond to the move.[30] An Younggil (8p) called AlphaGo's move 37 "a rare and intriguing shoulder hit" but said Lee's counter was "exquisite". He stated that control passed between the players several times before the endgame, and especially praised AlphaGo's moves 151, 157, and 159, calling them "brilliant".[51]

AlphaGo showed anomalies and moves from a broader perspective which professional Go players described as looking like mistakes at the first sight but an intentional strategy in hindsight.[52] As one of the creators of the system explained, AlphaGo does not attempt to maximize its points or its margin of victory, but tries to maximize its probability of winning.[30][53] If AlphaGo must choose between a scenario where it will win by 20 points with 80 percent probability and another where it will win by 1 and a half points with 99 percent probability, it will choose the latter, even if it must give up points to achieve it.[30] In particular, move 167 by AlphaGo seemed to give Lee a fighting chance and was declared to look like an obvious mistake by commentators. An Younggil stated "So when AlphaGo plays a slack looking move, we may regard it as a mistake, but perhaps it should more accurately be viewed as a declaration of victory?"[54]

                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
First 99 moves
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
Moves 100–199