1. ADP with MCTS algorithm for Gomoku
- Author
-
Zhentao Tang, Le Lv, Dongbin Zhao, and Kun Shao
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,Artificial neural network ,Computer science ,Monte Carlo tree search ,Monte Carlo method ,02 engineering and technology ,Evaluation function ,Search tree ,Dynamic programming ,Tree (data structure) ,Core (game theory) ,020901 industrial engineering & automation ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Algorithm - Abstract
Inspired by the core idea of AlphaGo, we combine a neural network, which is trained by Adaptive Dynamic Programming (ADP), with Monte Carlo Tree Search (MCTS) algorithm for Gomoku. MCTS algorithm is based on Monte Carlo simulation method, which goes through lots of simulations and generates a game search tree. We rollout it and search the outcomes of the leaf nodes in the tree. As a result, we obtain the MCTS winning rate. The ADP and MCTS methods are used to estimate the winning rates respectively. We weight the two winning rates to select the action position with the maximum one. Experiment result shows that this method can effectively eliminate the neural network evaluation function's “short-sighted” defect. With our proposed method, the game's final prediction result is more accurate, and it outperforms the Gomoku with ADP algorithm.
- Published
- 2016