Game Theory in Video Game AI (and its Limitations)
Anyone who has spent as much time playing video games as I have knows that the behavior of game controlled opponents (also called AIs, CPUs, NPCs, bots, etc.) can make or break a game’s single player experience. We want to be challenged by the computer, but we want to win. We expect computer controlled opponents to react intelligently, but realistically. The trouble is, there is often a fine line between a challenging but fair opponent and one that is simply too difficult and frustrating, or too easy and boring.
Below I have linked two resources relevant to this post. The first, an article from tutsplus by Darran Jamieson discusses what makes an AI for a game engaging. The second, from a book called Emotion Notions: Modeling Personality in Game Character AI by Erik Vick, expands upon some of the uses and limitations of game theory in video game AI.
http://gamedevelopment.tutsplus.com/articles/making-ai-fun-when-good-enough-is-good-enough–cms-23460
It seems perfectly logical that game theory might play a significant role in the development of computer opponents, and this is true, to a point. Without game theory, we might imagine creating an AI opponent for a game which makes decisions completely randomly. In almost all cases, this would not be a compelling opponent to play against. This is where game theory comes in — by considering the choices a human player might make, the computer can produce a proper response to each.
However, this is also where game theory has its limitations. If the computer, using pure game theory concepts, produces and acts upon a best response to each of the human player’s actions, it can quickly become un-fun. As Jamieson notes, such opponents become too predictable — the same player action always results in the same response by the computer. In most cases, the game simply becomes boring. In others, the computer feels far too powerful: imagine playing a fighting game like Mortal Kombat or Super Smash Bros. against an opponent with perfect reflexes and who always chooses the best response to the player’s actions. In these cases, the game becomes no longer about beating the opponent, in a sense, but rather about finding and exploiting a flaw in the machine allowing the player to score a kill.
Jamieson goes on to discuss why, from a player’s perspective, game AIs can often be un-fun opponents. The answer? “Because the artificial intelligence was so obviously artificial” (Jamieson). If one creates a video game AI that uses only game theory to make decisions, every game will be the same. The computer will react in the same way to each of the players movements. It will always choose the best response to the player’s current action. Further, the computer opponent will not plan ahead, potentially making it very easy to defeat. It will choose the best response to the current state of the game, which may harm it in the long run or give the player a very clear path to winning.
On the other hand, if we allow the computer to consider not only the current state of the game, but possible futures states arising from its action and the player’s reaction, the computer can become simply unbeatable. There is a common algorithm called minimax which allows the computer to do exactly this in deciding its next action. Vick examines and explains minimax in the context of a Tic-Tac-Toe game, and shows that implementing the algorithm for Tic-Tac-Toe leads to a no-win-scenario for the player. Regardless of what the player does, there is always a way for the computer to lead the game to a draw (or against a foolish human, a win for the computer), and the perfect minimax algorithm will do exactly this. This happens in many other games as well, such as Checkers, where unbeatable computer algorithms can have been implemented.
By now I hope I have shown that while game theory plays a roll in video game AIs, on its own it is not nearly enough to make a fun, engaging computer opponent. However, there are countless video games today which do implement fun, fair, challenging opponents. How they do this is outside the scope of this post, and a large field on its own. If you are curious though, I do recommend reading through Jamieson’s article. There is plenty on the web to find and read, and Jamieson gives a good overview of some common methods for creating fun opponents.
There is also another post on this blog (from 2012) on the subject of game theory in video games, though it focuses on player interaction rather than computer opponents: