annotate org/lpsolve.org @ 17:0f6ace87343a

minor typographical changes.
author Robert McIntyre <rlm@mit.edu>
date Mon, 06 Aug 2012 17:26:48 -0400
parents 7698e9bdff2b
children 2bec94944460
rev   line source
rlm@10 1 #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization
rlm@0 2 #+author: Robert McIntyre & Dylan Holmes
rlm@0 3 #+EMAIL: rlm@mit.edu
rlm@12 4 #+description: Using Lpsolve to find effective pokemon types in clojure.
rlm@12 5 #+keywords: Pokemon, clojure, linear optimization, lp_solve, LpSolve
rlm@4 6 #+SETUPFILE: ../../aurellem/org/setup.org
rlm@2 7 #+INCLUDE: ../../aurellem/org/level-0.org
rlm@4 8
rlm@0 9 * Introduction
rlm@11 10 This post continues the [[./types.org][previous one]] about pok\eacute{}mon types.
rlm@11 11 Pok\eacute{}mon is a game in which adorable creatures battle each
rlm@11 12 other using fantastic attacks. It was made into a several gameboy
rlm@11 13 games that all share the same battle system. Every pok\eacute{}mon in
rlm@11 14 the gameboy game has one or two /types/, such as Ground, Fire, Water,
rlm@11 15 etc. Every pok\eacute{}mon attack has exactly one type. Certain
rlm@11 16 defending types are weak or strong to other attacking types. For
rlm@11 17 example, Water attacks are strong against Fire pok\eacute{}mon, while
rlm@11 18 Electric attacks are weak against Ground Pok\eacute{}mon. In the
rlm@11 19 games, attacks can be either twice as effective as normal (Water
rlm@11 20 vs. Fire), neutrally effective (Normal vs. Normal), half as effective
rlm@11 21 (Fire vs. Water), or not effective at all (Electric vs. Ground). We
rlm@12 22 represent these strengths and weaknesses as the numbers 2, 1,
rlm@11 23 $\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to
rlm@11 24 another.
rlm@0 25
rlm@11 26 If a pokemon has two types, then the strengths and weakness of each
rlm@11 27 type are /multiplied/ together. Thus Electric (2x weak to Ground)
rlm@11 28 combined with Flying (immune to Ground (0x)) is immune to Ground.
rlm@11 29 Fire (2x weak to Water) combined with Water (1/2x resistant to Water)
rlm@11 30 is neutral to Water. If both types are resistant to another type, then
rlm@11 31 the combination is doubly-resistant (1/4x) to that type. If both types
rlm@11 32 are weak to a certain type then the combination is double-weak (4x) to
rlm@11 33 that type.
rlm@11 34
rlm@11 35 In the [[./types.org][previous post]], we used the best-first search algorithm to find
rlm@11 36 the most effective Pok\eacute{}mon type combinations. Afterwards, we
rlm@11 37 realized that we could transform this search problem into a /linear
rlm@12 38 optimization problem/. This conversion offers several advantages:
rlm@11 39 first, search algorithms are comparatively slow, whereas linear
rlm@11 40 optimization algorithms are extremely fast; second, it is difficult to
rlm@11 41 determine whether a search problem has any solution, whereas it is
rlm@11 42 straightforward to determine whether a linear optimization problem has
rlm@11 43 any solution; finally, because systems of linear equations are so
rlm@11 44 common, many programming languages have linear equation solvers
rlm@11 45 written for them.
rlm@11 46
rlm@11 47 In this article, we will:
rlm@0 48 - Solve a simple linear optimization problem in C :: We demonstrate
rlm@0 49 how to use the linear programming C library, =lp_solve=, to
rlm@11 50 solve a simple linear optimization problem.
rlm@0 51 - Incorporate a C library into Clojure :: We will show how we gave
rlm@0 52 Clojure access to the linear programming C library, =lp_solve=.
rlm@0 53 - Find effective Pokemon types using linear programming :: Building
rlm@11 54 on our earlier code, we answer some questions that were
rlm@11 55 impossible to answer using best-first search.
rlm@11 56 - Present our results :: We found some cool examples and learned a lot
rlm@11 57 about the pok\eacute{}mon type system as a whole.
rlm@0 58
rlm@0 59
rlm@0 60 ** Immortal Types
rlm@13 61
rlm@11 62 In the game, pok\eacute{}mon can have either one type or two types. If
rlm@11 63 this restriction is lifted, is there any combination of types that is
rlm@0 64 resistant to all types? I call such a combination an /Immortal Type/,
rlm@0 65 since if that type's pattern was repeated over and over again towards
rlm@0 66 infinity, the resulting type would be immune to all attack types.
rlm@0 67
rlm@0 68 * Linear Programming
rlm@0 69
rlm@0 70 Linear programming is the process of finding an optimal solution to a
rlm@0 71 linear equation of several variables which are constrained by some linear
rlm@0 72 inequalities.
rlm@0 73
rlm@0 74 ** The Farmer's Problem
rlm@0 75
rlm@10 76 Let's solve the Farmer's Problem, an example linear programming problem
rlm@0 77 borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm.
rlm@0 78
rlm@0 79
rlm@0 80 #+BEGIN_QUOTE
rlm@0 81 *The Farmer's Problem:* Suppose a farmer has 75 acres on which to
rlm@0 82 plant two crops: wheat and barley. To produce these crops, it costs
rlm@0 83 the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat
rlm@0 84 and $210 per acre for the barley. The farmer has $15000 available for
rlm@0 85 expenses. But after the harvest, the farmer must store the crops while
rlm@0 86 awaiting favorable market conditions. The farmer has storage space
rlm@0 87 for 4000 bushels. Each acre yields an average of 110 bushels of wheat
rlm@0 88 or 30 bushels of barley. If the net profit per bushel of wheat (after
rlm@0 89 all expenses have been subtracted) is $1.30 and for barley is $2.00,
rlm@0 90 how should the farmer plant the 75 acres to maximize profit?
rlm@0 91 #+END_QUOTE
rlm@0 92
rlm@0 93 The Farmer's Problem is to maximize profit subject to constraints on
rlm@0 94 available farmland, funds for expenses, and storage space.
rlm@0 95
rlm@0 96 | | Wheat | Barley | Maximum total |
rlm@0 97 |----------+----------------------+---------------------+--------------|
rlm@0 98 | / | < | > | <> |
rlm@0 99 | Farmland | \(w\) acres | \(b\) acres | 75 acres |
rlm@0 100 | Expense | $120 per acre | $210 per acre | $15000 |
rlm@0 101 | Storage | 110 bushels per acre | 30 bushels per acre | 4000 bushels |
rlm@0 102 |----------+----------------------+---------------------+--------------|
rlm@0 103 | Profit | $1.30 per bushel | $2.00 per bushel | |
rlm@0 104
rlm@0 105 ** Solution using LP Solve
rlm@0 106 In a new file, =farmer.lp=, we list the variables and constraints
rlm@0 107 of our problem using LP Solve syntax.
rlm@0 108
rlm@3 109 #+begin_src lpsolve :tangle ../lp/farmer.lp
rlm@0 110 /* Maximize Total Profit */
rlm@0 111 max: +143 wheat +60 barley;
rlm@0 112
rlm@0 113
rlm@0 114 /* -------- Constraints --------*/
rlm@0 115
rlm@0 116 /* the farmer can't spend more money than he has */
rlm@0 117 +120 wheat +210 barley <= 15000;
rlm@0 118
rlm@0 119 /* the harvest has to fit in his storage space */
rlm@0 120 +110 wheat +30 barley <= 4000;
rlm@0 121
rlm@0 122 /* he can't use more acres than he owns */
rlm@0 123 +wheat +barley <= 75;
rlm@0 124 #+end_src
rlm@0 125
rlm@0 126 Running the =lp_solve= program on =farmer.lp= yields the following output.
rlm@0 127
rlm@0 128 #+begin_src sh :exports both :results scalar
rlm@11 129 lp_solve ~/proj/pokemon-types/lp/farmer.lp
rlm@0 130 #+end_src
rlm@0 131
rlm@0 132 #+results:
rlm@0 133 :
rlm@0 134 : Value of objective function: 6315.62500000
rlm@0 135 :
rlm@0 136 : Actual values of the variables:
rlm@0 137 : wheat 21.875
rlm@0 138 : barley 53.125
rlm@0 139
rlm@16 140
rlm@0 141 This shows that the farmer can maximize his profit by planting 21.875
rlm@0 142 of the available acres with wheat and the remaining 53.125 acres with
rlm@0 143 barley; by doing so, he will make $6315.62(5) in profit.
rlm@0 144
rlm@0 145 * Incorporating =lp_solve= into Clojure
rlm@0 146
rlm@11 147 There is a [[http://lpsolve.sourceforge.net/5.5/Java/README.html][Java API]] written by Juergen Ebert which enables Java
rlm@11 148 programs to use =lp_solve=. Although Clojure can use this Java API
rlm@11 149 directly, the interaction between Java, C, and Clojure is clumsy:
rlm@0 150
rlm@0 151 ** The Farmer's Problem in Clojure
rlm@11 152
rlm@0 153 We are going to solve the same problem involving wheat and barley,
rlm@11 154 that we did above, but this time using clojure and the =lp_solve= API.
rlm@0 155
rlm@16 156 #+name: intro
rlm@0 157 #+begin_src clojure :results silent
rlm@0 158 (ns pokemon.lpsolve
rlm@11 159 (:import lpsolve.LpSolve)
rlm@11 160 (:require pokemon.types)
rlm@16 161 (:require incanter.core)
rlm@13 162 (:require rlm.map-utils))
rlm@0 163 #+end_src
rlm@0 164
rlm@11 165 The =lp_solve= Java interface is available from the same site as
rlm@11 166 =lp_solve= itself, http://lpsolve.sourceforge.net/ Using it is the
rlm@11 167 same as many other =C= programs. There are excellent instructions to
rlm@11 168 get set up. The short version is that you must call Java with
rlm@0 169 =-Djava.library.path=/path/to/lpsolve/libraries= and also add the
rlm@0 170 libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For
rlm@0 171 example, in my =.bashrc= file, I have the line
rlm@11 172 =LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=. If everything
rlm@11 173 is set-up correctly,
rlm@0 174
rlm@16 175 #+name: body
rlm@0 176 #+begin_src clojure :results verbatim :exports both
rlm@0 177 (import 'lpsolve.LpSolve)
rlm@0 178 #+end_src
rlm@0 179
rlm@0 180 #+results: body
rlm@0 181 : lpsolve.LpSolve
rlm@0 182
rlm@0 183 should run with no problems.
rlm@0 184
rlm@0 185 ** Making a DSL to talk with LpSolve
rlm@0 186 *** Problems
rlm@0 187 Since we are using a =C= wrapper, we have to deal with manual memory
rlm@0 188 management for the =C= structures which are wrapped by the =LpSolve=
rlm@0 189 object. Memory leaks in =LpSolve= instances can crash the JVM, so it's
rlm@0 190 very important to get it right. Also, the Java wrapper follows the
rlm@0 191 =C= tradition closely and defines many =static final int= constants
rlm@0 192 for the different states of the =LpSolve= instance instead of using Java
rlm@0 193 enums. The calling convention for adding rows and columns to
rlm@0 194 the constraint matrix is rather complicated and must be done column by
rlm@0 195 column or row by row, which can be error prone. Finally, I'd like to
rlm@0 196 gather all the important output information from the =LpSolve= instance
rlm@0 197 into a final, immutable structure.
rlm@0 198
rlm@0 199 In summary, the issues I'd like to address are:
rlm@0 200
rlm@0 201 - reliable memory management
rlm@0 202 - functional interface to =LpSolve=
rlm@0 203 - intelligible, immutable output
rlm@0 204
rlm@0 205 To deal with these issues I'll create four functions for interfacing
rlm@0 206 with =LpSolve=
rlm@0 207
rlm@16 208 #+name: declares
rlm@0 209 #+begin_src clojure :results silent
rlm@0 210 (in-ns 'pokemon.lpsolve)
rlm@0 211
rlm@0 212 ;; deal with automatic memory management for LpSolve instance.
rlm@0 213 (declare linear-program)
rlm@0 214
rlm@0 215 ;; functional interface to LpSolve
rlm@0 216 (declare lp-solve)
rlm@0 217
rlm@0 218 ;; immutable output from lp-solve
rlm@0 219 (declare solve get-results)
rlm@0 220 #+end_src
rlm@0 221
rlm@11 222
rlm@0 223 *** Memory Management
rlm@0 224
rlm@0 225 Every instance of =LpSolve= must be manually garbage collected via a
rlm@0 226 call to =deleteLP=. I use a non-hygienic macro similar to =with-open=
rlm@0 227 to ensure that =deleteLP= is always called.
rlm@0 228
rlm@16 229 #+name: memory-management
rlm@0 230 #+begin_src clojure :results silent
rlm@0 231 (in-ns 'pokemon.lpsolve)
rlm@0 232 (defmacro linear-program
rlm@0 233 "solve a linear programming problem using LpSolve syntax.
rlm@0 234 within the macro, the variable =lps= is bound to the LpSolve instance."
rlm@0 235 [& statements]
rlm@0 236 (list 'let '[lps (LpSolve/makeLp 0 0)]
rlm@0 237 (concat '(try)
rlm@0 238 statements
rlm@0 239 ;; always free the =C= data structures.
rlm@0 240 '((finally (.deleteLp lps))))))
rlm@0 241 #+end_src
rlm@0 242
rlm@0 243
rlm@0 244 The macro captures the variable =lps= within its body, providing for a
rlm@0 245 convenient way to access the object using any of the methods of the
rlm@0 246 =LpSolve= API without having to worry about when to call
rlm@0 247 =deleteLP=.
rlm@0 248
rlm@0 249 *** Sensible Results
rlm@0 250 The =linear-program= macro deletes the actual =lps= object once it is
rlm@0 251 done working, so it's important to collect the important results and
rlm@0 252 add return them in an immutable structure at the end.
rlm@0 253
rlm@16 254 #+name: get-results
rlm@0 255 #+begin_src clojure :results silent
rlm@0 256 (in-ns 'pokemon.lpsolve)
rlm@0 257
rlm@0 258 (defrecord LpSolution
rlm@0 259 [objective-value
rlm@0 260 optimal-values
rlm@0 261 variable-names
rlm@0 262 solution
rlm@0 263 status
rlm@0 264 model])
rlm@0 265
rlm@0 266 (defn model
rlm@0 267 "Returns a textual representation of the problem suitable for
rlm@0 268 direct input to the =lp_solve= program (lps format)"
rlm@0 269 [#^LpSolve lps]
rlm@0 270 (let [target (java.io.File/createTempFile "lps" ".lp")]
rlm@0 271 (.writeLp lps (.getPath target))
rlm@0 272 (slurp target)))
rlm@0 273
rlm@0 274 (defn results
rlm@11 275 "Given an LpSolve object, solves the object and returns a map of the
rlm@0 276 essential values which compose the solution."
rlm@0 277 [#^LpSolve lps]
rlm@0 278 (locking lps
rlm@0 279 (let [status (solve lps)
rlm@0 280 number-of-variables (.getNcolumns lps)
rlm@0 281 optimal-values (double-array number-of-variables)
rlm@0 282 optimal-values (do (.getVariables lps optimal-values)
rlm@0 283 (seq optimal-values))
rlm@0 284 variable-names
rlm@11 285 (doall
rlm@11 286 ;; The doall is necessary since the lps object might
rlm@11 287 ;; soon be deleted.
rlm@0 288 (map
rlm@0 289 #(.getColName lps (inc %))
rlm@0 290 (range number-of-variables)))
rlm@0 291 model (model lps)]
rlm@0 292 (LpSolution.
rlm@0 293 (.getObjective lps)
rlm@0 294 optimal-values
rlm@0 295 variable-names
rlm@0 296 (zipmap variable-names optimal-values)
rlm@0 297 status
rlm@0 298 model))))
rlm@0 299
rlm@0 300 #+end_src
rlm@0 301
rlm@0 302 Here I've created an object called =LpSolution= which stores the
rlm@0 303 important results from a session with =lp_solve=. Of note is the
rlm@0 304 =model= function which returns the problem in a form that can be
rlm@0 305 solved by other linear programming packages.
rlm@0 306
rlm@0 307 *** Solution Status of an LpSolve Object
rlm@0 308
rlm@16 309 #+name: solve
rlm@0 310 #+begin_src clojure :results silent
rlm@0 311 (in-ns 'pokemon.lpsolve)
rlm@0 312
rlm@0 313 (defn static-integer?
rlm@0 314 "does the field represent a static integer constant?"
rlm@0 315 [#^java.lang.reflect.Field field]
rlm@0 316 (and (java.lang.reflect.Modifier/isStatic (.getModifiers field))
rlm@0 317 (integer? (.get field nil))))
rlm@0 318
rlm@0 319 (defn integer-constants [class]
rlm@0 320 (filter static-integer? (.getFields class)))
rlm@0 321
rlm@16 322 (defn constant-map
rlm@0 323 "Takes a class and creates a map of the static constant integer
rlm@0 324 fields with their names. This helps with C wrappers where they have
rlm@13 325 just defined a bunch of integer constants instead of enums."
rlm@0 326 [class]
rlm@0 327 (let [integer-fields (integer-constants class)]
rlm@0 328 (into (sorted-map)
rlm@0 329 (zipmap (map #(.get % nil) integer-fields)
rlm@0 330 (map #(.getName %) integer-fields)))))
rlm@16 331
rlm@16 332 (alter-var-root #'constant-map memoize)
rlm@0 333
rlm@0 334 (defn solve
rlm@0 335 "Solve an instance of LpSolve and return a string representing the
rlm@0 336 status of the computation. Will only solve a particular LpSolve
rlm@0 337 instance once."
rlm@0 338 [#^LpSolve lps]
rlm@0 339 ((constant-map LpSolve)
rlm@0 340 (.solve lps)))
rlm@0 341
rlm@0 342 #+end_src
rlm@0 343
rlm@0 344 The =.solve= method of an =LpSolve= object only returns an integer code
rlm@0 345 to specify the status of the computation. The =solve= method here
rlm@0 346 uses reflection to look up the actual name of the status code and
rlm@0 347 returns a more helpful status message that is also resistant to
rlm@0 348 changes in the meanings of the code numbers.
rlm@0 349
rlm@0 350 *** The Farmer Example in Clojure, Pass 1
rlm@0 351
rlm@0 352 Now we can implement a nicer version of the examples from the
rlm@0 353 [[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less
rlm@0 354 line-by-line translation of the Java code from that example.
rlm@0 355
rlm@16 356 #+name: farmer-example
rlm@0 357 #+begin_src clojure :results silent
rlm@0 358 (in-ns 'pokemon.lpsolve)
rlm@0 359 (defn farmer-example []
rlm@0 360 (linear-program
rlm@0 361 (results
rlm@0 362 (doto lps
rlm@0 363 ;; name the columns
rlm@0 364 (.setColName 1 "wheat")
rlm@0 365 (.setColName 2 "barley")
rlm@0 366 (.setAddRowmode true)
rlm@0 367 ;; row 1 : 120x + 210y <= 15000
rlm@0 368 (.addConstraintex 2
rlm@0 369 (double-array [120 210])
rlm@0 370 (int-array [1 2])
rlm@0 371 LpSolve/LE
rlm@0 372 15e3)
rlm@0 373 ;; row 2 : 110x + 30y <= 4000
rlm@0 374 (.addConstraintex 2
rlm@0 375 (double-array [110 30])
rlm@0 376 (int-array [1 2])
rlm@0 377 LpSolve/LE
rlm@0 378 4e3)
rlm@0 379 ;; ;; row 3 : x + y <= 75
rlm@0 380 (.addConstraintex 2
rlm@0 381 (double-array [1 1])
rlm@0 382 (int-array [1 2])
rlm@0 383 LpSolve/LE
rlm@0 384 75)
rlm@0 385 (.setAddRowmode false)
rlm@0 386
rlm@0 387 ;; add constraints
rlm@0 388 (.setObjFnex 2
rlm@0 389 (double-array [143 60])
rlm@0 390 (int-array [1 2]))
rlm@0 391
rlm@0 392 ;; set this as a maximization problem
rlm@0 393 (.setMaxim)))))
rlm@0 394
rlm@0 395 #+end_src
rlm@0 396
rlm@0 397 #+begin_src clojure :results output :exports both
rlm@0 398 (clojure.pprint/pprint
rlm@0 399 (:solution (pokemon.lpsolve/farmer-example)))
rlm@0 400 #+end_src
rlm@0 401
rlm@0 402 #+results:
rlm@0 403 : {"barley" 53.12499999999999, "wheat" 21.875}
rlm@0 404
rlm@0 405 And it works as expected!
rlm@0 406
rlm@0 407 *** The Farmer Example in Clojure, Pass 2
rlm@0 408 We don't have to worry about memory management anymore, and the farmer
rlm@0 409 example is about half as long as the example from the =LpSolve=
rlm@0 410 website, but we can still do better. Solving linear problems is all
rlm@0 411 about the constraint matrix $A$ , the objective function $c$, and the
rlm@0 412 right-hand-side $b$, plus whatever other options one cares to set for
rlm@0 413 the particular instance of =lp_solve=. Why not make a version of
rlm@0 414 =linear-program= that takes care of initialization?
rlm@0 415
rlm@0 416
rlm@0 417
rlm@16 418 #+name: lp-solve
rlm@0 419 #+begin_src clojure :results silent
rlm@0 420 (in-ns 'pokemon.lpsolve)
rlm@0 421 (defn initialize-lpsolve-row-oriented
rlm@0 422 "fill in an lpsolve instance using a constraint matrix =A=, the
rlm@0 423 objective function =c=, and the right-hand-side =b="
rlm@0 424 [#^LpSolve lps A b c]
rlm@0 425 ;; set the name of the last column to _something_
rlm@0 426 ;; this appears to be necessary to ensure proper initialization.
rlm@0 427 (.setColName lps (count c) (str "C" (count c)))
rlm@0 428
rlm@0 429 ;; This is the recommended way to "fill-in" an lps instance from the
rlm@0 430 ;; documentation. First, set row mode, then set the objective
rlm@0 431 ;; function, then set each row of the problem, and then turn off row
rlm@0 432 ;; mode.
rlm@0 433 (.setAddRowmode lps true)
rlm@0 434 (.setObjFnex lps (count c)
rlm@0 435 (double-array c)
rlm@0 436 (int-array (range 1 (inc (count c)))))
rlm@0 437 (dorun
rlm@0 438 (for [n (range (count A))]
rlm@0 439 (let [row (nth A n)
rlm@0 440 row-length (int (count row))]
rlm@0 441 (.addConstraintex lps
rlm@0 442 row-length
rlm@0 443 (double-array row)
rlm@0 444 (int-array (range 1 (inc row-length)))
rlm@0 445 LpSolve/LE
rlm@0 446 (double (nth b n))))))
rlm@0 447 (.setAddRowmode lps false)
rlm@0 448 lps)
rlm@0 449
rlm@0 450
rlm@0 451 (defmacro lp-solve
rlm@0 452 "by default:,
rlm@0 453 minimize (* c x), subject to (<= (* A x) b),
rlm@0 454 using continuous variables. You may set any number of
rlm@0 455 other options as in the LpSolve API."
rlm@0 456 [A b c & lp-solve-forms]
rlm@0 457 ;; assume that A is a vector of vectors
rlm@0 458 (concat
rlm@0 459 (list 'linear-program
rlm@0 460 (list 'initialize-lpsolve-row-oriented 'lps A b c))
rlm@0 461 `~lp-solve-forms))
rlm@0 462 #+end_src
rlm@0 463
rlm@0 464 Now, we can use a much more functional approach to solving the
rlm@0 465 farmer's problem:
rlm@0 466
rlm@16 467 #+name: better-farmer
rlm@0 468 #+begin_src clojure :results silent
rlm@0 469 (in-ns 'pokemon.lpsolve)
rlm@0 470 (defn better-farmer-example []
rlm@0 471 (lp-solve [[120 210]
rlm@0 472 [110 30]
rlm@0 473 [1 1]]
rlm@0 474 [15000
rlm@0 475 4000
rlm@0 476 75]
rlm@0 477 [143 60]
rlm@0 478 (.setColName lps 1 "wheat")
rlm@0 479 (.setColName lps 2 "barley")
rlm@0 480 (.setMaxim lps)
rlm@0 481 (results lps)))
rlm@0 482 #+end_src
rlm@0 483
rlm@0 484 #+begin_src clojure :exports both :results verbatim
rlm@0 485 (vec (:solution (pokemon.lpsolve/better-farmer-example)))
rlm@0 486 #+end_src
rlm@0 487
rlm@0 488 #+results:
rlm@0 489 : [["barley" 53.12499999999999] ["wheat" 21.875]]
rlm@0 490
rlm@0 491 Notice that both the inputs to =better-farmer-example= and the results
rlm@0 492 are immutable.
rlm@0 493
rlm@0 494 * Using LpSolve to find Immortal Types
rlm@11 495 ** Converting the Pok\eacute{}mon problem into a linear form
rlm@0 496 How can the original question about pok\eacute{}mon types be converted
rlm@11 497 into a linear problem?
rlm@0 498
rlm@0 499 Pokemon types can be considered to be vectors of numbers representing
rlm@0 500 their susceptances to various attacking types, so Water might look
rlm@0 501 something like this.
rlm@0 502
rlm@0 503 #+begin_src clojure :results scalar :exports both
rlm@0 504 (:water (pokemon.types/defense-strengths))
rlm@0 505 #+end_src
rlm@0 506
rlm@0 507 #+results:
rlm@0 508 : [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5]
rlm@0 509
rlm@0 510 Where the numbers represent the susceptibility of Water to the
rlm@0 511 attacking types in the following order:
rlm@0 512
rlm@0 513 #+begin_src clojure :results output :exports both
rlm@0 514 (clojure.pprint/pprint
rlm@0 515 (pokemon.types/type-names))
rlm@0 516 #+end_src
rlm@0 517
rlm@0 518 #+results:
rlm@0 519 #+begin_example
rlm@0 520 [:normal
rlm@0 521 :fire
rlm@0 522 :water
rlm@0 523 :electric
rlm@0 524 :grass
rlm@0 525 :ice
rlm@0 526 :fighting
rlm@0 527 :poison
rlm@0 528 :ground
rlm@0 529 :flying
rlm@0 530 :psychic
rlm@0 531 :bug
rlm@0 532 :rock
rlm@0 533 :ghost
rlm@0 534 :dragon
rlm@0 535 :dark
rlm@0 536 :steel]
rlm@0 537 #+end_example
rlm@0 538
rlm@0 539
rlm@13 540 So, for example, Water is resistant (x0.5) against Fire, which is
rlm@0 541 the second element in the list.
rlm@0 542
rlm@0 543 To combine types, these sorts of vectors are multiplied together
rlm@0 544 pair-wise to yield the resulting combination.
rlm@0 545
rlm@0 546 Unfortunately, we need some way to add two type vectors together
rlm@0 547 instead of multiplying them if we want to solve the problem with
rlm@0 548 =lp_solve=. Taking the log of the vector does just the trick.
rlm@0 549
rlm@0 550 If we make a matrix with each column being the log (base 2) of the
rlm@0 551 susceptance of each type, then finding an immortal type corresponds to
rlm@0 552 setting each constraint (the $b$ vector) to -1 (since log_2(1/2) = -1)
rlm@0 553 and setting the constraint vector $c$ to all ones, which means that we
rlm@0 554 want to find the immortal type which uses the least amount of types.
rlm@0 555
rlm@16 556 #+name: pokemon-lp
rlm@0 557 #+begin_src clojure :results silent
rlm@0 558 (in-ns 'pokemon.lpsolve)
rlm@0 559
rlm@0 560 (defn log-clamp-matrix [matrix]
rlm@0 561 ;; we have to clamp the Infinities to a more reasonable negative
rlm@0 562 ;; value because lp_solve does not play well with infinities in its
rlm@0 563 ;; constraint matrix.
rlm@0 564 (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %) row))
rlm@0 565 (incanter.core/log2
rlm@0 566 (incanter.core/trans
rlm@0 567 matrix))))
rlm@0 568
rlm@0 569 ;; constraint matrices
rlm@0 570 (defn log-defense-matrix []
rlm@0 571 (log-clamp-matrix
rlm@0 572 (doall (map (pokemon.types/defense-strengths)
rlm@0 573 (pokemon.types/type-names)))))
rlm@0 574
rlm@0 575 (defn log-attack-matrix []
rlm@0 576 (incanter.core/trans (log-defense-matrix)))
rlm@0 577
rlm@0 578 ;; target vectors
rlm@0 579 (defn all-resistant []
rlm@0 580 (doall (map (constantly -1) (pokemon.types/type-names))))
rlm@0 581
rlm@0 582 (defn all-weak []
rlm@0 583 (doall (map (constantly 1) (pokemon.types/type-names))))
rlm@0 584
rlm@0 585 (defn all-neutral []
rlm@0 586 (doall (map (constantly 0) (pokemon.types/type-names))))
rlm@0 587
rlm@0 588 ;; objective functions
rlm@0 589 (defn number-of-types []
rlm@0 590 (doall (map (constantly 1) (pokemon.types/type-names))))
rlm@0 591
rlm@0 592 (defn set-constraints
rlm@0 593 "sets all the constraints for an lpsolve instance to the given
rlm@0 594 constraint. =constraint= here is one of the LpSolve constants such
rlm@0 595 as LpSolve/EQ."
rlm@0 596 [#^LpSolve lps constraint]
rlm@0 597 (dorun (map (fn [index] (.setConstrType lps index constraint))
rlm@0 598 ;; ONE based indexing!!!
rlm@0 599 (range 1 (inc (.getNrows lps))))))
rlm@0 600
rlm@0 601
rlm@0 602 (defn set-discrete
rlm@0 603 "sets every variable in an lps problem to be a discrete rather than
rlm@0 604 continuous variable"
rlm@0 605 [#^LpSolve lps]
rlm@0 606 (dorun (map (fn [index] (.setInt lps index true))
rlm@0 607 ;; ONE based indexing!!!
rlm@0 608 (range 1 (inc (.getNcolumns lps))))))
rlm@0 609
rlm@0 610 (defn set-variable-names
rlm@0 611 "sets the variable names of the problem given a vector of names"
rlm@0 612 [#^LpSolve lps names]
rlm@0 613 (dorun
rlm@16 614 (keep-indexed
rlm@16 615 (fn [index name]
rlm@16 616 (.setColName lps (inc index) (str name)))
rlm@16 617 ;; ONE based indexing!!!
rlm@16 618 names)))
rlm@0 619
rlm@0 620 (defn poke-solve
rlm@0 621 ([poke-matrix target objective-function constraint min-num-types]
rlm@0 622 ;; must have at least one type
rlm@0 623 (let [poke-matrix
rlm@0 624 (concat poke-matrix
rlm@0 625 [(map (constantly 1)
rlm@0 626 (range (count (first poke-matrix))))])
rlm@0 627 target (concat target [min-num-types])]
rlm@0 628 (lp-solve poke-matrix target objective-function
rlm@0 629 (set-constraints lps constraint)
rlm@0 630 ;; must have more than min-num-types
rlm@0 631 (.setConstrType lps (count target) LpSolve/GE)
rlm@0 632 (set-discrete lps)
rlm@0 633 (set-variable-names lps (pokemon.types/type-names))
rlm@0 634 (results lps))))
rlm@0 635 ([poke-matrix target objective-function constraint]
rlm@0 636 ;; at least one type
rlm@0 637 (poke-solve poke-matrix target objective-function constraint 1)))
rlm@0 638
rlm@0 639 (defn solution
rlm@0 640 "If the results of an lpsolve operation are feasible, returns the
rlm@0 641 results. Otherwise, returns the error."
rlm@0 642 [results]
rlm@0 643 (if (not (= (:status results) "OPTIMAL"))
rlm@0 644 (:status results)
rlm@0 645 (:solution results)))
rlm@0 646 #+end_src
rlm@0 647
rlm@0 648 With this, we are finally able to get some results.
rlm@0 649
rlm@0 650 ** Results
rlm@16 651 #+name: results
rlm@0 652 #+begin_src clojure :results silent
rlm@0 653 (in-ns 'pokemon.lpsolve)
rlm@0 654
rlm@0 655 (defn best-defense-type
rlm@0 656 "finds a type combination which is resistant to all attacks."
rlm@0 657 []
rlm@0 658 (poke-solve
rlm@0 659 (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))
rlm@0 660
rlm@0 661 (defn worst-attack-type
rlm@0 662 "finds the attack type which is not-very-effective against all pure
rlm@0 663 defending types (each single defending type is resistant to this
rlm@0 664 attack combination"
rlm@0 665 []
rlm@0 666 (poke-solve
rlm@0 667 (log-attack-matrix) (all-resistant) (number-of-types) LpSolve/LE))
rlm@0 668
rlm@0 669 (defn worst-defense-type
rlm@0 670 "finds a defending type that is weak to all single attacking types."
rlm@0 671 []
rlm@0 672 (poke-solve
rlm@0 673 (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0 674
rlm@0 675 (defn best-attack-type
rlm@0 676 "finds an attack type which is super effective against all single
rlm@0 677 defending types"
rlm@0 678 []
rlm@0 679 (poke-solve
rlm@0 680 (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0 681
rlm@0 682 (defn solid-defense-type
rlm@0 683 "finds a defense type which is either neutral or resistant to all
rlm@0 684 single attacking types"
rlm@0 685 []
rlm@0 686 (poke-solve
rlm@0 687 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))
rlm@0 688
rlm@0 689 (defn solid-attack-type
rlm@0 690 "finds an attack type which is either neutral or super-effective to
rlm@0 691 all single attacking types."
rlm@0 692 []
rlm@0 693 (poke-solve
rlm@0 694 (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0 695
rlm@0 696 (defn weak-defense-type
rlm@0 697 "finds a defense type which is either neutral or weak to all single
rlm@0 698 attacking types"
rlm@0 699 []
rlm@0 700 (poke-solve
rlm@0 701 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0 702
rlm@0 703 (defn neutral-defense-type
rlm@0 704 "finds a defense type which is perfectly neutral to all attacking
rlm@0 705 types."
rlm@0 706 []
rlm@0 707 (poke-solve
rlm@0 708 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))
rlm@0 709
rlm@0 710 #+end_src
rlm@0 711
rlm@0 712 *** Strongest Attack/Defense Combinations
rlm@0 713
rlm@0 714 #+begin_src clojure :results output :exports both
rlm@0 715 (clojure.pprint/pprint
rlm@0 716 (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))
rlm@0 717 #+end_src
rlm@0 718
rlm@0 719 #+results:
rlm@0 720 #+begin_example
rlm@0 721 {":normal" 0.0,
rlm@0 722 ":ground" 1.0,
rlm@0 723 ":poison" 2.0,
rlm@0 724 ":flying" 1.0,
rlm@0 725 ":fighting" 0.0,
rlm@0 726 ":dragon" 0.0,
rlm@0 727 ":fire" 0.0,
rlm@0 728 ":dark" 1.0,
rlm@0 729 ":ice" 0.0,
rlm@0 730 ":steel" 1.0,
rlm@0 731 ":ghost" 0.0,
rlm@0 732 ":electric" 0.0,
rlm@0 733 ":bug" 0.0,
rlm@0 734 ":psychic" 0.0,
rlm@0 735 ":grass" 0.0,
rlm@0 736 ":water" 2.0,
rlm@0 737 ":rock" 0.0}
rlm@0 738 #+end_example
rlm@0 739
rlm@0 740 # #+results-old:
rlm@0 741 # : [[":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]]
rlm@0 742
rlm@0 743
rlm@0 744 This is the immortal type combination we've been looking for. By
rlm@0 745 combining Steel, Water, Poison, and three types which each have complete
rlm@0 746 immunities to various other types, we've created a type that is resistant to
rlm@0 747 all attacking types.
rlm@0 748
rlm@0 749 #+begin_src clojure :results output :exports both
rlm@0 750 (clojure.pprint/pprint
rlm@0 751 (pokemon.types/susceptibility
rlm@0 752 [:poison :poison :water :water :steel :ground :flying :dark]))
rlm@0 753 #+end_src
rlm@0 754
rlm@0 755 #+results:
rlm@0 756 #+begin_example
rlm@0 757 {:water 1/2,
rlm@0 758 :psychic 0,
rlm@0 759 :dragon 1/2,
rlm@0 760 :fire 1/2,
rlm@0 761 :ice 1/2,
rlm@0 762 :grass 1/2,
rlm@0 763 :ghost 1/4,
rlm@0 764 :poison 0,
rlm@0 765 :flying 1/2,
rlm@0 766 :normal 1/2,
rlm@0 767 :rock 1/2,
rlm@0 768 :electric 0,
rlm@0 769 :ground 0,
rlm@0 770 :fighting 1/2,
rlm@0 771 :dark 1/4,
rlm@0 772 :steel 1/8,
rlm@0 773 :bug 1/8}
rlm@0 774 #+end_example
rlm@0 775
rlm@0 776 # #+results-old:
rlm@0 777 # : {: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}
rlm@0 778
rlm@0 779
rlm@0 780 Cool!
rlm@0 781
rlm@0 782 #+begin_src clojure :results output :exports both
rlm@0 783 (clojure.pprint/pprint
rlm@0 784 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))
rlm@0 785 #+end_src
rlm@0 786
rlm@0 787 #+results:
rlm@0 788 #+begin_example
rlm@0 789 {":normal" 0.0,
rlm@0 790 ":ground" 0.0,
rlm@0 791 ":poison" 0.0,
rlm@0 792 ":flying" 0.0,
rlm@0 793 ":fighting" 0.0,
rlm@0 794 ":dragon" 0.0,
rlm@0 795 ":fire" 0.0,
rlm@0 796 ":dark" 1.0,
rlm@0 797 ":ice" 0.0,
rlm@0 798 ":steel" 0.0,
rlm@0 799 ":ghost" 1.0,
rlm@0 800 ":electric" 0.0,
rlm@0 801 ":bug" 0.0,
rlm@0 802 ":psychic" 0.0,
rlm@0 803 ":grass" 0.0,
rlm@0 804 ":water" 0.0,
rlm@0 805 ":rock" 0.0}
rlm@0 806 #+end_example
rlm@0 807
rlm@0 808 Dark and Ghost are the best dual-type combo, and are resistant or
rlm@0 809 neutral to all types.
rlm@0 810
rlm@0 811 #+begin_src clojure :results output :exports both
rlm@0 812 (clojure.pprint/pprint
rlm@0 813 (pokemon.types/old-school
rlm@0 814 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))
rlm@0 815 #+end_src
rlm@0 816
rlm@0 817 #+results:
rlm@0 818 #+begin_example
rlm@0 819 {":normal" 0.0,
rlm@0 820 ":ground" 0.0,
rlm@0 821 ":poison" 0.0,
rlm@0 822 ":flying" 0.0,
rlm@0 823 ":fighting" 0.0,
rlm@0 824 ":dragon" 0.0,
rlm@0 825 ":fire" 0.0,
rlm@0 826 ":ice" 0.0,
rlm@0 827 ":ghost" 1.0,
rlm@0 828 ":electric" 0.0,
rlm@0 829 ":bug" 0.0,
rlm@0 830 ":psychic" 1.0,
rlm@0 831 ":grass" 0.0,
rlm@0 832 ":water" 0.0,
rlm@0 833 ":rock" 0.0}
rlm@0 834 #+end_example
rlm@0 835
rlm@0 836 Ghost and Psychic are a powerful dual type combo in the original games,
rlm@0 837 due to a glitch which made Psychic immune to Ghost type attacks, even
rlm@14 838 though the game claims that Ghost is strong against Psychic.
rlm@0 839
rlm@0 840 #+begin_src clojure :results verbatim :exports both
rlm@0 841 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))
rlm@0 842 #+end_src
rlm@0 843
rlm@0 844 #+results:
rlm@0 845 : INFEASIBLE
rlm@0 846
rlm@0 847 #+begin_src clojure :results verbatim :exports both
rlm@0 848 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))
rlm@0 849 #+end_src
rlm@0 850
rlm@0 851 #+results:
rlm@0 852 : INFEASIBLE
rlm@0 853
rlm@0 854
rlm@0 855 #+begin_src clojure :results verbatim :exports both
rlm@0 856 (pokemon.types/old-school
rlm@0 857 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))
rlm@0 858 #+end_src
rlm@0 859
rlm@0 860 #+results:
rlm@0 861 : INFEASIBLE
rlm@0 862
rlm@0 863
rlm@0 864 #+begin_src clojure :results output :exports both
rlm@0 865 (clojure.pprint/pprint
rlm@0 866 (pokemon.types/old-school
rlm@0 867 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))
rlm@0 868 #+end_src
rlm@0 869
rlm@0 870 #+results:
rlm@0 871 #+begin_example
rlm@0 872 {":normal" 0.0,
rlm@0 873 ":ground" 0.0,
rlm@0 874 ":poison" 0.0,
rlm@0 875 ":flying" 0.0,
rlm@0 876 ":fighting" 0.0,
rlm@0 877 ":dragon" 1.0,
rlm@0 878 ":fire" 0.0,
rlm@0 879 ":ice" 0.0,
rlm@0 880 ":ghost" 0.0,
rlm@0 881 ":electric" 0.0,
rlm@0 882 ":bug" 0.0,
rlm@0 883 ":psychic" 0.0,
rlm@0 884 ":grass" 0.0,
rlm@0 885 ":water" 0.0,
rlm@0 886 ":rock" 0.0}
rlm@0 887 #+end_example
rlm@0 888
rlm@11 889 The best attacking type combination is Dragon from the original games.
rlm@11 890 It is neutral against all the original types except for Dragon, which
rlm@11 891 it is strong against. There is no way to make an attacking type that
rlm@11 892 is strong against every type, or even one that is strong or neutral
rlm@11 893 against every type, in the new games.
rlm@0 894
rlm@0 895
rlm@0 896 *** Weakest Attack/Defense Combinations
rlm@0 897
rlm@0 898 #+begin_src clojure :results output :exports both
rlm@0 899 (clojure.pprint/pprint
rlm@0 900 (pokemon.types/old-school
rlm@0 901 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))
rlm@0 902 #+end_src
rlm@0 903
rlm@0 904 #+results:
rlm@0 905 #+begin_example
rlm@0 906 {":normal" 5.0,
rlm@0 907 ":ground" 0.0,
rlm@0 908 ":poison" 0.0,
rlm@0 909 ":flying" 0.0,
rlm@0 910 ":fighting" 0.0,
rlm@0 911 ":dragon" 0.0,
rlm@0 912 ":fire" 1.0,
rlm@0 913 ":ice" 2.0,
rlm@0 914 ":ghost" 1.0,
rlm@0 915 ":electric" 1.0,
rlm@0 916 ":bug" 1.0,
rlm@0 917 ":psychic" 0.0,
rlm@0 918 ":grass" 3.0,
rlm@0 919 ":water" 2.0,
rlm@0 920 ":rock" 0.0}
rlm@0 921 #+end_example
rlm@0 922
rlm@0 923 # #+results-old:
rlm@0 924 # : [[":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]]
rlm@0 925
rlm@0 926 #+begin_src clojure :results output :exports both
rlm@0 927 (clojure.pprint/pprint
rlm@0 928 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))
rlm@0 929 #+end_src
rlm@0 930
rlm@0 931 #+results:
rlm@0 932 #+begin_example
rlm@0 933 {":normal" 4.0,
rlm@0 934 ":ground" 1.0,
rlm@0 935 ":poison" 1.0,
rlm@0 936 ":flying" 0.0,
rlm@0 937 ":fighting" 1.0,
rlm@0 938 ":dragon" 0.0,
rlm@0 939 ":fire" 0.0,
rlm@0 940 ":dark" 0.0,
rlm@0 941 ":ice" 4.0,
rlm@0 942 ":steel" 0.0,
rlm@0 943 ":ghost" 1.0,
rlm@0 944 ":electric" 3.0,
rlm@0 945 ":bug" 0.0,
rlm@0 946 ":psychic" 1.0,
rlm@0 947 ":grass" 1.0,
rlm@0 948 ":water" 1.0,
rlm@0 949 ":rock" 2.0}
rlm@0 950 #+end_example
rlm@0 951
rlm@0 952 # #+results-old:
rlm@0 953 # : [[":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]]
rlm@0 954
rlm@0 955
rlm@0 956 This is an extremely interesting type combination, in that it uses
rlm@0 957 quite a few types.
rlm@0 958
rlm@0 959 #+begin_src clojure :results verbatim :exports both
rlm@0 960 (reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))
rlm@0 961 #+end_src
rlm@0 962
rlm@0 963 #+results:
rlm@0 964 : 20.0
rlm@0 965
rlm@0 966 20 types is the /minimum/ number of types before the attacking
rlm@0 967 combination is not-very-effective or worse against all defending
rlm@0 968 types. This would probably have been impossible to discover using
rlm@0 969 best-first search, since it involves such an intricate type
rlm@0 970 combination.
rlm@0 971
rlm@0 972 It's so interesting that it takes 20 types to make an attack type that
rlm@11 973 is weak to all types that the combination merits further
rlm@11 974 investigation.
rlm@0 975
rlm@0 976 Unfortunately, all of the tools that we've written so far are focused
rlm@0 977 on defense type combinations. However, it is possible to make every
rlm@0 978 tool attack-oriented via a simple macro.
rlm@0 979
rlm@16 980 #+name: attack-oriented
rlm@0 981 #+begin_src clojure :results silent
rlm@0 982 (in-ns 'pokemon.lpsolve)
rlm@0 983
rlm@0 984 (defmacro attack-mode [& forms]
rlm@0 985 `(let [attack-strengths# pokemon.types/attack-strengths
rlm@0 986 defense-strengths# pokemon.types/defense-strengths]
rlm@0 987 (binding [pokemon.types/attack-strengths
rlm@0 988 defense-strengths#
rlm@0 989 pokemon.types/defense-strengths
rlm@0 990 attack-strengths#]
rlm@0 991 ~@forms)))
rlm@0 992 #+end_src
rlm@0 993
rlm@0 994 Now all the tools from =pokemon.types= will work for attack
rlm@0 995 combinations.
rlm@0 996
rlm@0 997 #+begin_src clojure :results output :exports both
rlm@0 998 (clojure.pprint/pprint
rlm@0 999 (pokemon.types/susceptibility [:water]))
rlm@0 1000 #+end_src
rlm@0 1001
rlm@0 1002 #+results:
rlm@0 1003 #+begin_example
rlm@0 1004 {:water 1/2,
rlm@0 1005 :psychic 1,
rlm@0 1006 :dragon 1,
rlm@0 1007 :fire 1/2,
rlm@0 1008 :ice 1/2,
rlm@0 1009 :grass 2,
rlm@0 1010 :ghost 1,
rlm@0 1011 :poison 1,
rlm@0 1012 :flying 1,
rlm@0 1013 :normal 1,
rlm@0 1014 :rock 1,
rlm@0 1015 :electric 2,
rlm@0 1016 :ground 1,
rlm@0 1017 :fighting 1,
rlm@0 1018 :dark 1,
rlm@0 1019 :steel 1/2,
rlm@0 1020 :bug 1}
rlm@0 1021 #+end_example
rlm@0 1022
rlm@0 1023
rlm@0 1024 #+begin_src clojure :results output :exports both
rlm@0 1025 (clojure.pprint/pprint
rlm@0 1026 (pokemon.lpsolve/attack-mode
rlm@0 1027 (pokemon.types/susceptibility [:water])))
rlm@0 1028 #+end_src
rlm@0 1029
rlm@0 1030 #+results:
rlm@0 1031 #+begin_example
rlm@0 1032 {:water 1/2,
rlm@0 1033 :psychic 1,
rlm@0 1034 :dragon 1/2,
rlm@0 1035 :fire 2,
rlm@0 1036 :ice 1,
rlm@0 1037 :grass 1/2,
rlm@0 1038 :ghost 1,
rlm@0 1039 :poison 1,
rlm@0 1040 :flying 1,
rlm@0 1041 :normal 1,
rlm@0 1042 :rock 2,
rlm@0 1043 :electric 1,
rlm@0 1044 :ground 2,
rlm@0 1045 :fighting 1,
rlm@0 1046 :dark 1,
rlm@0 1047 :steel 1,
rlm@0 1048 :bug 1}
rlm@0 1049 #+end_example
rlm@0 1050
rlm@0 1051 Now =pokemon.types/susceptibility= reports the /attack-type/
rlm@0 1052 combination's effectiveness against other types.
rlm@0 1053
rlm@0 1054 The 20 type combo achieves its goal in a very clever way.
rlm@0 1055
rlm@0 1056 First, it weakens its effectiveness to other types at the expense of
rlm@0 1057 making it very strong against flying.
rlm@0 1058
rlm@0 1059 #+begin_src clojure :results output :exports both
rlm@0 1060 (clojure.pprint/pprint
rlm@0 1061 (pokemon.lpsolve/attack-mode
rlm@0 1062 (pokemon.types/susceptibility
rlm@0 1063 [:normal :normal :normal :normal
rlm@0 1064 :ice :ice :ice :ice
rlm@0 1065 :electric :electric :electric
rlm@0 1066 :rock :rock])))
rlm@0 1067 #+end_src
rlm@0 1068
rlm@0 1069 #+results:
rlm@0 1070 #+begin_example
rlm@0 1071 {:water 1/2,
rlm@0 1072 :psychic 1,
rlm@0 1073 :dragon 2,
rlm@0 1074 :fire 1/4,
rlm@0 1075 :ice 1/4,
rlm@0 1076 :grass 2,
rlm@0 1077 :ghost 0,
rlm@0 1078 :poison 1,
rlm@0 1079 :flying 512,
rlm@0 1080 :normal 1,
rlm@0 1081 :rock 1/16,
rlm@0 1082 :electric 1/8,
rlm@0 1083 :ground 0,
rlm@0 1084 :fighting 1/4,
rlm@0 1085 :dark 1,
rlm@0 1086 :steel 1/1024,
rlm@0 1087 :bug 4}
rlm@0 1088 #+end_example
rlm@0 1089
rlm@0 1090 Then, it removes it's strengths against Flying, Normal, and Fighting
rlm@0 1091 by adding Ghost and Ground.
rlm@0 1092
rlm@0 1093 #+begin_src clojure :results output :exports both
rlm@0 1094 (clojure.pprint/pprint
rlm@0 1095 (pokemon.lpsolve/attack-mode
rlm@0 1096 (pokemon.types/susceptibility
rlm@0 1097 [:normal :normal :normal :normal
rlm@0 1098 :ice :ice :ice :ice
rlm@0 1099 :electric :electric :electric
rlm@0 1100 :rock :rock
rlm@0 1101 ;; Spot resistances
rlm@0 1102 :ghost :ground])))
rlm@0 1103 #+end_src
rlm@0 1104
rlm@0 1105 #+results:
rlm@0 1106 #+begin_example
rlm@0 1107 {:water 1/2,
rlm@0 1108 :psychic 2,
rlm@0 1109 :dragon 2,
rlm@0 1110 :fire 1/2,
rlm@0 1111 :ice 1/4,
rlm@0 1112 :grass 1,
rlm@0 1113 :ghost 0,
rlm@0 1114 :poison 2,
rlm@0 1115 :flying 0,
rlm@0 1116 :normal 0,
rlm@0 1117 :rock 1/8,
rlm@0 1118 :electric 1/4,
rlm@0 1119 :ground 0,
rlm@0 1120 :fighting 1/4,
rlm@0 1121 :dark 1/2,
rlm@0 1122 :steel 1/1024,
rlm@0 1123 :bug 2}
rlm@0 1124 #+end_example
rlm@0 1125
rlm@0 1126 Adding the pair Psychic and Fighting takes care of its strength
rlm@0 1127 against Psychic and makes it ineffective against Dark, which is immune
rlm@0 1128 to Psychic.
rlm@0 1129
rlm@0 1130 Adding the pair Grass and Poison makes takes care of its strength
rlm@0 1131 against poison and makes it ineffective against Steel, which is immune
rlm@0 1132 to poison.
rlm@0 1133
rlm@0 1134 #+begin_src clojure :results output :exports both
rlm@0 1135 (clojure.pprint/pprint
rlm@0 1136 (pokemon.lpsolve/attack-mode
rlm@0 1137 (pokemon.types/susceptibility
rlm@0 1138 [;; setup
rlm@0 1139 :normal :normal :normal :normal
rlm@0 1140 :ice :ice :ice :ice
rlm@0 1141 :electric :electric :electric
rlm@0 1142 :rock :rock
rlm@0 1143 ;; Spot resistances
rlm@0 1144 :ghost :ground
rlm@0 1145 ;; Pair resistances
rlm@0 1146 :psychic :fighting
rlm@0 1147 :grass :poison])))
rlm@0 1148 #+end_src
rlm@0 1149
rlm@0 1150 #+results:
rlm@0 1151 #+begin_example
rlm@0 1152 {:water 1,
rlm@0 1153 :psychic 1/2,
rlm@0 1154 :dragon 1,
rlm@0 1155 :fire 1/4,
rlm@0 1156 :ice 1/2,
rlm@0 1157 :grass 1,
rlm@0 1158 :ghost 0,
rlm@0 1159 :poison 1/2,
rlm@0 1160 :flying 0,
rlm@0 1161 :normal 0,
rlm@0 1162 :rock 1/4,
rlm@0 1163 :electric 1/4,
rlm@0 1164 :ground 0,
rlm@0 1165 :fighting 1/2,
rlm@0 1166 :dark 0,
rlm@0 1167 :steel 0,
rlm@0 1168 :bug 1/2}
rlm@0 1169 #+end_example
rlm@0 1170
rlm@0 1171 Can you see the final step?
rlm@0 1172
rlm@13 1173 It's adding the Water type, which is weak against Water, Dragon, and
rlm@13 1174 Grass and strong against Rock and Fire.
rlm@0 1175
rlm@0 1176 #+begin_src clojure :results output :exports both
rlm@0 1177 (clojure.pprint/pprint
rlm@0 1178 (pokemon.lpsolve/attack-mode
rlm@0 1179 (pokemon.types/susceptibility
rlm@0 1180 [;; setup
rlm@0 1181 :normal :normal :normal :normal
rlm@0 1182 :ice :ice :ice :ice
rlm@0 1183 :electric :electric :electric
rlm@0 1184 :rock :rock
rlm@0 1185 ;; Spot resistances
rlm@0 1186 :ghost :ground
rlm@0 1187 ;; Pair resistances
rlm@0 1188 :psychic :fighting
rlm@0 1189 :grass :poison
rlm@0 1190 ;; completion
rlm@0 1191 :water])))
rlm@0 1192 #+end_src
rlm@0 1193
rlm@0 1194 #+results:
rlm@0 1195 #+begin_example
rlm@0 1196 {:water 1/2,
rlm@0 1197 :psychic 1/2,
rlm@0 1198 :dragon 1/2,
rlm@0 1199 :fire 1/2,
rlm@0 1200 :ice 1/2,
rlm@0 1201 :grass 1/2,
rlm@0 1202 :ghost 0,
rlm@0 1203 :poison 1/2,
rlm@0 1204 :flying 0,
rlm@0 1205 :normal 0,
rlm@0 1206 :rock 1/2,
rlm@0 1207 :electric 1/4,
rlm@0 1208 :ground 0,
rlm@0 1209 :fighting 1/2,
rlm@0 1210 :dark 0,
rlm@0 1211 :steel 0,
rlm@0 1212 :bug 1/2}
rlm@0 1213 #+end_example
rlm@0 1214
rlm@0 1215 Which makes a particularly beautiful combination which is ineffective
rlm@0 1216 against all defending types.
rlm@0 1217
rlm@0 1218
rlm@0 1219 # #+begin_src clojure :results scalar :exports both
rlm@0 1220 # (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])))))
rlm@0 1221 # #+end_src
rlm@0 1222
rlm@0 1223 # #+results:
rlm@0 1224 # | [: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] |
rlm@0 1225
rlm@0 1226
rlm@0 1227 Is there anything else that's interesting?
rlm@0 1228
rlm@0 1229 #+begin_src clojure :exports both
rlm@0 1230 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))
rlm@0 1231 #+end_src
rlm@0 1232
rlm@0 1233 #+results:
rlm@0 1234 : INFEASIBLE
rlm@0 1235
rlm@0 1236 #+begin_src clojure :exports both
rlm@0 1237 (pokemon.types/old-school
rlm@0 1238 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))
rlm@0 1239 #+end_src
rlm@0 1240
rlm@0 1241 #+results:
rlm@0 1242 : INFEASIBLE
rlm@0 1243
rlm@0 1244 #+begin_src clojure :exports both
rlm@0 1245 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))
rlm@0 1246 #+end_src
rlm@0 1247
rlm@0 1248 #+results:
rlm@0 1249 : INFEASIBLE
rlm@0 1250
rlm@0 1251 #+begin_src clojure :exports both
rlm@0 1252 (pokemon.types/old-school
rlm@0 1253 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))
rlm@0 1254 #+end_src
rlm@0 1255
rlm@0 1256 #+results:
rlm@0 1257 : INFEASIBLE
rlm@0 1258
rlm@0 1259 #+begin_src clojure :exports both
rlm@0 1260 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))
rlm@0 1261 #+end_src
rlm@0 1262
rlm@0 1263 #+results:
rlm@0 1264 : INFEASIBLE
rlm@0 1265
rlm@0 1266 #+begin_src clojure :exports both
rlm@0 1267 (pokemon.types/old-school
rlm@0 1268 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))
rlm@0 1269 #+end_src
rlm@0 1270
rlm@0 1271 #+results:
rlm@0 1272 : INFEASIBLE
rlm@0 1273
rlm@0 1274 There is no way to produce a defense-type that is weak to all types.
rlm@0 1275 This is probably because there are many types that are completely
rlm@0 1276 immune to some types, such as Flying, which is immune to Ground. A
rlm@0 1277 perfectly weak type could not use any of these types.
rlm@0 1278
rlm@0 1279 * Summary
rlm@0 1280
rlm@14 1281 Overall, the pok\eacute{}mon type system is slanted towards defense
rlm@14 1282 rather than offense. While it is possible to create superior
rlm@11 1283 defensive types and exceptionally weak attack types, it is not
rlm@11 1284 possible to create exceptionally weak defensive types or very powerful
rlm@11 1285 attack types.
rlm@0 1286
rlm@0 1287 Using the =lp_solve= library was more complicated than the best-first
rlm@0 1288 search, but yielded results quickly and efficiently. Expressing the
rlm@0 1289 problem in a linear form does have its drawbacks, however --- it's
rlm@0 1290 hard to ask questions such as "what is the best 3-type defensive combo
rlm@0 1291 in terms of susceptibility?", since susceptibility is not a linear
rlm@0 1292 function of a combo's types. It is also hard to get all the solutions
rlm@0 1293 to a particular problem, such as all the pokemon type combinations of
rlm@0 1294 length 8 which are immortal defense types.
rlm@0 1295
rlm@0 1296 * COMMENT main-program
rlm@0 1297 #+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none
rlm@0 1298 <<intro>>
rlm@0 1299 <<body>>
rlm@0 1300 <<declares>>
rlm@0 1301 <<memory-management>>
rlm@0 1302 <<get-results>>
rlm@0 1303 <<solve>>
rlm@0 1304 <<farmer-example>>
rlm@0 1305 <<lp-solve>>
rlm@0 1306 <<better-farmer>>
rlm@0 1307 <<pokemon-lp>>
rlm@0 1308 <<results>>
rlm@0 1309 <<attack-oriented>>
rlm@0 1310 #+end_src
rlm@0 1311
rlm@0 1312
rlm@0 1313