## Algorithms for Game AI
However, searching more deeply costs more computation, and the search depth is usually, in practice, fixed or decided by iterative deepening to limit the time cost. In multi-agent competitive games, adversarial search algorithms such as Minimax [13] are often used, where the agents must act against opponents and maximize their own benefits. Monte Carlo Tree Search (MCTS) [14] is one of the most popular search algorithms due to its efficiency and robustness with no domain knowledge needed. Many variants of MCTS have been proposed to further improve its efficiency by incorporating upper confidence bounds [15], domain knowledge [16], and parallelization [17]. * Optimization algorithms refine solutions to achieve specific goals, which are used to train agents with parameterized models. Among these, linear programming algorithms optimize objective functions under a set of constraints; evolutionary methods, such as Genetic Algorithms (GA) and Evolutionary Strategies (ES) [18], create a population of individuals where the fitter ones have a higher probability of reproducing and inheriting part of their structures, inspired by the process of natural selection; gradient descent is the foundation of deep learning, which achieves the efficient parameter tuning of modern artificial neural networks. These algorithms train policy models or value models containing prior knowledge before actual gameplay, which can be combined with real-time planning algorithms during the inference phase. * Supervised learning is a data-driven method to learn patterns and relationships from labeled data. In the context of game AI, the data usually refer to the game states or observations, and the task is to learn a policy model or value model that predicts the action or the estimated value under the current state. These algorithms require a great deal of labeled data in the form of state-action or state-value pairs, usually collected from data on human gameplay or data generated by other game-playing algorithms. In general, there are two types of applications based on the data source. Applying supervised learning on human data can learn implicit human knowledge and store it in policy models or value models. Another type of application, known as policy distillation [19], relies on data generated by other models, which is used to distill a lightweight model from a larger one to improve computational efficiency or to consolidate multiple task-specific policies into a single unified policy. * Reinforcement learning (RL) studies how agents should take actions in an environment to maximize cumulative rewards over time. Typically, RL models the environment as a Markov Decision Process (MDP), where the transition probability and rewards satisfy the Markov property that they are only related to the current state and action. When the transition model is known, generalized policy iteration, such as value iteration, uses dynamic programming to solve the optimal policy and its value function based on Bellman Equation. However, in most cases, the environment model is unknown, and model-free algorithms are preferable as they learn from experiences by interacting with the environment. There are two kinds of model-free algorithms: \(\bigcirc\) Value-based algorithms optimize the policy by approximating the values of states or state-action pairs and selecting better actions based on these values. There are different ways to update the value function [20]. A Monte Carlo (MC) algorithm updates the value function based on the cumulative rewards towards the end of the episode, while a temporal difference (TD) algorithm updates the value function based on the current reward and the value of the next state in a bootstrapping manner. Algorithms such as DQN [21] use deep neural networks to approximate the state-action value function, which can be applied to games with large state space. \(\odot\) Policy-based algorithms directly learn parameterized policies based on gradients of some performance measure using the gradient descent method.