Applying Game Theory to Video Game Design ● Part II

[Originally posted on GamersInfo.net – July 15, 2006]

 

In Part I, we talked a little about the types of games and how to represent those games on paper, specifically the matrix game in which strategies are laid out for two players in a table. We discussed how a player’s strategies can dominate each other and that dominating strategies should always be chosen over the ones they dominate. And finally, we discussed the concept of the saddle point; the outcome of the most cautious move by both players and therefore the best move for both players to make. (One thing that was not mentioned was that there may be multiple saddle points). If you recall from that discussion, sometimes there are no saddle points. If this is the case, the players have no way of knowing what move will result in the best payoff. This brings us to the concept of a mixed strategy. In this part of the discussion, the information goes a bit deeper and may require that you reread in order to fully understand the material as presented. If you have not read Part I of this essay, you are advised to go back and do so.

Mixed Strategies

Player 1 Strategies
Player 2 Strategies Kick Grapple
Block 0 -6
Reversal 3 2
Do Nothing -3 -6

Figure 1.0

 

A player plays a mixed strategy any time his choice is one made by a random mechanism. If player 1 has no idea which of his strategies is the most cautious play (i.e. there are no saddle points), he has no choice but to choose a move at random. This could be a coin toss, a dice roll, or in the case of computer games a randomly generated number. Some form of probability formula will need to be used to determine the potential for each choice; however, in the case of a coin toss, on a game in which player 1 has 2 possible moves, the probability of either choice being taken would be 50% or 1 in 2.

Figure 1.0 shows a game with no saddle point. This means that player 1 will play a mixed strategy and has a 1 in 2 (or Ѕ or .50) chance of choosing to kick and a 1 in 2 chance of choosing to grapple on a coin toss. With this information, we can determine the best move for player 2 with a little math.

The formula is: (probability * payoff 1) + (probability * payoff 2)

  • If player 2 uses Block against a mixed strategy (random choice) by player 1, he has an expected payoff of Ѕ(0) + Ѕ(-6) or -3.
  • If player 2 uses Reversal, he has an expected payoff of Ѕ(3) + Ѕ(2) or 2 Ѕ.
  • If player 2 uses Do Nothing, he has an expected payoff of Ѕ(-3) + Ѕ(-6) or -4 Ѕ.

Which choice do you think is the best for player 2 against player 1 choosing at random? Remember, player 2 wants a higher or positive value. The subject of mixed strategies, like much of Game Theory goes even deeper and it is recommended that you study further; however, the information presented will give you a good start toward determining the best outcomes of mixed strategies.

The interesting aspect to this type of gameplay is that player 1 could guess that player 2 knows he is going to play a mixed strategy and that player 2 will thus base his move upon that knowledge. This might then affect player 1’s move and the cycle continues in this fashion between the two players mentally until each player has determined their best possible move and the choices are finally made.

Utility Theory

We now have a basic understanding of how to explain two player games on paper and to figure out which strategies are best for each player, even if a player has to make a choice at random. What we still do not know is how to assign values to the outcomes. Certainly we could assign arbitrary values based on gut instinct, and in many cases of game design this is adequate as long as there is some rational relationship between the values. This essay would not be complete however without at least a small discussion of Utility Theory. Utility Theory is essentially how mathematicians determine what the outcomes of each strategy in a game are worth to the players. Continuing with the fighting game example, Utility Theory will allow us to determine how much value a kick has versus a reversal for a player, etc. Utility Theory simply determines the order of preference of all outcomes for each player. In a two-person game, the order in which the first player desires the outcomes is usually the reverse of the order that the second player desires. While it is a good idea to have some knowledge of this particular area of Game Theory and the equations which are used, it is not required to build a good design. However, knowing the terminology and concepts behind the theory will at least help you understand how payoffs are best determined.

Game Trees

Gameplay is best represented by a Matrix Game when the moves of both players occur simultaneously; however, not all games require players to move at the same time. Chess for instance requires sequential gameplay in which one player makes a move, followed by player two’s move and play continues in this alternating fashion until the game is won, stalemated, or drawn. Player two makes his choice after player one has chosen and so on. In a game like this, it is best to represent the game using a game tree. Take a look at figure 1.1.

 


