Presentation information

General Session

General Session » [GS] J-1 Fundamental AI, theory

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

Wed. Jun 5, 2019 9:00 AM - 10:20 AM Room E (301A Medium meeting room)

Chair:Takahisa Toda Reviewer:Yoichi Sasaki

10:00 AM - 10:20 AM

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

〇Ryo Ishibashi1, Koichi Moriyama1, Atsuko Mutoh1, Tohgoroh Matsui2, Nobuhiro Inuzuka1 (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.