Earlier today artificial intelligence development won another victory with the defeat of Lee Sedol, the world champion of the ancient game of Go. Go, a 3,000 year old Chinese game, has long been considered a game so complex and intuitive in nature that no computer could defeat a professional human player. However with this loss in round one of the five round match to be played over the coming days AlphaGo, the name of the artificial intelligence developed by Google’s DeepMind team, has taken a commanding lead in upsetting the assumptions of both artificial intelligence developers and Go players alike.
What is Go?
Go is a game that has been played in eastern countries for thousands of years. Most popular in China, Korea, and Japan, Go has long been the eastern equivalent to the West’s strategic game of choice, chess. However where chess has wide variety of pieces, each with its own movement patterns, in addition to specific and special rules (i.e. castling, pawn promotion), Go is much simpler.
Like chess the pieces, referred to as stones, are black and white. The highest levels of Go are played on a 19×19 grid as opposed to the 8×8 grid of chess. Rather than playing within the squares as in chess, Go stones are placed at any point where the grid the lines intersect on the board (the corners of the square). Players take turns placing a stone on the board until one controls more territory than the other. The only other rule is that if a stone or stones are surrounded by your opponent’s, then those stones are made prisoners. The territory is then ceded to your opponent.
While the rules are very simple, the number of options a player is left can be staggering. To give an example, in Chess there are 20 possible opening moves. In Go, there are 361. It has been estimated that there are 1060 possible board states in a game of chess. There is an estimated 10700 possible board states in Go.
Man vs. Machine
In 1997 the IBM super computer Deep Blue defeated world chess champion Garry Kasparov. Deep Blue did this by using “brute force” calculations. Brute-force calculations are where a computer will go through all possible sequence of moves to arrive at the desired outcome, in the case of chess a checkmate. However this same method used to overthrow human chess champions will not work in a game of Go.
There are so many moves and possible board states in Go that brute-force calculations are impossible to perform. Even professional Go players do not always know exactly why they place a stone where they do. They rely on intuition and instinct when playing. Two aspects very difficult to create within a computer program.
An Intuitive AI
The way the Google DeepMind team gave intuition to the AlphaGo artificial intelligence was through the use of two deep neural networks, referred to as the Policy Network and the Value Network.
The Policy Network reduces the enormous complexity of the possible move search tree. Instead of having to consider hundreds of different moves at each step, it only considers a handful of promising moves that are suggested by the Policy Network.
The Value Network is used to reduce the depth of the search. Instead of having an incredibly deep search that goes down perhaps 300 moves or all the way to the end of a game, the Value Network sets a modest depth of around 20 moves. The network then evaluates that position without playing all the way to the end of the game.
The Match
Prior to the match, world champion Lee Sedol speculated that he would defeat the AlphaGo either 5-0 or perhaps 4-1.
Demis Hassabis, DeepMind chief executive, explained how AlphaGo prepared for the match.
“After it’s learned that, it’s got to reasonable standards by looking at professional games. It then played itself, different versions of itself millions and millions of times and each time get incrementally slightly better – it learns from its mistakes.”
The first round between AlphaGo and Lee lasted nearly 4 hours and was described as a “close first game” by Google. AlphaGo eventually won by resignation after 186 moves. Google said the game “looked to be neck-and-neck for its entirety, filled with complex fighting on both sides.”
Lee said of the match, “I was very surprised because I did not think that I would lose the game . . . A mistake I made at the very beginning lasted until the very last.”
“I didn’t think AlphaGo would play the game in such a perfect manner,” he told reporters after the match. “I would like to express my respect to the programmers for making such an amazing program.”
There are still four rounds left to play, and everyone is eager to see if Lee can recover from this initial defeat. At stake in all this, other than human versus artificial intelligence, is a prize of $1 million dollars (£700,000), the largest prize ever for a Go match. If Google and AlphaGo win, they plan to donate the prize to charity.
