# Mathematical research of Pokémon

In competitive Pokémon-play, two players pick a team of six Pokémon out of the 718 available. These are picked independently, that is, player $A$ is unaware of player $B$'s choice of Pokémon. Some online servers let the players see the opponents team before the match, allowing the player to change the order of its Pokémon. (Only the first matters, as this is the one that will be sent into the match first. After that, the players may switch between the chosen six freely, as explained below.) Each Pokémon is assigned four moves out of a list of moves that may or may not be unique for that Pokémon. There are currently 609 moves in the move-pool. Each move is assigned a certain type, and may be more or less effective against Pokémon of certain types. However, a Pokémon may have more than one type. In general, move effectiveness is given by $0.5x$, $1x$ and $2x$. However, there are exceptions to this rule. Ferrothorn, a dual-type Pokémon of steel and grass, will take $4x$ damage against fire moves, since both of its types are weak against fire. All moves have a certain probability that it will work.

In addition, there are moves with other effects than direct damage. For instance, a move may increase one's attack, decrease your opponent's attack, or add a status deficiency on your opponent's Pokémon, such as making it fall asleep. This will make the Pokémon unable to move with a relatively high probability. If it is able to move, the status of "asleep" is lifted. Furthermore, each Pokémon has a "Nature" which increases one stat (out of Attack, Defense, Special Attack, Special Defense, Speed), while decreases another. While no longer necessary for my argument, one could go even deeper with things such as IV's and EV's for each Pokémon, which also affects its stats.

A player has won when all of its opponents Pokémon are out of play. A player may change the active Pokémon freely. (That is, the "battles" are 1v1, but the Pokémon may be changed freely.)

Has there been any serious mathematical research towards competitive Pokémon play? In particular, has there been proved that there is always a best strategy? What about the number of possible "positions"? If there always is a best strategy, can one evaluate the likelihood of one team beating the other, given best play from both sides? (As is done with chess engines today, given a certain position.)

EDIT: For the sake of simplicity, I think it is a good idea to consider two positions equal when

1) Both positions have identical teams in terms of Pokémon. (Natures, IVs, EVs and stats are omitted.) As such, one can create a one-to-one correspondence between the set of $12$ Pokémon in position $A$ and the $12$ in position $B$ by mapping $a_A \mapsto a_B$, where $a_A$ is Pokémon $a$ in position $A$.

2) $a_A$ and $a_B$ have the same moves for all $a\in A, B$.

-
They pick independently. Added a short note. – Andrew Thompson Jun 11 '14 at 20:48
Certainly there must exist a best strategy (albeit maybe not a unique one). – naslundx Jun 11 '14 at 21:09
I don't think this answers your question because I don't think it discuss battling, but there's at least one paper in the arXiv on the mathematics of Pokémon. – Jair Taylor Jun 12 '14 at 1:13
@JairTaylor right- that paper uses some clever Pokémon-engineering to ensure the outcome of each battle beforehand, so it doesn't really go into this :) – Istvan Chung Jun 12 '14 at 6:47
@Bryan in my day we had 150 and we were glad! – mikeTheLiar Jun 12 '14 at 18:19

Has there been serious research? Probably not. Have there been modeling efforts? Almost certainly, and they probably range anywhere from completely ham-handed to somewhat sophisticated.

At its core, the game is finite; there are two players and a large but finite set of strategies. As such, existence of a mixed-strategy equilibrium is guaranteed. This is the result of Nash, and is actually an interesting application of the Brouwer Fixed-Point theorem.

That said, the challenge isn't really in the math; if you could set up the game, it's pretty likely that you could solve it using some linear programming approach. The challenge is in modeling the payoff, capturing the dynamics and, to some degree (probably small), handling the few sources of intrinsic uncertainty (i.e. uncertainty generated by randomness, such as hit chance).

Really, though, this is immaterial since the size of the action space is so large as to be basically untenable. LP solutions suffer a curse of dimensionality -- the more actions in your discrete action space, the more things the algorithm has to look at, and hence the longer it takes to solve.

