Choose wisely the tool,
For each has its role, and each,
Can help or hinder

Choosing effective AI methods for a game is largely determined by the characteristics of the game and the characteristics of the AI algorithms you wish to design². These two aspects need to be considered independently of one another.

Some games are purely deterministic, each state is predetermined by the last state. Other games are stochastic however, in that some of what happens is random and cannot be practically predicted⁵. The stochasticity in games varies from completely deterministic as in Chess to games such as Roulette which are largely based on stochastic random outcomes. These random elements mean that player actions don't necessarily determine the outcome of the playthrough of a game and several playthroughs where the player took the exact same actions may not lead to the same outcomes. This can lead to problems when designing AI algorithms. Standard Tree Search algorithms, for example, require modifications to account for this uncertainty and this will generally lead to a programmer having to design much more complex algorithms with more computational requirements, for example in Monte Carlo Tree Search algorithms ¹.

Observability refers to how much information about the game state is available to the player. In a game like Chess, the entirety of the game state is available to the player at all times. This game is therefore described as having perfect information. A real-time strategy game like Age of Empires, however, is about exploring the map and discovering new information about the world to act on. This game would be described as having hidden information and is only partially observable. The simplest approach to designing an AI for a game with hidden information would be to only allow access to the current information available. This works well for action based games, strategy games however have a fog of war with limits the available information significantly and therefore requires active information gathering. This means that making effective AI for games with partial observability often requires designing methods to model the hidden information⁴. This in turn also increases the computational complexity of the AI algorithm.

Another characteristic that needs to be taken into account when choosing an AI design for a game is how often an agent can take an action in the game. On the time granularity scale, there are two different types of game; real-time and turn-based. AI game playing methods are affected by time granularity in that it affects how far ahead you can look. Using a tree search algorithm in a turn-based game like Chess where several actions in the future equate to a fairly short period of time would be feasible to do. With a real-time game where several actions ahead would need to be calculated in a very short amount of time would be much more computationally complex. Macro-actions in a tree search ³ could be used to try to solve some of these issues, however.

1 C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton, "A Survey of Monte Carlo Tree Search Methods", IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, 2012.

2 G. Yannakakis and J. Togelius, Artificial intelligence and games. Cham: Springer International Publishing, 2018. Available: http://gameaibook.org/book.pdf#page=120 [Accessed: 13- Feb- 2019]

3 D. Perez et al., "Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions", IEEE Transactions on Computational Intelligence and AI in Games, vol. 6, no. 1, pp. 31-45, 2014. Available: 10.1109/tciaig.2013.2263884.

4 H. Fujita and S. Ishii, "Model-Based Reinforcement Learning for Partially Observable Games with Sampling-Based State Estimation", Neural Computation, vol. 19, no. 11, pp. 3051-3087, 2007. Available: https://www.mitpressjournals.org/doi/10.1162/neco.2007.19.11.3051.

5 E. Hansen, D. Bernstein and S. Zilberstein, "Dynamic Programming for Partially Observable Stochastic Games", 2004. Available: http://www.aaai.org/Papers/AAAI/2004/AAAI04-112.pdf. [Accessed 15 February 2019].