Paper Info
Title
Fittest survival: an enhancement mechanism for Monte Carlo tree search
Abstract
Monte Carlo tree search (MCTS), which constructs a search tree of game states and evaluates expected rewards by thousands of Monte Carlo simulations, has become the pre-eminent approach for many challenging games. One severe challenge of MCTS is the contradiction between the accuracy of states' evaluation and practical time consumption for simulations, both of which are critical for a competitive game program. This paper proposes and evaluates fittest survival Monte Carlo tree search (FS-MCTS) which provides a novel mechanism to enhance MCTS towards correct direction with fewer simulations. The key idea of FS-MCTS is to keep states with significant advantages to survive while eliminate the others. This is the meaning of 'fittest survival'. In this sense, FS-MCTS no longer completely depends on the evaluation accuracy of game states which severely relies on adequate simulation times. We evaluate FS-MCTS in the problems of poker. Experimental results show that FS-MCTS, combining with several variants of popular UCB policies, performs better than their vanilla versions when a certain number of simulations are guaranteed for its theoretical prerequisites.
Year
DOI
Venue
2021
10.1504/IJBIC.2021.118092
INTERNATIONAL JOURNAL OF BIO-INSPIRED COMPUTATION
Keywords
DocType
Volume
Monte Carlo tree search, MCTS, Texas poker, tree pruning, significance test
Journal
18
Issue
ISSN
Citations 
2
1758-0366
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Zhang Jiajia136.01
Xiaozhen Sun200.34
Dandan Zhang300.34
Xuan Wang429157.12
Shuhan Qi53814.95
Qian Tao65914.00