EditorialApplying Game Theory to Video Game Design – Part I

Game Theory is the mathematical theory of conflict and cooperation. It is a study of choices and outcomes, of strategies and payoffs. Mathematicians apply Game Theory to business strategies, wars, global politics and economics; any event that puts two or more ‘players’ into conflict. It is used to predict the payoffs of strategies that a player may take in these ‘games’.

As game designers in the entertainment industry, learning and applying the basic principals and techniques of Game Theory in our daily work will help us build better games. Where mathematicians use Game Theory to predict global events and determine strategies for the players involved, game designers can use it to map out the strategies of our games in a logical and rational manner. We can use it to visually represent the choices and outcomes we want our players to have.

Game Theory is a subject involving complex equations and warrants further study beyond the scope of this essay. However, this three part series will attempt to give you a basic understanding of Game Theory in a way that relates directly to helping you build better game designs.

Types of Games

Ultimately, Game Theory deals with three basic types of games:

  • Two-Person Zero-Sum Games
  • Two-Person Non-Zero-Sum Games
  • N-Person Games
In the Two-Person Zero-Sum Game, both players are in direct conflict with each other at all times. Any payoffs one player receives results in an equal loss to his opponent. A good example of this might be a fighting game like Tekken or Dead or Alive. In a fighting game, there are typically two players in direct opposition. When player A makes a choice to kick player B, succeeding at that kick will result in a payoff to player A in the form of points, whereas player B will lose stamina. Ultimately, one player will lose.

Non-Zero-Sum Games result when the players involved do not always find themselves in direct opposition. In these types of games, some choices may pay off well for both players while some may result in negative results for both. Nuclear War could be considered a Non-Zero-Sum Game. Obviously the choice to fire nuclear weapons at each other would result in a losing situation for both players.

The N-Person Game is simply a game in which there are more than two players. In these types of games, if players are allowed to communicate with each other, it is possible for coalitions to form, in which several players may group up against others. Real Time Strategy games such as Command & Conquer or Age of Empires can be categorized as an N-Person Game as can just about any game in which there is more than two players: First Person Shooters, MMOs, etc.

Let’s discuss a few techniques for describing these games on paper.

The Matrix Game

Most games and their choices/moves/strategies can be broken down into arrays. Games broken down in this way are referred to as m x n or Matrix Games. The table below illustrates this point for one input cycle of a vastly simplified fighting game with a limited move set.

Player A Strategies
KickGrapple
Player B Strategies
Block0-6
Reversal36
Do Nothing-3-6
Figure 1.0

Figure 1.0 shows an example turn in which player A may either kick or grapple player B. Player B can choose to block, perform a reversal, or do nothing. This is a 3x2 matrix game, thus there are 6 possible strategies. In this game, a negative number is favorable to player A (representing a successful attack), while a positive number is favorable to player B (representing a successful defense). The strategies are chosen simultaneously. Let’s assume player A chooses to kick and player B chooses to block. As you can see, this results in a payoff of 0. Player A does not receive any points and neither does player B as the kick is harmlessly deflected. But what if player B had chosen to attempt a reversal instead? The result against player A’s kick would have been 3 points to player B as he grabs player A’s leg and smashes his elbow into it (remember, player B wants positive numbers). Now assume that player B chose to do nothing. Player A's kick lands in this case and he is awarded with a -3 payoff, which could take the form of 3 points to his score and 3 points of stamina taken form player B.

Dominance

What do you think player B’s best strategy is in Figure 1.0? You’d probably guess reversal. Why do we actually know this? It is because reversal is said to dominate the block and do nothing strategies. Domination occurs when each outcome (or payoff) of a particular strategy is at least as good or better than the corresponding outcome of another strategy and one outcome is strictly better than the corresponding outcome of that strategy. Therefore, since the reversal strategy scores higher against a kick than blocking does and higher against a grapple than blocking does, it is said to dominate the block strategy. The same is true when comparing reversal to do nothing. Since this is the case, player B’s best strategy will always be to perform a reversal as he has the best chance for success against player A’s options. For player B to choose to block or do nothing in this situation would not be considered rational moves.

What do you think player A’s best strategy is: kick or grapple? Remember, player A desires a low or negative number. Having trouble? That’s because player A does not have a dominating strategy. On the one hand, grapple scores lower than kick against a block and lower than kick against do nothing; however, against a reversal, grapple scores higher which is something player A does not want.

Saddle Points

Sometimes, Zero-Sum Games will have what are referred to as saddle points. Take a look at Figure 1.1.

Player A Strategies
KickGrapple
Player B Strategies
Block0-6
Reversal3 (saddle point)6
Do Nothing-3-6
Figure 1.1

The reversal strategy dominates all other strategies for player B. And a rational player B should therefore never play anything but the reversal move. Knowing this, a rational player A will never want to play the grapple move. Why? Because doing so would cause a loss of 6 points to him as player B reverses his grapple. Therefore, player A should always choose to kick. Confused yet? The reasoning is simple once you understand the concepts. Anytime you have an outcome of a strategy that is both the lowest value in its row and the highest value in its column at the same time, you have what is referred to as a saddle point. It is the outcome which results from the most cautious play by both players. Obviously, player A gets the short end of the stick in this case, losing 3 points as player B reverses his kick; however, if he had chosen to grapple it would have been much worse. Likewise, if player B had chosen anything other than the reversal, they would have taken a hard hit. So the most cautious and rational move for player A is kick, whereas the same goes for player B’s reversal move.

Based upon dominance and saddle points, who would you think this game favors? Player A or player B? Using a matrix such as this can help us ensure our designs are fair. The last thing a competent designer wants is a game design that is weighted toward one player. In a game where there are no saddle points, no player has a clearly defined choice that will give certain victory. If that is the case, chance comes into play when making a choice. This is referred to as a Mixed Strategy. We’ll discuss this more in part II. Keep in mind that these concepts still work if we’re talking about a single player game. The computer simply takes the role of player B.

In Part II, we’ll discuss Mixed Strategies, Game Trees, and Utility Theory.

Other Articles By This Author

About the Author, Matthew Doyle (A.K.A P1ut0nium)

I’ve been playing video games since I was around 10. I’ve also been trying to make them for half my life, finally landing my first gig with another studio at the tender age of 30.

I started my own game dev company, Plutonium Games back in 2000. While our first title, Cleric, received a great deal of attention and press coverage (even making it into PC Gamer once), we just couldn’t land a publishing deal. As of 2006, I’m working as the Lead World Designer on Warhammer Online at Mythic Entertainment (my second job in the biz). I’m also a traditional artist, and try to find time here and there to do fantasy/sci-fi oil paintings and illustration, and am an aspiring novelist in the genres of fantasy, science-fiction, and horror.