[2E1-J-1] Fundamental AI, theory: quantum computing and search

[2E1-J-1-04] Reusing a Search Tree in Novelty-Based Pruning

〇Ryo Ishibashi¹, Koichi Moriyama¹, Atsuko Mutoh¹, Tohgoroh Matsui², Nobuhiro Inuzuka¹ (1. Nagoya Institute of Technology, 2. Chubu University)

Keywords:Monte-Calro Tree Search, Game Playing

Novelty-Based Pruning (NBP) is a Monte-Carlo Tree Search (MCTS) method that introduced a pruning mechanism based on the novelty of nodes to search more unknown nodes in limited time. When an action is chosen, MCTS methods start a new search from a root node corresponding to the new state. However, it is not appropriate for NBP because the new search clears all information on what sub-trees should be pruned and the information is created again by redundant searches. This work proposes a novel method reusing a searched tree starting with a node corresponding to the new state, which is a child of the old root node. It is expected to increase the number of unknown nodes searched in limited time. In experiments of general video game playing, the number was slightly increased; however, it was not signicantly different from the normal NBP.