Discovering Effective Pokémon Types Using Linear Optimization

Written by:

Robert McIntyre & Dylan Holmes

1 Introduction

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.

Present our results: We found some cool examples and learned a lot about the pokémon type system as a whole.

1.1 Immortal Types

In the game, pokémon can have either one type or two types. If this restriction is lifted, is there any combination of types that is resistant to all types? I call such a combination an Immortal Type, since if that type's pattern was repeated over and over again towards infinity, the resulting type would be immune to all attack types.

2 Linear Programming

Linear programming is the process of finding an optimal solution to a linear equation of several variables which are constrained by some linear inequalities.

2.1 The Farmer's Problem

Let's solve the Farmer's Problem, an example linear programming problem borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm.

The Farmer's Problem: Suppose a farmer has 75 acres on which to plant two crops: wheat and barley. To produce these crops, it costs the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat and $210 per acre for the barley. The farmer has $15000 available for expenses. But after the harvest, the farmer must store the crops while awaiting favorable market conditions. The farmer has storage space for 4000 bushels. Each acre yields an average of 110 bushels of wheat or 30 bushels of barley. If the net profit per bushel of wheat (after all expenses have been subtracted) is $1.30 and for barley is $2.00, how should the farmer plant the 75 acres to maximize profit?

The Farmer's Problem is to maximize profit subject to constraints on available farmland, funds for expenses, and storage space.

	Wheat	Barley	Maximum total
Farmland	$w$ acres	$b$ acres	75 acres
Expense	$120 per acre	$210 per acre	$15000
Storage	110 bushels per acre	30 bushels per acre	4000 bushels
Profit	$1.30 per bushel	$2.00 per bushel

2.2 Solution using LP Solve

In a new file, farmer.lp, we list the variables and constraints of our problem using LP Solve syntax.

/* Maximize Total Profit */
max: +143 wheat +60 barley;


/* --------  Constraints  --------*/

/* the farmer can't spend more money than he has */
+120 wheat +210 barley <= 15000;

/* the harvest has to fit in his storage space */
+110 wheat +30 barley <= 4000;

/* he can't use more acres than he owns */
+wheat +barley <= 75;

Running the lp_solve program on farmer.lp yields the following output.

lp_solve ~/proj/pokemon-types/lp/farmer.lp

Value of objective function: 6315.62500000

Actual values of the variables:
wheat                      21.875
barley                     53.125

This shows that the farmer can maximize his profit by planting 21.875 of the available acres with wheat and the remaining 53.125 acres with barley; by doing so, he will make $6315.62(5) in profit.

3 Incorporating `lp_solve` into Clojure

There is a Java API written by Juergen Ebert which enables Java programs to use lp_solve. Although Clojure can use this Java API directly, the interaction between Java, C, and Clojure is clumsy:

3.1 The Farmer's Problem in Clojure

We are going to solve the same problem involving wheat and barley, that we did above, but this time using clojure and the lp_solve API.

(ns pokemon.lpsolve
  (:import lpsolve.LpSolve)
  (:require pokemon.types)
  ;;(:require incanter.core)
  (:require rlm.map-utils))

The lp_solve Java interface is available from the same site as lp_solve itself, http://lpsolve.sourceforge.net/ Using it is the same as many other C programs. There are excellent instructions to get set up. The short version is that you must call Java with -Djava.library.path=/path/to/lpsolve/libraries and also add the libraries to your export LD_LIBRARY_PATH if you are using Linux. For example, in my .bashrc file, I have the line LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH. If everything is set-up correctly,

