# A Survey of Planning and Learning in Games
## 4 Planning in Games
### Planning Techniques
#### 4.1.3 Monte Carlo Tree Search  
Monte Carlo tree search [146] combines tree search with Monte Carlo (MC) evaluation and is an example of decision-time planning. The core idea in MCTS is to iteratively grow a tree that accumulates value estimates obtained from MC simulations. These estimates are used to direct subsequent simulations towards more promising trajectories, making the tree effectively asymmetric. The basic implementation of MCTS is composed of four steps [95]: selection, expansion, simulation, and backup. Starting from the current node (or state), referred to as the root node, and during the selection step, the tree policy traverses the tree until a leaf node is reached. In the expansion step, one or more child nodes are added to this leaf node, further expanding the three. These child nodes consist of states that can be reached from the leaf node via yet unexplored actions. Next, in the simulation step, a complete episode is simulated, starting from the selected node or one of its newly-added child nodes. A rollout policy is used to select the actions during this simulation. Finally, during the backup step, the return generated by the simulated episode is backed up to update the statistics of the nodes traversed by the tree policy during the current iteration; see Figure 7.  
These four steps continue to be executed (always starting from the root node) until no more time is left or some other computational resource is exhausted, at which time MCTS chooses an action according to some method that depends on the statistics accumulated in the root node (e.g., the action having the highest action value or the action with the largest visit count). Several methods can be used to implement both the tree and rollout policies. A popular implementation of the tree policy is the selection rule used by the upper confidence bounds (UCB) applied to trees (UCT) [163] algorithm (a variant of MCTS), defined as:  
\[a^{*}=\operatorname*{argmax}_{a\in A(s)}\left\{Q(s,a)+C\sqrt{\frac{lnN(s)}{N(s, a)}}\right\}, \tag{1}\]  
where, for a given action \(a\) and state \(s\), the statistics accumulated during the simulations are used to derive respectively: \(Q(s,a)\), the average reward obtained for a given action \(a\); \(N(s,a)\), the number of times action \(a\) has been performed in state \(s\); and \(N(s)\), the number of times state \(s\) has been visited. \(C\) is a  
Figure 7: The four steps of the Monte Carlo tree search (MCTS) process: selection, expansion, simulation, and backup. constant (also called the exploration constant) used to balance exploration and exploitation. \(a^{*}\) denotes the action that is selected. The rollout policy is commonly implemented via a uniform random selection policy. Over time many different implementations have been proposed for these policies, as well as multiple variations and enhancements to the MCTS algorithm. A survey can be found in [164]. Section 5.2.5 also presents some of this work, in particular that concerning the combination of MCTS with several learning techniques in the context of games. In the domain of game AI research MCTS was first applied to the game of Go where it achieved very good results (i.e., Crazy Stone [146] in \(9\times 9\) Go). MCTS and its variants (e.g., UCT) eventually led to master level play in Go (e.g., MoGo [145] in \(9\times 9\) Go) and currently are used as the base of most of the strongest Go programs [165]. These early successes contributed to the popularity of MCTS and its subsequent use to solve a plethora of different challenges in many other game genres. Examples of this include ad-hoc teamwork coordination [166], solving cooperative problems with no prior knowledge [167], dynamically adjusting the difficulty of games [26; 168], generating agents that exhibit a more human-like playing style [169; 170], micromanagement in RTS games [171; 162; 172; 173], generating personas for NPCs in fighting games [174], opponent modeling [175], and controlling several agents in constrained learning scenarios applied to serious games [176].