All-resistant pokémon types: a progress report

In the Pokemon type system with eighteen types, is there a type combination that is resistant or better to each type of attack?

If you are allowed only combinations of one or two types, as in the canonical games, the answer is No. And arguably this is reasonable game design from a rock-paper-scissors balance perspective.

But suppose you are allowed combinations of any number of types. In particular (a) you may have any number of types, not just one or two. For example, [fire, water, grass, electric], and (b) you may have more than one copy of each monotype, for example [fire, fire, fire, water].

Type effectiveness is computed in the usual way: you take the effectiveness of each monotype in your combination and multiply them together. For example, fire is 2x weak to water, so [fire,fire,fire] is 8x weak to water.

Now the question is: if you are allowed any combination of types, is there a type combination that is resistant or better to each type of attack? And here the answer is YES, and there is moreover a minimal example. It is:

[flying, water, water, poison, poison, ground, dark, steel]

This is the only all-resistant combination with a size-eight combination of types, and you can't do it with fewer.

Of course, once you have ONE all-resistant type combination, you can derive many others from it. For example, if R is an all-resistant combination, then any (positive) multiple of R is also all-resistant. And if T is any monotype (such as ice), you can prove to yourself that 2R+T is also an all-resistant type.

But this new type seems directly dependent on R — it's not an independent example. Are there other all-resistant types, independent of this one?

Yes, here's one: {:water 6, :ground 3, :flying 6, :dark 1, :steel 4}

(meaning six copies of water, three of ground, etc.) This happens to be the solution that uses the smallest variety of types. And we haven't rigorously defined what "independent" means, but I'd argue it matches our intuitive definition of independence from our earlier example because it has no poison in it, and more generally neither of these two types contains the other.

If we take that as our working definition — two type combinations are independent if neither one contains the other one — we can ask "How many independent, minimal all-resistant type combinations are there, and can we enumerate them all?"

This is the project that has occupied my attention in one form or another over the past decade.

To answer this question, we'll convert it into a math problem. There are a few clever insights that will help us, which I'll outline presently:

1. You can represent the type-effectiveness chart as a matrix, computing type effectiveness through matrix multiplication.

   You do this by taking base-2 logarithms so that 2x,1x,0.5x,and 0x effectiveness instead become 1,0,-1, and -∞.

2. Accordingly, you can express the all-resistance condition as a system of eighteen linear inequalities S*x <= -1, over the nonnegative integers. Eighteen corresponds to the number of pokemon types.
3. The intuitive concept of "minimal and independent solutions" corresponds to the mathematical concept of "pareto-optimal solutions", or "the pareto frontier of the system S*x <= -1".
4. The space of all-resistant types is essentially shaped like a linear cone. There are specialized algorithms for finding the "basis" points of a linear cone. The basis points are a superset of the pareto frontier: if you compute all the basis points, you've found the frontier.

5. Immunity (0x effectiveness) is hard to deal with computationally, because it introduces nonlinearities/infinities. You can handle the immunities of a given type such as steel (which is immune to poison) by dealing with steel-containing types and steel-excluding types separately. For steel-containing types, the type chart may as well say that everything is neutral (1x) to poison, except steel which has finite resistance (0.5x). For steel-excluding types, steel's resistances don't matter, so we can replace them all in the type chart with 1x.

   You can prove that you'll derive the same space of solutions with these modified type charts as you would with the original infinity-containing type chart. And although you'll get some false-positive pareto-optimal solutions, you won't miss any of the true pareto-optimal solutions.

6. Nominally there are six types with immunities, meaning that in order to eliminate all immunities from the type chart, we must have six-fold bifrucation or 64 possibilities.

   Fortunately, the specific type chart introduces dependencies among the immunities. For example, every all-resistant type must include steel or fairy or both (in order to resist dragon), and so there is no need to search among combinations that exclude both steel and fairy.

   Through such reductions, we cut the number of cases we must consider down to 36. Not bad!

   {flying} x {normal, dark, both} x {steel, fairy, both} x {ghost, not} x {ground, not}

   These 36 cases correspond to 36 slightly-mutated type charts — 36 non-overlapping linear cones in 18-dimensional space. ¹

The final step is actually computing/enumerating the complete set of minimal, all-resistant type combinations.

I found the program normaliz, which enables you to compute the so-called "Hilbert basis" of a cone. I gave each of the thirty-six disjoint cones an arbitrarily-chosen mnemonic nickname, naming them "bulbasaur, charizard, metapod, …" and every fifth pokemon thereafter.

In principle it is as easy as using the program normaliz to find the Hilbert basis of each of these 36 disjoint cones. Then in a second pass, eliminate the basis points within each cone that aren't actually pareto optimal in that cone (if x and y are both in the hilbert basis of a cone but x < y, then y is not pareto optimal.) Then in a third pass, aggregate the remaining candidates together and perform a similar pass (if x and y are in this union, but x < y, then y is not pareto optimal).

Unfortunately, the Hilbert basis computations seem to be very computationally intensive in practice. It has taken hours of multi-core compute time, and in some cones the calculation freezes after ~40 weeks of processor time. Besides which, I only have so much RAM.

I am heartened that, of the ten cones I've fully solved, most contain only ~20 candidate points after the second pass reduction (one contains around 250, and another 100, and another 2. But these are exceptions.) They do each contain around a million candidates before that reduction, which makes me wonder if I am wasting cycles computing the Hilbert basis as an intermediate to computing the pareto frontier. (I don't think it's obviously a waste—there are combinatorially really a lot of zones to check.)

I will perhaps need to understand more about optimal settings to normaliz, or find a calculation route that does not depend on computing the Hilbert basis but rather computes the frontier directly. (Computing the frontier directly was my initial approach, but most algorithms I tried seem worse than normaliz.)