Google backed AlphaGo’s big win: How AI is cracking an ancient Chinese game

Lee Sudol might have come back to snatch one win against DeepMind's AlphaGo, but nonetheless the AI's three victories are a big deal.

Written by Shruti Dhapola | Updated: March 14, 2016 11:12 am
AlphaGo, Lee Sedol, Lee Sedol AlphaGo, Lee Sedol vs AlphaGo, DeepMind, DeepMind YouTube, DeepMind Google, AI, Go, Chinese game Go, technology, technology news AlphaGo’s 3-1 victory in the game of Go against world human champion Lee Sedol is a big achievement for AI. In this photo, South Korean professional Go player Lee Sedol, right, drinks water after putting the first stone against Google’s artificial intelligence program, AlphaGo, as Google DeepMind’s lead programmer Aja Huang, left, sits during the Google DeepMind Challenge Match in Seoul, South Korea. (Source: AP)

Google-owned DeepMind’s AlphaGo, a computer program has created  history. AlphaGo, which is a general Artificial Intelligence (AI) program, has now thrice beaten world champion Lee Sedol at the ancient Chinese game of Go. Lee managed to snatch one win in the five match series; the final game will be played on March 15. DeepMind, the company behind AlphaGo was bought by Google in 2014, and is now central to its AI efforts.

This is not the first time that AlphaGo has beaten a human champion at the game of Go. In January 2016, AlphaGo beat reigning European champion at Go, Fan Hui. AlphaGo won 5-0 against Hui. Here’s why AlphaGo’s latest victory against Lee Sedol is such a big deal.

Watch the fourth match of AlphaGo vs Lee Sedol

What’s the game of Go?

Go is an ancient Chinese game, that’s popular in East Asia. In Chinese the game is called weiqi, in Japan it is igo, in Korean it is baduk. Over 60 million people watched the first game online in China alone, and over 100 million people watched the online live feed globally.

The game, which is played on board of 19×19 grid squares, with black and white stones has one objective: capture more than 50 per cent of the board by surrounding vacant areas with stones. Black starts first in this, and players can only place the stone on the intersection of the grid.

AlphaGo, Lee Sedol, Lee Sedol AlphaGo, Lee Sedol vs AlphaGo, DeepMind, DeepMind YouTube, DeepMind Google, AI, Go, Chinese game Go, technology, technology news South Korean professional Go player Lee Sedol reviews the match after winning the fourth match of the Google DeepMind Challenge Match against Google’s artificial intelligence program, AlphaGo, in Seoul, South Korea. (Source: AP)

The game goes on until both sides agree that there are no more places to put one’s stones, or until one side decides to resign in an apparent loss. When the game is over, each player counts the number of vacant dots inside his or her territory. Players can capture their competitor’s stones, which are then known as prisoners. There is a bonus point for each prisoner. Stones once placed on the board, can’t be moved.

There are two simple rules for game: One is a stone must have at least one liberty to stay alive in the game. Liberty is an open point either up, down, left right around the stone. The stone can also be part of a group, which has at least one such liberty. The other is that a player can’t repeat the exact same position of stones from a previous move on the board.

The game is more than 3,000 years old, and there are more than 40 million Go players around the world. South Korea, even has dedicated TV channels showing Go matches and teaching strategies all day.

So why is it a challenge for computers to learn this game?

Unlike Chess, which is much more logical, the game of Go is seen as intuitive, something that computers can’t just master. As DeepMind’s scientists point out unlike the Deep Blue program for Chess, they can’t just use the ‘brute force,’ search method to beat players at Go. Brute Force would require a full and exhaustive search for all possible moves to play Go. Except that’s not possible with Go; the search tree, which relies on coming up with possible moves, is too enormous.

AlphaGo, Lee Sedol, Lee Sedol AlphaGo, Lee Sedol vs AlphaGo, DeepMind, DeepMind YouTube, DeepMind Google, AI, Go, Chinese game Go, technology, technology news Lee Sedol, left, shakes hands with Google co-founder Sergey Brin, right, after finishing the fourth match of the Google DeepMind Challenge Match against Google’s artificial intelligence program, AlphaGo, in Seoul, South Korea. (Source: AP)

As Google DeepMind’s CEO Demis Hassabis explains in one video, there are more configurations in the Go game, than there are atoms in the universe; and while chess has 20 typical moves, in Go you can have 200 potential moves at one point. He further says that some of the world’s top Go players might often attribute a move to intuition or because it felt right, and that’s something you can’t teach a computer so easily.

So how does AlphaGo work?

AlphaGo works using two deep neural networks (artificial networks inspired by biological neural networks) to mimic the moves of expert players of go. DeepMind has shown it millions of Go positions and moves from human-played games.

The first neural network used is called the policy network, and the other is the Valley network. AlphaGo doesn’t consider all the moves in one go, instead it concentrates on a couple of promising moves in the beginning via the policy network. The valley network reduces the depth of the search, and instead of going all the way down to the end of the game, it looks at a more reasonable number, like say 20 moves.

Google’s DeepMind scientists call this way of search as “more akin to imagination.” The AlphaGO program is evaluated internally as well, and it can play millions of games a day, something humans cannot do.

Why is the victory such a big deal?

For DeepMind and AlphaGo, the wins against Lee Sedol mark a big step in the future of how Artificial Intelligence will evolve. In fact, experts had thought that it would take ten more years before a computer could beat humans at Go.

AlphaGo, Lee Sedol, Lee Sedol AlphaGo, Lee Sedol vs AlphaGo, DeepMind, DeepMind YouTube, DeepMind Google, AI, Go, Chinese game Go, technology, technology news CEO of Google DeepMind Demis Hassabis speaks during a press conference after finishing the third match of the Google DeepMind Challenge Match between South Korean professional Go player Lee Sedol and Google’s artificial intelligence program, AlphaGo, in Seoul, South Korea. (Source: AP)

When the first victory happened, Hassabis compared the win to the moon-landing and tweeted, “#AlphaGo WINS!!!! We landed it on the moon. So proud of the team!! Respect to the amazing Lee Sedol too.”

As Demis Hassabis explained in the second match post-conference, the idea with these matches is also to figure out the weakness of AlphaGo.

“AlphaGo has an estimate of how it’s doing throughout the game, which is not always correct. In the second half (of the second game), it got more confident. These matches will help us know if something is missing and probe the weakness of AlphaGo,” he had said at the press conference. It should also be noted that the programmers can’t correct or fix AlphaGo after each game to teach it new moves, the program learns on its own.

After losing the second match, human Go champion Lee Sedol said he was speechless, adding that he didn’t feel like he was leading the second game at all. “AlphaGo played a near perfect game,” the reigning human champion had said at the end of the second game.

However the fourth match has also shown that the AI is capable of making an error. “We came here to learn what mistakes AlphaGo makes. This loss is very valuable to us, and we don’t know what we happened yet, and we will analyse the game carefully once we are back in the UK,” said Hassabis at the post match conference.

with AP inputs