Games have long been an important test of artificial intelligence (AI). Recently, scientists at London-based Google DeepMind reported they had developed a program that was able beat a professional human player in the ancient Chinese game of Go. Although AI systems have beaten champions before at Jeopardy!, chess, and checkers, mastering Go has long been viewed as greater challenge owing to the enormous number of possible combinations and the difficulty in scoring positions. Their achievement confirms an observation Tractica made in our report on Deep Learning for Enterprise Applications that this technology is advancing rapidly and also supports our forecast that annual software revenue for enterprise applications of deep learning and other neural nets will increase from $109 million in 2015 to $10.4 billion by 2024. However, the real significance of the announcement was not the victory but the way in which it was achieved.
What is Go?
In Mandarin, the word Go means “encircling game” and it is the oldest board game still played today. The objective is to control an area larger than one’s opponent. Black makes the first move, after which White and Black alternate placing one stone on an empty intersection on the board. A stone is removed when all the intersections adjacent to it are occupied by the other player. The number of pieces varies constantly. Despite these simple rules, the number of possible patterns in Go is orders of magnitude more complex than chess (10761) compared to 10120). Traditional brute force approaches of calculating every possible move are not possible when working with such large numbers. Prior to 2015, the best Go programs in the world could only beat players ranked at an amateur level.
The new program was able to beat not only the best existing Go programs but the European Go champion by mimicking the arrangement of neurons in the human brain. Although in 1997 an IBM computer was able to defeat Grandmaster Garry Kasparov at chess, the announcement more closely parallels AI advances playing the game of Checkers.
In the 1950s, an IBM computer scientist named Arthur Samuel developed a program to play draughts or checkers. Samuel thought that programming computers to play games would eventually bear fruit when it came to solving more general problems. He chose checkers because the rules are relatively straightforward, but the game still required a strategy to win.
In checkers, Red makes the first move after which Red and Black alternate. Each player begins with 12 pieces placed in the three rows. Pieces can only move one space diagonally forward. The object of the game is to capture all of the other player’s pieces or place them so there are other available moves.
The main routine of Samuel’s program determined the next move based on board positions. Since he had only a limited amount of computer memory, Samuel implemented what is called alpha-beta pruning. Instead of calculating each path until it came to the game’s eventual conclusion, Samuel developed a scoring function based on the position of the pieces at that point in time. This function measured the chances of winning for each side at the given position. It took into account the number of pieces on each side, the number of kings, and how close pieces were to being kinged. The program then chose its next move to optimize the value of its position and minimize its opponent’s score, but only for a limited number of moves ahead. The number of moves is called the look ahead. Samuel continued to work on checkers throughout his life until the mid-1970s, at which point his program could beat a respectable amateur. One of the innovations he introduced was to have the program play itself to develop a library of past games.
Eventually, a team the University of Alberta developed a program called Chinook that solved the problem of checkers. Drawing on 1014 calculations, and a library of end moves, if a human player made no mistakes the best he or she could hope for is a draw.
Significant Step Forward
DeepMind scientists succeeded by taking a new approach to Go. They abandoned alpha-beta pruning and brute force entirely. Instead, they used two different neural nets: a value network to evaluate board positions and a policy network to select moves. These deep neural networks are trained by a combination of supervised learning by analyzing thousands of human expert games, and reinforcement learning by playing tens of thousands of games against itself. The researchers also introduced a new search algorithm that combines a Monte Carlo simulation with the value and policy networks. The resulting program, named AlphaGo, achieved a 99.8% winning rate against other Go programs, and defeated the current human European Go champion by 5 games to 0.
Is There a Link Between Intelligence and Chess?
News that the IBM 701 could play checkers caused IBM stock to jump by 15 points in the early 1950s. When IBM’s Deep Blue defeated Garry Kasparov at chess in 1997, it made headlines worldwide. AlphaGo’s win against a human opponent is making similar waves. While many people will see this as a sign that computers are becoming more intelligent, the correlation between human intelligence (IQ) and game playing ability has not been proven. A 2006 study found no differences in intelligence between strong adult chess players and regular people.
In March, AlphaGo will challenge Lee Sedol, currently the strongest player in the world. Expect more ink to be spread about how intelligent machines are becoming. What is likely to be overlooked is the real significance of the announcement. Deep learning neural nets can solve difficult problems that have eluded traditional approaches for large enterprises, and ultimately it is the business applications for AI that will create tremendous market value and continue to propel the technology advances forward.