pokemon-types: org/lpsolve.org comparison

comparison org/lpsolve.org @ 11:4ea23241ff5b

cleaned up prose

author	Robert McIntyre <rlm@mit.edu>
date	Wed, 02 Nov 2011 10:28:50 -0700
parents	eedd6897197d
children	89462678a932

comparison

equal deleted inserted replaced

-:eedd6897197d
+:4ea23241ff5b
 #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization
 #+author: Robert McIntyre & Dylan Holmes
 #+EMAIL:     rlm@mit.edu
+#+description: Using Lpsolve to func effective pokemon types in clojure.
+#+keywords: Pokemon, clojure, linear optimization, lp_spolve, LpSolve
 #+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
+This post continues the [[./types.org][previous one]] about pok\eacute{}mon types.
-locate the most effective Pok\eacute{}mon type
+Pok\eacute{}mon is a game in which adorable creatures battle each
-combinations. Afterwards, we realized that we could transform this
+other using fantastic attacks.  It was made into a several gameboy
-search problem into a /linear optimization problem/.  This conversion
+games that all share the same battle system.  Every pok\eacute{}mon in
-offeres several advantages: first, search algorithms are comparatively
+the gameboy game has one or two /types/, such as Ground, Fire, Water,
-slow, whereas linear optimization algorithms are extremely fast;
+etc. Every pok\eacute{}mon attack has exactly one type. Certain
-second, it is difficult to determine whether a search problem has any
+defending types are weak or strong to other attacking types.  For
-solution, whereas it is straightforward to determine whether a linear
+example, Water attacks are strong against Fire pok\eacute{}mon, while
-optimization problem has any solution; finally, because systems of
+Electric attacks are weak against Ground Pok\eacute{}mon.  In the
-linear equations are so common, many programming languages have linear
+games, attacks can be either twice as effective as normal (Water
-equation solvers written for them.
+vs. Fire), neutrally effective (Normal vs. Normal), half as effective
+(Fire vs. Water), or not effective at all (Electric vs. Ground). We
-In this article, we will
+represent these strengths and weakessness as the numbers 2, 1,
+$\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to
+another.
+If a pokemon has two types, then the strengths and weakness of each
+type are /multiplied/ together.  Thus Electric (2x weak to Ground)
+combined with Flying (immune to Ground (0x)) is immune to Ground.
+Fire (2x weak to Water) combined with Water (1/2x resistant to Water)
+is neutral to Water. If both types are resistant to another type, then
+the combination is doubly-resistant (1/4x) to that type. If both types
+are weak to a certain type then the combination is double-weak (4x) to
+that type.
+In the [[./types.org][previous post]], we used the best-first search algorithm to find
+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
+solve a simple linear optimization problem.
-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, (...)
+on our earlier code, we answer some questions that were
-- Present our results ::
+impossible to answer using best-first search.
+- Present our results :: We found some cool examples and learned a lot
+about the pok\eacute{}mon type system as a whole.
-#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
+In the game, pok\eacute{}mon can have either one type or two types. If
-restriction is lifted, is there any combination of types that is
+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.
 /* 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
+lp_solve ~/proj/pokemon-types/lp/farmer.lp
 #+end_src
 #+results:
 :
 : Value of objective function: 6315.62500000
 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
+There is a [[http://lpsolve.sourceforge.net/5.5/Java/README.html][Java API]] written by Juergen Ebert which enables Java
-Solve. Although Clojure can use this Java API directly, the
+programs to use =lp_solve=. Although Clojure can use this Java API
-interaction between Java, C, and Clojure is clumsy:
+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.
+that we did above, but this time using clojure and the =lp_solve= 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))
+(:use [clojure.contrib def set [seq :only [indexed]] pprint])
-(rlm.ns-rlm/ns-clone rlm.light-base)
+(:import lpsolve.LpSolve)
-(use 'clojure.set)
+(:require pokemon.types)
-(import 'lpsolve.LpSolve)
+(:require incanter.core))
-(use '[clojure [pprint :only [pprint]]])
+#+end_src
-#+end_src
+The =lp_solve= Java interface is available from the same site as
-The LpSolve Java interface is available from the same site as
+=lp_solve= itself, http://lpsolve.sourceforge.net/ Using it is the
-=lp_solve= itself, http://lpsolve.sourceforge.net/
+same as many other =C= programs. There are excellent instructions to
-Using it is the same as many other =C=
+get set up.  The short version is that you must call Java with
-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=.
+=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=.  If everything
-If everything is set-up correctly,
+is set-up correctly,
 #+srcname: body
 #+begin_src clojure :results verbatim :exports both
 (import 'lpsolve.LpSolve)
 #+end_src
 ;; 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.
 (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
+"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
+	  (doall
-	   ;; soon be deleted
+;; The doall is necessary since the lps object might
+	   ;; soon be deleted.
 	   (map
 	    #(.getColName lps (inc %))
 	    (range number-of-variables)))
 	  model (model lps)]
 (LpSolution.
 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
+** Converting the Pok\eacute{}mon 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.
 #+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))
 (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))))
 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
 ":grass" 0.0,
 ":water" 0.0,
 ":rock" 0.0}
 #+end_example
-The best attacking type combination is strangely Dragon from the
+The best attacking type combination is Dragon from the original games.
-original games.  It is neutral against all the original types except
+It is neutral against all the original types except for Dragon, which
-for Dragon, which it is strong against.  There is no way to make an
+it is strong against.  There is no way to make an attacking type that
-attacking type that is strong against every type, or even one that is
+is strong against every type, or even one that is strong or neutral
-strong or neutral against every type, in the new games.
+against every type, in the new games.
 *** Weakest Attack/Defense Combinations
 #+begin_src clojure :results output :exports both
 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.
+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.
 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
+Overall, the pok\eacute{}mon type system is slanted more towards
-rather than offense.  While it is possible to create superior
+defense rather than offense.  While it is possible to create superior
-defensive types and exceptionally weak attack types, it is not possible to
+defensive types and exceptionally weak attack types, it is not
-create exceptionally weak defensive types or very powerful attack
+possible to create exceptionally weak defensive types or very powerful
-types.
+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
 <<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 @ 11:4ea23241ff5b