Single-player Monte-Carlo tree search for SameGame

Abstract

Classic methods such as A^∗ and IDA^∗ are a popular and successful choice for one-player games. However, without an accurate admissible evaluation function, they fail. In this article we investigate whether Monte-Carlo tree search (MCTS) is an interesting alternative for one-player games where A^∗ and IDA^∗ methods do not perform well. Therefore, we propose a new MCTS variant, called single-player Monte-Carlo tree search (SP-MCTS). The selection and backpropagation strategy in SP-MCTS are different from standard MCTS. Moreover, SP-MCTS makes use of randomized restarts. We tested IDA^∗ and SP-MCTS on the puzzle SameGame and used the cross-entropy method to tune the SP-MCTS parameters. It turned out that our SP-MCTS program is able to score a substantial number of points on the standardized test set.

Introduction

The traditional approaches to deterministic one-player games with perfect information [27] are applying A^∗ [23], IDA^∗ [29] or one of their variants (e.g., Multiobjective A^∗ [40], Limited-damage A^∗ [2]). These methods have been quite successful for solving this type of games. The disadvantage of the methods is that they require an admissible heuristic evaluation function. The construction of such a function can be difficult. Since Monte-Carlo tree search (MCTS) [11], [17], [28] does not require an admissible heuristic and because of its success in two-player games [30] and multi-player games [41], MCTS seems a promising approach for deterministic one-player games with perfect information as well [39], [43].

So far, MCTS has not been widely applied in one-player games. One example is the sailing domain [28], which is a non-deterministic game with perfect information. MCTS has also been used for optimization and planning problems which can be represented as deterministic one-player games. Chaslot et al. [10] applied MCTS in production management problems. Mesmay et al. [32] proposed the MCTS variant TAG for optimizing libraries for different platforms.

This article proposes an MCTS method, called single-player Monte-Carlo tree search (SP-MCTS), for a one-player game.¹ MCTS for two-player games forms the starting point for this search method. We adapted MCTS by two modifications resulting in SP-MCTS. The modifications are (1) in the selection strategy and (2) in the backpropagation strategy. SP-MCTS is tested in the puzzle² SameGame, because there exists no reliable admissible heuristic evaluation function for this game. This article also investigates whether the cross-entropy method [36] is able to fine tune the parameters of SP-MCTS.

The article is organized as follows. In Section 2 we present the rules, complexity and related work of SameGame. In Section 3 we discuss why classic approaches such as A^∗ and IDA^∗ are not suitable for SameGame. Then, we introduce the SP-MCTS approach in Section 4. Section 5 describes the cross-entropy method which is used for tuning the SP-MCTS parameters. Experiments and results are given in Section 6. Section 7 gives the conclusions and indicates future research.