Solving Geometry Friends using Monte-Carlo Tree Search with directed graph representation
Hyun-Tae Kim, Du-Mim Yoon, Kyung-Joong Kim · 2014
Geometry Friends is a platform game with two different objects (rectangle and circle). Players can control the geometries to collect all the diamonds in the level. It requires both of efficient path planning and careful objects control with physics law. It has been revealed that it is not easy to achieve human-level performance for the game. In our early work, we show that simple A* search can be used for the problem. Although it's useful, it sometimes falls into local optimum. In this work, we propose to use Monte-Carlo Tree Search (MCTS) to generate plans for the game object. Because the game levels are not suitable for the MCTS, we propose to represent them into a directed graph with special properties. Experimental results demonstrate the potential of the MCTS approach for the Geometry Friends game.