This paper presents N-Tuple Bandit Online Evolution (NTBOE), a novel algorithm for eficiently playing multi-action adversarial games. Its main advantage is the use of a structure composed of a set of multiarmed bandits to store information about the best combination of actions that can be played in the player's turn. Accessing this structure, to get an estimation of how good is to be in a particular game state, is several times faster than accessing the forward model of the game. Thanks to that, it is possible to explore more game states than the state of the art algorithms since it is able to go deeper in the search space. The performance of the proposed method has been assessed using the game ASMACAG as a testbed. The results obtained show that the proposed method overcomes state-of-the-art methods such as Monte Carlo Tree Search and Online Evolution.
Bandit Online Evolution (NTBOE). To assess the performance of the proposed method, the game
A Simple Multi-Action CArd Game (ASMACAG) [
The main contributions of this work are as follows: • We present a complete re-implementation of ASMACAG using Python 3.8 and a set of several good practices to provide code that is easily readable and understandable. • We present N-Tuple Bandit Online Evolution (NTBOE), a new method to play multi-action adversarial games. • We assess the performance of NTBOE playing versus two baseline methods (Random and One Step Looking Ahead) and two state-of-the-art ones (Monte Carlo Tree Search and Online Evolution).
As far as we know, this is the first paper using a method such as NTBEA to obtain the best combination of actions to be played in the player’s turn.
The rest of the paper has been organized as follows: Section 2 presents a summary of the most relevant related methods. Section 3 exposes the problem definition that this paper tries to solve and Section 4 explains the ASMACAG game. Section 5 briefly explains the 4 methods implemented to be compared with the proposed one, presented in Section 6. The experiments done to assess the performance of the proposed method and the results obtained are showed in Section 7. Finally, Section 8 summarizes the main conclusions arisen from this work.
One of the problems of previous multi action games’ implementations is that, due to complex game rules, it should be quite complex to implement a bot for playing them. This is one of the reasons for developing ASMACAG since it provides a simple enough context in which the bots can be tested and understood and it allows for easy step by step debugging, while being complex enough that the results it yields are statistically relevant. For instance, ASMACAG is very convenient for artificial intelligence courses since the way to implement a new bot is very straightforward.
One of the most relevant works for playing multi action games is [
The main diference of the proposed NTBOE method with respect to the state of the art ones is that NTBOE stores information about the action combinations that can be used for selecting new turn candidates to be analyzed. In addition, evaluating the candidates using the internal structure composed of multi armed bandits is several times faster than evaluating using the forward model of the game. Therefore, using NTBOE more game states can be explored in the same time period increasing the probability of finding the optimum actions combination.
This section introduces the terminology and the notation that will be used throughout this paper
and formulates the problem to be solved. The notation follows the one exposed by P. Cowling
et al. in [
A game is defined as a direct graph (, Λ) where are the nodes and Λ the edges of the graph. The nodes are called states of the game. The leaf nodes are called terminal states and the other nodes non-terminal states. In general, a game has a positive number of players. Some games also have an environment player (player 0). Each state is associated with a number () ∈ {0, . . . , }, that represents the player about to act. Each terminal state is associated with a vector ( ) ∈ R, which represents the reward vector. In some games, the non-terminal states can also be associated with an immediate reward vector that gives an idea of how well the players are doing. A heuristic function () can be used to estimate the reward vector (), given the state (terminal or not).
The game starts at time = 0 in the initial state 0. At time = 0, 1, 2, . . . , if state is non terminal, player () chooses an edge (, +1) ∈ Λ and the game transitions through that edge to the state +1. This continues until a terminal state is reached at time = . Then, each player receives a reward equal to their corresponding entry in the vector ( ) and the game ends. If the game allows immediate rewards, players receive the immediate reward (+1) after reaching the state +1.
Players typically do not choose edges directly, but choose actions. In the simplest case, each outgoing edge of a state corresponds to an action that player () can play. The set of actions from a state is denoted (). Note that, given a state , the player () can play just one action (i.e. choose an edge (, +1)) from the ones included in ().
In multi-action games a player can play several consecutive actions in a turn. A turn, given a state at time , is defined as a list () = [1, 2, . . . , ] where is the number of consecutive actions that the player must play in its turn, 1 ∈ (), 2 ∈ (+1) and ∈ (+− 1). The order in which actions are played into the turn can be very important on some multi-action games, since to play some action before other can modify the immediate reward obtained after playing the last action of the turn .
Therefore, the problem that the agents have to solve is, given a game state , to find the list () that leads to the highest immediate expected reward (+) when the turn finished (i.e. after playing the last action of the turn).
ASMACAG is a simple card game proposed as a tool to test, develop and debug bots that
implement artificial intelligence algorithms in the context of multi-action games. It was first
presented in [
The rules for ASMACAG are simple by design, since the game has been designed as a tool whose aim is to be as straightforward as possible. This design philosophy allows to easily step-by-step debug the bots and understand their decisions while also staying complex enough for the results to be relevant and representative of their performance. The rules in the base version are as follows (note that each player of the game is a bot following an specific algorithm for decision-making): • It is an adversarial game with 2 players, each of them is dealt 9 cards. • There is a board with 20 cards dealt on it, which must contain only numbers. • The cards include numbers from 1 to 6 and the special values x2 and %2. The deck where the card are dealt from contains 8 cards of each of the numbers from 2 to 5, 5 cards of numbers 1 and 6 and 6 instances of each one of the special cards. • Each player must play 3 cards per turn with no possibility to skip. Playing a card consists in taking it from your hand and placing it on any card available on the board, if it is numbered, or just using it directly if it has an special value. After playing a card both the played card and the used card from the board, if applicable, will be discarded. Turns alternate until there are no cards left on either player’s hand. • Each time a numbered card is played ( − ) * points are awarded to the player that used it, where is the value of the card played, is the value of the card on the board and is a factor that defaults to 1. Special cards afect the value of when computing the score of the next numbered card played by any of the players. The x2 special card will duplicate while the %2 card will halve it.
• The player plays a 6 card on a 2 card. = 1. The players gets (6 − 2) * 1 = 4 points. • The player plays a 6 card on a 2 card. = 2. The players gets (6 − 2) * 2 = 8 points. • The player plays a 4 card on a 6 card. = 2. The players gets (4 − 6) * 2 = − 4 points. • The player plays a 5 card on a 2 card. = 0.25 since, e.g. the opponent played two consecutive %2 cards in the previous turn. The players gets (5 − 2) * 0.25 = 0.75 points.
An aspect taken into account in the design of the ASMACAG software is the need for flexibility in the test environment, specially regarding the rules. All these rules need to be programmed to be easily modified as needed during the testing process, by just coding a class that implements a forward model compatible with the game. Also, the parameters of the rules need to be easily accessible and changeable. This parameters include things, such as the number of cards dealt at each time, the amount of existing cards of each type, the range of numbers in the numbered cards, the number of actions to play per turn, etc.
According to the terminology exposed in the Section 3, in ASMACAG the number of players is = 2, there is not environment player and = 3, i.e. the turn () is composed by three actions. Thanks to the existence of the special cards x2 and %2, the order in which the actions are played can modify the immediate reward (+3) obtained after playing the actions contained in the turn ().
Implementing a new bot for playing ASMACAG is very straightforward. A new bot must inherit from Player class and implement three methods: the constructor, the one who returns a string with the name of the bot and the think function, which given the current state of the game and a time budget must return the action to be played. As an example, the implementation of a bot that always returns a random action from the existing ones given the current game state of the game can be seen in https://github.com/dvs99/ASMACAG/blob/master/Players/RandomPlayer.py.
This algorithm will just choose randomly one of the available valid actions when required to decide, without looking into the next action to play at all. It is included to be used as a minimal baseline, to check that each of the other algorithms are able to beat it in an statistically relevant and consistent way.
This algorithm will just perform a greedy search on the available valid actions at one moment of the turn, playing the one that returns the best value. Once again, it will not go through the next actions that could be played during that turn. It is useful as a baseline heuristic algorithm, testing the capability of each of the other algorithms to win against it, when applying the same heuristic.
This algorithm is probably the most researched of the ones tested and it has been selected for its
relevance and importance in the AI field during the last decades. First coined in 2006 [
At each iteration, the method has to selected which child node has to be explored using a multi arm bandit. This is made by the UCB equation which balance between exploiting the node with the best or exploring nodes with less visits . The formula for a particular node is expressed as follows: () = + √︂ ln + (1) is the average of the rewards that have been obtained in the past by choosing the action , is the total number of times an action has had to be chosen, is the number of times the action has been chosen, and is a parameter which balances between the exploitation and the exploration parts of the UCB functions. Greater values benefits exploration versus exploitation. The value is a small number (e.g. = 0.05) that is used to avoid having to divide by zero in the equation. In those cases, i.e. when an action has never been chosen before, the value obtained will be very high to give the opportunity to explore, at least once, all possible actions.
In our particular implementation of the MCTS algorithm, the tree only explores the possible action combination in a player turn.
This algorithm has been selected for its relevance for the problem of multi-action adversarial games and focuses on the idea of solving the problem that is the most specific to multi-action games, which is finding the right combination of actions to compose a turn and therefore should be quite eficient when trying to win at ASMACAG. The algorithm has the followings steps: 1. A set of individuals are randomly generated. Each individual (or genome) is a combination of actions that can be played in a turn. In ASMACAG each individual has three components (or genes). 2. The set of individuals are evaluated using the forward model and a score is obtained using a heuristic function. 3. The worst individuals, according to the obtained score, are removed from the set. This process is controlled by the survivor rate parameter. 4. New individuals are generated doing crossover operations. 5. Each individual is mutated according to a mutation rate .
6. The process is repeated until convergence or until the time budget is reached.
As a novel approach to solving multi-action adversarial games, the N-Tuple Bandit
Evolutionary Algorithm(NTBOE) is proposed. This algorithm was first designed for its use in ofline
optimization of an heuristic function [
The N-Tuple model in the algorithm directly models the statistics, while approximating the
iftness and number of evaluations of each modeled combination of parameters [
The advantage it can have over other approaches, and specifically against other evolutionary algorithms, is that the N-Tuple based model in the algorithm is faster to access than the game itself. The algorithm tests several turns against that model, which approximates the reward based on the data received up to that point, per each time it tests a turn with the actual game. This allows the NTBOE algorithm to test a lot more possible turns in the same amount of time.
Algorithm 1 shows the procedure of the method. The first step of the model is create the N-Tuple Bandits model Γ where the score obtained after playing the actions into the turn, using the forward model, will be stored. In this work, a 1D Multi arm bandit per action (i.e. 3) is used together with 3 2D multi arm bandits for action combination (1st action + 2nd action, 1st action + 3rd action, and 2nd action + 3rd action). In total, the model consists of 6 multi arm bandits.
The second step of the method is an initialization step. It is detailed in Algorithm 2. A population Π of random individuals is obtained and each one is evaluated using the forward model of the game (line 6). The model Γ is updated with the scores obtained in these evaluations. The best individual (and its score) is returned as the current one. This process is very important to fill the model with valuable information. Then, the iterative process stars, at each iteration new individuals are created mutating the current one (line 5). For mutating an individual one action is randomly selected (using ) and it is randomly changed for another possible action given the state of the game at this moment. We call to this new individuals neighbors. Each neighbor is evaluated using the model Γ (line 10) and a score is obtained. Note that at this moment the individual is evaluated using the model Γ instead of the forward model. These individuals are evaluated using the model Γ by the Equation 2. It consist of the sum of all the UCB values (see Equation 1) of each one of the bandits belonging to the model. Evaluating an individual using Γ is several times faster than evaluating it using the forward model. ( ()) = ∑︁ (, ()) ∈Γ (2)
The previous process returns a candidate to be a better solution to the current one. It is evaluated using the forward model and the model Γ is updated with the score obtained. Then, if its score is better than the one obtained by the current, it becomes the new current. If not, the current individual remains being the same.
At the end, the current individual is the actions combination (or turn) () obtained as solution.
The performance of the proposed NTBOE method is assessed playing games against the two baselines and the two state of the art methods presented in Section 5. In all cases 1000 games have been played between two methods. Each algorithm will be the first player for half of the games played against any other algorithm and the second player for the other half of them. This will allow to reduce the bias introduced by the fact that the game is easier to win as the ifrst player. All algorithms will have a budget to make decisions which will be defined as time limit per turn, this time will be of 1 second. Regarding the evaluation of the game states where an heuristic () is needed, all bots will make use of the same one, it being the score diference between the players. Finally, to evaluate the performance of each bot the number of wins will be used.
Two experiments have been performed: 1. The best parameter combination is obtained for bots MCTS, OE and NTBOE. For each of this bots a set of possible values per parameter will be chosen. The other parameters are ifxed to a particular values. Then, 1000 games will be played against OSLA Player per each possible value for the parameter, keeping the rest of the parameters constant. Table 1 shows the configuration of this experiments. 2. An all versus all tournament has been performed among all the tuned versions of the bots. 1000 games have been played between two methods.
Table 2 shows the results of the experiment performed to tune the parameter in MCTS. The optimum value is = 8. Table 3 shows the results of the experiments done for tuning the parameters of the OE algorithm. According to the results obtained the parameters for this method has been adjusted to = 125, = 0.15, = 0.15. Table 4 shows the results of the experiments done for tuning the parameters of the proposed NTBOE algorithm. According to Bot to be tuned, parameter to be tuned, possible values and how other parameters have been fixed. the results obtained the parameters for this method has been adjusted to = 5, = 0.55, = 1000. the least performant bot, which is the expected result given that it doesn’t make any attempt on finding a good combination of actions for the whole turn. Then
relatively closely, showing that it can find combinations of actions but it is not as eficient as the evolutionary algorithms in doing so. Then both OE Player and NTBOE Player are quite ahead, because they use their evolutionary aspect to very eficiently find good combinations of actions. Within them, NTBOE seems to have a not extremely big but clearly significant advantage. In the particular match against OE the proposed NTBOE method was able to won the 60% of the games. This proves that this novel approach to multi-action game solving, proposed on this work, can yield better results than the current state-of-the-art algorithms.
The experiments presented in this work can be easily reproduced by running the Pyhton script https://github.com/dvs99/ASMACAG/blob/master/reproduce_experiments.py.
This paper has presented a novel method called N-Tuple Bandit Online Evolution to play multi action adversarial games. The results obtained have shown that the proposed NTBOE algorithm Results table from the experiment for adjusting OE Player’s , and parameters. Best result in bold. Results table from the experiment for adjusting NTBOE , and parameters. Best result in bold.
NTBEA wins
OSLA wins
Ties 25 75 125 175 75 75 75 75 75 75 75 75 75 5 10 20 50 120 20 20 20 20 20 20 20 20 20 20 0.3 0.3 0.3 0.3 0.3 overcomes state of the art methods when playing ASMACAG. Future work will focus on assessing the performance of NTBOE in other multi action games.