This post continues the previous one about pokémon types. Pokémon is a game in which adorable creatures battle each other using fantastic attacks. It was made into a several gameboy games that all share the same battle system. Every pokémon in the gameboy game has one or two types, such as Ground, Fire, Water, etc. Every pokémon attack has exactly one type. Certain defending types are weak or strong to other attacking types. For example, Water attacks are strong against Fire pokémon, while Electric attacks are weak against Ground Pokémon. In the games, attacks can be either twice as effective as normal (Water vs. Fire), neutrally effective (Normal vs. Normal), half as effective (Fire vs. Water), or not effective at all (Electric vs. Ground). We represent these strengths and weaknesses as the numbers 2, 1, \(\frac{1}{2}\), and 0, and call them the susceptance of one type to another.

If a pokemon has two types, then the strengths and weakness of each type are multiplied together. Thus Electric (2x weak to Ground) combined with Flying (immune to Ground (0x)) is immune to Ground. Fire (2x weak to Water) combined with Water (1/2x resistant to Water) is neutral to Water. If both types are resistant to another type, then the combination is doubly-resistant (1/4x) to that type. If both types are weak to a certain type then the combination is double-weak (4x) to that type.

In the previous post, we used the best-first search algorithm to find the most effective Pokémon type combinations. Afterwards, we realized that we could transform this search problem into a linear optimization problem. This conversion offers several advantages: first, search algorithms are comparatively slow, whereas linear optimization algorithms are extremely fast; second, it is difficult to determine whether a search problem has any solution, whereas it is straightforward to determine whether a linear optimization problem has any solution; finally, because systems of linear equations are so common, many programming languages have linear equation solvers written for them.

In this article, we will:

Solve a simple linear optimization problem in C We demonstrate how to use the linear programming C library, lp_solve , to solve a simple linear optimization problem. Incorporate a C library into Clojure We will show how we gave Clojure access to the linear programming C library, lp_solve . Find effective Pokemon types using linear programming Building on our earlier code, we answer some questions that were impossible to answer using best-first search.