MATHEMATICS
The program that beat the Go world champion was largely self-taught.
– All systems Go! A computer victory
Compared to the ancient Chinese strategy game Go, chess is easy. That is why engineers at Google’s artificial intelligence arm are so excited that their program Alphago has beaten the Go world champion. “It’s been the grand challenge of AI since Deep Blue beat Kasparov at chess,” says Demis Hassabis, an AI guru at Deepmind, the London lab acquired by Google.
And it happened about 10 years before experts predicted. The program, which models the way a human brain learns using so-called “neural networks” largely taught itself to improve its game by playing millions of matches against itself.
Alphago beat world champion Lee Se-dol in Seoul, South Korea, four-one in March after trouncing European Go champion Fan Hui last year five-nil. Asked what it was like playing the machine, Fan said he would’ve thought Alphago was a person if he hadn’t known better. But he described it as “a little strange”. The British Go Association’s Toby Manning declared its quick moves and eerie calm distinctly non-human. But there are human elements to Alphago’s processes, says Toby Walsh, an AI researcher at the University of New South Wales.
Originating in China more than 2,500 years ago, Go has a straightforward aim: to secure territory. Players take turns placing black and white stones on a 19x19 grid. When a stone is surrounded, it is taken off the board. A player wins when he has covered 50% of the board.
Sounds simple, but it’s anything but. As with chess, Go is a game of “perfect information” – players can see every move and know where every piece lies. But unlike chess, where players might have 25 options at each turn and can think four or five moves ahead, there are hundreds of options each move in Go. There are more Go board configurations than atoms in the Universe, and computer processors are nowhere near powerful enough to run through them all.
The Deepmind program combined two state-of-the-art machine-learning techniques to master the game. The Monte Carlo tree search randomly samples moves, plays them to the end, and selects the patterns most often associated with success.
It combined this approach with “deep learning” which so far has worked spectacularly for Google programs that have learnt to recognise cats and human faces on the internet. David Silver, a Deepmind computer scientist, describes that process as “akin to imagination”.
Alphago underwent three layers of training. The program learnt skills by being fed thousands of games played by Go masters. Those skills were honed by playing against itself. Finally it learnt the skill of assessing who was winning. That’s crucial because while chess players can tell at a glance who’s in the stronger position, Go, with its larger board and hundreds of pieces, makes the task much harder.
Advances in computer processing mean faster and more comprehensive searches, Walsh says, so Alphago will only get better.
“If I were earning my income as a Go grandmaster, I’d start looking into a second job.”