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.5×, 1× and 2×. However, there are exceptions to this rule. Ferrothorn, a dual-type Pokémon of steel and grass, will take 4× 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 aAaB, where aA is Pokémon a in position A.

2) aA and aB have the same moves for all aA,B.

Answer

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.

Attribution
Source : Link , Question Author : Andrew Thompson , Answer Author : Emily

Leave a Comment