Why is Good AI for Games So Difficult?
A Simple Question That Needs Explanation
AI and Games is a YouTube series made possible thanks to crowdfunding on Patreon as well as right here with paid subscriptions on Substack.
Support the show to have your name in video credits, contribute to future episode topics, watch content in early access and receive exclusive supporters-only content
Why is it so difficult to build good AI for video games?
You hear all these stories in the news about AI learning to play StarCraft, Dota2, Overcooked, DOOM, Street Fighter, Rocket League and more, but yet when you boot up the latest and greatest on your chosen platform, non-player characters and other enemy opponents don't seem to be anywhere near as smart.
So what gives? In this issue of AI and Games, we're going to unpack this question.
Playing a Game VS Being the Game
Despite my making over 100 videos on the subject of AI for video games on YouTube, this is an issue I've never succinctly described. But it's increasingly one that needs to be addressed: if a team of researchers can train an AI to play your favourite AAA title, while the built-in AI for regular play is nowhere near as complex. It's understandably a question people will ask. For this issue, I am focussing solely on the challenge of a games programmer trying to make compelling AI, rather than the challenge of a researcher or hobbyist trying to train an AI to play a game. These are two distinctly different problems, and I can dedicate a separate article to the latter of the two at a later date.
With that in mind, it's important to distinguish between these two things: an AI that learns to play a game operates in a very different capacity from one that is programmed to be part of a game you're playing on your chosen platform. If we consider for example StarCraft 2, where Google DeepMind trained the AlphaStar bot to become a grandmaster, this is a machine learning AI that is trained outside of the game itself. It spends weeks learning to become the very best player, costing millions of dollars to produce, and relying on data recorded of top-tier human players that it learns from. Once trained, it can make decisions very quickly given it already knows how to respond to these scenarios being presented to it. In addition, it isn't part of the game itself, it's an external AI program making decisions that pass in as inputs to the game, much like a human player would.
Meanwhile, the AI built into the game, is created by a team of programmers and designers during the development process. It has to accomodate for varying skill levels, address the needs of game designers who want the AI to operate in a specific way, and also is at the mercy of the games resources. AI has to operate alongside core game logic, rendering, physics, input management, online connectivity and much more besides. Plus, as we've seen throughout the dozens of episodes I've made on YouTube over the years, the types of AI techniques used in games are more often than not quite different from those you're seeing in the news.
The likes of AlphaStar and the OpenAI Five are machine learning systems that are trained on vast server farms, and generative AI tools like DALL-E and GPT still need to run on these servers after training given their size and complexity. Whereas non-player characters and enemy AI in games typically use symbolic AI, where the system looks at all of the possible configurations of the world, and determines which configuration it should reach by searching for a path towards it and it does so at runtime on your PC or console. There are exceptions to this of course, but there are also reasons for why this is often adopted in a video game, which we'll unpack later.
Now to really get into the meat of the topic, we're going to discuss some core AI principles that should get those brain juices pumping.
The State Space Problem
For those without a background in computer science or AI, here is some theoretical fundamentals; basic terminology that anyone who has studied the field will be familiar with, and it's how we can begin to define the challenges presented by different games from the perspective of a developer.
Perhaps the most critical element to understand is the notion of a state: a snapshot of a problem in which the AI is trying to solve. In a game, this can range from the position of relevant items in strategy games between turns, to the position and activities of all enemies in the current frame of a first person shooter. It's important to only capture the relevant information of the current state, rather than fill it up with unnecessary info, given every possible unique value that can exist will influence the number of unique states that exist. Knowing how many pixels are rendered in the health UI is far less useful, than simply knowing how much health the player has a number.
Based on the current state, an AI can then make an action. The idea being that the action will change the state in some way. The easiest way to understand this is the movement of a piece in a board game. The action taken is one that is permissible by the game state, and in doing so it often (but not always) leads to a new state. This is known as a state-transition system or function: the idea that actions in the world will change it provided we pick good actions in key moments.
Understanding the number of possible states, the number of actions and how they interlink is a big issue for any AI system, be it for in-game behaviour or for trained AI bots. This web of states connected by actions, is known as a state space. A symbolic AI system needs to be able to search the state space for good collections of actions to execute in sequence. While a machine learning system needs to learn what actions make the most sense in a given state, often by measuring the value of an action, either in its immediate future (because you killed an enemy) or 10 minutes from now, given you put enough good actions together to win the game.
But the relationship between states and actions can become increasingly fraught, and make it difficult for a game developer or researcher to approach the problem. For one, the sheer amount of states can be an issue. A small and simple puzzle game may only have hundreds, or thousands of unique states, but for many a contemporary videogame, when you consider the number of unique situations that can exist, it quickly moves into the millions if not billions. In fact, as discussed in my previous episode on AlphaStar, it's estimated that StarCraft is as described below:
For clarity: that number is a two followed by 1685 zeroes. That’s a number larger than the total number of atoms in the universe.
But to make matters worse, are notions of determinism and observability. Determinism is essentially whether there is any random chance at play in the game. This can mean we can't guarantee based on a given state whether an action will execute as intended, or can predict the behaviour of other AI characters. It's what made Ms. Pac-Man a much more complex game for players when compared to the 1980 original, given now the ghosts can opt to move randomly.
Plus, all of this relies on the idea that we know for sure the current state of the game. Do we recognise the actual state of the game? If you consider a strategy game, or a card game you typically don't know the entire state, only what is directly in front of you. So the system has make a judgement based on limited knowledge or guess what state it's currently in, which can equally problematic.
The Challenge for the Game Developer
Now this is but the tip of the iceberg for a myriad of technical aspects of AI. But from here we have enough of a grasp to begin to understanding why, as a video game developer, building AI can prove a challenge.
It's important to state that, from the top, the resulting system that makes decisions needs to be fast. And depending on the genre, that speed can often be in but mere milliseconds. An enemy in a first-person shooter needs to come up with an action that makes sense now, not spend 3 seconds thinking about it. Otherwise by the time it comes up with a super intelligent solution to the problem, the situation has changed so drastically the solution is largely useless. Plus if it did spend 3 seconds thinking about it, it would probably cause the games performance to stutter. While we're long passed the days of the PS3 and Xbox 360, where games like Spec Ops: The Line had strict limits of only 8 active AI at once, the performance budgets for AI characters haven't improved drastically in the years since. Largely because of all of the flashy graphics, but that's an issue for another time.
To maintain good performance, in games it's common for both the problem space to be rapidly reduced, but the mechanisms to come up with solutions are much more truncated. Systems like Finite State Machines and Behaviour Trees solve this problem in two distinct ways: first they ensure that logic for possible actions is tighter and more explicit, it reduces the process of finding and selecting the correct action to a series of conditions. This is useful for a game designer, given you know why an AI is going to behave in the way that it does, and can account for a variety of circumstances. But that in turn robs the AI of more intelligent or interesting decisions it could possibly make.
Alternative solutions, such as planning systems like in FEAR help to resolve this. Goal Oriented Action Planning uses a description language to allow the AI to search for good combinations of actions to create plans of attack. But even then this is tightly constrained, with most plans in FEAR only being a handful of actions in length and even then it has to re-assess whether that plan is valid as it executes, given the plan to jump through a window now no longer makes sense because the player is now standing in the way.
Plus we haven't factored in things like what information about the state of the game each AI should know, what goals they should have, whether those goals change, where in the game world can they move? How do you differentiate between valid options? This latter point a concept I explored in my AI 101 episode on Utility AI, which often helps solve this problem.
All of this highlights the problems that exist for creating non player characters in games, the need to make intelligent decisions quickly is often one that - if calculated optimally for every character - would make games less performant and often result in sluggish behaviour for what is meant to be an interactive medium. While many of the games highlighted here are older and subject to stricter system limitations, these problems still persist today. Games are increasingly more complex environments as the technology continues to make significant gains, and that makes it all that much harder to maintain the illusion of intelligence across the entirety of a gameplay experience.
This alone is why we often see concessions being made. AI that cheats and has access to knowledge it shouldn't in the likes of a strategy or horror game makes sense because it allows for it to make decisions that fit the spirit of the game more effectively than trying to operate without it. AI characters that fake collaboration in the heat of the moment is more practical than trying to get two systems to work together to figure out a good strategy. Even trying to anticipate the players actions can be a nightmare, given players are unreliable and prone to changing up playstyles or approaches as situations unfold, so a Director AI may cheat and read information directly from the player to help it out.
In each of these cases, it's more important to ensure the experience is fun, rather than the AI be exceedingly intelligent. Because at the end of the day, players don't want something that is as intelligent as it could be. Because AI in a game that operates at the peak of its faculties isn't fun to play against. You want something interesting and fallible, and that's a challenge in and of itself.
Machine Learning for Video Games
Now you might have read to all of this and then thought, well that's because we're still using older AI techniques: state machines, utility functions, planning algorithms. I already mentioned the use of machine learning and deep learning, why isn't that just used all of the time?
With machine learning it's a chicken and egg problem: you need the game to be ready in order for the ML system to learn how to play within the rules you've set. This creates the final trained system (often referred to as a policy), which will know what to do for each state in the game it encounters. But if the game is changed, then it could have an impact on the quality of the policy. And so you need to train it again. This doesn't really work for a game that is in development, given you're often fixing bugs, making adjustments or even finalising and adding content at various stages of the development timeline. Any one of these can lead to the policy having to be retrained.
This is what makes big success stories like AlphaStar and the OpenAI Five misleading: given those systems were trained years after the game came out, based on a large amount of existing replay data, that can only be generated by an online community playing the game regularly after launch. But even then, it suffers from the same limitations: given you'll have noticed that neither of these systems have ever re-appeared in their respective games. The reason for that? The games get patched with balance changes, and more often than not in games such as StarCraft and Dota, it means that the trained policies drop in quality significantly as a result of changes to the meta, only it's much harder (and more expensive) for them to readjust to these changes compared to a regular player.
This isn't to say it's impossible to use ML for enemy AI, but you'll notice from many of the examples I've listed over the years on AI and Games, such as Forza and Gran Turismo, they tend to be in complex but tightly defined problem spaces: in fact racing games are a fantastic place to experiment with them. However, as discussed in a previous article, we tend to find more use for machine learning in other areas of game development.
Closing
This episode of AI 101 has been about highlighting why AI is a real challenge in the context of game development. Naturally I can't cover the whole subject in one readily accessible YouTube video, but hopefully you get the idea (and of course, all you game devs out there, get in the comments and share the problems you've experienced over the years). Meanwhile, in some future episodes of AI 101 I will dig deeper into specific genres: look at a genre of game, and explore why it is difficult to build AI for it, as well as the common approaches that are taken by developers to make games for it. Plus I'll also unpack the challenges for researchers in training AI to play games as well. Be sure to leave a comment or two with your own ideas!
Special thanks to the AI and Games Production Team on the AI and Games Patreon who suggested this topic. The Production Team are my top crowdfunding supporters, and every month we have meetings where I talk about everything in the pipeline, but also get critical feedback and suggestions from the team that we then discuss in more detail. It was the Production Team's idea not only for this episode, but also for future topics, and together we've ironed it out into what you're seeing now.