Last year, I wrote an article about Street Fighter and Game Theory for Mathematics Awareness month. This year, the theme is “Unraveling Complex Systems” and I thought I would take the opportunity to expand on the mathematics of fighting games. Lately I’ve been playing a lot of Marvel vs Capcom 3, and in this article I’m going to attempt to show how the online community in MvC3 is a complex system. This article is intended for casual video gamers, but the mathematically curious might enjoy playing with included sample code. The sample code has been written in Scheme using Racket, formerly known as Dr. Scheme.

Marvel vs Capcom 3 and Rock, Paper, Scissors

In my last article, I made the case that fighting games in general can be thought of as a game of “Rock, Paper, Scissors”. In Marvel vs. Capcom 3, there are several different levels of “Rock, Paper, Scissors” going on within a single match. In addition to the “High, Low, Overhead” game discussed in my previous article, we also have games like “Attack, Block, Throw” and “Jump-in, Anti-Air, Projectile”. You can even see something of a “Rock, Paper, Scissors” game going on between different characters. What makes MvC3 different from other games in the fighting genre is that you have a roster of three characters playing simultaneously. This makes between individual character differences less important in the larger scheme of things, but what is more important is the strategy behind those three characters.

In MvC3, there are three basic strategies: “rush-down”, “keep-away”, and “turtle”. The “rush-down” strategy is simple, get up close to the opponent and attempt to dish out as much damage as possible. Some characters lend themselves to this strategy more than others, with a few notable ones being Wesker and Wolverine. The idea behind “keep-away” is to control the distance between you and your opponent using ranged attacks and projectiles. Some characters with a good keep-away game include Storm and Sentinel. The last strategy is “turtling”, which is playing a defensive game while waiting for an opportunity to punish a mistake from the opponent. Characters like Haggar and Hulk can make short work of an opponent once the right opportunity arises. While “turtling” can be highly effective against “rush-down” tactics, it tends to not do well against “keep-away” tactics. Thus, “rush-down” beats “keep-away”, “keep-away” beats “turtle”, and “turtle” beats “rush-down” – completing our game of “Rock, Paper, Scissors”. The pay-off matrix for this model might look something like this:

	Rush-Down	Keep-Away	Turtle
Rush-Down	(0,0)	(10,0)	(0,10)
Keep-Away	(0,10)	(0,0)	(10,0)
Turtle	(10,0)	(0,10)	(0,0)

Consider a match-up between characters like Wolverine and Storm. Wolverine’s set of moves might complement a rush-down approach while Storm’s set of moves complement a keep-away strategy. The player playing Storm would likely attempt to “keep-away” from Wolverine as long as possible, chipping away at his health via block damage. Essentially, Wolverine has forced into a “turtle” position while the distance between the two is large because he doesn’t have the tools to attack from afar. Wolverine’s “rush-down” game doesn’t start until he closes the distance between them. Once Wolverine is in close, it’s going to be hard for Storm to shake him. Storm would need to switch into a “turtle” strategy until she can find an opening between the oncoming attacks to create some distance again.

Keep in mind that these are strategies, and not dispositions of particular character. While some characters in MvC3 may lend themselves to a certain strategy over others, you have three characters to choose from and all of them can be played in any of these three styles to some extent. A individual character’s weaknesses can be compensated for with the appropriate assists. For example, the Wolverine player might choose a partner like Magneto with a beam-assist to help with his ranged game and the Storm player might choose a defensive assist like Haggar to help counter rush-down tactics.

In a given game of MvC3, it’s important to be able to change strategies on the fly. You might start the match with a “rush-down” approach, change to “keep-away” when the opponent starts “turtling”, then go back to a “rush-down” to finish off the match. Abstractly, we can look at MvC3 as a mixed strategy by assigning a probability to each of these three play styles. For example, lets consider two players in a hypothetical match. Player 1 chooses a rush-down heavy team mixed with a little turtling — lets say 80% rush down, 0% keep away, and 20% turtling. Player 2 chooses a well balanced team, but leaning slightly towards the keep-away game – 30% rush-down, 40% keep-away, and 30% turtling. We can multiply these strategies with our pay-off matrix to find the expected outcome. In this case, the average pay-off is 3.8 for player 1 and 3.2 for player 2. Over the long run, we might expect player 1 to win roughly 54% of the time. By specializing in one strategy at the expense of others, player 1 has gained a slight advantage over player 2. However, player 1’s strategy could also be foiled by a player that has chosen to focus on “turtling”. Consider a third player with a strategy of 0% rush-down, 40% keep-away, and 60% turtle. This player would have a 5.6 to 3.2 advantage over player 1, but be at a slight disadvantage to player two by a rate of 3 to 3.6.

