State similarity based Rapid Action Value Estimation for general game playing MCTS agents

As Monte Carlo Tree Search has been established as one of the most promising algorithms in the field of Game AI, several approaches have been proposed in an attempt to exploit as much information as possible during the tree search, most important of which include Rapid Action Value Estimation and its variants. These techniques estimate for each action in a node an additional value (AMAF), based on statistics of all simulations where the action was selected deeper in the search tree. In this study, a methodology for determining the most suitable node for using its AMAF scores during the selection phase is presented. Two different approaches are proposed under the scope of discovering similar nodes’ states based on the actions selected towards their paths; in the first one, N-grams are employed to detect similar paths, while in the second one a vectorized representation of the actions taken is used. The suggested algorithms are tested in the context of general game playing achieving quite satisfactory results in terms of both win rate and overall score.