How Facebook’s AI Researchers Built a Game-Changing Go Engine
From the post:
One of the last bastions of human mastery over computers is the game of Go—the best human players beat the best Go engines with ease.
That’s largely because of the way Go engines work. These machines search through all possible moves to find the strongest.
While this brute force approach works well in draughts and chess, it does not work well in Go because of the sheer number of possible positions on a board. In draughts, the number of board positions is around 10^20; in chess it is 10^60.
But in Go it is 10^100—that’s significantly more than the number of particles in the universe. Searching through all these is unfeasible even for the most powerful computers.
So in recent years, computer scientists have begun to explore a different approach. Their idea is to find the most powerful next move using a neural network to evaluate the board. That gets around the problem of searching. However, neural networks have yet to match the level of good amateur players or even the best search-based Go engines.
Today, that changes thanks to the work of Yuandong Tian at Facebook AI Research in Menlo Park and Yan Zhu at Rutgers University in New Jersey. These guys have combined a powerful neural network approach with a search-based machine to create a Go engine that plays at an impressively advanced level and has room to improve.
The new approach is based in large part on advances that have been made in neural network-based machine learning in just the last year or two. This is the result of a better understanding of how neural networks work and the availability of larger and better databases to train them.
This is how Tian and Zhu begin. They start with a database of some 250,000 real Go games. They used 220,000 of these as a training database. They used the rest to test the neural network’s ability to predict the next moves that were played in real games.
…
If you want the full details, check out:
Better Computer Go Player with Neural Network and Long-term Prediction by Yuandong Tian, Yan Zhu.
Abstract:
Competing with top human players in the ancient game of Go has been a long-term goal of artificial intelligence. Go’s high branching factor makes traditional search techniques ineffective, even on leading-edge hardware, and Go’s evaluation function could change drastically with one stone change. Recent works [Maddison et al. (2015); Clark & Storkey (2015)] show that search is not strictly necessary for machine Go players. A pure pattern-matching approach, based on a Deep Convolutional Neural Network (DCNN) that predicts the next move, can perform as well as Monte Carlo Tree Search (MCTS)-based open source Go engines such as Pachi [Baudis & Gailly (2012)] if its search budget is limited. We extend this idea in our bot named darkforest, which relies on a DCNN designed for long-term predictions. Darkforest substantially improves the win rate for pattern-matching approaches against MCTS-based approaches, even with looser search budgets. Against human players, darkforest achieves a stable 1d-2d level on KGS Go Server, estimated from free games against human players. This substantially improves the estimated rankings reported in Clark & Storkey (2015), where DCNN-based bots are estimated at 4k-5k level based on performance against other machine players. Adding MCTS to darkforest creates a much stronger player: with only 1000 rollouts, darkforest+MCTS beats pure darkforest 90% of the time; with 5000 rollouts, our best model plus MCTS beats Pachi with 10,000 rollouts 95.5% of the time.
The author closes with this summary:
This kind of research is still in its early stages, so improvements are likely in the near future. It may be that humans are about to lose their mastery over computers in yet another area.
I may have to go read the article again because the program as described:
- Did not invent the game of Go or any of its rules.
- Did not play any of the 220,000 actual Go games used for training.
That is to say that the Game of Go was invented by people and people playing Go supplied the basis for this Go playing computer.
Not to take anything away from the program or these researchers, but humans are hardly about to lose “…mastery over computers in yet another area.”
Humans remain the creators of such games, the source of training data and the measure against which the computer measures itself.
Who do you think is master in such a relationship?*
* Modulo that the DHS wants to make answers from computers to be the basis for violating your civil liberties. But that’s a different type of “mastery” issue.