what is the difference between AlphaGo’s success at Go and computer’s dominance in chess?

Go is a game quadrillions of orders of magnitude more complex than chess, and AlphaGo mastered it using learning techniques closer to the way that human brains work instead of raw computational power 

AlphaGo’s win over Lee Sedol, a world class Go player, is a major milestone in Computer Science. It would be easy to compare this to Gary Kasparov’s defeat to Deep Blue in 1997 and the subsequent dominance of computers at chess, but the merit of this even should not be understated. To illustrate, let’s examine some of the key differences between computer chess and AlphaGo:

Complexity: it has been estimated that the possible number of positions in chess is about 10^50 (a 1 followed by 50 zeroes), while Go’s is 2×10^170 (a 2 followed by 170 zeroes). This means Go can not be evaluated through pure computational power as of today. Furthermore, computers are not 2×10^120 times more powerful than they were in 1997 to make up for the difference in complexity.

Evaluation: traditional algorithms in chess usually score positions based on complex formulas, which measure the value of the pieces and reward certain attributes of a position (like pawn structure, king safety, bishop colors, etc). They take these values and create decision trees that are aggressively pruned in order to reach ever greater depths. Furthermore, chess has been fully solved for all instances where 6 or less pieces remain in the board. This information is stored in databases that chess programs can access and use to improve their evaluation trees.

Go on the other hand, is a more spatial and abstract game. Oftentimes, independent battles occur in different parts of the board, which at one point converge in one outcome. Since decision trees can not be practically developed for a game of such complexity, humans have relied in intuition and pattern recognition. Basic patterns do exist, but they are very local and tactical. AlphaGo managed to abstract and mimic these cognitive techniques into algorithms that can be constantly improved.

Learning: Chess computers decide on openings and endings from databases, and “improve” their game by storing previous calculations into yet more databases (or “hash files”), so that if the position occurs again they leverage those results to go deeper in their calculations. Many hobbyists analyze certain positions to great depths outside games to provide their computers with this extra information and develop and edge over their opponents.

AlphaGo has reached its current level of proficiency by analyzing thousands of high quality games and “learning” from them by modifying its own evaluation through the use neural networks. In addition, AlphaGo took those games and played millions of variations (through Monte Carlo analysis) to further feed its learning process. As a result, it is able to play moves that humans would have never considered, but proved to be correct and strong.

Computation: the current state of chess software can only leverage a limited number of computational resources, which with very few exceptions must be local and tightly managed. The current algorithms are unable to leverage very high scale parallelization, preventing them from leveraging GPUs and even a very high count of CPUs. AlphaGo is able to make efficient use of distributed resources which include both CPU and GPUs.

In summary, AlphaGo’s achievement is a much larger win in many different categories of Computer Science than chess was. More importantly some of these advances create fundamental capabilities that support learning and decision making, with direct and practical applications in our daily lives.

Leave a Reply