Because of this, most tools that people used are inherently Monte Carlo-based -- simulations are run over and over, with new random seeds, and the likelihood of winning is measured statistically.

These Monte Carlo methods have their down-sides, too. Certain player actions, such as switching your Blastoise for your Pikachu, are deterministic decisions. But we've already seen that the action space is too large to prescribe determinism in many cases. Handling this in practice becomes difficult. You could treat this as a random action with some probability (even though in the real world it is not random at all), and increase your number of Monte Carlo runs, or you could apply some heuristic, such as "swap to Blastoise if the enemy type is fire and my current pokemon is under half-health." However, writing these heuristics relies on an assumption that your breakpoints are nearly-optimal, and it's rarely actually clear that such is the case.

As a result, games like Pokemon are interesting because optimal solutions are difficult to find. If there were 10 pokemon and 20 abilities, it would not be so fun. The mathematical complexity, if I were to wager, is probably greater than chess, owing simply to the size of the action space and the richer dynamics of the measurable outcomes. This is one of the reasons the game and the community continue to be active: people find new ideas and new concepts to explore.

Also, the company making the game keeps making new versions. That helps.

A final note: one of the challenges in the mathematical modeling of the game dynamics is that the combat rules are very easy to implement programmatically, but somewhat more difficult to cleanly describe mathematically. For example, one attack might do 10 damage out front, and then 5 damage per round for 4 rounds. Other attacks might have cooldowns, and so forth. This is easy to implement in code, but more difficult to write down a happy little equation for. As such, it's a bit more challenging to do things like try to identify gradients etc. analytically, although it could be done programmatically as well. It would be an interesting application for automatic differentiation, as well.

-
These heuristics sound like an excellent exercise in genetic programming. – Asaf Karagila Jun 11 '14 at 21:16
@AsafKaragila Indeed. – Emily Jun 11 '14 at 21:18
Similarly, a best deck and strategy must exist for Magic: The Gathering, but the complexity is so high that it's impractical to pursue. Chess for a game, is actually rather low on the complexity scale. There's no probability, the game always starts in the same state, and I can enumerate as a human, the possible moves on my next turn. And chess is still too complex to mathematically solve. – Cruncher Jun 12 '14 at 14:00
With Magic: The Gathering it's probably more realistic to say that it's fiscally impractical to pursue, if you allow for all cards that ever were, since some of them are ridiculously overpowered. They just cost a boat load of money. – Wayne Werner Jun 12 '14 at 16:30
I modeled a very limited scenario (Charmander vs Gen 1 Misty with no PP limitations) and solved it exactly as a Markov Decision Process (since the Gen 1 AI uses a known, simple distribution of actions). However, even this limited case was very complicated. Simply simulating general Gen 1 battles is enormously complex and the difficulty grows exponentially with every new generation as new interactions between abilties are introduced. – Antimony Jun 13 '14 at 5:02

I think it's worth pointing out that even stripping away most of the complexity of the game still leaves a pretty hard problem.

