It’s official: Lee Se-dol has lost his first two Go games against AlphaGo, the computer program from Google’s DeepMind. Going into the match, Lee said he was confident, predicting victory in all 5 games. So when he lost the first game, he was shellshocked: “I didn’t expect to lose,” he said.”Even when I was behind, I still didn’t imagine that I’d lose. I didn’t think that it would be able to play such an excellent game.”
He’s now 0-2 out of 5 against AlphaGo, with $1 million on the line.
As Lee sat in front of the press after the second loss, he looked visibly shaken. “Yesterday I was surprised but today it’s more than that — I am speechless,” he said. Lee rocked back and forth slightly while DeepMind founder Demis Hassabis described the program’s confidence through the game, fidgeting as the cameras snapped hundreds of photos. He has a day to think about his strategy before game 3 on Saturday
I can understand how for some, a person losing a board game to a computer might seem inconsequential; after all, the best minds in Chess were beaten by computers decades ago. But this isn’t Chess. Go, a roughly 3,000 year old game (called as weiqi in China, igo in Japan, and baduk in Korea), is staggeringly more complex than other strategy board games. It’s estimated that there are some 10761 possible games of Go (compared with 10120 for Chess)—more than the number of atoms in the known universe. This means that even the most powerful computers on the planet can’t calculate ahead to conclusively determine the best move to play. Human players rely on a mix of skill, instinct, and imagination.
I know quite well how much of a challenge it is to program a machine to mimic the art of play. After all, my dad wrote the first commercial Go program.
Some of my earliest memories are of playing Go. I remember how heavy the black and white stones seemed large in my little hands, the loud clink as stone met wood. Even now, as I reach back into my memories, I feel my tongue start to press into my cheek, my face of intense thinking that was frequently made over puzzling board positions. I can feel the anticipation as I try to lure my opponent into a trap, and the rush of victory when he errs and I know that the game is mine. I can’t even begin to determine how many hours I have spent playing; weeks of my life, I’m sure, if you add them all together.
My dad, Bruce Wilcox, was kind of a big deal in the American Go scene back in the early ’90s and ’00s when I was a kid. Everyone at the US Go Congress (the annual meeting of the American Go Association) knew his name, even though he’s “only” a 5-dan amateur. He wasn’t the best go player in the world, or even the US—not even close. But he was among the first to do something that, at the time, seemed impossible: he programmed a computer to play Go, and to play it well.
Back in the early 1970s, a good decade before he even met my mother, my dad had a job at the University of Michigan. He was working as an artificial intelligence researcher for a professor by the name of Walter Reitman. My dad’s area of programming, at the time, was information retrieval: the kind of programming approach used in search engines. His first project was a program called Autonote, which was, essentially, a search engine to look for things you had written as notes. In 1972, Dr. Reitman asked my dad if he wanted to take charge of a new project to create a program that could play Go.
The idea, as the professor pitched it, was that a Go program was essentially a complex information retrieval problem. Moves could be stored in a sort of index; the program just had to figure out what types of moves to play and when. At the time, only two academic programs existed that attempted to play a full-size game of Go, and both could be easily beaten by a complete beginner to the game. As it happened, my dad was a complete beginner; he had never played the game before. But he said yes, thinking it sounded like an interesting challenge, and started studying Go.
One of the catchy phrases often used to describe Go is that it takes a minute to learn, but a lifetime to master. On the surface, its rules are simple. 1) Play alternates between players, each playing exactly one stone per turn. Stones are placed on cross-hatches of a 19 x 19 board (so at the beginning, there are a total of 361 possible moves). You cannot move a stone once it is placed, not place a stone on top of another. 2) Stones are removed if and only if all the cross-hatches connected to them are filled by the opponent’s stones. 3) You cannot repeat the board position (to stop an endless string of capture-capture back). And 4) The game ends when both players pass or one resigns. Whomever has encircled the most cross-hatches (or “territory”) with their stones wins.
With so few rules, it’s a cinch to play. But playing well is much tricker, especially for a computer. The number of potential moves in a given situation is astoundingly large, with possible paths of play branching with every play into a seemingly uncountable number of results. Thus it’s impossible to create a program, even with modern computing power, which can ‘read out’ every possible scenario deeply enough—through what may be over a hundred moves—to determine the best play. Chess programs were able to rise in skill quickly because the number of possible options is relatively limited. A full size Go board is equivalent to six interlocking Chess boards; in Go, you can lose one Chess-sized battle but still win the war.
The program my dad developed was able to determine where it was in the game—phases based on board position and strategy known to Go players—and propose moves related to those phases from a stored index of moves. It also paused to evaluate how it was doing overall, determining the size of each player’s territory and which groups were weak and vulnerable to attack, and it picked its move type based on an ordered hierarchy of importance. And the program had a knowledge-based, goal-directed search algorithm that allowed it to read out potential capture scenarios with surprising accuracy. It was the first program that could actually beat novice players, and the first to enter a human tournament.
He went on to program NEMESIS, the first Go program sold commercially in the U.S. and Japan, in the mid 1980s. So by the time I was born in 1985, he was well known in the Go community. But even by the 1990s, after programming Go for over twenty years, my dad’s programs could not beat a professional player, let alone the world champion.
How did the Google team teach a computer to play professional-level Go? Well, in part, they didn’t—the computer taught itself.
As the programmers explained in their January Nature paper, the program first studied common patterns in Go—much like a person would—by analyzing some 30 million moves played by human players. Then it played itself over, and over, and over again, using deep learning to improve its game. As Discover’s Carl Engelking explained, “Deep learning algorithms rely on artificial neural networks that operate similarly to the connections in our brain, and they allow computers to identify patterns from mounds of data at a speed humans could never obtain.”
At this point, AlphaGo has played millions upon millions of games, more than any human can even imagine playing. But even still, you would think the computer’s circuits would get fried trying to predict the best moves. There are literally hundreds of possible options for each stone throughout much of the game, and strong human players are able to read ahead, predicting their opponent’s play. Indeed, if the computer tried to play out each possible move and calculate the best one by brute computing force, they surely would—but the programmers have found a way to circumvent that. AlphaGo doesn’t try to calculate every possible outcome; instead it is programmed to use tree search methods to narrow in on the right moves. It only reads as far as it needs to, just like the best players do.
AlphaGo has been studying since it beat Fan Hui, the European Go champion. Professional players have remarked about how differently it has played this week as compared to the games in January. Lee’s game, on the other hand, has not dramatically changed.
Some have said that Lee wasn’t the best opponent for AlphaGo to begin with. Although he is the world champion, like all humans, he is stronger at some aspects of the game than others. Lee’s forte is fighting, but his openings are generally weaker than other top-level pros. AlphaGo, too, seems to be best at mid and endgame, which means that to win, a player has to take a sizable advantage from the get-go. So it’s possible that a player with a different style would have a stronger chance against the seasoned A.I. Chinese pro Ke Jie certainly thinks he can beat the machine (“AlphaGo may have defeated Lee Se-dol, but it can’t beat me,” Ke wrote on Weibo).
Or, perhaps, the key to winning will be to break the unspoken rules of Go. In addition to his programming, my dad is known for an unconventional Go opening called “The Great Wall.” While he didn’t invent it, he was particularly fond of it, and even explained its strategy in his book on the game, EZ-GO: Oriental Strategy In A Nutshell. Instead of sketching out territory on the corners and sides, the Wall puts the player in position to play a violent game—which would play to Lee’s strengths.
According to game commenters, Lee Se-dol did try to test the program’s ability to handle unconventional opening moves in the first game, but he paid the price for trying to trick the machine. But perhaps he didn’t push hard enough—or, perhaps, the program is simply unstoppable.
Lee Se-dol became a professional Go player at just 12 years old. He’s won 18 world championships, and played more Go than most of us can imagine. But the match against AlphaGo is different from every game he’s ever played. For the first time, he’s up against an opponent with the ultimate poker face.
“Normally, you can sense your opponent’s breathing, their energy. And lots of times you make decisions which are dependent on the physical reactions of the person you’re playing against,” Lee said to the BBC. “With a machine, you can’t do that.”
He seemed nervous in game 1, but at the beginning of game 2, Lee was calm and assured. He played cautiously. “Such play from a Go master of Lee’s caliber would usually strike fear into the hearts of opponents,” wrote Go Game Guru’s David Omerod. But, “the machine wasn’t at all intimidated by Lee’s quiet confidence.”
AlphaGo doesn’t sweat or have a tell when it makes a mistake. It doesn’t overthink its next moves or psych itself out. It has all the advantages of the most studied Go master without the failings of us mere mortals. Its play is uncannily human, but it is definitively not. So perhaps it isn’t so surprising after all that the machine keeps winning.
“The third game is not going to be all that easy for me, but I am going to exert my best efforts so that I can win at least one game,” Lee said, hopeful.
My dad is still involved in A.I., though he’s moved on from Go. He now works at the forefront of natural language programming, including chatbot technology, and has won the esteemed Loebner Prize three times, in 2011, 2014 and 2015.