Metagaming

In the example above, we’ve seen how it’s possible to adjust strategies to gain an advantage over a particular opponent. In the event that you know nothing about your opponent’s strategy, your best bet (from a mathematical standpoint) is to play each strategy with equal probability. However, the pay-off from this particular strategy is that you’ll break even – win 1/3 of the matches, lose 1/3 of the matches and tie 1/3 of the matches. In order to win with any consistency, it is necessary to predict which strategy your opponent will play. This is where metagaming comes in.

Metagaming is the art of stepping outside of the game and using information external to the game rules to optimize the potential pay-off. In MvC3, we might examine the frequency with which each character is played and keep track of trends in player strategy. If the majority of the population is predominantly playing one strategy, then it’s possible build a counter-strategy that will result in a favorable outcome. For example, Sentinel tends to emerge as a high-frequency character in MvC3 online matches. Sentinel’s strong keep-away game (high beam, low beam, rinse & repeat) tends to shutdown a large number of beginning players. In order to win against Sentinel, it’s necessary to be able to close that distance and rush him down. A character like Wesker might be particularly well suited for this role.

The metagame of MvC3 is constantly changing. As new strategies become dominant, new counter strategies emerge. On occasion, one of these new counter strategies will become dominant and new counter strategies will will start to develop. Each individual player is an autonomous agent. That player makes his/her own decisions about how to play. However, this player is not alone and may face a diverse range of opponents, each with their own individual strategies. Depending on what types of opponents a player faces, that player can learn from those matches and adapt a new strategy when appropriate.

From a mathematical standpoint, the metagame in MvC3 is essentially a “complex system”. We have a network of independent players connected together by matches played online. The game itself is highly structured with a fixed set of rules, but when we look at the system as a whole it can exhibit a variety of unexpected behaviors. To look at this system from a mathematical viewpoint, we might take a modeling approach. We set up a simple model of the system, add some players and connections between them, then let the model run and see what kinds of properties emerge.

Genetic Algorithms

One way that we might model this system is by using a genetic algorithm. A genetic algorithm is a programming paradigm based on evolution by natural selection. Natural selection dictates that the organisms that are best fitted for survival in a population are the ones that live to reproduce and pass their genes on to a new generation. In the context of this particular system, our environment is a population of players with varying strategies. Instead of genes, we have strategies employed by those players. If a player’s strategy works relatively well against the population, that player will likely continue to use it. If a strategy doesn’t work, it’s back to training for a new one.

With this basic genetic algorithm, let’s see what happens when we start with a small group of 5 players each playing a perfectly balanced game (1/3, 1/3, 1/3). After each play-off, the top 4 players keep their existing strategies and the loser goes back to the drawing board and chooses a new strategy at random. As we look at the changes in strategy over time, we can see that the top 4 players stay the same, generation after generation. We say that (1/3, 1/3, 1/3) is an “evolutionarily stable strategy”. As long as the majority of the population plays this strategy, no new strategy can take over the population. In gaming, this is not really a desirable thing to happen. The game isn’t fun when every plays the same thing, and players generally refer to this as a “stale metagame”. It really shouldn’t be that surprising that the system behaves like this, considering that (1/3, 1/3, 1/3) is the mathematically optimal strategy for this particular payoff matrix.

One of the interesting things about complex systems, is that you often see a high sensitivity to initial conditions. If we make a small change to the initial strategies in the previous example, say (.34, .33, .33) instead of (1/3, 1/3, 1/3), this increases the likeliness of a new strategy to infiltrate that elusive top four. There’s an element of randomness as to when the new strategy will succeed, it could happen after the first generation or after the hundredth. Once it does, it starts to change the environment which allows other new strategies to succeed as well. In some sample runs of this population, only one or two of the original strategies were left after 10,000 generations – but there’s a great deal of variance between trials. Playing a well balanced game is often a key feature of the new strategies, but might start to see a slight shift from “rush-down” to “turtle” emerging over time, countering the initial population’s slight bias toward this strategy.

