# A Survey of Planning and Learning in Games
## 4 Planning in Games
### Discussion  
The previous subsection presented some planning techniques used in the context of game AI. The discussion also highlighted the different degrees of adoption and success of these techniques in the domain of games. An interesting point to make in this regard is that while some of the techniques mentioned were tailored specifically for games (e.g., Minimax and MCTS), others were borrowed from other research fields (e.g., CBP, HTNs, and Automated Planning) and consequently had to be extended to cope with the specificities inherit to the virtual environments where games take place, such as uncertainty and partial observability. AP techniques are among those that suffered the most in terms of adoption because of this, although several extensions have been proposed in order to address these difficulties. Another interesting observation is that while some of these techniques were specifically tailored for games, their different underlying approaches have had a significant impact on their applicability. Minimax and Alpha-Beta are such examples. While having enjoyed large success in classical board games, as fundamental pieces of some of the most well-known milestones in AI (e.g., IBM's Deep Blue and Chinook), when faced with game environments featuring large branching factors or lacking good heuristics such as in Go, uncertainty such as in backgammon, and continuous and/or real time decision making such as in RTS games, some of their underlying limitations ended up being exposed and ultimately proved to be an obstacle to their adoption in more complex games and different game genres. MCTS on the other hand, while initially applied to the game of Go, where it achieved great success, proved to be more extensible and has gained significant popularity and applications in other game genres, such as RTS games. A final interesting remark concerns the use of planning techniques (i.e., HTNs and MCTS) in the domain of virtual reality and, more specifically, serious games. It should be expectable to see more examples of the integration of planning in the domain of virtual, augmented, and mixed reality in the future. Similarly to what was done regarding learning techniques, Table 3 presents an overall comparison concerning the different planning techniques presented. Again, the aspects used for the comparison represent some of the relevant questions that researchers/practitioners may ask themselves when deciding on which technique to use to solve a specific problem related to game AI. Regardless of this, all of these techniques have found application in the context of games. Table 4, found at the end of this subsection, presents a brief summary of some of these applications. Section 5 presents even more examples of application of these techniques in combination with learning techniques in the context of games. \begin{table}
\begin{tabular}{c c} \hline \hline
**Research Topics** & **Planning Techniques** \\ \hline DDA & MCTS [26; 168], BT [214] \\ GVGP & MCTS [177; 178; 179] \\ MaM/MiM & (HTN, MCTS) [162], MCTS [171; 172; 173], RP [186], POP [187] \\ OM & CBP [210], MCTS [175] \\ LID & A* [151], CBP [208; 209] \\ PCG & POP [195] \\ GDST & (A*, RRT, MCTS) [152], RRT [200; 201; 202; 203], BT [212; 213] \\ A* [150], RRT [198], CBP [206]. HTN [7,155; 156], \\ AGAI & MCTS [169; 170; 174; 176], (DP, RP) [189], EP [188] \\ PF & A* [148; 149], RRT [197] \\ MAC & HTN [157; 158], MCTS [166; 167], PSP [191] \\ NP & HTN [161], TP [192], EP [193], INP [194] \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Table presenting some of the most common game AI research topics together with examples of proposed implementations using the planning techniques discussed.