A comparison between UCB and UCB-Tuned as selection policies in GGP

1 Introduction

One of the aims of Artificial Intelligence (AI) has been the development of intelligent agents capable of playing board game at the same level -or even better- than humans [4]. The challenge in developing playing agents drift that they must possess characteristics pertaining to human intelligence, such as deduction, reasoning, problem resolution, intelligent search, knowledge representation, planning, learning, creativity, perception and natural language processing among others [21]. AI has proposed agents capable of playing at the level of human champions in specific games, like Chinook [19] (there is a strategy that allows the player to win regardless the plays by its opponent [18]), Deep Blue for Chess [6] and Dark Knight for Banqi or Chinese Chess [13].

The field of AI that has focused its efforts in developing intelligent agents capable of playing any kind of game is General Game Playing (GGP). In GGP, agents must be able to develop their own playing strategies autonomously, without human intervention, having played the game previously and just considering the rule given at the start of the game (often using the Game Description Language) [4, 21].

Although the agents in GGP cannot be compared to specialized game agents in terms of performance, their use is higher as they can perform in different domains, even the techniques developed in GGP can be used in other areas such as business process, electronic business, military operations, among others [11, 12].

An important result in the GGP area has been the implementation of the Monte Carlo Tree Search method (MCTS) proposed by Finnsson [10] and used at the CadiaPlayer agent which have won the GGP international competition three times. MCTS method defined the state of the art of agents in GGP [11]. MCTS is guided by Monte Carlo Methods [5], using the results of previous explorations to estimate with higher precision the values of the promising results [5, 9].

Algorithms based on MCTS use a tree structure where each edge represents a possible movement and each node represents a state of the game. Each node has associated a series of statistics like the number of victories and the number of node visits. The algorithm consist of the iterative application of four steps [9]: selection, expansion, simulation and backpropagation. During the selection step, the tree is traversed from the root until a node which can be expanded is reached, using a selection criterion that determines which node should be visited in each level. Next, in the expansion step, the new node is added to the tree. Then, during the simulation step, an execution of the game is done from the state of the node added, running the moves of each player, until the game ends. Finally, in the backpropagation step the result of the previous step is propagated in each visited node.

Every time that the MCTS performs the selection step, it faces with following dilemma: which node should be visited, the one who seems to be the best at the moment or other nodes less promising that may turn out to be better in later iterations. This is known as the Exploration-Exploitation Dilemma, the Multi Armed Bandit Problem (MABP) is representative of this dilemma [15, 22]. The MABP is described as follows: given a set of K slot machines where each one has certain probability to be chosen to gain a reward, the question is: which slot machine should be activated if it is desired to obtain the greatest possible reward. Upper Confidence Bound (UCB), proposed in [3], is the most popular algorithm used in MABP, and it has been used in MCTS as selection policy with excellent results [10], UCB+MCTS is known as Upper Confidence Bounds Applied to Trees (UCT).

Due to its results in specific games UCB is the most used policy in GGP [7, 8] since it is an independent domain so no previous knowledge of the game is required. Since the conception of UCB, new policies have been developed to MABP like UCB-Tuned [3], UCB-V, PAC-UCB [2], UCB-Minimal [14], Minimax Optimal Strategy (MOSS) [1], and others [5]. So far there is no evidence of the application of said policies in GGP, this may be due to the excellent results obtained by UCB. However, these policies are also domain independent so they can be applied to GGP in order to evaluate whether they improve UCB in victories obtained.

Perick et al. [16] present a comparative study of various policies in MCTS using as study case the Tron game. The results show that UCB-Tuned is the policy with the best performance. However, if these policies are applied to GGP domain, and due to the variety of games in the literature, it is possible to obtain different results from those obtained by Perick et al. when applied to other games.

This paper shows a comparative study of the performance of the UCB and UCB-Tuned policies in GGP using the Breakthrough, Knightthrough and Connect Four games. The purpose of this comparison is to analyze the behavior of these policies and their performance in terms of victories in the GGP context. To the best of our knowledge no comparison has been done previously with these games using these policies.

In Section 2, the Monte Carlo Tree Search is described; in Section 3, the selection policies are described; in Section 4, the comparative analysis is presented; in Section 5, the results are presented. Finally, in Section 6 the conclusions are outlined.

2 Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a guided method based on Monte Carlo simulations [5], which uses the results of previous explorations for estimating the most promising moves in the game with better precision [5, 9]. In the tree structure each edge is a possible move and each node is a state of the game associated with a set of statistics values: the number of victories and the number of visits. Figure 1 shows a game tree whose nodes show the victories in the left side and the visits in the right side. The game tree starts only with the root and it is expanded according to the method used.

