AlphaGo

• 1. Introduction

  ›

  AlphaGo is a computer program that plays Go, the ancient board game long considered the most complex strategic pursuit ever devised by human minds. On a March evening in 2016, inside the Four Seasons Hotel in Seoul, South Korea, a machine sat down across from Lee Sedol, one of the finest Go players alive, and won. Not just once. Four times out of five. The world paid attention. Perhaps a hundred million people worldwide watched the match unfold.

  This was not supposed to happen yet. Most experts believed a program as powerful as AlphaGo was at least five years away. Some thought it would take a decade. Before the first stone was placed, most observers expected Lee to win. What changed everything was a program built in London by a company called DeepMind, and the question its victory raised has not gone away: when a machine beats humanity's best thinker at its most demanding game, what does that mean for the rest of us?

• 2. Why Go Was Different

  ›

  Go had held out against computers for almost two decades after IBM's Deep Blue beat world chess champion Garry Kasparov in 1997. The reason was not stubbornness but mathematics. Go's enormous branching factor makes traditional AI methods, including alpha-beta pruning, tree traversal, and heuristic search, practically useless. Its strategic and aesthetic character makes it nearly impossible to write a simple evaluation function that tells a computer whether a position is good or bad.

  By 2012, the best Go programs could only match the level of an amateur 5-dan player, far below any professional. That year, the software Zen, running on a four-PC cluster, managed to beat professional Masaki Takemiya only at a five-stone handicap. In 2013, Crazy Stone beat Yoshio Ishida at a four-stone handicap. These were incremental steps, and a handicap of several stones is a very large advantage to give away. Beating a professional without any handicap at all seemed a distant dream.

  According to DeepMind's David Silver, the AlphaGo research project formed around 2014 with a specific goal: test how well a neural network using deep learning could compete at Go. When AlphaGo running on a single computer was pitted against available rivals including Crazy Stone and Zen in 500 test games, it won all but one.

• 3. The Algorithm Inside

  ›

  AlphaGo combines machine learning with a method called Monte Carlo tree search, guided by two distinct neural networks. The first is a value network, which estimates the probability of winning from any given position. The second is a policy network, which identifies the most likely strong moves. Both networks are convolutional neural networks with 12 layers, trained through reinforcement learning.

  The system did not start from scratch. AlphaGo was first trained on a database of around 30 million moves drawn from recorded human games, learning to mimic expert play. Once it reached a sufficient level, it was set to play large numbers of games against copies of itself, using what it learned from each contest to improve. A small amount of game-specific preprocessing is applied before data enters the neural networks, for example to detect whether a move matches a nakade pattern, a specific tactical configuration in Go.

  The program is also designed, deliberately, to resign. If its calculated probability of winning falls below 20 percent, it concedes rather than play on. DeepMind described this choice as avoiding "disrespectfully" wasting the opponent's time. In the distributed version that competed against Fan Hui in October 2015, the hardware involved 1,202 CPUs and 176 GPUs.

• 4. Fan Hui and the First Barrier

  ›

  In October 2015, AlphaGo defeated Fan Hui, the European Go champion, by five games to zero. Fan Hui held a 2-dan professional ranking, which sits at the lower end of professional grades that run to 9-dan. It was the first time any computer program had beaten a professional human Go player on a full-sized 19x19 board without a handicap.

  DeepMind chose not to announce the result immediately. The news was held back until the 27th of January 2016, timed to coincide with the publication of a paper in the journal Nature laying out the algorithms behind the program. By then, DeepMind had already arranged a far more ambitious contest.

  Fan Hui, after losing to AlphaGo, did not retreat from the experience. He accepted an offer to serve as an advisor for the DeepMind team. Michael Rechtshaffen of the Los Angeles Times later described him in a review of the documentary film as "spirited" and "personable", a contrast to the introspective Lee Sedol. Fan Hui himself described the process by which DeepMind had trained AlphaGo: showing it amateur games to build foundational understanding, then setting it to play versions of itself thousands of times, a form of reinforcement learning that let the program learn the game for itself.

• 5. Lee Sedol and the Divine Move

  ›

  Lee Sedol held a 9-dan professional ranking, the highest available, and at the time of the match he had the second-highest number of Go international championship victories in the world, behind only Lee Chang-ho, who had kept the world championship title for 16 years. Lee was not specifically chosen because AlphaGo had been trained to face him. The program was not designed to target any individual human opponent.

  The five games were played on the 9th, 10th, 12th, 13th, and the 15th of March 2016 at the Four Seasons Hotel in Seoul. AlphaGo ran on Google's cloud servers located in the United States, using 1,920 CPUs and 280 GPUs as reported by The Economist. Each side had two hours of thinking time plus three 60-second periods of byoyomi, the overtime system used in Go. The match used Chinese rules with a 7.5-point komi, the points awarded to white as compensation for moving second.

  Lee won the first three games by resignation. Then came the fourth game, and move 78. Lee played a move that professionals immediately called the "divine move". AlphaGo's policy network had assigned that specific move such a low probability that it had not prepared a correct response. The program's computing resources were diverted and it lost the thread. Lee won by resignation at move 180, becoming the only human player to beat AlphaGo across all 74 of its official games. In June 2016, DeepMind's Aja Huang disclosed at a presentation in the Netherlands that the team had patched the logical weakness exposed by move 78. AlphaGo won the fifth and final game by resignation, taking the series four games to one.

  The prize was one million US dollars. Because AlphaGo won the series, the prize was donated to charities including UNICEF. Lee Sedol received 150,000 dollars for participating in all five games and an additional 20,000 dollars for his win in game four. After game two, Lee said he felt "speechless": "From the very beginning of the match, I could never manage an upper hand for one single move. It was AlphaGo's total victory." He called his game four win "a priceless win that I would not exchange for anything."

  In recognition of the victory, the Korea Baduk Association awarded AlphaGo an honorary 9-dan title for exhibiting creative skills and pushing forward the game's progress.

