Darkforest

This article is about Facebook's Go-playing computer program. For other uses, see Dark Forest.

Darkforest is a computer go program developed by Facebook, Inc., based on deep learning techniques using a convolutional neural network. Its updated version Darkfores2 combines the techniques of its predecessor with Monte Carlo tree search. ^{[1] [2]} The MCTS effectively takes tree search methods commonly seen in computer chess programs and randomizes them. ^[3] With the update, the system is known as Darkfmcts3. ^[4]

Darkforest is of similar strength to programs like CrazyStone and Zen. ^[5] It has been tested against a professional human player at the 2016 UEC cup. Google's AlphaGo program won against a professional player in October 2015 using a similar combination of techniques. ^[6]

Darkforest is named after Liu Cixin's science fiction novel The Dark Forest . ^[7]

Background

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 cutting-edge hardware, and Go’s evaluation function could change drastically with one stone change. However, by using a Deep Convolutional Neural Network designed for long-term predictions, Darkforest has been able to substantially improve the win rate for bots over more traditional Monte Carlo Tree Search based approaches.

Matches

Against human players, Darkfores2 achieves a stable 3d ranking on KGS Go Server, which roughly corresponds to an advanced amateur human player. However, after adding Monte Carlo Tree Search to Darkfores2 to create a much stronger player named darkfmcts3, it can achieve a 5d ranking on the KGS Go Server.

Against other AI

darkfmcts3 is on par with state-of-the-art Go AIs such as Zen, DolBaram and Crazy Stone but lags behind AlphaGo. ^[8] It won 3rd place in January 2016 KGS Bot Tournament against other Go AIs.

News Coverage

After Google's AlphaGo won against Fan Hui in 2015, Facebook made its AI's hardware designs public, alongside releasing the code behind DarkForest as open-source, along with heavy recruiting to strengthen its team of AI engineers. ^[3]

Style of play

Darkforest uses a neural network to sort through the 10¹⁰⁰ board positions, and find the most powerful next move. ^[9] However, neural networks alone cannot match the level of good amateur players or the best search-based Go engines, and so Darkfores2 combines the neural network approach with a search-based machine. A database of 250,000 real Go games were used in the development of Darkforest, with 220,000 used as a training set and the rest used to test the neural network's ability to predict the next moves played in the real games. This allows Darkforest to accurately evaluate the global state of the board, but local tactics were still poor. Search-based engines have poor global evaluation, but are good at local tactics. Combining these two approaches is difficult because search-based engines work much faster than neural networks, a problem which was solved in Darkfores2 by running the processes in parallel with frequent communication between the two. ^[9]

Conventional strategies

Go is generally played by analyzing the position of the stones on the board. Some advanced players have described it as playing in some part subconsciously. Unlike chess and checkers, where AI players can simply look farther forward at moves than human players, but with each round of Go having on average 250 possible moves, that approach is ineffective. Instead, neural networks copy human play by training the AI systems on images of successful moves, the AI can effectively learn how to interpret how the board looks, as many grandmasters do. ^[10] In November 2015, Facebook demonstrated the combination of MCTS with neural networks, which played with a style that "felt human". ^[10]

Flaws

It has been noted that Darkforest still has flaws in its play style. Sometimes the bot plays tenuki ("move elsewhere") pointlessly when local powerful moves are required. When the bot is losing, it shows the typical behavior of MCTS, it plays bad moves and loses more. The Facebook AI team has acknowledged these as areas of future improvement. ^[11]

Program architecture

The family of Darkforest computer go programs is based on convolution neural networks. ^[3] The most recent advances in Darkfmcts3 combined convolutional neural networks with more traditional Monte Carlo tree search. ^[3] Darkfmcts3 is the most advanced version of Darkforest, which combines Facebook's most advanced convolutional neural network architecture from Darkfores2 with a Monte Carlo tree search.