Figure 1.1 – a Perfect Information Game Tree
 

This game tree was built to represent a simple war game, perhaps an RTS such as Command & Conquer. It starts with player 1 at the top having two choices for his turn: Build Missile Base or Do Nothing. The point where this decision occurs is considered a node on the tree. The lines leaving the node are the choices the player has. Do Nothing ends the sequence with a payoff of ‘U’, which we will leave undetermined. If player 1 decided to build a missile base, we advance to the second node in the tree which is labeled player 2. At this node, player 2 may now make a decision based on what player 1 did (note: player 2 may or may not know what player 1 has done. This will depend upon how your game mechanic works). Player 2 may do nothing, build an anti-missile base to defend his base form player 1’s missiles, or send bombers to player 1’s missile base to destroy it. Again, these choices are represented by the lines leaving the player 2 node. If player 2 chooses to do nothing, the sequence ends with a payoff of ‘V’ again undetermined for the purposes of this discussion. Following the tree we see that we return to player 1; however, there are two player 1 nodes now. Which one we follow depends upon player 2’s choice in the previous node. If player 2 chose to build an anti-missile base, player 1 could now either send his own bombers against the anti-missile base or simply do nothing in response. Bear in mind that this game tree is vastly simplified. There could be many more choices and many more branches.

Any two-person game tree may be transformed into a matrix game table. Simply take each strategy of player 1 and line them up on the top of the table from left to right, then take each strategy of player 2 and line them up on the left of the table from top to bottom. Then, place the payoffs as indicated. Figure 1.2 represents the game tree from figure 1.0 in a matrix format.

Player 1’s choices

A. Do nothing. B. Build missile base, then take no further aggressive action. C. Build missile base, then take aggressive action against player 2 building anti-missile base only. D. Build missile base, then take aggressive action against player 2 bombing missile base only. E. Build missile base, then always take aggressive action in response to player 2.

Player 1
Player 2 A B C D E
Do Nothing u v v v v
Build Anti-Missile Base u x w x w
Bomb Missile Base u z z y y

Figure 1.2 – Turning a game tree into a matrix game

 

Information Sets

The tree in figure 1.1 represents what is called a ‘perfect information’ game. A perfect information game occurs when there are no strategies or moves in which chance is a factor and all choices from a particular level of the game tree are not in the same information set. An information set occurs when there are multiple choices for a player on one level of a game tree that keeps the player from knowing where he is on the tree. See Figure 1.3 below for a game that does NOT have perfect information.

 


Figure 1.3 – Not so perfect
 

This game tree shows another simplified war game. It starts with a roll of the dice (or randomly generated number) which determines how many soldiers each player receives. The first number represents player 1’s soldier production, and the second number represents player 2’s soldier production. Notice that the first and third outcomes both produce +100 soldiers for player 1. As a result, these strategies are considered to be in the same information. What does this mean for player 1? It means he does not know where on the game tree he is when his first choice comes up if the results of the initial random outcome are +100 soldiers for him. Is he on the first node or the third one? We represent this information set by connecting the two nodes which player 1 could conceivably be on with a dotted line. Likewise, notice that the first and second strategies off of the original chance node both give player 2 +50 soldiers. Because of this, player 2’s first and second nodes toward the bottom of the tree are considered to be in the same information set. Player 2 has no way of knowing whether he is in the first or second branch.

The fact that there are information sets in this tree and that the first node is a randomly chosen one means that this is NOT a perfect information game. Neither player can be 100% certain as to where they are on the game tree.

As you can see, game trees allow designers to map out sequential games easily; however, game trees for a very complex game will have to be broken up somehow. Obviously you cannot represent your entire game in one giant game tree. You’ll need to subdivide the choices logically.

In Part III we will briefly discuss non-zero sum games, touch on the concept of an N-Person game and offer some final thoughts on the application of Game Theory in your designs.

0 comments on “Applying Game Theory to Video Game Design ● Part IIAdd yours →

What do you think? No really...I'd like to know.