Large action spaces is one of the most problematic aspects of turn-based strategy games for all types of AI methods. Some of the state-of-the-art algorithms such as Online Evolutionary Planning and Evolutionary Monte Carlo Tree Search (MCTS) have tried to deal with this problem, but they required a fixed number of actions in each turn. In general strategy games, this assumption can't be held, as the number of actions that can be executed in a turn is flexible and will vary during the game. This paper studies pruning techniques and the insertion of domain knowledge to deal with high branching factors in a new turn-based strategy game: Tribes. The experiments show that, with the help of these techniques, MCTS can increase its performance and outperform the rule-based agents and Rolling Horizon Evolutionary Algorithms. Moreover, some insights into the tree shape and the behaviour of MCTS with and without pruning techniques are provided.
Turn-based multi-action strategy games raise the interest
in the AI domain due to, among other things, their huge
branching factors. These kinds of games contain a
considerable number of actions within a turn, which the player
executes in sequence. The order of actions is important as
previous actions influence latter ones. The branching factor can
significantly increase up to billions next states. Compared to
Go and Chess, the branching factor is much higher in
turnbase
New search algorithms have been developed to tackle
strategy games, such as Online Evolutionary Planning
(OEP)
Using a single action rather than a complete turn as a
representation for MCTS is one possible solution. It decreases
the branching factor and makes the tree deeper
This paper aims to investigate classic pruning techniques and analysing the tree structure and behaviours of MCTS for Tribes. This paper compares the performance of MCTS with pruning with the original MCTS agent, Rolling Horizon Evolutionary Algorithms (RHEA) agent and rule-based agent which are agents that outperformed MCTS in the original Tribes paper (Perez et al. 2020). Moreover, the different MCTS pruning techniques are analysed by their tree shape in terms of the influence of turn and branching factor. 2
2.1
MCTS
There are different enhancements used to improve the
performance of MCTS under large branching factors. These
methods either reduce the branching factor by domain
knowledge or handle the requirement of visiting all nodes
before exploitation. First-Play urgency
Pruning is another technique used to deal with huge
branching factors. The benefits of pruning are that poor actions can
be ignored, focusing more on promising actions, resulting in
a much deeper tree and potentially a quicker convergence.
Moreover, it can be used without heuristic functions and can
be applied in any domains
Pruning techniques can be divided into two categories:
hard and soft pruning. The hard version prunes the tree by
eliminating actions with the lowest evaluated score. Soft
pruning prunes actions after certain iterations, but the
eliminated actions will be chosen in a later iteration. The benefit
of soft pruning is alleviating the risk of removing the good
actions
RHEA is an evolutionary algorithm that achieves good results in several real-time games(Perez et al. 2013). RHEA learns online, during the game, in a different way to other evolutionary algorithms that learn offline. It first generates random individuals, each one representing a sequence of actions. It then evaluates the final state arrived after executing, from the current state, all the actions in the individual sequentially. Evolutionary operators such as selection, crossover and mutation are used to generate new individuals based on old ones. The first action in the individual with the highest value is returned once the budget is exhausted. 3
3.1
Tribes (Perez et al. 2020) is a re-implementation of the game
The Battle of Polytopia
The game takes place in N N tiles. Each tile contains the terrain type (plain, mountain, shallow water or deep water). Each tile can only have one resource, building and unit at the same time. Villages, resource and ruins will be generated in tiles at the beginning of the game. Ruins contain randomized bonuses (special unit, technology, resources, etc.) and can be explored by units. There are two game modes, being Capital and Score mode. The goal in the Score mode is to maximize the score or take all the enemies’ capitals within 30 turns. Instead of reaching as much score as possible within 30 turns, the Capital mode only requires to capture the enemy’s capital, or initial city. The score comes from a variety of actions such as exploring, resource gathering, capturing villages and cites, and constructing determined buildings. At the beginning of the game, each player controls one of the four available Tribes (Xin Xi, Imperius, Bardur and Oumaji). They have a starting unit and a researched technique, being different for each tribe. Each player starts with five stars, which are the resource currency. Each player executes as many actions as possible within a turn until they decide to end it, or no more actions are available.
There are three crucial aspects of the game, technology, economy management and combat, which determine the playing strategy. The critical element in economy management is handling stars, which is used for building, gathering resources, spawning units and researching technologies. Stars are produced by cities on each turn. Buildings and resources provide population to the city. When the population exceeds the level of the city, the city is upgraded, and a bonus (extra production, units, city border growth, etc.) is unlocked. For city levels 5 and higher, the player can select a bonus between the strongest game unit (super unit or Giant) or building a park (extra score). The higher the city level is, the higher the number of stars it produces per turn. The building can only be built in their own territory, which is formed by the 3 3 tiles around the city. The types of units and buildings that can be spawned and constructed are limited at the beginning of the game, and more types are unlocked by researching the different 24 technologies available. Two types of combat units can be spawned, being melee (Warrior, Rider, Defender, Swordsman, Knight) and ranged (Archer, Catapult). Each unit has different attack power, range and health points (HP). They can also embark in port buildings and become a boat unit. Boats have three levels: boat, ship and battleship. Attack power, movement range and HP are increased when upgrading the boat unit. Moreover, a different type of units can perform a distinct combination of actions per turn. Most of them can attack and/or move in a turn, but others can do multiple consecutive actions. Once a unit defeats three other units, the former is upgraded to a veteran, having much higher HP. Units can capture the enemy’s city or neutral villages after staying in that city/village for more than a turn. The Mind Bender is a special unit which can heal friendly units and convert enemies to their faction. More details about the game can be found in the original paper (Perez et al. 2020).
There are three kinds of actions in Tribes, being unit (the only set without requiring stars to perform actions), city and tribe. The unit actions include attack, move, capture, convert, disband, examine, upgrade and become a veteran. Some of these actions are specialized for the particular unit type, or can only be performed when its corresponding technique is researched. The city actions include constructing and destroying buildings, burning, growing and clearing forests, resource gathering, spawning a unit and levelling up. The tribes action includes research, build a road in a non-enemy tile and end the player’s turn. Roads speed up the units’ movement and can be used by any player. Some actions decrease the action space for a turn. For example, the build action consumes resources and results in lacking enough stars for executing subsequent actions in that turn. The other actions, such as researching unlocking features, increases the action space for a turn. This situation makes Tribes a complex environment for decision making, with huge branching factors when a player owns many units and cities. A strong playing strategy must balance actions for technology, economy management and combat, as well as a proficient order of actions per turn. 3.2
We use 3 algorithms from the original framework (Perez et al. 2020) as baseline approaches: MCTS, RHEA and rulebased agents. It is interesting to compare to RHEA and rulebased agents as they outperform MCTS in the original paper.
Rule Based (RB): The simple rule-based agent is the only agent that does not rely on the forward model in this paper. The forward model allows the agent to sample a possible future state given a particular action in the current state. In (Perez et al. 2020), RB has the second-highest winning rate and in particular beats MCTS in 56:2% of the games. The agent only uses the information of the current state, evaluating each action separately and returning the one with the highest value. If there is more than one action with the highest value, it picks up randomly to break the tie. The evaluation is hand-crafted and relies on domain knowledge. The main weakness of this agent is that it considers every action independently and does not consider the action’s effect in the game state. The insights of this agent are that it disables the destroy and disband action and focus on capturing, examining ruins and turning units into veteran ones when possible. For more details about rule-based agents can refer to (Perez et al. 2020).
RHEA, described in Section 2.3, achieved the best performance in (Perez et al. 2020) with a 63% winning rate against MCTS. In the experiments of this paper, the RHEA agent uses the same parameters: population size of 1 and individual length of 20. Similar to the RB agent, the disbanding action and destroying actions are removed.
Section 2.1, has below 50% wining rate agents RHEA an
Heuristic: A heuristic function is used to evaluate a game state. It compares the difference between two states and evaluates them based on seven features. The features in (Perez et al. 2020) include the differences between production, number of technologies, score, number of units, number of kills and the total level of cities. Different features have different weights, set to 5, 4, 0:1, 4, 2, 3 and 2 respectively, by trial and error. Two features added in this paper, stressing the importance of building and occupying the enemy’s cities. Every new building will provide 5 points and each unit in the enemy’s city will add 10 points to the score of the state. 3.3
MCTS with hard pruning modifies the tree policy of MCTS to reduce the branching factor. The tree policy not only guides search, it also prunes the node’s children if they are visited from the parent more than the 20 times. The number of remaining nodes, being the number of children kept after pruning, is based on the branching factor and the limit for minimum nodes, shown in Equation 1. It will prune the children of nodes until the number of children matches the number of remaining nodes by evaluating its state based on heuristic described above. The children with the lowest value are pruned and never visited in the later iteration. remainingN odes = max ( log n; T ) (1) controls the speed of pruning when the number of actions grows. This parameter plays a vital role in deciding the number of the remaining nodes when the branching factor becomes huge. The higher it is, the more children are kept. T is the minimum number of actions that need to be kept after pruning. If there is any action set smaller than T , pruning is not applied. The reason for using logarithm to prune the tree is to reduce most of the actions when the actions set becomes extremely large. The parameters are decided by running the experiment under a different setting. The setting with the highest winning rate is used.
Besides pruning by the tree, the destroy action is excluded as it does not provide any rewards and results in a reduced score. Furthermore, MCTS with hard pruning has another parameter to decide to prune the move actions or not. Thus there are two versions of MCTS with hard pruning: with and without move pruning. The reason for pruning the move is that it increases the action space significantly: every unit has multiple move actions based on its move distance and the road. When it comes to the later game, a player tends to have many units, increasing the action space significantly. The move action is pruned by the equation 1. It firstly extracts the move action from all action sets. The move actions whose destination is not a ruins or a city tile are extracted and picked by the equation 1 with = 1 and T = 5. The pruned move action will then be removed and never be considered in the action set of the current node. Although the pruned actions are removed in the current node, they might appear in the following nodes meaning they still will be considered in a later step. 3.4
This variant of MCTS is a modification of MCTS with hard
pruning. Instead of permanently removing the pruned nodes,
the algorithm unprunes the nodes in later iterations. This
process allows the tree to search for every node and alleviate
the risk of pruning the best action. It is done by
increasing the number of remaining nodes if the iteration number
is over the value given by Equation 2
4
This section provides the experimental setup for testing MCTS with pruning followed by the results of our tests. Finally, an analysis of the MCTS tree is provided. 4.1
Both versions (hard pruning and progressive widening) of MCTS with pruning (i.e. with and without move pruning) were pitched against the rule-based, the default MCTS and RHEA agents, as included in the framework. For all search agents, the stopping condition is set to 2000 usages of the forward model’s next method.
Each agent pairing plays 5000 games (25 seeds with 200 repetitions). The seeds are the same as in the original paper (Perez et al. 2020) and they are used to generate different levels, all of size 11 11 tiles. Because levels might not be balanced for both contestants, players swap starting positions within the 40 repetitions of every seed. Each game is independent, meaning that no information is carried from one game to the next. The game mode is Capital with full observability, thus the winning condition is set to take over the enemy’s capital city. In order to have finite games, a winner is declared after 50 turns, corresponding to the player with the highest score at that point. 4.2
Table 1 shows the results of both versions of MCTS competing with three baseline approaches. The first row and first column indicates the version (hard pruning or progressive widening) and with or without move pruning respectively. Default MCTS shows 43:8% and 37% winning rates when playing against the RB and RHEA agents, respectively (not in the table). With the help of pruning techniques, all versions of MCTS have more than 50% winning rate playing against the baseline approaches.
With the help of hard pruning, MCTS increases its win rate approximately 8% and 12% compared to the original MCTS when playing against RB and RHEA, respectively. Move pruning and progressive widening further increase the performance of MCTS with hard pruning. MCTS with hard pruning and move pruning shows the highest winning rate when competing against the original MCTS and RHEA. As can be seen, pruning moves increases the performance of MCTS in relation to only applying progressive widening or hard pruning. Although using hard pruning or progressive widening is clearly better than using no pruning at all, the difference between these two methods is minimal. The winning rate is higher for progressive widening when playing against RB, but lower than hard pruning when the opponent is default MCTS and RHEA. The difference however is likely not to be significant, and different parameters for Equation (?) may alter the unpruning rate and provide a better value estimate of the different moves. Overall, although hard pruning, progressive widening, and domain knowledge (move pruning) can improve the performance, using domain knowledge has clearer effects in the winning rate.
Table 2 shows the statistics of the different versions of
MCTS over 15000 games (aggregated for each 5000
pairings against the baseline approaches). It shows the
statistics of average winning rate over three baseline approach,
final score, researched technologies percentage, number of
owned cities at the end game and final production. The
values obtained for these statistics for the
This section shows which action groups and actions are executed more often, an analysis of the tree depth and the fully expanded rate of the recommend action node in terms of different action spaces and turns in the game. The fully expanded rate of the recommended action node is measured between 0 and 1. If the value is 1, it means the recommended action node has visited all of its possible children (excluding the pruned nodes), from its current state. A value of 0 indicates that no children have been explored1.
During the game, the unit action group is the most frequently chosen: 68% of the time. The city and tribe action groups are only chosen 20:5% and 11:4% of the time respectively. This difference are a consequence of unit actions taking a large proportion of the action space. The most frequently executed action is move. The move action has the largest percentage (58:9%) among all actions, also explaining why the unit action group has the largest proportion. The move action does not provide a significant reward per se, but it can lead to future reward if the unit moves to ruins or enemy cities. Applying the move pruning does not change the proportion between the action groups. This may be caused by move actions being taken towards the end of the turn.
Figures 2 and 3 show the influence of the branching factor in the depth of MCTS and fully expanded rate of the recommend action node. The original MCTS is unable to go deeper than 2 levels and visit all the possible actions from the current state when the branching factor is over 50. With the help of pruning techniques, this problem happens only when the size of the action space grows over 180. This is three times larger than in the original MCTS, providing better action value estimates in early game turns (when the action 1Note that these are the children of the node of the recommended action, not the children of the root. space tends to be smaller). The depth of the tree sharply decreases when the branching factor grows. As expected, due to the unpruning mechanism, progressive widening explores more shallow trees than hard pruning, which is most noticeable when the action space size is between 100 and 150. Compared to hard pruning, progressive widening is unable to fully explore the chosen action when the branching factor becomes over 100. Although hard pruning also faces this issue, it happens later than progressive widening. The rate of exploration shown in Figure 3 shows a similar trend: hard pruning is able to delay the decay of children explored further than progressive widening, and both approaches show clearly that they allow the tree to visit a higher proportion of actions from the root than when there is no pruning at all. With no pruning, the rate of default MCTS decays dramatically when the action space size reaches 50. Figures 2 and 3 show the effect of unpruning in progressive widening and how the search tree is explored differently in each case.
Figures 4 and 5 show the influence of the game turn in
the depth of MCTS and the fully expanded rate of the
recommended action node. Note that, in Tribes, the size of
the action space tends to grow (particularly if the game is
favourable to the player) with the number of turns. An
analysis of this can be foun
5
This paper focuses on exploring pruning techniques for MCTS in a multi-action strategy game, Tribes, in which players must execute multiple actions in a turn while managing other game aspects such as economy, technology research and resource gathering. Moreover, the size of action space is not fixed and generally increases during the game, resulting in a high and difficult to manage branching factor.
MCTS can handle large branching factors but it
struggles when the action space size reaches more than a
hundred
We propose different avenues of future work. One
possibility is to explore other pruning algorithms, like
NaiveMCTS