# A Survey of Planning and Learning in Games
## 1 Introduction  
Games have always been widely used as a development and testing environment in the study of artificial intelligence (AI) in academia [1]. The fact that games are well defined by explicit rules, vary greatly in the challenges they pose (e.g., the challenges posed by a puzzle game are very different from those posed by a real time strategy (RTS) game) and that the techniques developed in the domain of games can be transferred to other research fields (e.g., education, psychology) are some of the aspects that have greatly contributed to this [1]. While initial research on game AI focused particularly on classical board games such as chess and checkers, more recently video games have attracted significant research interest, a fact proven by the several international competitions (e.g., the General Video Game AI (GVGAI) competition [2], the General Game Playing (GGP) competition [3], and the Geometry Friends Game AI competition [4]) held annually in multiple international conferences dedicated to game AI (e.g., the Conference on Games (CoG), formerly Conference on Computational Intelligence and Games (CIG), the Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), and the International Conference on the Foundations of Digital Games (FDG)). This growing interest has also been fueled by an increasing commercial interest by the gaming industry on finding solutions to create games that are more enjoyable, challenging and engaging, and that ultimately provide a more personalized experience to the human players, in the form of, for example, more sophisticatedAI (i.e., non-player characters or NPCs) that exhibit more complex behaviors and skills and act more naturally and human-like [1; 5; 6; 7; 8]. In terms of academic accomplishments, games have been at the center of some of the most astonishing and well-known achievements in AI. Ranging from classical board games to video games, AI research has devised computer programs that can play at human master level and even at human world champion level. Examples of these achievements include IBM's Deep Blue [9], the computer program that defeated the world chess champion in 1997; Chinook [10], the World Man-Machine Checkers Champion and the first program to win a human world championship in 1994; Logistello [11], the computer program that defeated the human Othello world champion in 1997; and Quackle, the computer program that defeated the former Scrabble world champion in 2006 [12]. Other examples include KnightCap [13] and Meep [14] in chess and TD-Gammon [15] in backgammon, all of which were able to achieve master level play. More recent examples include the Deep Q-Network (DQN) [16] algorithm, which achieved human level gameplay and above on several games from the Atari 2600 gaming platform, using raw images as input; AlphaGo [17], the computer program that defeated the human European Go champion in 2015; OpenAI Five [18], the first AI to defeat the world champions at an e-sport game, Dota 2, in 2019; and AlphaStar [19], the first AI to defeat a top professional player in StarCraft II in 2018. Planning and learning, two well-known paradigms and subfields of AI, have contributed greatly to these achievements. Planning is concerned with the implementation of computational methods (or computer programs) that can devise plans (i.e., sequences of actions) in order to achieve a specified goal or a set of goals, whereas learning is focused on the implementation of computer programs that automatically improve their performance over time on future tasks by making observations about the world [12]. While both paradigms have achieved great success in the context of game AI, they both present some shortcomings. Planning techniques, for example, require a model of the environment as well as an accurate description of the planning task (e.g., the specification of the actions that can be performed) to plan, which may not be readily available in more complex environments, such as those featured in video games [20].