Title: Fittest survival: an enhancement mechanism for Monte Carlo tree search

Authors: Jiajia Zhang; Xiaozhen Sun; Dandan Zhang; Xuan Wang; Shuhan Qi; Tao Qian

Addresses: Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China ' Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China ' Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China ' Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China ' Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China ' Department of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, China

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.

Keywords: Monte Carlo tree search; MCTS; Texas poker; tree pruning; significance test.

DOI: 10.1504/IJBIC.2021.118092

International Journal of Bio-Inspired Computation, 2021 Vol.18 No.2, pp.122 - 130

Received: 27 Aug 2020
Accepted: 22 Dec 2020
Published online: 12 Oct 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article