pokemon-types: org/lpsolve.org comparison

comparison org/lpsolve.org @ 0:e03d363ed9a9

initial committ for pokemon types report

author	Robert McIntyre <rlm@mit.edu>
date	Sun, 16 Oct 2011 06:57:42 -0700
parents
children	55bba4805393

comparison

equal deleted inserted replaced

--1:000000000000
+:e03d363ed9a9
+#+title: Discovering Effective Pokemon Types Using Linear Optimization
+#+author: Robert McIntyre & Dylan Holmes
+#+EMAIL:     rlm@mit.edu
+#+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"
+#+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" />
+#+OPTIONS:   H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
+#+SETUPFILE: ../templates/level-0.org
+#+INCLUDE: ../templates/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
+offered 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, a typical 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 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

Mercurial > pokemon-types

comparison org/lpsolve.org @ 0:e03d363ed9a9