(import 'lpsolve.LpSolve)

lpsolve.LpSolve

should run with no problems.

3.2 Making a DSL to talk with LpSolve

3.2.1 Problems

Since we are using a C wrapper, we have to deal with manual memory management for the C structures which are wrapped by the LpSolve object. Memory leaks in LpSolve instances can crash the JVM, so it's very important to get it right. Also, the Java wrapper follows the C tradition closely and defines many static final int constants for the different states of the LpSolve instance instead of using Java enums. The calling convention for adding rows and columns to the constraint matrix is rather complicated and must be done column by column or row by row, which can be error prone. Finally, I'd like to gather all the important output information from the LpSolve instance into a final, immutable structure.

In summary, the issues I'd like to address are:

reliable memory management
functional interface to LpSolve
intelligible, immutable output

To deal with these issues I'll create four functions for interfacing with LpSolve

(in-ns 'pokemon.lpsolve)

;; deal with automatic memory management for LpSolve instance.
(declare linear-program)

;; functional interface to LpSolve
(declare lp-solve)

;; immutable output from lp-solve
(declare solve get-results)

3.2.2 Memory Management

Every instance of LpSolve must be manually garbage collected via a call to deleteLP. I use a non-hygienic macro similar to with-open to ensure that deleteLP is always called.

(in-ns 'pokemon.lpsolve)
(defmacro linear-program
  "solve a linear programming problem using LpSolve syntax.
   within the macro, the variable =lps= is bound to the LpSolve instance."
  [& statements]
  (list 'let '[lps (LpSolve/makeLp 0 0)]
        (concat '(try)
                statements
                ;; always free the =C= data structures.
                '((finally (.deleteLp lps))))))

The macro captures the variable lps within its body, providing for a convenient way to access the object using any of the methods of the LpSolve API without having to worry about when to call deleteLP.

3.2.3 Sensible Results

The linear-program macro deletes the actual lps object once it is done working, so it's important to collect the important results and add return them in an immutable structure at the end.

(in-ns 'pokemon.lpsolve)

(defrecord LpSolution
  [objective-value
   optimal-values
   variable-names
   solution
   status
   model])

(defn model
  "Returns a textual representation of the problem suitable for
  direct input to the =lp_solve= program (lps format)"
  [#^LpSolve lps]
  (let [target (java.io.File/createTempFile "lps" ".lp")]
    (.writeLp lps (.getPath target))
    (slurp target)))

(defn results
  "Given an LpSolve object, solves the object and returns a map of the
  essential values which compose the solution."
  [#^LpSolve lps]
  (locking lps
    (let [status (solve lps)
          number-of-variables (.getNcolumns lps)
          optimal-values (double-array number-of-variables)
          optimal-values (do (.getVariables lps optimal-values)
                             (seq optimal-values))
          variable-names
          (doall 
           ;; The doall is necessary since the lps object might
           ;; soon be deleted.
           (map
            #(.getColName lps (inc %))
            (range number-of-variables)))
          model (model lps)]
      (LpSolution.
       (.getObjective lps)
       optimal-values
       variable-names
       (zipmap variable-names optimal-values)
       status
       model))))

Here I've created an object called LpSolution which stores the important results from a session with lp_solve. Of note is the model function which returns the problem in a form that can be solved by other linear programming packages.

3.2.4 Solution Status of an LpSolve Object

(in-ns 'pokemon.lpsolve)

(defn static-integer?
  "does the field represent a static integer constant?"
  [#^java.lang.reflect.Field field]
  (and (java.lang.reflect.Modifier/isStatic (.getModifiers field))
       (integer? (.get field nil))))

(defn integer-constants [class]
  (filter static-integer? (.getFields class)))

(defn constant-map
  "Takes a class and creates a map of the static constant integer
  fields with their names.  This helps with C wrappers where they have
  just defined a bunch of integer constants instead of enums."
  [class]
     (let [integer-fields (integer-constants class)]
       (into (sorted-map)
             (zipmap (map #(.get % nil) integer-fields)
                     (map #(.getName %) integer-fields)))))

(alter-var-root #'constant-map memoize)
             
(defn solve
  "Solve an instance of LpSolve and return a string representing the
  status of the computation. Will only solve a particular LpSolve
  instance once."
  [#^LpSolve lps]
  ((constant-map LpSolve)
   (.solve lps)))

The .solve method of an LpSolve object only returns an integer code to specify the status of the computation. The solve method here uses reflection to look up the actual name of the status code and returns a more helpful status message that is also resistant to changes in the meanings of the code numbers.

3.2.5 The Farmer Example in Clojure, Pass 1

Now we can implement a nicer version of the examples from the lp\_solve website. The following is a more or less line-by-line translation of the Java code from that example.

(in-ns 'pokemon.lpsolve)
(defn farmer-example []
  (linear-program
   (results
    (doto lps
      ;; name the columns
      (.setColName 1 "wheat")
      (.setColName 2 "barley")
      (.setAddRowmode true)
      ;; row 1 : 120x + 210y <= 15000
      (.addConstraintex 2
                        (double-array [120 210])
                        (int-array [1 2])
                        LpSolve/LE
                        15e3)
      ;; row 2 : 110x + 30y <= 4000
      (.addConstraintex 2
                        (double-array [110 30])
                        (int-array [1 2])
                        LpSolve/LE
                        4e3)
      ;; ;; row 3 : x + y <= 75
      (.addConstraintex 2
                        (double-array [1 1])
                        (int-array [1 2])
                        LpSolve/LE
                        75)
      (.setAddRowmode false)

      ;; add constraints
      (.setObjFnex 2
                   (double-array [143 60])
                   (int-array [1 2]))
            
      ;; set this as a maximization problem
      (.setMaxim)))))

(clojure.pprint/pprint
 (:solution (pokemon.lpsolve/farmer-example)))

{"barley" 53.12499999999999, "wheat" 21.875}

And it works as expected!

3.2.6 The Farmer Example in Clojure, Pass 2

We don't have to worry about memory management anymore, and the farmer example is about half as long as the example from the LpSolve website, but we can still do better. Solving linear problems is all about the constraint matrix $A$ , the objective function $c$, and the right-hand-side $b$, plus whatever other options one cares to set for the particular instance of lp_solve. Why not make a version of linear-program that takes care of initialization?

(in-ns 'pokemon.lpsolve)
(defn initialize-lpsolve-row-oriented
  "fill in an lpsolve instance using a constraint matrix =A=, the
  objective function =c=, and the right-hand-side =b="
  [#^lpsolve.LpSolve lps A b c]
  ;; set the name of the last column to _something_
  ;; this appears to be necessary to ensure proper initialization.
  (.setColName lps (count c) (str "C" (count c)))

  ;; This is the recommended way to "fill-in" an lps instance from the 
  ;; documentation. First, set row mode, then set the objective
  ;; function, then set each row of the problem, and then turn off row
  ;; mode. 
  (.setAddRowmode lps true)
  (.setObjFnex lps (count c)
               (double-array c)
               (int-array (range 1 (inc (count c)))))
  (dorun
   (for [n (range (count A))]
     (let [row (nth A n)
           row-length (int (count row))]
       (.addConstraintex lps
                         row-length
                         (double-array row)
                         (int-array (range 1 (inc row-length)))
                         LpSolve/LE
                         (double (nth b n))))))
  (.setAddRowmode lps false)
  lps)


(defmacro lp-solve
  "by default:,
   minimize (* c x), subject to (<= (* A x) b),
   using continuous variables.  You may set any number of
   other options as in the LpSolve API." 
  [A b c & lp-solve-forms]
  ;; assume that A is a vector of vectors
  (concat
   (list 'linear-program
         (list 'initialize-lpsolve-row-oriented 'lps A b c))
   `~lp-solve-forms))

Now, we can use a much more functional approach to solving the farmer's problem:

(in-ns 'pokemon.lpsolve)
(defn better-farmer-example []
  (lp-solve  [[120 210]
              [110 30]
              [1 1]]
             [15000
              4000
              75]
             [143 60]
             (.setColName lps 1 "wheat")
             (.setColName lps 2 "barley")
             (.setMaxim lps)
             (results lps)))

(vec (:solution (pokemon.lpsolve/better-farmer-example)))

[["barley" 53.12499999999999] ["wheat" 21.875]]

Notice that both the inputs to better-farmer-example and the results are immutable.

4 Using LpSolve to find Immortal Types

4.1 Converting the Pokémon problem into a linear form

How can the original question about pokémon types be converted into a linear problem?

Pokemon types can be considered to be vectors of numbers representing their susceptances to various attacking types, so Water might look something like this.

(:water (pokemon.types/defense-strengths))

[1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5]

Where the numbers represent the susceptibility of Water to the attacking types in the following order:

(clojure.pprint/pprint
 (pokemon.types/type-names))

[:normal
 :fire
 :water
 :electric
 :grass
 :ice
 :fighting
 :poison
 :ground
 :flying
 :psychic
 :bug
 :rock
 :ghost
 :dragon
 :dark
 :steel]

So, for example, Water is resistant (x0.5) against Fire, which is the second element in the list.

To combine types, these sorts of vectors are multiplied together pair-wise to yield the resulting combination.

Unfortunately, we need some way to add two type vectors together instead of multiplying them if we want to solve the problem with lp_solve. Taking the log of the vector does just the trick.

If we make a matrix with each column being the log (base 2) of the susceptance of each type, then finding an immortal type corresponds to setting each constraint (the $b$ vector) to -1 (since log₂(1/2) = -1) and setting the constraint vector $c$ to all ones, which means that we want to find the immortal type which uses the least amount of types.

(in-ns 'pokemon.lpsolve)

(defn log-clamp-matrix [matrix]
  ;; we have to clamp the Infinities to a more reasonable negative
  ;; value because lp_solve does not play well with infinities in its
  ;; constraint matrix.
  (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %) 
                      (map #(/ (Math/log %) (Math/log 2)) row)))
        (apply mapv vector ;; transpose
               matrix))) 

;; constraint matrices
(defn log-defense-matrix []
  (log-clamp-matrix
   (doall (map (pokemon.types/defense-strengths)
               (pokemon.types/type-names)))))

(defn log-attack-matrix []
  (apply mapv vector (log-defense-matrix)))

;; target vectors
(defn all-resistant []
  (doall (map (constantly -1) (pokemon.types/type-names))))

(defn all-weak []
  (doall (map (constantly 1) (pokemon.types/type-names))))

(defn all-neutral []
  (doall (map (constantly 0) (pokemon.types/type-names))))

;; objective functions
(defn number-of-types []
  (doall (map (constantly 1) (pokemon.types/type-names))))

(defn set-constraints
  "sets all the constraints for an lpsolve instance to the given
  constraint. =constraint= here is one of the LpSolve constants such
  as LpSolve/EQ."
  [#^LpSolve lps constraint]
  (dorun (map (fn [index] (.setConstrType lps index constraint))
              ;; ONE based indexing!!!
              (range 1 (inc (.getNrows lps))))))

(defn set-discrete
  "sets every variable in an lps problem to be a discrete rather than
  continuous variable"
  [#^LpSolve lps]
  (dorun (map (fn [index] (.setInt lps index true))
              ;; ONE based indexing!!!
              (range 1 (inc (.getNcolumns lps))))))

(defn set-variable-names
  "sets the variable names of the problem given a vector of names"
  [#^LpSolve lps names]
  (dorun
   (keep-indexed
    (fn [index name]
      (.setColName lps  (inc index) (str name)))
    ;; ONE based indexing!!!
    names)))

(defn poke-solve 
  ([poke-matrix target objective-function constraint min-num-types]
     ;; must have at least one type
     (let [poke-matrix
           (concat poke-matrix
                   [(map (constantly 1)
                         (range (count (first poke-matrix))))])
           target (concat target [min-num-types])]
       (lp-solve poke-matrix target objective-function
                 (set-constraints lps constraint)
                 ;; must have more than min-num-types
                 (.setConstrType lps (count target) LpSolve/GE)
                 (set-discrete lps)
                 (set-variable-names lps (pokemon.types/type-names))
                 (results lps))))
  ([poke-matrix target objective-function constraint]
     ;; at least one type
     (poke-solve poke-matrix target objective-function constraint 1)))

(defn solution 
  "If the results of an lpsolve operation are feasible, returns the
  results. Otherwise, returns the error."
  [results]
  (if (not (= (:status results) "OPTIMAL"))
    (:status results)
    (:solution results)))

With this, we are finally able to get some results.

4.2 Results

(in-ns 'pokemon.lpsolve)

(defn best-defense-type
  "finds a type combination which is resistant to all attacks."
  []
  (poke-solve 
   (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))

(defn worst-attack-type
  "finds the attack type which is not-very-effective against all pure
  defending types (each single defending type is resistant to this
  attack combination"
  []
  (poke-solve
   (log-attack-matrix)  (all-resistant) (number-of-types) LpSolve/LE))

(defn worst-defense-type
  "finds a defending type that is weak to all single attacking types."
  []
  (poke-solve
   (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))

(defn best-attack-type
  "finds an attack type which is super effective against all single
defending types"
  []
  (poke-solve
   (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))

(defn solid-defense-type
  "finds a defense type which is either neutral or resistant to all
  single attacking types"
  []
  (poke-solve
   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))

(defn solid-attack-type
  "finds an attack type which is either neutral or super-effective to
  all single attacking types."
  []
  (poke-solve
   (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))

(defn weak-defense-type
  "finds a defense type which is either neutral or weak to all single
  attacking types"
  []
  (poke-solve
   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))

(defn neutral-defense-type
  "finds a defense type which is perfectly neutral to all attacking
  types."
  []
  (poke-solve
   (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))

4.2.1 Strongest Attack/Defense Combinations

(clojure.pprint/pprint
 (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))

{":normal" 0.0,
 ":ground" 1.0,
 ":poison" 2.0,
 ":flying" 1.0,
 ":fighting" 0.0,
 ":dragon" 0.0,
 ":fire" 0.0,
 ":dark" 1.0,
 ":ice" 0.0,
 ":steel" 1.0,
 ":ghost" 0.0,
 ":electric" 0.0,
 ":bug" 0.0,
 ":psychic" 0.0,
 ":grass" 0.0,
 ":water" 2.0,
 ":rock" 0.0}

This is the immortal type combination we've been looking for. By combining Steel, Water, Poison, and three types which each have complete immunities to various other types, we've created a type that is resistant to all attacking types.

(clojure.pprint/pprint
 (pokemon.types/susceptibility 
  [:poison :poison :water :water :steel :ground :flying :dark]))

{:water 1/2,
 :psychic 0,
 :dragon 1/2,
 :fire 1/2,
 :ice 1/2,
 :grass 1/2,
 :ghost 1/4,
 :poison 0,
 :flying 1/2,
 :normal 1/2,
 :rock 1/2,
 :electric 0,
 :ground 0,
 :fighting 1/2,
 :dark 1/4,
 :steel 1/8,
 :bug 1/8}

Cool!

(clojure.pprint/pprint
 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))

{":normal" 0.0,
 ":ground" 0.0,
 ":poison" 0.0,
 ":flying" 0.0,
 ":fighting" 0.0,
 ":dragon" 0.0,
 ":fire" 0.0,
 ":dark" 1.0,
 ":ice" 0.0,
 ":steel" 0.0,
 ":ghost" 1.0,
 ":electric" 0.0,
 ":bug" 0.0,
 ":psychic" 0.0,
 ":grass" 0.0,
 ":water" 0.0,
 ":rock" 0.0}

Dark and Ghost are the best dual-type combo, and are resistant or neutral to all types.

(clojure.pprint/pprint
 (pokemon.types/old-school
  (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))

{":normal" 0.0,
 ":ground" 0.0,
 ":poison" 0.0,
 ":flying" 0.0,
 ":fighting" 0.0,
 ":dragon" 0.0,
 ":fire" 0.0,
 ":ice" 0.0,
 ":ghost" 1.0,
 ":electric" 0.0,
 ":bug" 0.0,
 ":psychic" 1.0,
 ":grass" 0.0,
 ":water" 0.0,
 ":rock" 0.0}

Ghost and Psychic are a powerful dual type combo in the original games, due to a glitch which made Psychic immune to Ghost type attacks, even though the game claims that Ghost is strong against Psychic.

(pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))

INFEASIBLE

(pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))

INFEASIBLE

(pokemon.types/old-school
 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))

INFEASIBLE

(clojure.pprint/pprint
 (pokemon.types/old-school
  (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))

{":normal" 0.0,
 ":ground" 0.0,
 ":poison" 0.0,
 ":flying" 0.0,
 ":fighting" 0.0,
 ":dragon" 1.0,
 ":fire" 0.0,
 ":ice" 0.0,
 ":ghost" 0.0,
 ":electric" 0.0,
 ":bug" 0.0,
 ":psychic" 0.0,
 ":grass" 0.0,
 ":water" 0.0,
 ":rock" 0.0}

The best attacking type combination is Dragon from the original games. It is neutral against all the original types except for Dragon, which it is strong against. There is no way to make an attacking type that is strong against every type, or even one that is strong or neutral against every type, in the new games.

4.2.2 Weakest Attack/Defense Combinations

(clojure.pprint/pprint
 (pokemon.types/old-school
  (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))

{":normal" 5.0,
 ":ground" 0.0,
 ":poison" 0.0,
 ":flying" 0.0,
 ":fighting" 0.0,
 ":dragon" 0.0,
 ":fire" 1.0,
 ":ice" 2.0,
 ":ghost" 1.0,
 ":electric" 1.0,
 ":bug" 1.0,
 ":psychic" 0.0,
 ":grass" 3.0,
 ":water" 2.0,
 ":rock" 0.0}

(clojure.pprint/pprint
 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))

{":normal" 4.0,
 ":ground" 1.0,
 ":poison" 1.0,
 ":flying" 0.0,
 ":fighting" 1.0,
 ":dragon" 0.0,
 ":fire" 0.0,
 ":dark" 0.0,
 ":ice" 4.0,
 ":steel" 0.0,
 ":ghost" 1.0,
 ":electric" 3.0,
 ":bug" 0.0,
 ":psychic" 1.0,
 ":grass" 1.0,
 ":water" 1.0,
 ":rock" 2.0}

This is an extremely interesting type combination, in that it uses quite a few types.

(reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))

20.0

20 types is the minimum number of types before the attacking combination is not-very-effective or worse against all defending types. This would probably have been impossible to discover using best-first search, since it involves such an intricate type combination.

It's so interesting that it takes 20 types to make an attack type that is weak to all types that the combination merits further investigation.

Unfortunately, all of the tools that we've written so far are focused on defense type combinations. However, it is possible to make every tool attack-oriented via a simple macro.

(in-ns 'pokemon.lpsolve)

(defmacro attack-mode [& forms]
  `(let [attack-strengths# pokemon.types/attack-strengths
         defense-strengths# pokemon.types/defense-strengths]
     (binding [pokemon.types/attack-strengths
               defense-strengths#
               pokemon.types/defense-strengths
               attack-strengths#]
       ~@forms)))

Now all the tools from pokemon.types will work for attack combinations.

(clojure.pprint/pprint
 (pokemon.types/susceptibility [:water]))

{:water 1/2,
 :psychic 1,
 :dragon 1,
 :fire 1/2,
 :ice 1/2,
 :grass 2,
 :ghost 1,
 :poison 1,
 :flying 1,
 :normal 1,
 :rock 1,
 :electric 2,
 :ground 1,
 :fighting 1,
 :dark 1,
 :steel 1/2,
 :bug 1}

(clojure.pprint/pprint
 (pokemon.lpsolve/attack-mode 
  (pokemon.types/susceptibility [:water])))

{:water 1/2,
 :psychic 1,
 :dragon 1/2,
 :fire 2,
 :ice 1,
 :grass 1/2,
 :ghost 1,
 :poison 1,
 :flying 1,
 :normal 1,
 :rock 2,
 :electric 1,
 :ground 2,
 :fighting 1,
 :dark 1,
 :steel 1,
 :bug 1}

Now pokemon.types/susceptibility reports the attack-type combination's effectiveness against other types.

The 20 type combo achieves its goal in a very clever way.

First, it weakens its effectiveness to other types at the expense of making it very strong against flying.

(clojure.pprint/pprint
 (pokemon.lpsolve/attack-mode
  (pokemon.types/susceptibility
   [:normal :normal :normal :normal
    :ice :ice :ice :ice
    :electric :electric :electric
    :rock :rock])))

{:water 1/2,
 :psychic 1,
 :dragon 2,
 :fire 1/4,
 :ice 1/4,
 :grass 2,
 :ghost 0,
 :poison 1,
 :flying 512,
 :normal 1,
 :rock 1/16,
 :electric 1/8,
 :ground 0,
 :fighting 1/4,
 :dark 1,
 :steel 1/1024,
 :bug 4}

Then, it removes it's strengths against Flying, Normal, and Fighting by adding Ghost and Ground.

(clojure.pprint/pprint
 (pokemon.lpsolve/attack-mode
  (pokemon.types/susceptibility
   [:normal :normal :normal :normal
    :ice :ice :ice :ice
    :electric :electric :electric
    :rock :rock
    ;; Spot resistances
    :ghost :ground])))

{:water 1/2,
 :psychic 2,
 :dragon 2,
 :fire 1/2,
 :ice 1/4,
 :grass 1,
 :ghost 0,
 :poison 2,
 :flying 0,
 :normal 0,
 :rock 1/8,
 :electric 1/4,
 :ground 0,
 :fighting 1/4,
 :dark 1/2,
 :steel 1/1024,
 :bug 2}

Adding the pair Psychic and Fighting takes care of its strength against Psychic and makes it ineffective against Dark, which is immune to Psychic.

Adding the pair Grass and Poison makes takes care of its strength against poison and makes it ineffective against Steel, which is immune to poison.

(clojure.pprint/pprint
 (pokemon.lpsolve/attack-mode
  (pokemon.types/susceptibility
   [;; setup
    :normal :normal :normal :normal
    :ice :ice :ice :ice
    :electric :electric :electric
    :rock :rock
    ;; Spot resistances
    :ghost :ground
    ;; Pair resistances
    :psychic :fighting
    :grass :poison])))

{:water 1,
 :psychic 1/2,
 :dragon 1,
 :fire 1/4,
 :ice 1/2,
 :grass 1,
 :ghost 0,
 :poison 1/2,
 :flying 0,
 :normal 0,
 :rock 1/4,
 :electric 1/4,
 :ground 0,
 :fighting 1/2,
 :dark 0,
 :steel 0,
 :bug 1/2}

Can you see the final step?

It's adding the Water type, which is weak against Water, Dragon, and Grass and strong against Rock and Fire.

(clojure.pprint/pprint
 (pokemon.lpsolve/attack-mode
  (pokemon.types/susceptibility
   [;; setup
    :normal :normal :normal :normal
    :ice :ice :ice :ice
    :electric :electric :electric
    :rock :rock
    ;; Spot resistances
    :ghost :ground
    ;; Pair resistances
    :psychic :fighting
    :grass :poison
    ;; completion
    :water])))

{:water 1/2,
 :psychic 1/2,
 :dragon 1/2,
 :fire 1/2,
 :ice 1/2,
 :grass 1/2,
 :ghost 0,
 :poison 1/2,
 :flying 0,
 :normal 0,
 :rock 1/2,
 :electric 1/4,
 :ground 0,
 :fighting 1/2,
 :dark 0,
 :steel 0,
 :bug 1/2}

Which makes a particularly beautiful combination which is ineffective against all defending types.

Is there anything else that's interesting?

(pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))

INFEASIBLE

(pokemon.types/old-school
 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))

INFEASIBLE

(pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))

INFEASIBLE

(pokemon.types/old-school
 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))

INFEASIBLE

(pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))

INFEASIBLE

(pokemon.types/old-school
 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))

INFEASIBLE

There is no way to produce a defense-type that is weak to all types. This is probably because there are many types that are completely immune to some types, such as Flying, which is immune to Ground. A perfectly weak type could not use any of these types.

5 Summary

Overall, the pokémon type system is slanted towards defense rather than offense. While it is possible to create superior defensive types and exceptionally weak attack types, it is not possible to create exceptionally weak defensive types or very powerful attack types.

Using the lp_solve library was more complicated than the best-first search, but yielded results quickly and efficiently. Expressing the problem in a linear form does have its drawbacks, however — it's hard to ask questions such as "what is the best 3-type defensive combo in terms of susceptibility?", since susceptibility is not a linear function of a combo's types. It is also hard to get all the solutions to a particular problem, such as all the pokemon type combinations of length 8 which are immortal defense types.

	Wheat	Barley	Maximum total
Farmland	\(w\) acres	\(b\) acres	75 acres
Expense	$120 per acre	$210 per acre	$15000
Storage	110 bushels per acre	30 bushels per acre	4000 bushels
Profit	$1.30 per bushel	$2.00 per bushel