AlphaGo

AlphaGo logo

AlphaGo is a computer program developed by Google DeepMind in London to play the board game Go.^[1] In October 2015, it became the first computer Go program to beat a professional human Go player without handicaps on a full-sized 19×19 board.^[2]^[3] In March 2016, it beat Lee Sedol in the first three games in a five-game match, the first time a computer Go program has beaten a 9-dan professional without handicaps.^[4]. However, it lost to Lee Sedol in the fourth game.

AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play.

History and competitions

Go is considered much more difficult for computers to win than other games such as chess, because its much larger branching factor makes it prohibitively difficult to use traditional AI methods such as Alpha–beta pruning, Tree traversal and heuristic search.^[2]^[5]

Almost two decades after IBM's computer Deep Blue beat world chess champion Garry Kasparov in the 1997 match, the strongest Go programs using artificial intelligence techniques only reached about amateur 5 dan level,^[6] and still could not beat a professional Go player without handicaps.^[2]^[3]^[7] In 2012, the software program Zen, running on a four PC cluster, beat Masaki Takemiya (9p) two times at five and four stones handicap.^[8] In 2013, Crazy Stone beat Yoshio Ishida (9p) at four-stones handicap.^[9]

AlphaGo represents a significant improvement over previous Go programs. In 500 games against other available Go programs, including Crazy Stone and Zen,^[10] AlphaGo running on a single computer won all but one.^[11] In a similar matchup, AlphaGo running on multiple computers won all 500 games played against other Go programs, and 77% of games played against AlphaGo running on a single computer. The distributed version in October 2015 was using 1,202 CPUs and 176 GPUs.^[6]

Match against Fan Hui

In October 2015, the distributed version of AlphaGo defeated the European Go champion Fan Hui,^[12] a 2 dan (out of 9 dan possible) professional, five to zero.^[3]^[13] This is the first time a computer Go program has beaten a professional human player on a full-sized board without handicap.^[14] The announcement of the news was delayed until 27 January 2016 to coincide with the publication of a paper in the journal Nature^[6] describing the algorithms used.^[3]

Match against Lee Sedol

AlphaGo is currently challenging South Korean professional Go player Lee Sedol, who is ranked 9 dan,^[7]^{[needs update]} with five games taking place at the Four Seasons Hotel in Seoul, South Korea on 9, 10, 12, 13, and 15 March 2016,^[15]^[16] which will be video streamed live.^[17] Aja Huang, a DeepMind team member and amateur 6-dan Go player, will place stones on the Go board for AlphaGo, which will be running through Google's cloud computing with its servers located in the United States.^[18] The match will adopt the Chinese rules with a 7.5-point komi, and each side will have two hours of thinking time plus three 60-second byoyomi periods.^[19] The version of AlphaGo playing against Lee uses 1,920 CPUs and 280 GPUs.^[20]

Four games of the match have been played so far, the first three of which were won by AlphaGo following resignations by Lee Sedol.^[21]^[22] Lee Sedol managed to beat AlphaGo in the fourth game, winning by resignation at move 180.

The prize is $1M. Since AlphaGo has won three out of five and thus the series, the prize will be donated to charities, including UNICEF.^[23] Lee Sedol will receive at least $150,000 for participating in all the five games and an additional $20,000 for each win.^[19]

Hardware

AlphaGo was tested on hardware with various numbers of CPUs and GPUs, running in asynchronous or distributed mode. Two seconds of thinking time is given to each move. The resulting Elo ratings are listed below.^[6]

Configuration and performance
Configuration	Search threads	No. of CPU	No. of GPU	Elo rating
Asynchronous	40	48	1	2,151
Asynchronous	40	48	2	2,738
Asynchronous	40	48	4	2,850
Asynchronous	40	48	8	2,890
Distributed	12	428	64	2,937
Distributed	24	764	112	3,079
Distributed	40	1,202	176	3,140
Distributed	64	1,920	280	3,168

Algorithm

AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play. It uses Monte Carlo tree search, guided by a "value network" and a "policy network," both implemented using deep neural network technology.^[2]^[6] A limited amount of game-specific feature detection pre-processing is used to generate the inputs to the neural networks.^[6]