OPEN IN VIEWER

Fig.1

An example of MCTS for the Tic Tac Toe game.

In each interaction MCTS performs four steps which are repeated cyclically until a stop criterion is satisfied [5, 9] (see Algorithm 1 and Fig. 2): Selection, Expansion, Simulation and Backpropagation.

Selection In this step the game tree is traversed from the root to a leaf (see Fig. 2a and algorithm 2). In each level the method must decide which node should be expanded, this decision is guided by a selection policy. At the beginning, a policy based on the rate between the number of victories and visits is used, but recently, the UCB method is used.

OPEN IN VIEWER

Fig.2

MCTS method.

These steps are repeated until a stop criterion is satisfied, this can be a limit of simulations, run time or iterations. Finally, when the method ends, the agent must choose between the child-node of the root-node considering any of the next criteria [5]:

Max child The node with the greatest number of victories is chosen.

In each iteration, in the selection step, in each level of the game tree, the MCTS method faces the following decision: Which node should be visited? The best one so far or some else that may be better than this one in future iterations? The above is known as the Exploration-Exploitation Trade-Off, which the Multi Armed Bandit Problem (MABP) also belongs.

The decision of which node should be visited in each level of the game tree is equivalent to decide which slot machine to activate in MABP, so each node can be a machine as follows:

The number of victories of a node is equivalent to number of times that a slot machine has given rewards.

Due to their equivalence, it is possible to use the techniques developed to MABP in MCTS. A selection policy is an algorithm that allows to decide in MABP which slot machine to activate. The most popular policy is Upper Confidence Bound.

In order to make the comparison, the GGP-Base framework was used and the Breakthrough, Knightthrough (both games used in  [7, 8]) and Connect Four.

4.2 Breakthrough

Breakthrough is a board game of i × j size for two players and with turn-based moves. At the beginning, the first two rows of each player had pawns (see Fig. 3). The goal is to take a pawn to the first row of the opponent; for this, the pawn, can move one square forward or diagonally, being able to capture only diagonally. Breakthrough has been solved for a board size of 6 × 5 determining that the second player has a strategy that allows it to win no matter what moves the other player does [17]. For the research here presented a 6 × 6 board was used which is available in GGP-Base.

OPEN IN VIEWER

Fig.3

Breakthrough 6 × 6.

4.3 Knightthrough

Like Breakthrough, Knightthrough is a board game of i × j size, for two players with turn-based moves, but with the difference that instead of using pawns it uses knights (see Fig. 4). The goal is to take a knight to the first row of the opponent. For the research here presented, a 8 × 8 board was used, which is available in GGP-Base.

OPEN IN VIEWER

Fig.4

Knightthrough 8 × 8.

4.4 Connect Four

Connect Four is a board game for two players with turn-based moves (see Fig. 5). Each player has a set of discs of the one color which are added by the top of the board. The goal is to align four discs on the board before the other player. For the research, a 8 × 6 board was used, available in GGP-Base.

OPEN IN VIEWER

Fig.5

Connect Four 8 × 6.

To compare the policies, two agents were created, one base in UCB and the other in UCB-Tuned. The analysis was performed in two stages; in the first one the MCTS method was limited to 100 simulations per iteration, while in the second one the MCTS method was limited to 1000 simulations. In each stage the agents competed three times in 1000 matches of Breakthrough, 1000 of Knighttrough and 1000 of Connect Four. The results show that UCB-Tuned has the best performance in terms of victories when the MCTS method is limited to 100 simulations; however, when the method is limited to 1000 simulations UCB wins in two of the three games.

This paper shows a comparative analysis of two selection policies, UCB and UCB-Tuned, in the context of GGP, with the purpose of detecting which policy has the best performance in terms of numbers of victories. Taking the results obtained from the comparative analysis we can conclude that de policy with the best performance in GGP is UCB-Tuned when the MCTS is limited in the number of simulations which happens when the agents are limited in time, very common in competitions like The International General Game Playing Competition [11]. When the MCTS method has a greater number of simulations available, the best policy to use is UCB but only with a small difference over UCB-Tuned.

In the game Knightthrough, the UCB-Tuned policy wins in both stages so we can conclude that in this specific game UCB-Tuned is better to use than UCB.

As the results show that UCB-Tuned wins in four of six competitions, it may be concluded that this policy has better performance than UCB in General Game Playing.

This is a preliminary work so is left as future work:

The use of other games that are more complex than the games presented in this paper, for example Amazons, Chess or Go.