The very simplest game that can be said to bear any resemblance to Pokemon is rock-paper-scissors (RPS). (Imagine, for example, that there are only three Pokemon - let's arbitrarily call them Squirtle, Charmander, and Bulbasaur - and that Squirtle always beats Charmander, Charmander always beats Bulbasaur, and Bulbasaur always beats Squirtle.)

Already it's unclear what "best strategy" means here. There is a unique Nash equilibrium given by randomly playing Squirtle, Charmander, or Bulbasaur with probability exactly $\frac{1}{3}$ each, but in general just because there's a Nash equilibrium, even a unique Nash equilibrium, doesn't mean that it's the strategy people will actually gravitate to in practice.

There is in fact a professional RPS tournament scene, and in those tournaments nobody is playing the Nash equilibrium because nobody can actually generate random choices with probability $\frac{1}{3}$; instead, everyone is playing some non-Nash equilibrium strategy, and if you want to play to win (not just win $\frac{1}{3}$ of the time, which is the best you can hope for playing the Nash equilibrium) you'll instead play strategies that fare well against typical strategies you'll encounter. Two examples:

• Novice male players tend to open with rock, and to fall back on it when they're angry or losing, so against such players you should play paper.
• Novice RPS players tend to avoid repeating their plays too often, so if a novice player's played rock twice you should expect that they're likely to play scissors or paper next.

There is even an RPS programming competition scene where people design algorithms to play repeated RPS games against other algorithms, and nobody's playing the Nash equilibrium in these games unless they absolutely have to. Instead the idea is to try to predict what the opposing algorithm is going to do next while trying to prevent your opponent from predicting what you'll do next. Iocaine Powder is a good example of the kind of things these algorithms get up to.

So, even the very simple-sounding question of figuring out the "best strategy" in RPS is in some sense open, and people can dedicate a lot of time both to figuring out good strategies to play against other people and good algorithms to play against other algorithms. I think it's safe to say that Pokemon is strictly more complicated than RPS, enough so even this level of analysis is probably impossible.

Edit: It's also worth pointing out that another way that Pokemon differs from a game like chess is that it is imperfect information: you don't know everything about your opponent's Pokemon (movesets, EV distribution, hold items, etc.) even if you happen to know what they are. That means both players should be trying to predict these hidden variables about each other's Pokemon while trying to trick the other player into making incorrect predictions. My understanding is that a common strategy for doing this is to use Pokemon that have very different viable movesets and try to trick your opponent into thinking you're playing one moveset when you're actually playing another. So in this respect Pokemon resembles poker more than it does chess.

-
That write-up of Iocaine Powder is very cool! Since it wasn't explicitly discussed in @QiaochuYuan's answer, I want to point out that although beating humans and beating machines at RPS sound like specific problems, they're really more or less entire fields of study: machine learning (with crucial help from psychology) in the first case, and algorithmic information theory in the second. Before I start, I should warn you that I know almost nothing about the subjects I'm about to discuss, and I'd welcome clarifications and corrections from any experts passing by. – Vectornaut Jun 12 '14 at 6:31
(cont. 1) There are RPS strategies that use machine-learning techniques to exploit most humans' inability to play the Nash equilibrium strategy (perhaps the most famous example is nytimes.com/interactive/science/rock-paper-scissors.html). The success of these strategies presumably depends both on the robustness of the learning algorithms used and the quirks of human psychology and physiology that make us vulnerable to those algorithms. – Vectornaut Jun 12 '14 at 6:33
(cont. 2) Investigating the robustness of learning algorithms under various conditions is a branch of mathematics, and a huge one at that: you can find it on Wikipedia under headings like Computational_learning_theory and Statistical_learning_theory, in addition to good old Machine_learning. I would imagine, however, that guessing which conditions actually obtain when playing RPS against human opponents is a non-trivial psychology problem—and theorems tend to be more useful when you're confident that their conditions are satisfied. – Vectornaut Jun 12 '14 at 6:33
(cont. 3) Deterministic computers can't play the Nash equilibrium strategy because they can't make random choices. If you're playing RPS against a Turing machine whose number of states and input string size are known to you, then you're playing against one of finitely many possible opponents. If you have unlimited time and computational power, you can use your opponent's moves to identify it, and then it's game over. If you don't have unlimited resources, on the other hand, your opponent might be able to force a draw by generating a sequence of moves... – Vectornaut Jun 12 '14 at 6:36
(cont. 4) ... that you can't reliably predict using the resources at your disposal. The field of algorithmic information theory is more or less the study of how and when your opponent can do this. Ideas from algorithmic information theory can have practical consequences in cryptography, because the random strings used by many cryptosystems are algorithmically generated from relatively tiny non-algorithmically-generated "seeds," and the security of the cryptosystems depends on the unpredictability of the strings. – Vectornaut Jun 12 '14 at 6:37

Technical Machine is probably the closest thing you can get. This is a fairly sophisticated AI. It uses an expectminimax algorithm. In addition, if I recall correctly, it uses historical data from battle simulation servers to make assumptions about compositions of teams and movesets.

-