The system's neural networks were initially bootstrapped from human gameplay expertise. AlphaGo was initially trained to mimic human play by attempting to match the moves of expert players from recorded historical games, using a database of around 30 million moves.^[12] 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.^[2]

Style of play

AlphaGo has been described by the 9-dan player Myungwan Kim as playing "like a human" in its games against Fan Hui.^[24] The match referee Toby Manning has described the program's style as "conservative."^[25]

Responses to 2016 victory

AI community

AlphaGo's March 2016 victory was a major milestone in artificial intelligence research.^[26] Go had previously been regarded as a hard problem in machine learning that was expected to be out of reach for the technology of the time.^[26]^[27]^[28] Most experts thought a Go program as powerful as AlphaGo was at least five years away;^[29] some experts thought that it would take at least another decade before computers would beat Go champions.^[30]^[31] Most observers at the beginning of the 2016 matches expected Lee to beat AlphaGo, and even the designers of AlphaGo were surprised by its success: Google DeepMind co-founder Demis Hassabis said he was "stunned and speechless".^[26]

With games such as checkers, chess, and now Go won by computer players, victories at popular board games can no longer serve as major milestones for artificial intelligence in the way that they used to. Deep Blue's Murray Campbell called AlphaGo's victory "the end of an era... board games are more or less done and it's time to move on."^[26]

When compared with Deep Blue or with Watson, AlphaGo's underlying algorithms are potentially more general-purpose, and may be evidence that the scientific community is making progress toward artificial general intelligence.^[32] Some commentators believe AlphaGo's victory makes for a good opportunity for society to start discussing preparations for the possible future impact of machines with general purpose intelligence. (Note that AlphaGo itself only knows how to play Go, and doesn't possess general purpose intelligence: AlphaGo will not wake up one morning and decide it wants to learn how to use firearms.^[26]) In March 2016, AI researcher Stuart Russell stated that "AI methods are progressing much faster than expected, (which) makes the question of the long-term outcome more urgent," adding that "in order to ensure that increasingly powerful AI systems remain completely under human control... there is a lot of work to do."^[33] Some scholars, such as Stephen Hawking, warn that some future self-improving AI could gain actual general intelligence, leading to an unexpected AI takeover; other scholars disagree: AI expert Jean-Gabriel Ganascia believes that "Things like 'common sense'... may never be reproducible",^[34] and says "I don't see why we would speak about fears. On the contrary, this raises hopes in many domains such as health and space exploration."^[35] Computer scientist Richard Sutton said "I don't think people should be scared... but I do think people should be paying attention."^[36]

Go community

Go is a popular game in South Korea, China and Japan, and the 2016 matches were watched and analyzed by millions of people worldwide.^[26] Many top Go players characterized AlphaGo's unorthodox plays as seemingly-questionable moves that initially befuddled onlookers, but made sense in hindsight:^[30] "All but the very best Go players craft their style by imitating top players. AlphaGo seems to have totally original moves it creates itself."^[26] AlphaGo appeared to have unexpectedly become much stronger, even when compared with its October 2015 match^[37] where a computer had beat a Go professional for the first time ever without the advantage of a handicap.^[38] China's number one player, teenager Ke Jie, claims that he would be able to beat AlphaGo, but has so far refused to play against it for fear that it would "copy my style".^[39]

Toby Manning, the referee of AlphaGo's match against Fan Hui, and Hajin Lee, secretary general of the International Go Federation, both reason that in the future, Go players will get help from computers to learn what they have done wrong in games and improve their skills.^[38]

Lee apologized for his losses, stating that "I misjudged the capabilities of AlphaGo and felt powerless."^[26] He emphasized that the defeat was "Lee Se-dol's defeat" and "not a defeat of (all) human beings," and pointed out that the program does have weaknesses. Lee said his eventual loss to a machine was "inevitable" but stated that "robots will never understand the beauty of the game the same way that we humans do."^[34]

Similar systems

Facebook has also been working on their own Go-playing system darkforest, also based on combining machine learning and tree search.^[25]^[40] Although a strong player against other computer Go programs, as of early 2016, it had not yet defeated a professional human player.^[41] darkforest has lost to CrazyStone and Zen and is estimated to be of similar strength to CrazyStone and Zen.^[42]