Basic Decision Matrix
Let’s take a look at a simple decision matrix for an RTS.
| Rush | Produce | Defend | |
| Rush | 0,0 | 1,-1 | -.8,-.5 |
| Produce | -1,1 | 0,0 | .8, .2 |
| Defend | -.5,-.8 | +.2,+.8 | 0,0 |
Your action is on the left, theirs is on the top. The numbers say how much you can expect to gain (first number) and how much they can expect to gain (second number) for that combination.
So, if you rush an opponent that’s producing/expanding, you should expect to win. Other combinations are less drastic, and if you do the same thing your opponent does, it’s a draw.
Should I Stay or Should I Go?
Based on some weighting mechanisms, the AI is going to determine what is the best strategy to use. At first glance, it looks like rushing is the best strategy. The loss you suffer from a defending opponent is bad, but not terminal, and you can dominate an expanding/producing opponent easily.
But, that’s not the whole story. If the computer always does what the best option is, then this can be taken advantage of - the computer, in this case, will always rush, and so the human player can always defend and get an early lead.
This is the danger of AI today - it’s predictable. And while this is a pretty easy situation, the same pattern emerges in most games.
Looking at the three stages of decision making, we take out the stage of actually making the decision. Once we’ve got a workable decision matrix, we can determine what the opponent will do, and so we can determine what we should do… in this case, we know the opponent will rush, so we should defend.
Most players, admittedly, aren’t going to think about things in this way, and even then, I highly doubt that they’ll actually draw up little boxes. But, at some level, they’ll internalize these concepts. That’s why playing against humans is so different from playing the computer.
Why’s It So Dull?
Decisions aren’t easy if there’s a playbook. You can play blackjack in Vegas and get these little cards that will tell you what to do based on the cards. And that will get you optimum odds outside of counting. And guess what? It’s boring to do. It’s Progress Quest, only with drinks.
So, what can we do? There’s a few things that can be done to keep games interesting.
- Make ‘em hard. I mean, Nintendo Hard. Even if you know what to do, crank up the difficulty so much that doing it is still a pain. This is basically emphasizing the execution stage of decisions.
- Vary the challenges. Throw enough different things into the mix that the player constantly has to re-evaluate his strategies as he faces new combinations of opponents/whatever. This forces players to re-analyze their gameplan significantly, as the old models fall apart.
- Complicate the analysis. Add lots of factors, so that the player has to worry about a lot of things. This also targets the analysis stage.
- Make AI that actually reasons about things and understands higher-order decisions. This may not always be optimal! It’s a lot of work, and sometimes, players want AI that’s predictable, so that they can learn how to defeat them.
The usual game seems to take option 3 - making the game more complex. This often shows up as additional features or extra moves.
Unfortunately, this also has the effect of killing genres.
Personally, I think some combination of 2, 4, and 1 (in that order) is the way to go. Make challenges that are different enough that they feel fresh - this is where truly good designers come into play. Make the AI at least a little unpredictable, and then make the game hard in general.
I’m Sorry Dave, I Can’t Let You Have That Gold
You can probably make reasonably good AI reasonably easily. If you can build a decision matrix like the one above, the AI can choose randomly from the choices based on the overall effectiveness - in this case, choosing to rush frequently, defend infrequently, and expand rarely.
This kind of basic randomization can work. One old text-mode game (that I believe ran on Novell) featured enemies that, players claimed, set up ambushes, and were nearly psychic in their ability to sense the player’s plan. In reality, they just did the most obvious movement, except for a small random chance that they would do the opposite.
Game Design the Wrong Way » Complexity vs. Depth | 20-May-08 at 11:08 am | Permalink
[…] dealing with a single player game, one thing to look at is AI. As discussed here, if the AI always chooses the “best” option, it is predictable and therefore […]
cody | 14-Nov-08 at 2:50 pm | Permalink
Nice article.
“in this case, choosing to rush frequently, defend infrequently, and expand rarely.”
If you actually solve that game, isn’t optimal strategy more like defend frequently (70%), rush infrequently (20%), expand rarely (10%)? Rush is so strong that you should weight your choices towards beating it . . .
Archon Shiva | 13-Dec-08 at 5:11 am | Permalink
@cody: No. Because even assuming that your strategy worked out (which it doesn’t, see paragraph two), someone could then out-solve you by playing a expansion-heavy game, and beat you overall, (which doesn’t work either, because it gets absolutely clobbered by a rushing game).
The 70% rush strategy wins because because winning with rush is a lot more significant than winning with anything else: each time you rush an expanding opponent, you get ahead by 2 (+1 to his -1) points, whereas defending against one only nets you 0.3. So you have to successfully defend his rush seven times to make up for the one time he makes it. Your moves won’t be so perfectly matched to his, so it won’t work.
That said, I’m pretty sure a double-blind game can’t be “solved” in the game theory sense anyway; the best you can do is find an unexploitable strategy. I guess I would (simplistically) define that as a strategy that can only be beat by one that loses to pure randomness.
Michael Ralston | 16-Apr-09 at 12:19 pm | Permalink
For any such decision graph (IF the game is zero-sum), a mixed solution can be constructed that is unbeatable - where “unbeatable” means that the expected value of the BEST opposing strategy is 0.
That said, your example is non-zero-sum, and the optimal strategy is to negotiate an alternation of production and defense.
One way to compute an unbeatable strategy in a zero-sum game is simply to compute frequencies of each action such as to have an EV of at least 0 against all the pure strategies - in that case, no mixed strategy can possibly improve outcomes.
rwmksk | 19-Jan-12 at 4:33 am | Permalink
ABP5wf izoqpdsjeysm