Lee Sedol, a 9-dan Go professional and the current world champion, was defeated by a computer program four games to one in Seoul. The AI, AlphaGo, is the product of Google’s DeepMind project. The one million dollar purse will be donated to charity. Lee Sedol received about $170,000 in appearance fees and for his lone win. While all of the games were close, AlphaGo seemed like the superior player. While the AI played many seemingly nonsensical moves, later analysis showed most of them to be justified. AlphaGo threatens to make human players obsolete in the highest level of Go competition.
Go Bot Wins Historic Match, Defeats Lee Sedol 4-1
Go is an ancient Chinese game which was first played over 2,500 years ago. Players place stones onto the board aiming to capture opponent’s stones by completely surrounding them and eventually win by controlling more territory than the opponent. The game had previously been very difficult to program an AI for due to its tremendous state-space complexity, i.e. the number of possible moves available to the player throughout the game. Combined with the processing power required to map out all future moves and it isn’t much of a surprise that this victory has come so long after chess programs began beating human Grandmasters consistently. This made brute force attacks virtually impossible with present computers.
The first three games went to AlphaGo, clinching the match result without the AI appearing to be in serious danger. Lee Sedol, who had confidently predicted a 5-0 or perhaps 4-1 sweep at the beginning of the match, was able to win the fourth game only by finding a brilliant sacrificial move that AlphaGo had not seriously considered. This move, which was called “God’s Move” by fellow 9-dan Gu Li in commentary, secured a large advantage for Lee. The AI’s play deteriorated quickly until it eventually was forced to resign. The fifth game went to AlphaGo, which overcame an early mistake to win convincingly.
The match was reminiscent of the 1997 Deep Blue vs. Kasparov chess match. In that match, the world chess champion was defeated by a supercomputer with normal time limits in a series of games for the first time. It would not be the last, as computers can now regularly defeat top chess masters while giving material odds. Go is likely to follow in a similar direction, with top humans being significantly worse than computer programs within the next few years.
AlphaGo was running on a supercomputer, which had thousands of CPUs and hundreds of GPUs running in parallel to analyze the game. The moved played by the computer were actually placed on to the board by a member of the DeepMind team.
The program used neural networks, and played millions of games against slightly modified versions of itself to train. Rather than using a brute force attack, it had a policy network, which suggested just a few sensible moves for analysis, and a value network, which attempted to evaluate the resulting positions from those moves. It had previously defeated the top European Go player, Fan Hui, in October. A match against Ke Jie, who is widely considered to be the best Go player in the world currently seems likely in the near future. Ke has an 8-2 record against Lee in professional competition, and represents the last obstacle for the program being considered better than all humans.