Street Fighter Mathematics

The American Mathematical Society is celebrating April 2010 as Math Awareness Month and the theme for this year is Math and Sports. This was just the excuse I needed to write about the role of mathematics in what I consider an emerging sport: competitive video gaming. Acceptance of video games as a sport hasn't reached popular acceptance yet, but the particular type of video game that I'll be focusing on does have a real world analog which is a “sport” in the classical sense of the word. The “fighting game” genre, exemplified by Capcom's Street Fighter series, is the video game counter-part to mixed martial arts competitions. Despite the fantasy indulgences of video games, the mathematical concepts discussed here can be extended to real martial arts and a variety of other sports.

The basis for this discussion is a branch of mathematics referred to as Game Theory. Game Theory has a wide range of applications from economics and politics to evolutionary biology. At the heart of Game Theory are games, which have several key components. First, a game needs one or more players. Second, there needs to some choices available to these players. Finally, there needs to be a set of rules determining the pay-off for each player – such as whether a player wins or loses. The focus of Game Theory is on strategies, which are guidelines that a players uses for making choices in the game to obtain the most favorable outcome.

Ask any competitive player about the Game Theory of fighting games and they'll tell you that the genre essentially boils down to Rock, Paper, Scissors. In Rock, Paper, Scissors, each of the 2 players simultaneously makes a hand gesture for one of the three choices. Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. The goal of Rock, Paper, Scissors is to guess which gesture your opponent is going to throw and to play the gesture that beats its. Keep in mind that your opponent is going through the same line of reasoning, trying to guess which move you think they're going to play so that they can play the move that beats your move!

Mathematically, games like Rock, Paper, Scissors are represented by what's called a pay-off matrix. For a 2 player game, the choices for player 1 might be represented by different rows in the matrix and the choices for player 2 would be the different columns. The cells of the matrix contain a pair of numbers representing the pay-off for each player. For Rock, Paper, Scissors, we can describe the pay-off by using a 1 if the player wins, a -1 if the player loses, and a 0 if the players tie. This type of game is what we call a Zero-sum game, because every win for one player corresponds to a loss for the other player. The pay-off matrix would look like this:

P2: Rock P2: Paper P2: Scissors
P1: Rock (0,0) (-1,1) (1,-1)
P1: Paper (1,-1) (0,0) (-1,1)
P1: Scissors (-1,1) (1,-1) (0,0)

For example, consider the case where player 1 throws Rock and player 2 throws Scissors. We look for the row associated with Rock for player 1, row 1, and the column associated with Scissors for player 2, column 3. The contents of the cell at row 1 column 3 is the ordered pair (1,-1), which signifies that player 1 gets a win (+1) and player 2 gets a loss (-1). Furthermore, this game is symmetric because the options and pay-offs are the same for each player. Rock, Paper, Scissors is often used as a sort of “coin toss” because each player has equal odds of winning. If both players throws a random choice each round, player 1 should win about 1/3 of the time, player 2 should win about 1/3 of the time and the remaining 1/3 result in a tie. Rock, Paper, Scissors is a perfectly balanced game. The only way of winning consistently is to be able to anticipate your opponent's move in advance.

Fighting games are much more complex than Rock, Paper, Scissors, due in part by the large number of choices available to each player. For a game like Street Fighter II, with a 8-way joystick and 6 buttons, there are 576 possible inputs at any given point in time. This is far too many choices for me to list in a table, so for the moment lets focus on a simpler example. Consider a very simple fighting game with only 3 moves: an overhead attack, a high attack, and a low attack. These three attacks are analogous to the choices in Rock, Paper, Scissors. An overhead attack beats a low attack, a low attack beats a high attack, and a high attack beats an overhead attack. The pay-off matrix for this hypothetical fighting game might look like this:

P2: Overhead P2: High P2: Low
P1: Overhead (0,0) (-10,10) (10,-10)
P1: High (10,-10) (0,0) (-10,10)
P1: Low (-10,10) (10,-10) (0,0)