Darkfmcts3 relies on a convolution neural networks that predicts the next k moves based on the current state of play. It treats the board as a 19x19 image with multiple channels. Each channel represents a different aspect of board information based upon the specific style of play. For standard and extended play, there are 21 and 25 different channels, respectively. In standard play, each players liberties are represented as six binary channels or planes. The respective plane is true if the player one, two, or three or more liberties available. Ko (i.e. illegal moves) is represented as one binary plane. Stone placement for each opponent and empty board positions are represented as three binary planes, and the duration since a stone has been placed is represented as real numbers on two planes, one for each player. Lastly, the opponents rank is represented by nine binary planes, where if all are true, the player is a 9d level, if 8 are true, a 8d level, and so forth. Extended play additionally considers the boarder (binary plane that is true at the border), position mask (represented as distance from the board center, i.e. ${\displaystyle x^{(-0.5*distance^{2})}}$, where ${\displaystyle x}$ is a real number at a position), and each player's territory (binary, based on which player a location is closer to).

Darkfmct3 uses a 12-layer full convolutional network with a width of 384 nodes without weight sharing or pooling. Each convolutional layer is followed by a rectified linear unit, a popular activation function for deep neural networks. ^[12] A key innovation of Darkfmct3 compared to previous approaches is that it uses only one softmax function to predict the next move, which enables the approach to reduce the overall number of parameters. ^[3] Darkfmct3 was trained against 300 random selected games from an empirical dataset representing different game stages. The learning rate was determined by vanilla stochastic gradient descent.

Darkfmct3 synchronously couples a convolutional neural network with a Monte Carlo tree search. Because the convolutional neural network is computationally taxing, the Monte Carlo tree search focuses computation on the more likely game play trajectories. By running the neural network synchronously with the Monte Carlo tree search, it is possible to guarantee that each node is expanded by the moves predicted by the neural network.

Comparison with other systems

Darkfores2 beats Darkforest, its neural network-only predecessor, around 90% of the time, and Pachi, one of the best search-based engines, around 95% of the time. ^[9] On the Kyu rating system, Darkforest holds a 1-2d level. Darkfores2 achieves a stable 3d level on KGS Go Server as a ranked bot. ^[1] With the added Monte Carlo tree search, Darkfmcts3 with 5,000 rollouts beats Pachi with 10k rollouts in all 250 games; with 75k rollouts it achieves a stable 5d level in KGS server, on par with state-of-the-art Go AIs (e.g., Zen, DolBaram, CrazyStone); with 110k rollouts, it won the 3rd place in January KGS Go Tournament. ^[4]

See also

• Go and mathematics

References

1. Tian, Yuandong; Zhu, Yan (2015). "Better Computer Go Player with Neural Network and Long-term Prediction". arXiv: 1511.06410v1 [cs.LG].
2. "How Facebook's AI Researchers Built a Game-Changing Go Engine". MIT Technology Review. December 4, 2015. Retrieved 2016-02-03.
3. "Facebook AI Go Player Gets Smarter With Neural Network And Long-Term Prediction To Master World's Hardest Game". Tech Times. 2016-01-28. Retrieved 2016-04-24.
4. "Facebook's artificially intelligent Go player is getting smarter". VentureBeat. 27 January 2016. Retrieved 2016-04-24.
5. "Strachey Lecture - Dr Demis Hassabis by University of Oxford Live".
6. "No Go: Facebook fails to spoil Google's big AI day". The Guardian. 2016-01-28. ISSN   0261-3077 . Retrieved 2016-02-01.
7. "FB围棋项目负责人谈人机大战" [FB Go Project Manager Discusses Man vs Machine Showdown] (in Chinese). Tencent. 2016-03-01.
8. Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature . 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN   0028-0836. PMID   26819042.
9. "How Facebook's AI Researchers Built a Game-Changing Go Engine". MIT Technology Review. Retrieved 2016-04-24.
10. Metz, Cade (7 December 2015). "Google and Facebook Race to Solve the Ancient Game of Go With AI". WIRED. Retrieved 2016-04-24.
11. Kelion, Leo (27 January 2016). "Facebook trains AI to beat humans at Go board game - BBC News". BBC News. Retrieved 2016-04-24.
12. LeCun, Yann; Bengio, Yoshua; Hinton, Geoffrey (27 May 2015). "Deep learning". Nature. 521 (7553): 436–444. Bibcode:2015Natur.521..436L. doi:10.1038/nature14539. PMID   26017442.

External links

• Source code on Github