Google's AI Machine To Battle 'Go' Champion
Lee Se-dol, 33, one of the world’s top players of the ancient Asian pastime, is confident he can beat Alphago. But he hasn’t seen improvements made to the system – and the match results could have implications far beyond the game.
Expert go player Lee Se-dol ‘connects’ with a digital version of Demis Hassabis, CEO of Google’s DeepMind.
Recently in the South Korean capital, Seoul, Lee Se-dol, the 33-year-old master of the ancient Asian board game Go, will sit down to defend humanity.
On the other side of the table will be his opponent: Alphago, a programme built by Google subsidiary DeepMind which became, in October, the first machine to beat a professional human Go player, the European champion Fan Hui. That match proved that Alphago could hold its own against the best; this one will demonstrate whether “the best” have to relinquish that title entirely.
Lee, who is regularly ranked among the top three players alive, has been a Go professional for 21 years; Alphago won its first such match less than 21 weeks ago. Despite that, the computer has already played more games of Go than Lee could hope to fit in his life if he lived to a hundred, and it’s good…Very good.
At the press conference confirming the details of the match, Lee exuded confidence. “I don’t think it will be a very close match,” he told the assembled crowd with a sheepish grin. “I believe it will be 5–0, or maybe 4–1. So the critical point for me will be to not lose one match.”
DeepMind thinks otherwise. The company was founded by Demis Hassabis, a 39-year-old Brit who started the artificial intelligence (AI) research firm after a varied career taking in a neuroscience PhD, blockbuster video game development, and master-level chess – and he puts its chances of winning the match at around 50–50.
Clearly, one of them is wrong. Either Lee has vastly overestimated his chances against a new breed of AI, or Hassabis and company still don’t understand quite how powerful a player they are up against. But the answer to that, revealed over the course of five matches throughout the week, will have ramifications far beyond the world of Go.
The ancient Asian game of Go
On the surface, Go looks simple. Compared with chess – which has six different types of pieces, each with different movement rules, and fiddly additions such as castling and promotion – a Go board is the height of elegance.
Each player takes it in turns placing stones of their colour on a 19-by-19 board, attempting to surround and thus capture their opponent’s pieces. The player who has taken the most territory, by surrounding or occupying it with their own stones, at the end of the game is the winner.
But the simplicity of the rule-set belies the astonishing complexity that the game can demonstrate. The first move of a game of chess offers 28 possibilities; the first move of a game of Go can involve placing the stone in one of 361 positions. A game of chess lasts around 80 turns, while Go games last 150. That leads to a staggering number of possibilities: there are more legal board states for a game of Go or chess than there are atoms in the universe.
And so both chess and go are resistant to the tactic by which simpler games, such as naught and crosses or draughts (tic-tac-toe and checkers, to Americans), have been “solved”: by enumerating every possible move, and drawing up rules for how to guarantee that a computer will be able to play to at least a draw. Each game is just too complex.
Chess computers can at least rely on a modified version of the same tactic. Such machines, including Deep Blue – the computer made by IBM which beat grandmaster Gary Kasparov in 1997, ushering in an age of dominance by computers in chess – rely on calculating and then judging the value of vast numbers of possible moves. Deep Blue, for instance, could evaluate 200m possible moves in a second. Those machines play by looking into the future, to find the set of moves that will lead them to the strongest position, and then playing them out step by step.
That tactic doesn’t work for Go. Partly, that’s because of one further complication in the game: the immense difficulty of actually evaluating a move. A chess player can easily look at a board and see who is in the stronger position, often simply by counting the number of pieces on the board held by each player.
In Go, such an approach was long thought impossible. And even if that problem could be solved, the sheer scale of the game meant that exhaustively searching through every possible move left the machine far from competitive with even a weak human player. As a result, as recently as 2014, a leading developer of Go software estimated it would be a decade before a machine could beat a professional player.
In fact, it was less than a year.
DeepMind approached the problem by seeing whether the company could teach a neural network to play Go. The technology, which began with attempts to mimic the way the human brain interprets and processes information, is at the heart of DeepMind’s AI research, and lends itself well to what Hassabis, speaking on the eve of his trip to Seoul to oversee the competition, calls “deep reinforcement learning”.
The idea of applying neural networks to solve tricky problems in AI isn’t confined to DeepMind, but the technology is notoriously tricky to refine. Hassabis likens it to teaching a child, rather than programming a computer: even if the team knows what needs to be changed, they can’t simply add a line of code. Instead, they need to show the software enough examples of correct behaviour for it to draw its own inferences.
But DeepMind did hit upon a few genuine breakthroughs. “The big jump was the discovery of the value network, which was last summer,” Hassabis says. That was the realisation that a finely tuned neural network could solve one of the problems previously thought impossible, and learn to predict the winner of a game by looking at the board.
From there, progress was rapid. The value network, paired with a second neural network, the policy network, would work to pick a few possible moves (based on similar plays seen in previous matches) and then estimate which of the resulting board states would be strongest for the AlphaGo player.
Lee’s overconfidence, says Hassabis, is because he hasn’t seen the most recent progress. “He’s very confident, because he looked at the Fan Hui version” that played in October. “And clearly, if we were to play that, he would thrash it.
If DeepMind does win the match, it will be a watershed moment for AI with only one genuine precedent: Deep Blue’s victory over Kasparov in 1997. Hassabis’ chess days were over by then, but he followed the match as closely as he could – given that it fell weeks before his computer science finals at Cambridge (he graduated with a double first).
But if AlphaGo wins its match against Lee Se-dol, it will mean much more than just a stepping-stone in DeepMind’s own progress. One of the last areas of mental competition in which humanity had an advantage over machines will have been vanquished. If you still think you’re better than an AI, now is the time to think again.