Normally fighting games determine the result of a game by starting each player with a set amount of health and this is reduced when hit by the opponent. Perhaps each player starts with 100 health and each attack deducts 10 health from the other player. However, it's important not to think of these values as adding or subtracting health but as the net benefit towards that player. Dealing damage to the opponent makes the opponent closer to losing and consequently making the dealer that much closer to winning. You might think of this net benefit like “tug-of-war”, like where each move is a step in the direction of winning. Even the simple act of changing position in a fighting game can have benefits towards one player or another!

Given that different characters have different strengths and weaknesses, another level of Rock, Paper, Scissors tends to emerge at the character selection level. For example, we might see a game where long range characters tend to have an advantage over short range characters, medium range characters tend to have an advantage over long range characters, and short range characters tend to have an advantage over medium range characters. However, the characters might not all be perfectly balanced with one another.

Indeed, it is often the case where some characters might be better or worse than others when you look at all possible match-ups. In fighting games, these are referred to as Tier Rankings. Consider this example for Street Fighter IV. Each character plays against each other for 10 games, and the number of wins are recorded in the corresponding cell in the match-up table. The ranking is determined by how often a character wins across all possible opponents. In Street Fighter IV, playing Sagat is at an advantage against any given character, while Dan is at a disadvantage against any given character.

In these examples so far, the rules of the game work the same for both players – the pay-off matrices are symmetric. The ability to choose different characters in a fighting game leads us away from symmetric pay-offs into asymmetric pay-offs. Let's consider a variation of our 3-move fighting game in which the pay-offs are a little bit different:

P2: Overhead P2: High P2: Low
P1: Overhead (-5,5) (-10,10) (10,-10)
P1: High (10,-10) (0,0) (-5,5)
P1: Low (-15,15) (10,-10) (5,-5)

Here, player 2 has a stronger overhead attack but at the expense of a weaker low attack. A question that a Game Theorist would ask in such a game is “what is the optimal strategy for each player under these conditions?”. One way of looking at this is by applying the Minimax rule. Each player is assumed to minimize potential losses then maximize potential gains. Let's take a look at the best and worst case scenario for each player:

P2: Overhead P2: High P2: Low Min Loss for P1 Max Win for P1
P1: Overhead (-5,5) (-10,10) (10,-10) -10 10
P1: High (10,-10) (0,0) (-5,5) -5 10
P1: Low (-15,15) (10,-10) (5,-5) -15 10
Min Loss for P2 -10 -10 -10
Max Win for P2 15 10 5

Player 2 stands to lose the same no matter what player 1 plays (-10), but stands to gain the most by playing overhead. We're presented with a situation where it is now to player 2's benefit to use the overhead attack. Player 1 stands to win the same no matter what player 2 chooses (10), but he has the least to lose by going with the high attack (-5). Knowing that player 2 stands to benefit from using the overhead, player 1 can compensate for this by playing high attack.

However, the picture changes as we add multiple plays to the picture. If both player's always adhered purely to their respective optimal strategies, player 1 would consistently win by playing high against player 2's overhead. If player 2 realizes that player 1 is predominantly playing high, it's to his advantage to “mix-it-up” and play low once in a while to punish player 1 for using a pure strategy. In practice, what we often find in these games are mixed strategies in which the players choose the different attacks with varying probabilities. Player 1 won't always play high and player 2 won't always play overhead, but they might tend to play these more often than the other choices.

The study of how players will optimize their strategies is a fascinating area of mathematical research. The Nash-Equilibrium is pair of mixed strategies for player 1 and player 2 such that neither player stands to benefit from changing their strategies while the other keeps theirs the same. A closely related concept is the notion of an Evolutionary Stable Strategy (ESS). Once an ESS is adopted by the majority of the population, it will not be invaded by any alternative strategy.