When MvC3 first came out, the metagame was largely dominated by a single character: Sentinel. Upon observing this, Capcom issued a patch reducing Sentinel’s health. Some players criticized Capcom for this move, because it didn’t change the gameplay mechanics that were being abused, but from our example here we can see how a small change can have large effects on the metagame. Overall, I think this was a pretty smart move by Capcom – it was just enough change to make the metagame interesting again.

The previous two examples have dealt with small populations that are mostly uniform to start with. In the real world of MvC3 online play, there are thousands of players with dramatically different strategies to start with. To attempt to model the MvC3 metagame, we need to look at larger player pools with a greater diversity of play-styles. To get a feel for this, let’s look at a population of 20 random strategies, and replace the bottom 5 players with new strategies each round. With these changes, we see much more variance in the top players.

From one sample run with these conditions:

• The top strategy after the first generation was (0.54, 0.27, 0.19).
• The top strategy after 10 generations was (0.13, 0.81, 0.06).
• The top strategy after 100 generations was (0.69, 0.06, 0.24).
• The top strategy after 1,000 generations was (0.04, 0.81, 0.15).

There are many interesting observations to be made about the behavior of this model. First, we see that the metagame is much more dynamic when we start with random conditions instead of a uniform population. Balanced strategies tend to do well overall, but many of the top strategies are not necessarily balanced. Remember, its not the strategy alone that determines success, but the combination of the strategy and population. The fact that the top strategies after 10 and 1,000 generations are both “keep-away” heavy is a result of the population being “turtle” heavy during those particular generations. As the population changes, so do the winning strategies change. This ebb and flow from one strategy to another is what keeps the metagame interesting.

Conclusions

I think there’s a couple of important lessons to be learned here for people who are new to the fighting game genre. The first lesson is the importance of a balanced game. If everyone is playing a balanced game, then the only way to be successful to play a balanced game. The second lesson is to not underestimate “gimmick builds” – strategies that focus on maximizing a particular play style at the expense of other. When there is a tendency for the general population to play a certain way, the right counter strategy can be highly effective. The third lesson is to learn from your mistakes. If your team strategy isn’t working, don’t be afraid to mix it up. You might find a new strategy works better against the general population.

As a footnote, I’d like to point out that this model is a very simplified version of what goes on in MvC3 games. For an example of what some “real” MvC3 games look like, I’d recommend having a look at Andre vs Marn’s First to Ten. As you watch, see if you can identify when each player is playing which strategy. Does the rush-down/keep-away/turtle model fit with actual fights? How does changing out Akuma for Sentinel change Marn’s strategy? Is this change predicted by our model?

Further Investigations

I’ve intentionally been a little vague with the definition of complex system, in part because most definitions are high level descriptions of behavior. Am I correct in the assertion that MvC3 single player is not a complex system, but the MvC3 multiplayer “metagame” is a complex system?

One of the things I find interesting about MvC is the assist system. In this system, its technically possible for a player to employ two different strategies simultaneously. How can we change our model to account for this?

One common practice for genetic algorithms is to mix the genes of successful players to create new players, rather than just randomly selecting a new strategy as done in this example. Typically this is done by using a “crossover”, which selects randomly selects genes from two parents. How does this change the results of the genetic algorithm?

Another way of looking at the players is to actually model each player as a program. This technique is often called genetic programming. What kind of programs do you think would be most successful?

Further Reading

Gintas, H. (2000). Game Theory Evolving. Princeton University Press: Princeton.

Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press: Boston.

Koza, J. (1980). Genetic programming: on the programming of computers by means of natural selection. MIT Press: Boston.

Dawkins, R. (1976). The Selfish Gene. Oxford University Press: Oxford.

Felleisen, M., Findler, R., Flat, M. & Krishnamurthi, S. (2003). How to Design Programs. MIT Press: Boston. Available online at HTDP.ORG.