#+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization

 #+author: Robert McIntyre & Dylan Holmes

 #+EMAIL:     rlm@mit.edu

 #+SETUPFILE: ../../aurellem/org/setup.org

 #+INCLUDE: ../../aurellem/org/level-0.org

 

 

 

 * Introduction

 In the [[./types.org][previous post]], we used the best-first search algorithm to

 locate the most effective Pok\eacute{}mon type

 combinations. Afterwards, we realized that we could transform this

 search problem into a /linear optimization problem/.  This conversion

 offeres 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, (...)

 - Present our results :: 

  

 #which can be represented and solved as a system of linear equations.

   

 * COMMENT  

 This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 

 Pok\eacute{}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\eacute{}mon in the

 gameboy game has one or two /types/, such as Ground, Fire, Water,

 etc. Every pok\eacute{}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\eacute{}mon, while Electric attacks are

 weak against Ground Pok\eacute{}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).  Thus the range of defense

 values for a particular type is the set 0, 1/2, 1, 2. These are

 referred to in the game as being immune, resistant, neutral, and

 weak, respectively. I 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.

 

 ** Immortal Types

 

 In the game, pok\eacute{}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.

 

 * Linear Programming

 

 ** Terminology

 Linear programming is the process of finding an optimal solution to a

 linear equation of several variables which are constrained by some linear

 inequalities.

 

 In linear programming terminology, the function to be extremized is

 the /objective function/.

 

 ** COMMENT 

 First, we'll give a small example of a linear optimization problem,

 and show how it can be solved with Clojure and =lp_solve=.  Then,

 we'll show how finding immortal pok\eacute{}mon types can be converted

 into a linear problem suitable for solving in the same way.

 

 ** 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.

 

 

 #+BEGIN_QUOTE 

 *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?

 #+END_QUOTE

 

 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    |              |

 

 *** COMMENT

 can be represented as a linear optimization

  problem. In this form, it is a problem with two variables\mdash{}the number of

  acres of wheat, \(w\), and the number of acres of barley, \(b\). The

  aim is to maximize profit, which 

 

  subject to three constraints: the farmer can't spend more money

 than he has, the farmer can't use more acres than he owns, and the harvest has

 to fit in his storage space.

 

 We can express these constraints succinctly using matrix

 notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\),

 we want to maximize the expression \(143 w + 60 b\) subject to 

 

 \(

 \begin{cases}

 120 w + 210 b & \leq & 1500\\

 110 w + 30 b & \leq & 4000\\

 1 w + 1 w & \leq & 75

 \end{cases}

 \)

 

 #\(\begin{bmatrix}120&210\\110&30\\1 &

 #1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix}

 #\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\)

 

 ** Solution using LP Solve

 #(LP solve is available at http://www.example.com.)

 In a new file,  =farmer.lp=, we list the variables and constraints 

 of our problem using LP Solve syntax.

 

 #+begin_src lpsolve :tangle ../lp/farmer.lp

 /* 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;

 #+end_src

 

 

 #This is a set of linear equations ideal for solving using a program like

 #=lp_solve=. In Linear Algebra terms we are maximizing the linear function 

 

 #\(\text{profit} = 143\text{ wheat} + 60\text{ barley}\), subject to the constraints

 

 #Ax <= b,

 

 #where A is [120 210 110 30 1 1], x is [wheat barley] and b is [15000

 #4000 75].

 

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

 

 #+begin_src sh :exports both :results scalar

 ~/roBin/lpsolve/lp_solve ~/aurellem/src/pokemon/farmer.lp

 #+end_src

 

 #+results:

 : 

 : 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.

 

 

 #The farmer can make a profit of $6315.62 by planting 21.875 acres of

 #his land with wheat and the other 53.125 acres of his land with barley.

 

 * Incorporating  =lp_solve= into Clojure 

 

 There is a Java API available 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:

 

 

 The Java API for LP Solve makes it possible to use Lp Solve algorithms

 within Java. Although Clojure can use this  Java API directly, 

 

 

 ** 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 lpsolve API.

 

 #Because we ultimately intend to use Lp Solve to find optimal Pokemon type combinations.

 # we want to solve linear optimization problems within Clojure, the language 

 

 ** Setup

 =lp_solve= is a crufty =C= program which already comes with a JNI

 interface written by Juergen Ebert.  It's API is not

 particularly friendly from a functional/immutable perspective, but

 with a little work, we can build something that works great with

 clojure.

 

 #+srcname: intro

 #+begin_src clojure :results silent

 (ns pokemon.lpsolve

   (:use rlm.ns-rlm))

 (rlm.ns-rlm/ns-clone rlm.light-base)

 (use 'clojure.set)

 (import 'lpsolve.LpSolve)

 (use '[clojure [pprint :only [pprint]]])

 #+end_src

 

 The LpSolve 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, 

 

 #+srcname: body 

 #+begin_src clojure :results verbatim :exports both

 (import 'lpsolve.LpSolve)

 #+end_src

 

 #+results: body

 : lpsolve.LpSolve

 

 should run with no problems.

 

 ** Making a DSL to talk with LpSolve

 *** 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=

 

 #+srcname: declares

 #+begin_src clojure :results silent 

 (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)

 #+end_src

 

 *** 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.

 

 #+srcname: memory-management

 #+begin_src clojure :results silent

 (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))))))

 #+end_src

 

 

 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=. 

 

 *** 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.

 

 #+srcname: get-results

 #+begin_src clojure :results silent

 (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))))

 

 #+end_src

 

 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.

 

 *** Solution Status of an LpSolve Object

 

 #+srcname: solve

 #+begin_src clojure :results silent       

 (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-memo 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)))))

 	     

 (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)))

 

 #+end_src

 

 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.

 

 *** The Farmer Example in Clojure, Pass 1

 

 Now we can implement a nicer version of the examples from the

 [[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less

 line-by-line translation of the Java code from that example.

 

 #+srcname: farmer-example

 #+begin_src clojure :results silent

 (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)))))

 

 #+end_src

 

 #+begin_src clojure :results output :exports both 

 (clojure.pprint/pprint

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

 #+end_src

 

 #+results:

 : {"barley" 53.12499999999999, "wheat" 21.875}

 

 And it works as expected!

 

 *** 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?

 

 

 

 #+srcname: lp-solve

 #+begin_src clojure :results silent       

 (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 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))

  #+end_src

 

 Now, we can use a much more functional approach to solving the

 farmer's problem:

 

 #+srcname: better-farmer

 #+begin_src clojure :results silent

 (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)))

 #+end_src

 

 #+begin_src clojure  :exports both :results verbatim

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

 #+end_src

 

 #+results:

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

 

 Notice that both the inputs to =better-farmer-example= and the results

 are immutable.

 

 * Using LpSolve to find Immortal Types

 ** Converting the Pokemon problem into a linear form

 How can the original question about pok\eacute{}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.

 

 #+begin_src clojure :results scalar :exports both

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

 #+end_src 

 

 #+results:

 : [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:

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/type-names))

 #+end_src 

 

 #+results:

 #+begin_example

 [:normal

  :fire

  :water

  :electric

  :grass

  :ice

  :fighting

  :poison

  :ground

  :flying

  :psychic

  :bug

  :rock

  :ghost

  :dragon

  :dark

  :steel]

 #+end_example

 

 

 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_2(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.

 

 #+srcname: pokemon-lp

 #+begin_src clojure :results silent

 (in-ns 'pokemon.lpsolve)

 

 (require 'pokemon.types)

 (require 'incanter.core)

 

 (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 %) row))

        (incanter.core/log2

 	(incanter.core/trans

 	 matrix))))

 

 ;; constraint matrices

 (defn log-defense-matrix []

   (log-clamp-matrix

    (doall (map (pokemon.types/defense-strengths)

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

 

 (defn log-attack-matrix []

   (incanter.core/trans (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

    (map (fn [[index name]]

 	  (.setColName lps  (inc index) (str name)))

 	;; ONE based indexing!!!

 	(indexed 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)))

 

 #+end_src

 

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

 

 ** Results

 #+srcname: results

 #+begin_src clojure :results silent  

 (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))

 

 #+end_src

 

 *** Strongest Attack/Defense Combinations

     

 #+begin_src clojure :results output :exports both 

 (clojure.pprint/pprint

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 # #+results-old:

 # : [[":normal" 0.0] [":ground" 1.0] [":poison" 0.0] [":flying" 1.0] [":fighting" 0.0] [":dragon" 1.0] [":fire" 0.0] [":dark" 0.0] [":ice" 0.0] [":steel" 2.0] [":ghost" 1.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.

 

 #+begin_src clojure :results output :exports both 

 (clojure.pprint/pprint

  (pokemon.types/susceptibility 

   [:poison :poison :water :water :steel :ground :flying :dark]))

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 # #+results-old:

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

 

 

 Cool!

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 Dark and Ghost are the best dual-type combo, and are resistant or

 neutral to all types.

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 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 to Psychic.

 

 #+begin_src clojure :results verbatim :exports both

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :results verbatim :exports both

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 

 #+begin_src clojure :results verbatim :exports both

 (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 The best attacking type combination is strangely 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.

 

 

 *** Weakest Attack/Defense Combinations

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 # #+results-old:

 # : [[":normal" 5.0] [":ground" 1.0] [":poison" 0.0] [":flying" 0.0] [":fighting" 2.0] [":dragon" 0.0] [":fire" 0.0] [":ice" 4.0] [":ghost" 1.0] [":electric" 4.0] [":bug" 0.0] [":psychic" 0.0] [":grass" 0.0] [":water" 1.0] [":rock" 1.0]]

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

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

 #+end_src

 

 #+results:

 #+begin_example

 {":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}

 #+end_example

 

 # #+results-old:

 # : [[":normal" 4.0] [":ground" 1.0] [":poison" 1.0] [":flying" 0.0] [":fighting" 2.0] [":dragon" 0.0] [":fire" 0.0] [":dark" 0.0] [":ice" 5.0] [":steel" 0.0] [":ghost" 1.0] [":electric" 5.0] [":bug" 0.0] [":psychic" 1.0] [":grass" 0.0] [":water" 1.0] [":rock" 2.0]]

 

 

 This is an extremely interesting type combination, in that it uses

 quite a few types.

 

 #+begin_src clojure :results verbatim :exports both

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

 #+end_src

 

 #+results:

 : 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.

 

 #+srcname: attack-oriented

 #+begin_src clojure :results silent

 (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)))

 #+end_src

 

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

 combinations.

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

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

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.lpsolve/attack-mode 

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

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 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.

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.lpsolve/attack-mode

   (pokemon.types/susceptibility

    [:normal :normal :normal :normal

     :ice :ice :ice :ice

     :electric :electric :electric

     :rock :rock])))

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 Then, it removes it's strengths against Flying, Normal, and Fighting

 by adding Ghost and Ground.

 

 #+begin_src clojure :results output :exports both

 (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])))

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 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.

 

 #+begin_src clojure :results output :exports both

 (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])))

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 Can you see the final step?

 

 It's adding the Water type, which is weak against Water and Dragon and

 strong against Rock and Fire.

 

 #+begin_src clojure :results output :exports both

 (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])))

 #+end_src

 

 #+results:

 #+begin_example

 {: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}

 #+end_example

 

 Which makes a particularly beautiful combination which is ineffective

 against all defending types.

 

 

 # #+begin_src clojure :results scalar :exports both

 # (with-out-str (clojure.contrib.pprint/pprint (seq (attack-mode (pokemon.types/susceptibility [:normal :normal :normal :normal :ice :ice :ice :ice :electric :electric :electric :rock :rock  :ground :ghost :psychic :fighting :grass :poison])))))

 # #+end_src

 

 # #+results:

 # | [: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] |

 

 

 Is there anything else that's interesting?

 

 #+begin_src clojure :exports both

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :exports both

 (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :exports both

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :exports both

 (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :exports both

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

 #+end_src

 

 #+results:

 : INFEASIBLE

 

 #+begin_src clojure :exports both

 (pokemon.types/old-school

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

 #+end_src

 

 #+results:

 : 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.

 

 * Summary

 

 Overall, the pok\eacute{}mon type system is slanted more 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.

 

 

 * COMMENT main-program

 #+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none

 <<intro>>

 <<body>>

 <<declares>>

 <<memory-management>>

 <<get-results>>

 <<solve>>

 <<farmer-example>>

 <<lp-solve>>

 <<better-farmer>>

 <<pokemon-lp>>

 <<results>>

 <<attack-oriented>>

 #+end_src

 

 

 * COMMENT Stuff to do.

 ** TODO fix namespaces to not use rlm.light-base