Computers Can Beat Humans at Go fact

Did a Computer Really Beat a Human at Go?

In March of 2016, Google’s AI, AlphaGo, beat Lee Sedol, one of the best professional Go players in the world, in four out of five games in a no-mercy match. This historic event was the first time that a computer player beat a top-level professional Go player and is a major milestone for the field of Artificial Intelligence.

FACT: Computers can also win at breakthrough (the Atari/Apple game), chess, jeopardy and some other games that allow for the utilization of pattern recognition and semantic learning (aspects of machine learning and cognitive AI). Learn more about cognitive Ai.

TIP: See a preview of the paid article DeepMind’s Mastering the game of Go with deep neural networks and tree search (published in Nature).

What is Go and Why Does it Matter?

Go is an extremely complex game with roots in Ancient China. Despite having a simple rule set in which players “capture” each others’ stones on a 19-by-19 grid, Go has always been respected as one of the most complex and strategic games around. In 2008, there were an estimated 40 million Go players from all over the world.^[1]

For a long time, computers have been able to beat people at most games. For example, in 1997, IBM’s Deep Blue beat Chess Grandmaster and world champion Gary Kasparov in chess a chess match with a score of 3.5 to 2.5.^[2] With that said, Go is much more complicated than chess with 10^170 possibilities in the former compared to 10^120 possibilities in the latter. That’s a difference of 10^50 – one-hundred quintillion more possible board configurations.^[3]

As recently as 2010, even Artificial Intelligence textbooks wrote that the field was 20-30 years away from creating a machine that could beat professional Go players. When DeepMind’s AlphaGo beat Fan Hui – a professional European Go player – in October 2015, it was quite a surprise.^[4] However, as Hui was ranked as only a 2-Dan professional (out of 9 possible professional Dan’s), it was agreed the AI was still unable to conquer the best humans at the game.^[5]

AlphaGo versus Lee Sedol

Earlier wins aside and lesser players aside, in March 2016, AlphaGo challenged Lee Sedol – a 9-Dan professional and 18-time world champion – in Go.^[6] Despite his confidence going into the match, Sedol was beaten by AlphaGo in four out of the five games played in the no-mercy set.^[7]

After winning the games, AlphaGo was awarded $1,000,000 USD which Google announced would be donated to charities (including Go organizations). Lee Sedol was awarded $170,000 USD (both for participating and for beating AlphaGo in the fourth match.

After the historic win, AlphaGo was named an honorary “9-Dan” professional rating by the Korea Baduk Association for its mastery level “close to the territory of divinity”.^[8]

How Did AlphaGo Win? How Does AlphaGo Work?

Even though AlphaGo’s mastery has been authoritatively declared “Godlike” (at least in an honorific sense concerning Go), the mechanics behind the program itself are entirely logical and scientific.

As mentioned above, Go is much more complex than previously-beaten games such as chess. A computer plays chess by looking at every possible move, and then every possible move that can stem from each of those moves, and so forth down to some specified level of depth (how many moves ahead it is allowed to search). The computer then searches all the possible moves it can play and chooses the one that gets it closest to winning.

This searching strategy works in chess because there are approximately 20 moves a player can make at each turn. However, in Go, there are approximately 200 moves that a player can make at any turn.^[9] This means that for a chess AI to look 3 moves ahead, it has to search about 8000 possible board configurations (20 x 20 x 20 ). If a Go AI has to look 3 moves ahead, it has to search 8,000,000 possible board configurations (200 x 200 x 200). With each additional move, this difference grows exponentially (by a factor of 10).

To compensate for this extreme complexity, the technology for playing Go had to change its strategy. Instead of searching through each move with “brute-force” or even heuristically-guided search techniques, a Go-playing AI has to rely on pattern recognition and probability.

Machine Learning and AlphaGo

The basis of AlphaGo is a pairing of neural networks, mathematical models that simulate the functions of the neurons in the human brain^[10], in tandem with machine learning techniques and probabilistic search. This allows AlphaGo to learn patterns from both matches that it’s watched (training) and from Go matches that it’s played (experience).^[11]

In other words, AlphaGo was first taught to mimic how Go professionals play, and then perfected its craft by playing other versions of itself and finding the patterns that helped it to win. Every time it made a move, it used all of its previous experience to look at the moves available and choose the one which it thought was statistically most-likely to lead to a win.

Despite the complexity of this algorithm, all of these techniques had been seen and used in other applications before, and AlphaGo’s hardware is nothing extraordinary.^[12] What is special about AlphaGo is that it represents the true sophistication of the state of Artificial Intelligence – and it shows that, with well-understood processes, we can create machines that can outperform us at even the most complicated of tasks.

1. “Go (game)” Wikipedia.org
2. “Artificial Intelligence: A Modern Approach” Berkeley.edu
3. “Names of Large Numbers” Wikipedia.org
4. “Google achieves AI ‘breakthrough’ by beating Go champion” BBC.com
5. “Go Ranks and Ratings” Wikipedia.org
6. “AlphaGo Versus Lee Sedol” Wikipedia.org
7. “Lee Sedol” Wikipedia.org
8. “AlphaGo Gets Divine Go Ranking” Straitstimes.com
9. Artificial Intelligence: Go master Lee Se-dol wins against AlphaGo program
10. “Artificial Neural Network” Wikipedia.org
11. “AlphaGo” Wikipedia.org
12. “How the Computer Beat the Go Master” Scientificamerican.com