NAIL122 AI for Games�Monte Carlo Tree Search��Peter Guba, Jakub Gemrot
Faculty of Mathematics and Physics
Charles University
Motivation
Motivation�Why should you care?
Motivation�Why should you care?
Motivation�Why should you care?
Motivation�Why should you care?
Motivation�Why should you care?
An intuitive explanation
MCTS – High-level description
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.
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�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
What have you learned so far?�
Go to this link and try to write down your current understanding of MCTS.
Monte Carlo Tree Search Roots�Monte Carlo Method
Monte Carlo Method�Approximating values
Source: https://en.wikipedia.org/wiki/Monte_Carlo_integration
int i, throws = 99999, insideCircle = 0;
double randX, randY, pi;
srand(time(NULL));
for (i = 0; i < throws; ++i) {
randX = rand() / (double) RAND_MAX;
randY = rand() / (double) RAND_MAX;
if (randX * randX + randY * randY < 1)
++insideCircle;
}
pi = 4.0 * insideCircle / throws;
Monte Carlo Integration�Approximating values
Source: https://en.wikipedia.org/wiki/Monte_Carlo_integration
Integral we want to estimate.
Random variable following some distribution, e.g., uniform.
Integral estimation using N points.
Monte Carlo Tree Search Roots�Multi-armed bandit problem
Multi-armed Bandit�How to gamble properly
We kinda expect to have a simulator we can interact with in order to solve the problem before we pull an arm in real-life.
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2), 235-256.
How to select which arm to pull?�Upper Confidence Bounds
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2), 235-256.
In MCTS, this will correspond to the number of pulls in the parent node, not the overall total number of pulls!!!
How to select which arm to pull?�Upper Confidence Bounds
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2), 235-256.
Exploitation part
How to select which arm to pull?�Upper Confidence Bounds
Where does this part come from?
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
How to select which arm to pull?�Upper Confidence Bounds
This shrinks rapidly with increasing number of pulls, so the UCB formula provides an upper bound on the true mean value with a high degree of confidence (hence the name).
How to select which arm to pull?�Upper Confidence Bounds
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2), 235-256.
How to select which arm to pull?�Upper Confidence Bounds
Monte Carlo Tree Search�Going step by step
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�Step 1: Selection
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�Step 2: Expansion
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
Expansion:�If we are using UCB, we must try all available moves before building the next ply. ��Unless we have some game-specific knowledge available, we cannot discriminate between the moves without trying them first.
The strategy here is then either to choose uniformly at random or have the actions taken in some predetermined order.
MCTS�Step 3: Simulation
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
Simulation:�Again, without game-specific knowledge, we can’t discriminate between the available moves, so we pick the moves at random.
MCTS�Step 3.5: Evaluation
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
Evaluation:�Simplest way: 1 = win, 0 = loss (optionally 0.5 = draw)
It is common to use some game score we are maximizing or some heuristic as the reward (in which case, they UCB formula may need to be adjusted).
MCTS�Step 4: Backpropagation
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
Back-propagation:�The back-propagation is then about updating values we track for nodes in order to compute their UCB values. Just take care to correctly recognize, which player is to play in order to correctly interpret values for wins and losses.
MCTS�Choosing a move
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
BestChild:�Finally, selecting a best root child may follow different strategies.
Max – highest reward
Robust – the most visited
Max-Robust – Max+Robust, if none exist continue the search (violating any-time principle)
Secure – maximizes lower confidence bound
Monte Carlo Tree Search�End Notes
MCTS�Pros and Cons
Pros:
Cons:
MCTS�Observations
MCTS�History till 2009
1990 Abramson demonstrates that Monte Carlo simulations can be used to evaluate value of state [1].
1993 Brugmann [31] applies Monte Carlo methods to the field of computer Go.
1998 Ginsberg’s GIB program competes with expert Bridge players.
1998 MAVEN defeats the world scrabble champion [199].
2002 Auer et al. [13] propose UCB1 for multi-armed bandit, laying the theoretical foundation for UCT.
2006 Coulom [70] describes Monte Carlo evaluations for tree-based search, coining the term Monte� Carlo tree search.
2006 Kocsis and Szepesvari [119] associate UCB with tree-based search to give the UCT algorithm.
2006 Gelly et al. [96] apply UCT to computer Go with remarkable success, with their program MOGO.
2006 Chaslot et al. describe MCTS as a broader framework for game AI [52] and general domains [54].
2007 CADIAPLAYER becomes world champion General Game Player [83].
2008 MOGO achieves dan (master) level at 9 9 Go [128].
2009 FUEGO beats top human professional at 9 9 Go [81].
2009 MOHEX becomes world champion Hex player [7].
Taken 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.
MCTS�Literature and other resources
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.
Świechowski, M., Godlewski, K., Sawicki, B., & Mańdziuk, J. (2021). Monte Carlo Tree Search: A Review of Recent Modifications and Applications. arXiv preprint arXiv:2103.04931.
Bandit algorithm and various strategies:
https://towardsdatascience.com/bandit-algorithms-34fd7890cb18#b390
UCB:
https://towardsdatascience.com/the-upper-confidence-bound-ucb-bandit-algorithm-c05c2bf4c13f
That’s it for today!