# HG changeset patch # User Robert McIntyre # Date 1320254930 25200 # Node ID 4ea23241ff5b02f25004fdc2f76008c48fdfec7c # Parent eedd6897197d1517ac95076f339e974e95f3e4a5 cleaned up prose diff -r eedd6897197d -r 4ea23241ff5b org/lpsolve.org --- a/org/lpsolve.org Wed Nov 02 08:02:11 2011 -0700 +++ b/org/lpsolve.org Wed Nov 02 10:28:50 2011 -0700 @@ -1,87 +1,78 @@ #+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 -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. +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). We +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. -In this article, we will +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 - optimization problem. + 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 :: + on our earlier code, we answer some questions that were + impossible to answer using best-first search. +- Present our results :: We found some cool examples and learned a lot + about the pok\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 -restriction is lifted, is there any combination of types that is +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 @@ -161,21 +152,10 @@ +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: @@ -190,55 +170,35 @@ 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, - +There is a [[http://lpsolve.sourceforge.net/5.5/Java/README.html][Java API]] written by Juergen Ebert which enables Java +programs to use =lp_solve=. Although Clojure can use this Java API +directly, the interaction between Java, C, and Clojure is clumsy: ** 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. +that we did above, but this time using clojure and the =lp_solve= API. #+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]]]) + (:use [clojure.contrib def set [seq :only [indexed]] pprint]) + (:import lpsolve.LpSolve) + (:require pokemon.types) + (:require incanter.core)) #+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 +The =lp_solve= Java interface is available from the same site as +=lp_solve= itself, http://lpsolve.sourceforge.net/ Using it is the +same as many other =C= programs. There are excellent instructions to +get set up. The short version is that you must call Java with =-Djava.library.path=/path/to/lpsolve/libraries= and also add the libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For example, in my =.bashrc= file, I have the line -=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=. -If everything is set-up correctly, +=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=. If everything +is set-up correctly, #+srcname: body #+begin_src clojure :results verbatim :exports both @@ -287,6 +247,7 @@ (declare solve get-results) #+end_src + *** Memory Management Every instance of =LpSolve= must be manually garbage collected via a @@ -339,7 +300,7 @@ (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 @@ -349,8 +310,9 @@ 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 + (doall + ;; The doall is necessary since the lps object might + ;; soon be deleted. (map #(.getColName lps (inc %)) (range number-of-variables))) @@ -556,9 +518,9 @@ 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? +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 @@ -621,9 +583,6 @@ #+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 @@ -652,7 +611,6 @@ (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)))) @@ -710,7 +668,6 @@ (if (not (= (:status results) "OPTIMAL")) (:status results) (:solution results))) - #+end_src With this, we are finally able to get some results. @@ -954,11 +911,11 @@ ":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. +The best attacking type combination is Dragon from the original games. +It is neutral against all the original types except for Dragon, which +it is strong against. There is no way to make an attacking type that +is strong against every type, or even one that is strong or neutral +against every type, in the new games. *** Weakest Attack/Defense Combinations @@ -1038,7 +995,8 @@ 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 @@ -1345,11 +1303,11 @@ * 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. +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 @@ -1378,6 +1336,4 @@ #+end_src -* COMMENT Stuff to do. -** TODO fix namespaces to not use rlm.light-base