1.1 --- a/org/lpsolve.org	Wed Nov 02 08:02:11 2011 -0700
     1.2 +++ b/org/lpsolve.org	Wed Nov 02 10:28:50 2011 -0700
     1.3 @@ -1,87 +1,78 @@
     1.4  #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization
     1.5  #+author: Robert McIntyre & Dylan Holmes
     1.6  #+EMAIL:     rlm@mit.edu
     1.7 +#+description: Using Lpsolve to func effective pokemon types in clojure.
     1.8 +#+keywords: Pokemon, clojure, linear optimization, lp_spolve, LpSolve
     1.9  #+SETUPFILE: ../../aurellem/org/setup.org
    1.10  #+INCLUDE: ../../aurellem/org/level-0.org
    1.11  
    1.12  
    1.13  
    1.14  * Introduction
    1.15 -In the [[./types.org][previous post]], we used the best-first search algorithm to
    1.16 -locate the most effective Pok\eacute{}mon type
    1.17 -combinations. Afterwards, we realized that we could transform this
    1.18 -search problem into a /linear optimization problem/.  This conversion
    1.19 -offeres several advantages: first, search algorithms are comparatively
    1.20 -slow, whereas linear optimization algorithms are extremely fast;
    1.21 -second, it is difficult to determine whether a search problem has any
    1.22 -solution, whereas it is straightforward to determine whether a linear
    1.23 -optimization problem has any solution; finally, because systems of
    1.24 -linear equations are so common, many programming languages have linear
    1.25 -equation solvers written for them.
    1.26 +This post continues the [[./types.org][previous one]] about pok\eacute{}mon types.
    1.27 +Pok\eacute{}mon is a game in which adorable creatures battle each
    1.28 +other using fantastic attacks.  It was made into a several gameboy
    1.29 +games that all share the same battle system.  Every pok\eacute{}mon in
    1.30 +the gameboy game has one or two /types/, such as Ground, Fire, Water,
    1.31 +etc. Every pok\eacute{}mon attack has exactly one type. Certain
    1.32 +defending types are weak or strong to other attacking types.  For
    1.33 +example, Water attacks are strong against Fire pok\eacute{}mon, while
    1.34 +Electric attacks are weak against Ground Pok\eacute{}mon.  In the
    1.35 +games, attacks can be either twice as effective as normal (Water
    1.36 +vs. Fire), neutrally effective (Normal vs. Normal), half as effective
    1.37 +(Fire vs. Water), or not effective at all (Electric vs. Ground). We
    1.38 +represent these strengths and weakessness as the numbers 2, 1,
    1.39 +$\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to
    1.40 +another.
    1.41  
    1.42 -In this article, we will 
    1.43 +If a pokemon has two types, then the strengths and weakness of each
    1.44 +type are /multiplied/ together.  Thus Electric (2x weak to Ground)
    1.45 +combined with Flying (immune to Ground (0x)) is immune to Ground.
    1.46 +Fire (2x weak to Water) combined with Water (1/2x resistant to Water)
    1.47 +is neutral to Water. If both types are resistant to another type, then
    1.48 +the combination is doubly-resistant (1/4x) to that type. If both types
    1.49 +are weak to a certain type then the combination is double-weak (4x) to
    1.50 +that type.
    1.51 +
    1.52 +In the [[./types.org][previous post]], we used the best-first search algorithm to find
    1.53 +the most effective Pok\eacute{}mon type combinations. Afterwards, we
    1.54 +realized that we could transform this search problem into a /linear
    1.55 +optimization problem/.  This conversion offeres several advantages:
    1.56 +first, search algorithms are comparatively slow, whereas linear
    1.57 +optimization algorithms are extremely fast; second, it is difficult to
    1.58 +determine whether a search problem has any solution, whereas it is
    1.59 +straightforward to determine whether a linear optimization problem has
    1.60 +any solution; finally, because systems of linear equations are so
    1.61 +common, many programming languages have linear equation solvers
    1.62 +written for them.
    1.63 +
    1.64 +In this article, we will:
    1.65   - Solve a simple linear optimization problem in C :: We demonstrate
    1.66        how to use the linear programming C library, =lp_solve=, to
    1.67 -      solve a simple linear
    1.68 -      optimization problem.
    1.69 +      solve a simple linear optimization problem.
    1.70   - Incorporate a C library into Clojure :: We will show how we gave
    1.71        Clojure access to the linear programming C library, =lp_solve=.
    1.72   - Find effective Pokemon types using linear programming :: Building
    1.73 -      on our earlier code, (...)
    1.74 -- Present our results :: 
    1.75 +      on our earlier code, we answer some questions that were
    1.76 +      impossible to answer using best-first search.
    1.77 +- Present our results :: We found some cool examples and learned a lot
    1.78 +     about the pok\eacute{}mon type system as a whole.
    1.79   
    1.80 -#which can be represented and solved as a system of linear equations.
    1.81 -  
    1.82 -* COMMENT  
    1.83 -This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 
    1.84 -Pok\eacute{}mon is a game in which adorable creatures battle each
    1.85 -other using fantastic attacks.  It was made into a several gameboy
    1.86 -games that all share the same battle system.  Every pok\eacute{}mon in the
    1.87 -gameboy game has one or two /types/, such as Ground, Fire, Water,
    1.88 -etc. Every pok\eacute{}mon attack has exactly one type. Certain defending
    1.89 -types are weak or strong to other attacking types.  For example, Water
    1.90 -attacks are strong against Fire pok\eacute{}mon, while Electric attacks are
    1.91 -weak against Ground Pok\eacute{}mon.  In the games, attacks can be either
    1.92 -twice as effective as normal (Water vs. Fire), neutrally effective
    1.93 -(Normal vs. Normal), half as effective (Fire vs. Water), or not
    1.94 -effective at all (Electric vs. Ground).  Thus the range of defense
    1.95 -values for a particular type is the set 0, 1/2, 1, 2. These are
    1.96 -referred to in the game as being immune, resistant, neutral, and
    1.97 -weak, respectively. I call them the /susceptance/ of one type to another.
    1.98 -
    1.99 -If a pokemon has two types, then the strengths and weakness of each
   1.100 -type are /multiplied/ together.  Thus Electric (2x weak to Ground)
   1.101 -combined with Flying (immune to Ground (0x)) is immune to
   1.102 -Ground.  Fire (2x weak to Water) combined with Water (1/2x resistant
   1.103 -to Water) is neutral to Water. If both types are resistant to another
   1.104 -type, then the combination is doubly-resistant (1/4x) to that type. If
   1.105 -both types are weak to a certain type then the combination is
   1.106 -double-weak (4x) to that type.
   1.107  
   1.108  ** Immortal Types
   1.109  
   1.110 -In the game, pok\eacute{}mon can have either one type, or two types. If this
   1.111 -restriction is lifted, is there any combination of types that is
   1.112 +In the game, pok\eacute{}mon can have either one type or two types. If
   1.113 +this restriction is lifted, is there any combination of types that is
   1.114  resistant to all types?  I call such a combination an /Immortal Type/,
   1.115  since if that type's pattern was repeated over and over again towards
   1.116  infinity, the resulting type would be immune to all attack types.
   1.117  
   1.118  * Linear Programming
   1.119  
   1.120 -** Terminology
   1.121  Linear programming is the process of finding an optimal solution to a
   1.122  linear equation of several variables which are constrained by some linear
   1.123  inequalities.
   1.124  
   1.125 -In linear programming terminology, the function to be extremized is
   1.126 -the /objective function/.
   1.127 -
   1.128 -** COMMENT 
   1.129 -First, we'll give a small example of a linear optimization problem,
   1.130 -and show how it can be solved with Clojure and =lp_solve=.  Then,
   1.131 -we'll show how finding immortal pok\eacute{}mon types can be converted
   1.132 -into a linear problem suitable for solving in the same way.
   1.133 -
   1.134  ** The Farmer's Problem
   1.135  
   1.136  Let's solve the Farmer's Problem, an example linear programming problem
   1.137 @@ -161,21 +152,10 @@
   1.138  +wheat +barley <= 75;
   1.139  #+end_src
   1.140  
   1.141 -
   1.142 -#This is a set of linear equations ideal for solving using a program like
   1.143 -#=lp_solve=. In Linear Algebra terms we are maximizing the linear function 
   1.144 -
   1.145 -#\(\text{profit} = 143\text{ wheat} + 60\text{ barley}\), subject to the constraints
   1.146 -
   1.147 -#Ax <= b,
   1.148 -
   1.149 -#where A is [120 210 110 30 1 1], x is [wheat barley] and b is [15000
   1.150 -#4000 75].
   1.151 -
   1.152  Running the =lp_solve= program on =farmer.lp= yields the following output.
   1.153  
   1.154  #+begin_src sh :exports both :results scalar
   1.155 -~/roBin/lpsolve/lp_solve ~/aurellem/src/pokemon/farmer.lp
   1.156 +lp_solve ~/proj/pokemon-types/lp/farmer.lp
   1.157  #+end_src
   1.158  
   1.159  #+results:
   1.160 @@ -190,55 +170,35 @@
   1.161  of the available acres with wheat and the remaining 53.125 acres with
   1.162  barley; by doing so, he will make $6315.62(5) in profit.
   1.163  
   1.164 -
   1.165 -#The farmer can make a profit of $6315.62 by planting 21.875 acres of
   1.166 -#his land with wheat and the other 53.125 acres of his land with barley.
   1.167 -
   1.168  * Incorporating  =lp_solve= into Clojure 
   1.169  
   1.170 -There is a Java API available which enables Java programs to use Lp
   1.171 -Solve. Although Clojure can use this Java API directly, the
   1.172 -interaction between Java, C, and Clojure is clumsy:
   1.173 -
   1.174 -
   1.175 -The Java API for LP Solve makes it possible to use Lp Solve algorithms
   1.176 -within Java. Although Clojure can use this  Java API directly, 
   1.177 -
   1.178 +There is a [[http://lpsolve.sourceforge.net/5.5/Java/README.html][Java API]] written by Juergen Ebert which enables Java
   1.179 +programs to use =lp_solve=. Although Clojure can use this Java API
   1.180 +directly, the interaction between Java, C, and Clojure is clumsy:
   1.181  
   1.182  ** The Farmer's Problem in Clojure
   1.183 +
   1.184  We are going to solve the same problem involving wheat and barley,
   1.185 -that we did above, but this time using clojure and the lpsolve API.
   1.186 -
   1.187 -#Because we ultimately intend to use Lp Solve to find optimal Pokemon type combinations.
   1.188 -# we want to solve linear optimization problems within Clojure, the language 
   1.189 -
   1.190 -** Setup
   1.191 -=lp_solve= is a crufty =C= program which already comes with a JNI
   1.192 -interface written by Juergen Ebert.  It's API is not
   1.193 -particularly friendly from a functional/immutable perspective, but
   1.194 -with a little work, we can build something that works great with
   1.195 -clojure.
   1.196 +that we did above, but this time using clojure and the =lp_solve= API.
   1.197  
   1.198  #+srcname: intro
   1.199  #+begin_src clojure :results silent
   1.200  (ns pokemon.lpsolve
   1.201 -  (:use rlm.ns-rlm))
   1.202 -(rlm.ns-rlm/ns-clone rlm.light-base)
   1.203 -(use 'clojure.set)
   1.204 -(import 'lpsolve.LpSolve)
   1.205 -(use '[clojure [pprint :only [pprint]]])
   1.206 +  (:use [clojure.contrib def set [seq :only [indexed]] pprint])
   1.207 +  (:import lpsolve.LpSolve)
   1.208 +  (:require pokemon.types)
   1.209 +  (:require incanter.core))
   1.210  #+end_src
   1.211  
   1.212 -The LpSolve Java interface is available from the same site as
   1.213 -=lp_solve= itself, http://lpsolve.sourceforge.net/ 
   1.214 -Using it is the same as many other =C=
   1.215 -programs. There are excellent instructions to get set
   1.216 -up.  The short version is that you must call Java with
   1.217 +The =lp_solve= Java interface is available from the same site as
   1.218 +=lp_solve= itself, http://lpsolve.sourceforge.net/ Using it is the
   1.219 +same as many other =C= programs. There are excellent instructions to
   1.220 +get set up.  The short version is that you must call Java with
   1.221  =-Djava.library.path=/path/to/lpsolve/libraries= and also add the
   1.222  libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For
   1.223  example, in my =.bashrc= file, I have the line
   1.224 -=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=.
   1.225 -If everything is set-up correctly, 
   1.226 +=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=.  If everything
   1.227 +is set-up correctly,
   1.228  
   1.229  #+srcname: body 
   1.230  #+begin_src clojure :results verbatim :exports both
   1.231 @@ -287,6 +247,7 @@
   1.232  (declare solve get-results)
   1.233  #+end_src
   1.234  
   1.235 +
   1.236  *** Memory Management
   1.237  
   1.238  Every instance of =LpSolve= must be manually garbage collected via a
   1.239 @@ -339,7 +300,7 @@
   1.240      (slurp target)))
   1.241  
   1.242  (defn results
   1.243 -  "given an LpSolve object, solves the object and returns a map of the
   1.244 +  "Given an LpSolve object, solves the object and returns a map of the
   1.245    essential values which compose the solution."
   1.246    [#^LpSolve lps]
   1.247    (locking lps
   1.248 @@ -349,8 +310,9 @@
   1.249  	  optimal-values (do (.getVariables lps optimal-values)
   1.250  			     (seq optimal-values))
   1.251  	  variable-names
   1.252 -	  (doall ;; the doall is necessary since the lps object might
   1.253 -	   ;; soon be deleted
   1.254 +	  (doall 
   1.255 +           ;; The doall is necessary since the lps object might
   1.256 +	   ;; soon be deleted.
   1.257  	   (map
   1.258  	    #(.getColName lps (inc %))
   1.259  	    (range number-of-variables)))
   1.260 @@ -556,9 +518,9 @@
   1.261  are immutable.
   1.262  
   1.263  * Using LpSolve to find Immortal Types
   1.264 -** Converting the Pokemon problem into a linear form
   1.265 +** Converting the Pok\eacute{}mon problem into a linear form
   1.266  How can the original question about pok\eacute{}mon types be converted
   1.267 -into a linear problem? 
   1.268 +into a linear problem?
   1.269  
   1.270  Pokemon types can be considered to be vectors of numbers representing
   1.271  their susceptances to various attacking types, so Water might look
   1.272 @@ -621,9 +583,6 @@
   1.273  #+begin_src clojure :results silent
   1.274  (in-ns 'pokemon.lpsolve)
   1.275  
   1.276 -(require 'pokemon.types)
   1.277 -(require 'incanter.core)
   1.278 -
   1.279  (defn log-clamp-matrix [matrix]
   1.280    ;; we have to clamp the Infinities to a more reasonable negative
   1.281    ;; value because lp_solve does not play well with infinities in its
   1.282 @@ -652,7 +611,6 @@
   1.283  (defn all-neutral []
   1.284    (doall (map (constantly 0) (pokemon.types/type-names))))
   1.285  
   1.286 -
   1.287  ;; objective functions
   1.288  (defn number-of-types []
   1.289    (doall (map (constantly 1) (pokemon.types/type-names))))
   1.290 @@ -710,7 +668,6 @@
   1.291    (if (not (= (:status results) "OPTIMAL"))
   1.292      (:status results)
   1.293      (:solution results)))
   1.294 -
   1.295  #+end_src
   1.296  
   1.297  With this, we are finally able to get some results.
   1.298 @@ -954,11 +911,11 @@
   1.299   ":rock" 0.0}
   1.300  #+end_example
   1.301  
   1.302 -The best attacking type combination is strangely Dragon from the
   1.303 -original games.  It is neutral against all the original types except
   1.304 -for Dragon, which it is strong against.  There is no way to make an
   1.305 -attacking type that is strong against every type, or even one that is
   1.306 -strong or neutral against every type, in the new games.
   1.307 +The best attacking type combination is Dragon from the original games.
   1.308 +It is neutral against all the original types except for Dragon, which
   1.309 +it is strong against.  There is no way to make an attacking type that
   1.310 +is strong against every type, or even one that is strong or neutral
   1.311 +against every type, in the new games.
   1.312  
   1.313  
   1.314  *** Weakest Attack/Defense Combinations
   1.315 @@ -1038,7 +995,8 @@
   1.316  combination.
   1.317  
   1.318  It's so interesting that it takes 20 types to make an attack type that
   1.319 -is weak to all types that the combination merits further investigation.
   1.320 +is weak to all types that the combination merits further
   1.321 +investigation.
   1.322  
   1.323  Unfortunately, all of the tools that we've written so far are focused
   1.324  on defense type combinations.  However, it is possible to make every
   1.325 @@ -1345,11 +1303,11 @@
   1.326  
   1.327  * Summary
   1.328  
   1.329 -Overall, the pok\eacute{}mon type system is slanted more towards defense
   1.330 -rather than offense.  While it is possible to create superior
   1.331 -defensive types and exceptionally weak attack types, it is not possible to
   1.332 -create exceptionally weak defensive types or very powerful attack
   1.333 -types.
   1.334 +Overall, the pok\eacute{}mon type system is slanted more towards
   1.335 +defense rather than offense.  While it is possible to create superior
   1.336 +defensive types and exceptionally weak attack types, it is not
   1.337 +possible to create exceptionally weak defensive types or very powerful
   1.338 +attack types.
   1.339  
   1.340  Using the =lp_solve= library was more complicated than the best-first
   1.341  search, but yielded results quickly and efficiently. Expressing the
   1.342 @@ -1378,6 +1336,4 @@
   1.343  #+end_src
   1.344  
   1.345  
   1.346 -* COMMENT Stuff to do.
   1.347 -** TODO fix namespaces to not use rlm.light-base
   1.348