A computer has beaten a human being at the ancient Asian game of Go, long thought to be the one board game that computers wouldn’t be able to crack.
Now, AlphaGo, a program developed by DeepMind, a Google company based in London, has beaten European Go champion Fan Hui in five out of five games.
The game of Go originated in China more than 2 500 years ago and is played by more than 40-million people worldwide.
The rules are simple, writes Demis Hassabis of Google DeepMind, on the Google blog, Players take turns to place black or white stones on a board, trying to capture the opponent’s stones or surround empty space to make points of territory. The game is played primarily through intuition and feel, and because of its beauty, subtlety and intellectual depth it has captured the human imagination for centuries.
“But as simple as the rules are, Go is a game of profound complexity,” he adds. “There are 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible positions – that’s more than the number of atoms in the universe, and more than a googol times larger than chess.
“This complexity is what makes Go hard for computers to play, and therefore an irresistible challenge to artificial intelligence (AI) researchers, who use games as a testing ground to invent smart, flexible algorithms that can tackle problems, sometimes in ways similar to humans.”
Computers have mastered noughts and crosses, checkers and more recently chess. They have also been programmed to play Atari games and beat humans on the quiz show Jeopardy.
“Traditional AI methods – which construct a search tree over all possible positions – don’t have a chance in Go,” says Hassabis. “So when we set out to crack Go, we took a different approach. We built a system, AlphaGo, that combines an advanced tree search with deep neural networks. These neural networks take a description of the Go board as an input and process it through 12 different network layers containing millions of neuron-like connections.
“One neural network, the ‘policy network’, selects the next move to play. The other neural network, the ‘value network’, predicts the winner of the game.
“We trained the neural networks on 30-million moves from games played by human experts, until it could predict the human move 57% of the time (the previous record before AlphaGo was 44%).
“But our goal is to beat the best human players, not just mimic them. To do this, AlphaGo learned to discover new strategies for itself, by playing thousands of games between its neural networks, and adjusting the connections using a trial-and-error process known as reinforcement learning. Of course, all of this requires a huge amount of computing power, so we made extensive use of Google Cloud Platform.”
Having beaten the European chamption, AlphaGo will take on Lee Sedol – the top Go player in the world – in March.