Fittest survival: an enhancement mechanism for Monte Carlo tree search
by Jiajia Zhang; Xiaozhen Sun; Dandan Zhang; Xuan Wang; Shuhan Qi; Tao Qian
International Journal of Bio-Inspired Computation (IJBIC), Vol. 18, No. 2, 2021

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.

Online publication date: Tue, 12-Oct-2021

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Bio-Inspired Computation (IJBIC):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com