NAIL139 AI for Games�MCTS adjustments��Peter Guba, Jakub Gemrot
Faculty of Mathematics and Physics
Charles University
MCTS – Reminder
MCTS�High-level description
MCTS iteration
Image adapted from: Santos, A., Santos, P. A., & Melo, F. S. (2017, August). Monte carlo tree search experiments in hearthstone. In 2017 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 272-279). IEEE.
Evaluation
MCTS domain of applicability
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in non-zero-sum games
MCTS in non-zero-sum games�What if one’s win isn’t the other’s loss?
We only need the game to be zero-sum so that we can simplify how we deal with rewards.
Solution: Evaluate states separately for both players, backpropagate both their rewards and switch based on which rewards you make selection in the first step.
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in other than 2-player games
Source papers:
Sturtevant, N. (2008). An analysis of UCT in multi-player games. ICGA Journal, 31(4), 195-208.
Baier, H., & Kaisers, M. (2020, August). Guiding multiplayer MCTS by focusing on yourself. In 2020 IEEE Conference on Games (CoG) (pp. 550-557). IEEE.
MCTS in other than 2-player games�What if we can’t just alternate between the players?
Single-player games
All that needs to be done is to always maximise the players reward instead of alternating between minimising and maximising.
Multi-player games
Similarly to non-zero-sum games, this means we can no longer infer the rewards of other players from those of one player, so we backpropagate rewards for all players.
MCTS in other than 2-player games�What if we can’t just alternate between the players?
What to do when there are too many players though?
In games with many players, one may not even explore the tree deep enough to pick a second move for the initial player
Some programs combat this using some version of the ‘paranoid assumption’ – assumption that all the other players formed a coalition against the player being modelled
Experiments with them seem to indicate that increasing search depth doesn’t improve performance unless they reach another level of the tree where the initial player moves
MCTS in other than 2-player games�What if we can’t just alternate between the players?
Opponent Move Abstraction
An approach based on the idea that, in games with multiple players, one should be more interested in their own moves than other players’
Build a search tree as usual
When backpropagating, aggregate rewards for moves that were preceded by the same moves of the player being modelled
MCTS in other than 2-player games�What if we can’t just alternate between the players?
MCTS in other than 2-player games�What if we can’t just alternate between the players?
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in simultaneous-moves games
Source paper:
Churchill, D., & Buro, M. (2013, August). Portfolio greedy search and simulation for large-scale combat in StarCraft. In 2013 IEEE Conference on Computational Inteligence in Games (CIG) (pp. 1-8). IEEE.
MCTS in simultaneous-moves games�How to model simultaneous moves?
First idea – just use normal MCTS
This means that one player will know the other’s moves, which will most likely completely mess with planning.
Example – if this were applied to rock paper scissors, the second player could always choose the move to win.
MCTS in simultaneous-moves games�How to model simultaneous moves?
Better idea – change the datastructure
Basically, the difference to normal MCTS is that, instead of each node having a one-dimensional list of children (which can be represented as a tree), it should have a two-dimensional one.
MCTS in simultaneous-moves games�How to model simultaneous moves?
Better idea – change the datastructure
Basically, the difference to normal MCTS is that, instead of each node having a one-dimensional list of children (which can be represented as a tree), it should have a two-dimensional one.
Image taken from: Schaeffer, M. S. N. S. J., & Shafiei, N. (2009). Comparing UCT versus CFR in simultaneous games. In IJCAI Workshop on General Game Playing.
MCTS in simultaneous-moves games�How to model simultaneous moves?
Better idea – change the datastructure
Basically, the difference to normal MCTS is that, instead of each node having a one-dimensional list of children (which can be represented as a tree), it should have a two-dimensional one.
When we apply this change to the structure we are building, we can perform selection by computing the UCB values of actions for both players.
Image taken from: Schaeffer, M. S. N. S. J., & Shafiei, N. (2009). Comparing UCT versus CFR in simultaneous games. In IJCAI Workshop on General Game Playing.
MCTS in simultaneous-moves games�How to model simultaneous moves?
Better idea – change the datastructure
This algorithm will not necessarily converge to a Nash Equilibrium however which means it can be exploited.
The solution to this is using a different tree policy than standard UCB – these are a bit complex however, so we won’t go over them here.
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in continuous games
Source paper:
Ba, S., Hiraoka, T., Onishi, T., Nakata, T., & Tsuruoka, Y. (2019, November). Monte Carlo Tree Search with variable simulation periods for continuously running tasks. In 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 416-423). IEEE.
MCTS in continuous games�
Two possibilities
- The game runs in real time
- The action space is continuous
MCTS in continuous games�What if actions take time?
When do we do our planning?
In real-time games, the world is changing while we think.
We could re-plan every game tick, which side-steps this problem, but is potentially very inefficient.
Also, no plan persistency in that case.
MCTS in continuous games�What if actions take time?
VSP MCTS (Variable Simulation Period MCTS)
Instead of just choosing actions, choose pairs of actions and time intervals for waiting before selecting the next action
Continuous search space means we can’t enumerate all actions – use progressive widening (limit each node’s number of children based on the number of times it has been visited)
Use an algorithm called HOO (hierarchical optimistic optimization) to generate time intervals to try
MCTS in continuous games�What if actions take time?
Selecting time intervals using the HOO algorithm
Actions and times are selected separately (actions can just be picked randomly)
For every MCTS node, a tree is constructed for selecting time intervals
Each node of this tree contains a closed time interval and an associated reward
MCTS in continuous games�What if actions take time?
Selecting time intervals using the HOO algorithm
Start with just the root node, which contains the entire time interval we are considering
Every time a new time interval is needed:
MCTS in continuous games�What if actions take time?
Selecting time intervals using the HOO algorithm
(The example shows 2D HOO, which is why there are always 4 children in the right-hand tree – in the version we discussed, there would be two.)
MCTS in continuous games�What if we have infinite actions?
What about games with continuous action spaces?
A combination of HOO and progressive widening can also be used to generate actions
If there are multiple sources of continuity, a multidimensional version of HOO can be used
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in stochastic games
Source paper:
Bjarnason, R., Fern, A., & Tadepalli, P. (2009, October). Lower bounding Klondike solitaire with Monte-Carlo planning. In Nineteenth international conference on automated planning and scheduling.
MCTS in stochastic games�How to take chance into accout?
First idea – take all possibilities into account
For example, randomness in the game comes from throwing a six-sided die, you could treat each outcome as a different move in the search tree (you would then select from among these moves randomly instead of using some sophisticated tree policy).
This approach falls apart when there is too much randomness. For example, in a game of Klondike Solitaire, this would mean trying all different configurations of the hidden cards.
MCTS in stochastic games�How to take chance into accout?
Improvement – take only some possibilities into account
You could limit the branching factor in the random nodes.
In experiments done on Klondike Solitaire, this didn’t seem to improve the performance of UCT. It did improve its speed however, so it should be able to explore more options in the same amount of time, making it more useful in practical applications.
MCTS in stochastic games�How to take chance into accout?
A different approach – building multiple trees
Run MCTS multiple times, each on a different fully determinized game, then average the results.
Performed better than either of the two previous approaches on Klondike Solitaire.
MCTS domain of applicability�
Games where MCTS is applicable
MCTS in imperfect information games
Source papers:
Van den Broeck, G., Driessens, K., & Ramon, J. (2009). Monte-Carlo tree search in poker using expected reward distributions. In Advances in Machine Learning: First Asian Conference on Machine Learning, ACML 2009, Nanjing, China, November 2-4, 2009. Proceedings 1 (pp. 367-381). Springer Berlin Heidelberg.
Cowling, P. I., Powley, E. J., & Whitehouse, D. (2012). Information set monte carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games, 4(2), 120-143.
Cowling, P. I., Whitehouse, D., & Powley, E. J. (2015, August). Emergent bluffing and inference with Monte Carlo tree search. In 2015 IEEE conference on computational intelligence and games (CIG) (pp. 114-121). IEEE.
MCTS in imperfect information games�How to treat unobservable information?
Randomness and partial information
The difference between the case discussed in the previous section and in this one is that the hidden information considered there is provided by the environment hence one does not need to model an opponent’s decision making over it
MCTS in imperfect information games�How to treat unobservable information?
Transforming opponent nodes into random ones
It is possible to model the opponent’s moves as a probability distribution learned from game replay data
This has been successfully applied to Texas Hold ‘em Poker
Should work fine with the first approach mentioned in the previous section, but not straightforwardly applicable to the second one (as determining cards doesn’t determine the opponent’s actions)
MCTS in imperfect information games�How to treat unobservable information?
What if we can’t train a good opponent model beforehand?
We can try using determinizations again
If we use the same approach as in the previous section, this will give us access to information we shouldn’t have
MCTS in imperfect information games�How to treat unobservable information?
Information sets to the rescue
Information set (for a player) = the set of states that are indistinguishable from the given player’s point of view
If you have some cards that I can’t see, then all the states which differ only in the identities of those cards belong in the same information set for me
MCTS in imperfect information games�How to treat unobservable information?
Information Set MCTS (ISMCTS)
Have nodes correspond to information sets instead of game states
Sample a new determinization at the start of every iteration and run the iteration using that determinization
All determinization therefore update the same tree, unlike in the approach discussed previously
MCTS in imperfect information games�How to treat unobservable information?
Information Set MCTS (ISMCTS)
Problem – the opponent’s moves are treated as fully observable
If we generalise the moves in the same way as we did with states, we destroy the opponent model (their actions are selected at random – we can’t model good decision-making if we don’t know their decision)
These two issues seem complementary – you either have one or the other
MCTS in imperfect information games�How to treat unobservable information?
Multiple Observer ISMCTS (MO-ISMCTS)
Build multiple ISMCTS trees, one for each player
At each turn, pick an action using the data in the corresponding player’s tree
Better, but the opponent model still suffers from the fact that its tree’s nodes correspond to information sets, thereby blending together information from different determinizations
MCTS in imperfect information games�How to treat unobservable information?
Many Tree ISMCTS (MT-ISMCTS)
Build one ISMCTS tree for every player’s information set
This allows for accurate opponent models while also accurately simulating hidden information
Armed with this, we can implement inference and bluffing
MCTS in imperfect information games�How to treat unobservable information?
Inference and MT-ISMCTS
Inference = figuring out what a given player’s hidden information is likely to be
Make trees persist across turns
Keep track of how many times each node is encountered when using a given determinization. Once the opponent makes a move, it is possible to use this to update the probabilities assigned to different world states
This can then be used to bias the generation of determinizations during subsequent calls of the algorithm in favour of more likely ones
MCTS in imperfect information games�How to treat unobservable information?
Bluffing and MT-ISMCTS
In the basic version of ISMCTS, you only sample determinizations that you know to be possible, ignoring the opponents’ points of view
To implement bluffing, it’s necessary to use self-determinizations = determinizations that you know to be false, but other players may consider plausible
To incentivise bluffing more, one can take a look at which move in the self-determinized trees was picked the most times and pick it instead of the real best action (provided that it isn’t too bad)
MCTS domain of applicability�
Games where MCTS is applicable
MCTS with multiple objectives
Source paper:
Perez, D., Mostaghim, S., Samothrakis, S., & Lucas, S. M. (2014). Multiobjective monte carlo tree search for real-time games. IEEE Transactions on Computational Intelligence and AI in Games, 7(4), 347-360.
MCTS with multiple objectives�What if succeeding isn’t as simple as not dying?
(Only works for single-player games)
Multiple objectives = multiple reward functions
How to adapt the UCB formula?
MCTS with multiple objectives�What if succeeding isn’t as simple as not dying?
MCTS in imperfect information games�How to treat unobservable information?
Hypervolume Indicator
MCTS domain of applicability�
Games where MCTS is applicable
Making MCTS more effective
1. Score bounded MCTS
2. All moves as first (AMAF)
3. Transposition tables and DAG
Score Bounded MCTS
Source paper:
Cazenave, T., & Saffidine, A. (2010, September). Score bounded Monte-Carlo tree search. In International Conference on Computers and Games (pp. 93-104). Springer, Berlin, Heidelberg.
Score Bounded MCTS�Alpha-beta-like cuts
Score Bounded MCTS�Alpha-beta-like cuts
Score Bounding propagation (pessimistic bounds)
Score Bounded MCTS�Alpha-beta-like cuts
Score Bounding propagation (optimistic bounds)
Score Bounded MCTS�Alpha-beta-like cuts
All moves as first (AMAF)
First mention:
Gelly, S., & Silver, D. (2007, June). Combining online and offline knowledge in UCT. In Proceedings of the 24th international conference on Machine learning (pp. 273-280).
Follow-up paper:
Gelly, S., & Silver, D. (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 175(11), 1856-1875.
All moves as first (AMAF)�Reusing information from simulations
AMAF idea
Picture the game Go. During a playout, we might be playing moves, which are either viable on top of the tree or as siblings to nodes selected during tree descent (selection phase).
As we know the result of the playout for these moves, we can update values of these nodes; if we reorder moves within the playout, these move would be a valid playout for such a nodes.
All moves as first (AMAF)�Reusing information from simulations
AMAF example
Image adapted from: Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., ... & Colton, S. (2012). A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1), 1-43.
Transposition tables and DAG
Used by, e.g.:
Kozelek, T. (2009). Methods of MCTS and the game Arimaa. Diploma thesis, Charles University, Prague, Czech Republic.
Méhat, J., & Cazenave, T. (2010). Combining UCT and nested Monte Carlo search for single-player general game playing. IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 271-277.
Thorougly discussed by:�Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS is building a tree, games can be DAG
When game is known to form DAG often, MCTS will not share information between nodes representing the same game states.
The idea of transposition tables is to track such a nodes, e.g., by maintaining a dictionary using a node state hash as a key, and then share state values between such a nodes.
Which leads to an idea to maintain DAG instead of a tree.
Where to store MCTS data?
How to treat backpropagation?
How to treat selection?
Transposition tables / DAG�How to work with graphs?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Backpropagation
We’re storing data with edges, all good.
How about the backpropagation then?
Should we backpropagate:
a.k.a. update-all
a.k.a. update-descent
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Backpropagation
We’re storing data with edges, all good.
How about the backpropagation then?
Should we backpropagate:
a.k.a. update-all
a.k.a. update-descent
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Tempting, as it would propagate information from the playout through all branches leading to the expanded node.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Backpropagation�w/ update-all
Let’s consider the following game after initial 4 iterations where we use update-all paths to the root strategy.
Bottom edges ware taken 1x, 1x, 2x but update-all result in seemingly taking 6 simulations from the root.
What happens next?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Backpropagation�w/ update-all
We will start
selecting left
edge from the
root which will
lead into
ignoring
the right one!
Never arrive to
optimum.
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Backpropagation�w/ update-all
The problem�lies in backprop.
where we
update-all
paths to root.
Life’s not
that easy…
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
MCTS with DAG – Selection problem
How about selection now?
Constructing DAG, we might expand an edge (an action) that will lead to a node that is well understood already…
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Transposition tables / DAG�How to work with graphs?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
Recursive weighted “exploit” score of the edge.
Transposition tables / DAG�How to work with graphs?
Image adapted from: Saffidine, A., Cazenave, T., & Méhat, J. (2012). UCD: Upper Confidence bound for rooted Directed acyclic graphs. Knowledge-Based Systems, 34, 26-33.
That’s it for today!