IMPROVING MONTE CARLO TREE SEARCH BY COMBINING RAVE AND QUALITY-BASED REWARDS ALGORITHMS

Monte-Carlo Tree Search is a state-of-the-art method for building intelligent agents ingames and has been focus of many researchs through past decade. By using thismethod, the agents are able to master the games through building a search tree basedon samples gathered by randomized simulations. In most of the researchs, the rewardfrom simulations are discrete values representing final state of the games (win, loss,draw), e.g., r ∈ {-1, 0, 1}. In this paper, we introduce a method which modifies rewardfor each playout. Then it backpropagates the reward through UCT and AMAF values.RAVE algorithm is used to evaluate the nodes more accurately in each tree breadth.We implemented the algorithm along with Last-Good-Reply, Decisive-move andPoolrave heuristics. In the end we used leaf parallelization in order to increase thesamples gathered by simulations. All implementations are examined in the game ofHEX in 9 × 9 board. We show the proposed method can improve the performance inthe domain discussed.

Keywords:

Monte-Carlo Tree Search , Game of HEX , Reinforcement Learning , Heuristics