What impresses me most about playing fighting games is the way players tend to converge on the optimal strategies. Finding the optimal mixed strategy for a two-player bi-matrix game (one with different pay-off for different players) is known to be computationally hard problem. The most efficient method (that I know of) for finding the Nash-Equilibrium is the Lemke-Howson Algorithm, which takes exponentially longer to carry out as the number of choices increases. Yet somehow “pro” players seem to naturally discover these strategies despite the huge number of choices in a typical fighting game. In many ways, this process is much like the emergence of evolutionary stable strategies. The players with bad strategies lose, the players with good strategies win, and the winners gradually converge on an optimal strategy based on the behavior of the other players in the pool. Evolution seems to be quite proficient at solving optimization problems.

At this point I've probably raised more questions than I've answered, but I see this as a “good thing”. There's a wealth of beautiful mathematics taking place in these games and just shedding some light on these problems is all I could hope for. Some of the problems discussed here are ones that will keep me searching for answers in years to come. The next time you find yourself in an arcade (one of the few that remain), take a moment to stop and watch a game of Street Fighter. I hope you'll find it as awe-inspiring as I do.

Guild Wars Solo Me/D

So I noticed a new comment on my old Guild Wars Me/D video, and it enticed me to play again.  Unfortunately, the build in the video had been completely changed in a recent patch.  Sand Shards no longer deals damage on misses, but instead causes a AoE DoT effect when it ends.  Whereas the old version pumped out a lot of damage if there were multiple foes to miss, the new version has lower damage output and causes the AI to scatter even easier.  Thus, I set out to see if I could make a new solo build with the same profession combination.

The survivability of the old build was still pretty much intact, but I no longer needed the self-blind of Signet of Midnight due to the change in Sand Shards functionality.  I went over to the Zaishen arena and started to play around.  What I found was that I could keep myself alive without blind by using a combination of Mystic Regeneration, Mirage Cloak and Armor of Sanctity.  I changed the elite skill to Signet of Illusions and reallocated my stat points.  This opened up a variety of other options for damage.  After some experimentation, I was able to down IWAY with the following combination:

Signet of Illusions - makes all skills use Illusion attribute (16)

Mystic Regeneration, Mirage Cloak. Armor of Sanctity - keep me alive

Channeling - energy management

Mystic Twister, Dust Cloak - additional damage

Faithful Intervention - just another enchantment

Template Code: OQpCAcwjQl9ue5uZ3pb51EA

With the proof of concept working, I decided to give it a whirl in PvE.  I went to my old Sunspear rep farming spot, East out of Camp Hojanu in Barbarous Shore.  Right outside the town are several packs of Heket which are mostly physical damage.  Since the packs were only 4 instead of 8 like IWAY, Channeling wasn't return quite enough energy to cover the enchantment maintenance.  I switched out Faithful Intervention for Auspicious Incantation for more energy.  With the energy problem solved, I didn't really need the blind effect on Dust Cloak anymore and switched it our Heart of Holy Flame to add burning instead.  The only problem with this farming spot are the Blue Tongue Heket monks that spawn randomly in the melee packs.  I had some success using Backfire on them, but they still could take a while to kill.  I decided it would be better to just avoid them altogether.

Template Code: OQpCAcwjQl9ueFdc3x701EA

Having Signet of Illusions leaves plenty of room for variation in the build, as it can use any skills with an effective attribute of 16.  I found that having Armor of Sanctity up was more important than Mirage Cloak in most cases.  The damage from letting Mirage Cloak drop and the synergy with Auspicious Incantation made it worth keeping, but it might be possible to do without it in some locations.  A Dervish primary could probably use a similar setup and might be able to get away without the energy management skills needed on my Mesmer.  Although Fast Casting is kind of nice against the Heket because they like to interrupt.  Not bad for a proof of concept, but more damage and a speed boost would be nice.

Anyways, good luck and happy hunting!