• 6. Master and the Sixty-Game Run

  ›

  On the 29th of December 2016, an account appeared on the Tygem Go server under the name "Magister". It played at the pace of 10 games per day with little or no resting between sessions. Many players quickly suspected it was not human. On the 30th of December it renamed itself "Master", then moved to the FoxGo server on the 1st of January 2017. On the 4th of January, DeepMind confirmed that both accounts were an updated version of AlphaGo, called AlphaGo Master.

  By the 5th of January 2017, Master's online record stood at 60 wins and 0 losses. Its opponents included world champions Ke Jie, Park Jeong-hwan, Yuta Iyama, Tuo Jiaxi, Mi Yuting, Shi Yue, Chen Yaoye, Li Qincheng, Gu Li, Chang Hao, Tang Weixing, Fan Tingyu, Zhou Ruiyang, Jiang Weijie, Chou Chun-hsun, Kim Ji-seok, Kang Dong-yun, Park Yeong-hun, and Won Seong-jin, as well as national champions and world championship runners-up including Lian Xiao, Tan Xiao, Meng Tailing, Dang Yifei, Huang Yunsong, Yang Dingxin, Gu Zihao, Shin Jinseo, Cho Han-seung, and An Sungjoon. Ke Jie had been quietly briefed in advance that Master was a version of AlphaGo. After losing, Gu Li offered a bounty of 100,000 yuan, equivalent to about 14,400 US dollars, to the first human player who could defeat it.

  Almost all 60 games were fast-paced, with byo-yomi of 20 or 30 seconds. When Master played against veteran Nie Weiping, it extended the byo-yomi to one minute out of consideration for his age. After winning its 59th game, the program revealed itself in the chat window to be controlled by Aja Huang of the DeepMind team, then changed its listed nationality to the United Kingdom. Ke Jie, by then widely recognized as the world's top player, said: "After humanity spent thousands of years improving our tactics, computers tell us that humans are completely wrong. I would go as far as to say not a single human has touched the edge of the truth of Go."

• 7. The Future of Go Summit

  ›

  In May 2017, the Future of Go Summit was held in Wuzhen. AlphaGo Master played three games against Ke Jie, who was the number one ranked player in the world at the time, and won all three. Google DeepMind offered prize money of 1.5 million dollars for the winner of that three-game match; the losing side received 300,000 dollars. Master also played two games with groups of top Chinese professionals, one pair Go game, and one game against a collaborating team of five human players.

  After winning the summit, the Chinese Weiqi Association awarded AlphaGo a professional 9-dan ranking. DeepMind then retired the program and disbanded the team that had worked on it, redirecting its resources toward other areas of AI research. As a farewell to the Go community, DeepMind published 50 full-length AlphaGo versus AlphaGo matches.

  Ke Jie, who had been 18 years old and considered the world's best Go player during the Lee Sedol match, had initially claimed he would beat AlphaGo, declining an earlier contest out of concern it would "copy my style". His confidence shifted as the games progressed. Toby Manning, the match referee for the Fan Hui contest, and Hajin Lee, secretary general of the International Go Federation, both reasoned after watching these events that computers would in future help Go players identify what they had done wrong and improve their skills.

• 8. After AlphaGo

  ›

  AlphaGo Zero, introduced in a Nature article on the 19th of October 2017, was trained without any human game data at all. Playing only against itself, it surpassed the strength of the version that defeated Lee Sedol in three days, winning 100 games to zero. It reached the level of AlphaGo Master in 21 days and exceeded all previous versions within 40 days. AlphaGo Zero achieved a 100-0 record against the early competitive version of AlphaGo.

  On the 5th of December 2017, DeepMind released a paper on arXiv introducing AlphaZero, a generalization of AlphaGo Zero's approach into a single algorithm. Within 24 hours, AlphaZero reached superhuman level in chess, shogi, and Go, defeating the world-champion programs Stockfish, Elmo, and the 3-day version of AlphaGo Zero in each case. AlphaZero was in turn succeeded by MuZero, which learns without being taught the rules of a game at all.

  On the 11th of December 2017, DeepMind released an AlphaGo teaching tool on its website. The tool draws on 6,000 Go openings sourced from 230,000 human games, with each opening analyzed through 10,000,000 simulations by AlphaGo Master.

  In 2017, the DeepMind AlphaGo team received the inaugural IJCAI Marvin Minsky Medal for Outstanding Achievements in AI. A 2018 paper in Nature cited AlphaGo's approach as the basis for a new method of computing potential pharmaceutical drug molecules. Murray Shanahan, a professor of cognitive robotics at Imperial College London and a senior research scientist at DeepMind, drew the connection directly: "In just the same way there are all kinds of realms of possibility within Go that have not been discovered, we could never have imagined the potential for discovering drugs and other materials."

  Lee Sedol announced his retirement from professional play on the 19th of November 2019. He explained that he could no longer see himself becoming the top overall player in Go due to the increasing dominance of AI. He referred to programs like AlphaGo as "an entity that cannot be defeated."