annotate org/lpsolve.org @ 20:47fa6dc56e30

remove incanter filth.
author Robert McIntyre <rlm@mit.edu>
date Sun, 10 Mar 2013 19:17:47 +0000
parents 2bec94944460
children f88b7d2c25d9
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@20 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@18 424 [#^lpsolve.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@20 564 (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %)
rlm@20 565 (map #(/ (Math/log %) (Math/log 2)) row)))
rlm@20 566 (apply mapv vector ;; transpose
rlm@20 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@20 576 (apply mapv vector (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 (defn set-discrete
rlm@0 602 "sets every variable in an lps problem to be a discrete rather than
rlm@0 603 continuous variable"
rlm@0 604 [#^LpSolve lps]
rlm@0 605 (dorun (map (fn [index] (.setInt lps index true))
rlm@0 606 ;; ONE based indexing!!!
rlm@0 607 (range 1 (inc (.getNcolumns lps))))))
rlm@0 608
rlm@0 609 (defn set-variable-names
rlm@0 610 "sets the variable names of the problem given a vector of names"
rlm@0 611 [#^LpSolve lps names]
rlm@0 612 (dorun
rlm@16 613 (keep-indexed
rlm@16 614 (fn [index name]
rlm@16 615 (.setColName lps (inc index) (str name)))
rlm@16 616 ;; ONE based indexing!!!
rlm@16 617 names)))
rlm@0 618
rlm@0 619 (defn poke-solve
rlm@0 620 ([poke-matrix target objective-function constraint min-num-types]
rlm@0 621 ;; must have at least one type
rlm@0 622 (let [poke-matrix
rlm@0 623 (concat poke-matrix
rlm@0 624 [(map (constantly 1)
rlm@0 625 (range (count (first poke-matrix))))])
rlm@0 626 target (concat target [min-num-types])]
rlm@0 627 (lp-solve poke-matrix target objective-function
rlm@0 628 (set-constraints lps constraint)
rlm@0 629 ;; must have more than min-num-types
rlm@0 630 (.setConstrType lps (count target) LpSolve/GE)
rlm@0 631 (set-discrete lps)
rlm@0 632 (set-variable-names lps (pokemon.types/type-names))
rlm@0 633 (results lps))))
rlm@0 634 ([poke-matrix target objective-function constraint]
rlm@0 635 ;; at least one type
rlm@0 636 (poke-solve poke-matrix target objective-function constraint 1)))
rlm@0 637
rlm@0 638 (defn solution
rlm@0 639 "If the results of an lpsolve operation are feasible, returns the
rlm@0 640 results. Otherwise, returns the error."
rlm@0 641 [results]
rlm@0 642 (if (not (= (:status results) "OPTIMAL"))
rlm@0 643 (:status results)
rlm@0 644 (:solution results)))
rlm@0 645 #+end_src
rlm@0 646
rlm@0 647 With this, we are finally able to get some results.
rlm@0 648
rlm@0 649 ** Results
rlm@16 650 #+name: results
rlm@0 651 #+begin_src clojure :results silent
rlm@0 652 (in-ns 'pokemon.lpsolve)
rlm@0 653
rlm@0 654 (defn best-defense-type
rlm@0 655 "finds a type combination which is resistant to all attacks."
rlm@0 656 []
rlm@0 657 (poke-solve
rlm@0 658 (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))
rlm@0 659
rlm@0 660 (defn worst-attack-type
rlm@0 661 "finds the attack type which is not-very-effective against all pure
rlm@0 662 defending types (each single defending type is resistant to this
rlm@0 663 attack combination"
rlm@0 664 []
rlm@0 665 (poke-solve
rlm@0 666 (log-attack-matrix) (all-resistant) (number-of-types) LpSolve/LE))
rlm@0 667
rlm@0 668 (defn worst-defense-type
rlm@0 669 "finds a defending type that is weak to all single attacking types."
rlm@0 670 []
rlm@0 671 (poke-solve
rlm@0 672 (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0 673
rlm@0 674 (defn best-attack-type
rlm@0 675 "finds an attack type which is super effective against all single
rlm@0 676 defending types"
rlm@0 677 []
rlm@0 678 (poke-solve
rlm@0 679 (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))
rlm@0 680
rlm@0 681 (defn solid-defense-type
rlm@0 682 "finds a defense type which is either neutral or resistant to all
rlm@0 683 single attacking types"
rlm@0 684 []
rlm@0 685 (poke-solve
rlm@0 686 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))
rlm@0 687
rlm@0 688 (defn solid-attack-type
rlm@0 689 "finds an attack type which is either neutral or super-effective to
rlm@0 690 all single attacking types."
rlm@0 691 []
rlm@0 692 (poke-solve
rlm@0 693 (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0 694
rlm@0 695 (defn weak-defense-type
rlm@0 696 "finds a defense type which is either neutral or weak to all single
rlm@0 697 attacking types"
rlm@0 698 []
rlm@0 699 (poke-solve
rlm@0 700 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))
rlm@0 701
rlm@0 702 (defn neutral-defense-type
rlm@0 703 "finds a defense type which is perfectly neutral to all attacking
rlm@0 704 types."
rlm@0 705 []
rlm@0 706 (poke-solve
rlm@0 707 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))
rlm@0 708
rlm@0 709 #+end_src
rlm@0 710
rlm@0 711 *** Strongest Attack/Defense Combinations
rlm@0 712
rlm@0 713 #+begin_src clojure :results output :exports both
rlm@0 714 (clojure.pprint/pprint
rlm@0 715 (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))
rlm@0 716 #+end_src
rlm@0 717
rlm@0 718 #+results:
rlm@0 719 #+begin_example
rlm@0 720 {":normal" 0.0,
rlm@0 721 ":ground" 1.0,
rlm@0 722 ":poison" 2.0,
rlm@0 723 ":flying" 1.0,
rlm@0 724 ":fighting" 0.0,
rlm@0 725 ":dragon" 0.0,
rlm@0 726 ":fire" 0.0,
rlm@0 727 ":dark" 1.0,
rlm@0 728 ":ice" 0.0,
rlm@0 729 ":steel" 1.0,
rlm@0 730 ":ghost" 0.0,
rlm@0 731 ":electric" 0.0,
rlm@0 732 ":bug" 0.0,
rlm@0 733 ":psychic" 0.0,
rlm@0 734 ":grass" 0.0,
rlm@0 735 ":water" 2.0,
rlm@0 736 ":rock" 0.0}
rlm@0 737 #+end_example
rlm@0 738
rlm@0 739 # #+results-old:
rlm@0 740 # : [[":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 741
rlm@0 742
rlm@0 743 This is the immortal type combination we've been looking for. By
rlm@0 744 combining Steel, Water, Poison, and three types which each have complete
rlm@0 745 immunities to various other types, we've created a type that is resistant to
rlm@0 746 all attacking types.
rlm@0 747
rlm@0 748 #+begin_src clojure :results output :exports both
rlm@0 749 (clojure.pprint/pprint
rlm@0 750 (pokemon.types/susceptibility
rlm@0 751 [:poison :poison :water :water :steel :ground :flying :dark]))
rlm@0 752 #+end_src
rlm@0 753
rlm@0 754 #+results:
rlm@0 755 #+begin_example
rlm@0 756 {:water 1/2,
rlm@0 757 :psychic 0,
rlm@0 758 :dragon 1/2,
rlm@0 759 :fire 1/2,
rlm@0 760 :ice 1/2,
rlm@0 761 :grass 1/2,
rlm@0 762 :ghost 1/4,
rlm@0 763 :poison 0,
rlm@0 764 :flying 1/2,
rlm@0 765 :normal 1/2,
rlm@0 766 :rock 1/2,
rlm@0 767 :electric 0,
rlm@0 768 :ground 0,
rlm@0 769 :fighting 1/2,
rlm@0 770 :dark 1/4,
rlm@0 771 :steel 1/8,
rlm@0 772 :bug 1/8}
rlm@0 773 #+end_example
rlm@0 774
rlm@0 775 # #+results-old:
rlm@0 776 # : {: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 777
rlm@0 778
rlm@0 779 Cool!
rlm@0 780
rlm@0 781 #+begin_src clojure :results output :exports both
rlm@0 782 (clojure.pprint/pprint
rlm@0 783 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))
rlm@0 784 #+end_src
rlm@0 785
rlm@0 786 #+results:
rlm@0 787 #+begin_example
rlm@0 788 {":normal" 0.0,
rlm@0 789 ":ground" 0.0,
rlm@0 790 ":poison" 0.0,
rlm@0 791 ":flying" 0.0,
rlm@0 792 ":fighting" 0.0,
rlm@0 793 ":dragon" 0.0,
rlm@0 794 ":fire" 0.0,
rlm@0 795 ":dark" 1.0,
rlm@0 796 ":ice" 0.0,
rlm@0 797 ":steel" 0.0,
rlm@0 798 ":ghost" 1.0,
rlm@0 799 ":electric" 0.0,
rlm@0 800 ":bug" 0.0,
rlm@0 801 ":psychic" 0.0,
rlm@0 802 ":grass" 0.0,
rlm@0 803 ":water" 0.0,
rlm@0 804 ":rock" 0.0}
rlm@0 805 #+end_example
rlm@0 806
rlm@0 807 Dark and Ghost are the best dual-type combo, and are resistant or
rlm@0 808 neutral to all types.
rlm@0 809
rlm@0 810 #+begin_src clojure :results output :exports both
rlm@0 811 (clojure.pprint/pprint
rlm@0 812 (pokemon.types/old-school
rlm@0 813 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))
rlm@0 814 #+end_src
rlm@0 815
rlm@0 816 #+results:
rlm@0 817 #+begin_example
rlm@0 818 {":normal" 0.0,
rlm@0 819 ":ground" 0.0,
rlm@0 820 ":poison" 0.0,
rlm@0 821 ":flying" 0.0,
rlm@0 822 ":fighting" 0.0,
rlm@0 823 ":dragon" 0.0,
rlm@0 824 ":fire" 0.0,
rlm@0 825 ":ice" 0.0,
rlm@0 826 ":ghost" 1.0,
rlm@0 827 ":electric" 0.0,
rlm@0 828 ":bug" 0.0,
rlm@0 829 ":psychic" 1.0,
rlm@0 830 ":grass" 0.0,
rlm@0 831 ":water" 0.0,
rlm@0 832 ":rock" 0.0}
rlm@0 833 #+end_example
rlm@0 834
rlm@0 835 Ghost and Psychic are a powerful dual type combo in the original games,
rlm@0 836 due to a glitch which made Psychic immune to Ghost type attacks, even
rlm@14 837 though the game claims that Ghost is strong against Psychic.
rlm@0 838
rlm@0 839 #+begin_src clojure :results verbatim :exports both
rlm@0 840 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))
rlm@0 841 #+end_src
rlm@0 842
rlm@0 843 #+results:
rlm@0 844 : INFEASIBLE
rlm@0 845
rlm@0 846 #+begin_src clojure :results verbatim :exports both
rlm@0 847 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))
rlm@0 848 #+end_src
rlm@0 849
rlm@0 850 #+results:
rlm@0 851 : INFEASIBLE
rlm@0 852
rlm@0 853
rlm@0 854 #+begin_src clojure :results verbatim :exports both
rlm@0 855 (pokemon.types/old-school
rlm@0 856 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))
rlm@0 857 #+end_src
rlm@0 858
rlm@0 859 #+results:
rlm@0 860 : INFEASIBLE
rlm@0 861
rlm@0 862
rlm@0 863 #+begin_src clojure :results output :exports both
rlm@0 864 (clojure.pprint/pprint
rlm@0 865 (pokemon.types/old-school
rlm@0 866 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))
rlm@0 867 #+end_src
rlm@0 868
rlm@0 869 #+results:
rlm@0 870 #+begin_example
rlm@0 871 {":normal" 0.0,
rlm@0 872 ":ground" 0.0,
rlm@0 873 ":poison" 0.0,
rlm@0 874 ":flying" 0.0,
rlm@0 875 ":fighting" 0.0,
rlm@0 876 ":dragon" 1.0,
rlm@0 877 ":fire" 0.0,
rlm@0 878 ":ice" 0.0,
rlm@0 879 ":ghost" 0.0,
rlm@0 880 ":electric" 0.0,
rlm@0 881 ":bug" 0.0,
rlm@0 882 ":psychic" 0.0,
rlm@0 883 ":grass" 0.0,
rlm@0 884 ":water" 0.0,
rlm@0 885 ":rock" 0.0}
rlm@0 886 #+end_example
rlm@0 887
rlm@11 888 The best attacking type combination is Dragon from the original games.
rlm@11 889 It is neutral against all the original types except for Dragon, which
rlm@11 890 it is strong against. There is no way to make an attacking type that
rlm@11 891 is strong against every type, or even one that is strong or neutral
rlm@11 892 against every type, in the new games.
rlm@0 893
rlm@0 894
rlm@0 895 *** Weakest Attack/Defense Combinations
rlm@0 896
rlm@0 897 #+begin_src clojure :results output :exports both
rlm@0 898 (clojure.pprint/pprint
rlm@0 899 (pokemon.types/old-school
rlm@0 900 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))
rlm@0 901 #+end_src
rlm@0 902
rlm@0 903 #+results:
rlm@0 904 #+begin_example
rlm@0 905 {":normal" 5.0,
rlm@0 906 ":ground" 0.0,
rlm@0 907 ":poison" 0.0,
rlm@0 908 ":flying" 0.0,
rlm@0 909 ":fighting" 0.0,
rlm@0 910 ":dragon" 0.0,
rlm@0 911 ":fire" 1.0,
rlm@0 912 ":ice" 2.0,
rlm@0 913 ":ghost" 1.0,
rlm@0 914 ":electric" 1.0,
rlm@0 915 ":bug" 1.0,
rlm@0 916 ":psychic" 0.0,
rlm@0 917 ":grass" 3.0,
rlm@0 918 ":water" 2.0,
rlm@0 919 ":rock" 0.0}
rlm@0 920 #+end_example
rlm@0 921
rlm@0 922 # #+results-old:
rlm@0 923 # : [[":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 924
rlm@0 925 #+begin_src clojure :results output :exports both
rlm@0 926 (clojure.pprint/pprint
rlm@0 927 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))
rlm@0 928 #+end_src
rlm@0 929
rlm@0 930 #+results:
rlm@0 931 #+begin_example
rlm@0 932 {":normal" 4.0,
rlm@0 933 ":ground" 1.0,
rlm@0 934 ":poison" 1.0,
rlm@0 935 ":flying" 0.0,
rlm@0 936 ":fighting" 1.0,
rlm@0 937 ":dragon" 0.0,
rlm@0 938 ":fire" 0.0,
rlm@0 939 ":dark" 0.0,
rlm@0 940 ":ice" 4.0,
rlm@0 941 ":steel" 0.0,
rlm@0 942 ":ghost" 1.0,
rlm@0 943 ":electric" 3.0,
rlm@0 944 ":bug" 0.0,
rlm@0 945 ":psychic" 1.0,
rlm@0 946 ":grass" 1.0,
rlm@0 947 ":water" 1.0,
rlm@0 948 ":rock" 2.0}
rlm@0 949 #+end_example
rlm@0 950
rlm@0 951 # #+results-old:
rlm@0 952 # : [[":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 953
rlm@0 954
rlm@0 955 This is an extremely interesting type combination, in that it uses
rlm@0 956 quite a few types.
rlm@0 957
rlm@0 958 #+begin_src clojure :results verbatim :exports both
rlm@0 959 (reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))
rlm@0 960 #+end_src
rlm@0 961
rlm@0 962 #+results:
rlm@0 963 : 20.0
rlm@0 964
rlm@0 965 20 types is the /minimum/ number of types before the attacking
rlm@0 966 combination is not-very-effective or worse against all defending
rlm@0 967 types. This would probably have been impossible to discover using
rlm@0 968 best-first search, since it involves such an intricate type
rlm@0 969 combination.
rlm@0 970
rlm@0 971 It's so interesting that it takes 20 types to make an attack type that
rlm@11 972 is weak to all types that the combination merits further
rlm@11 973 investigation.
rlm@0 974
rlm@0 975 Unfortunately, all of the tools that we've written so far are focused
rlm@0 976 on defense type combinations. However, it is possible to make every
rlm@0 977 tool attack-oriented via a simple macro.
rlm@0 978
rlm@16 979 #+name: attack-oriented
rlm@0 980 #+begin_src clojure :results silent
rlm@0 981 (in-ns 'pokemon.lpsolve)
rlm@0 982
rlm@0 983 (defmacro attack-mode [& forms]
rlm@0 984 `(let [attack-strengths# pokemon.types/attack-strengths
rlm@0 985 defense-strengths# pokemon.types/defense-strengths]
rlm@0 986 (binding [pokemon.types/attack-strengths
rlm@0 987 defense-strengths#
rlm@0 988 pokemon.types/defense-strengths
rlm@0 989 attack-strengths#]
rlm@0 990 ~@forms)))
rlm@0 991 #+end_src
rlm@0 992
rlm@0 993 Now all the tools from =pokemon.types= will work for attack
rlm@0 994 combinations.
rlm@0 995
rlm@0 996 #+begin_src clojure :results output :exports both
rlm@0 997 (clojure.pprint/pprint
rlm@0 998 (pokemon.types/susceptibility [:water]))
rlm@0 999 #+end_src
rlm@0 1000
rlm@0 1001 #+results:
rlm@0 1002 #+begin_example
rlm@0 1003 {:water 1/2,
rlm@0 1004 :psychic 1,
rlm@0 1005 :dragon 1,
rlm@0 1006 :fire 1/2,
rlm@0 1007 :ice 1/2,
rlm@0 1008 :grass 2,
rlm@0 1009 :ghost 1,
rlm@0 1010 :poison 1,
rlm@0 1011 :flying 1,
rlm@0 1012 :normal 1,
rlm@0 1013 :rock 1,
rlm@0 1014 :electric 2,
rlm@0 1015 :ground 1,
rlm@0 1016 :fighting 1,
rlm@0 1017 :dark 1,
rlm@0 1018 :steel 1/2,
rlm@0 1019 :bug 1}
rlm@0 1020 #+end_example
rlm@0 1021
rlm@0 1022
rlm@0 1023 #+begin_src clojure :results output :exports both
rlm@0 1024 (clojure.pprint/pprint
rlm@0 1025 (pokemon.lpsolve/attack-mode
rlm@0 1026 (pokemon.types/susceptibility [:water])))
rlm@0 1027 #+end_src
rlm@0 1028
rlm@0 1029 #+results:
rlm@0 1030 #+begin_example
rlm@0 1031 {:water 1/2,
rlm@0 1032 :psychic 1,
rlm@0 1033 :dragon 1/2,
rlm@0 1034 :fire 2,
rlm@0 1035 :ice 1,
rlm@0 1036 :grass 1/2,
rlm@0 1037 :ghost 1,
rlm@0 1038 :poison 1,
rlm@0 1039 :flying 1,
rlm@0 1040 :normal 1,
rlm@0 1041 :rock 2,
rlm@0 1042 :electric 1,
rlm@0 1043 :ground 2,
rlm@0 1044 :fighting 1,
rlm@0 1045 :dark 1,
rlm@0 1046 :steel 1,
rlm@0 1047 :bug 1}
rlm@0 1048 #+end_example
rlm@0 1049
rlm@0 1050 Now =pokemon.types/susceptibility= reports the /attack-type/
rlm@0 1051 combination's effectiveness against other types.
rlm@0 1052
rlm@0 1053 The 20 type combo achieves its goal in a very clever way.
rlm@0 1054
rlm@0 1055 First, it weakens its effectiveness to other types at the expense of
rlm@0 1056 making it very strong against flying.
rlm@0 1057
rlm@0 1058 #+begin_src clojure :results output :exports both
rlm@0 1059 (clojure.pprint/pprint
rlm@0 1060 (pokemon.lpsolve/attack-mode
rlm@0 1061 (pokemon.types/susceptibility
rlm@0 1062 [:normal :normal :normal :normal
rlm@0 1063 :ice :ice :ice :ice
rlm@0 1064 :electric :electric :electric
rlm@0 1065 :rock :rock])))
rlm@0 1066 #+end_src
rlm@0 1067
rlm@0 1068 #+results:
rlm@0 1069 #+begin_example
rlm@0 1070 {:water 1/2,
rlm@0 1071 :psychic 1,
rlm@0 1072 :dragon 2,
rlm@0 1073 :fire 1/4,
rlm@0 1074 :ice 1/4,
rlm@0 1075 :grass 2,
rlm@0 1076 :ghost 0,
rlm@0 1077 :poison 1,
rlm@0 1078 :flying 512,
rlm@0 1079 :normal 1,
rlm@0 1080 :rock 1/16,
rlm@0 1081 :electric 1/8,
rlm@0 1082 :ground 0,
rlm@0 1083 :fighting 1/4,
rlm@0 1084 :dark 1,
rlm@0 1085 :steel 1/1024,
rlm@0 1086 :bug 4}
rlm@0 1087 #+end_example
rlm@0 1088
rlm@0 1089 Then, it removes it's strengths against Flying, Normal, and Fighting
rlm@0 1090 by adding Ghost and Ground.
rlm@0 1091
rlm@0 1092 #+begin_src clojure :results output :exports both
rlm@0 1093 (clojure.pprint/pprint
rlm@0 1094 (pokemon.lpsolve/attack-mode
rlm@0 1095 (pokemon.types/susceptibility
rlm@0 1096 [:normal :normal :normal :normal
rlm@0 1097 :ice :ice :ice :ice
rlm@0 1098 :electric :electric :electric
rlm@0 1099 :rock :rock
rlm@0 1100 ;; Spot resistances
rlm@0 1101 :ghost :ground])))
rlm@0 1102 #+end_src
rlm@0 1103
rlm@0 1104 #+results:
rlm@0 1105 #+begin_example
rlm@0 1106 {:water 1/2,
rlm@0 1107 :psychic 2,
rlm@0 1108 :dragon 2,
rlm@0 1109 :fire 1/2,
rlm@0 1110 :ice 1/4,
rlm@0 1111 :grass 1,
rlm@0 1112 :ghost 0,
rlm@0 1113 :poison 2,
rlm@0 1114 :flying 0,
rlm@0 1115 :normal 0,
rlm@0 1116 :rock 1/8,
rlm@0 1117 :electric 1/4,
rlm@0 1118 :ground 0,
rlm@0 1119 :fighting 1/4,
rlm@0 1120 :dark 1/2,
rlm@0 1121 :steel 1/1024,
rlm@0 1122 :bug 2}
rlm@0 1123 #+end_example
rlm@0 1124
rlm@0 1125 Adding the pair Psychic and Fighting takes care of its strength
rlm@0 1126 against Psychic and makes it ineffective against Dark, which is immune
rlm@0 1127 to Psychic.
rlm@0 1128
rlm@0 1129 Adding the pair Grass and Poison makes takes care of its strength
rlm@0 1130 against poison and makes it ineffective against Steel, which is immune
rlm@0 1131 to poison.
rlm@0 1132
rlm@0 1133 #+begin_src clojure :results output :exports both
rlm@0 1134 (clojure.pprint/pprint
rlm@0 1135 (pokemon.lpsolve/attack-mode
rlm@0 1136 (pokemon.types/susceptibility
rlm@0 1137 [;; setup
rlm@0 1138 :normal :normal :normal :normal
rlm@0 1139 :ice :ice :ice :ice
rlm@0 1140 :electric :electric :electric
rlm@0 1141 :rock :rock
rlm@0 1142 ;; Spot resistances
rlm@0 1143 :ghost :ground
rlm@0 1144 ;; Pair resistances
rlm@0 1145 :psychic :fighting
rlm@0 1146 :grass :poison])))
rlm@0 1147 #+end_src
rlm@0 1148
rlm@0 1149 #+results:
rlm@0 1150 #+begin_example
rlm@0 1151 {:water 1,
rlm@0 1152 :psychic 1/2,
rlm@0 1153 :dragon 1,
rlm@0 1154 :fire 1/4,
rlm@0 1155 :ice 1/2,
rlm@0 1156 :grass 1,
rlm@0 1157 :ghost 0,
rlm@0 1158 :poison 1/2,
rlm@0 1159 :flying 0,
rlm@0 1160 :normal 0,
rlm@0 1161 :rock 1/4,
rlm@0 1162 :electric 1/4,
rlm@0 1163 :ground 0,
rlm@0 1164 :fighting 1/2,
rlm@0 1165 :dark 0,
rlm@0 1166 :steel 0,
rlm@0 1167 :bug 1/2}
rlm@0 1168 #+end_example
rlm@0 1169
rlm@0 1170 Can you see the final step?
rlm@0 1171
rlm@13 1172 It's adding the Water type, which is weak against Water, Dragon, and
rlm@13 1173 Grass and strong against Rock and Fire.
rlm@0 1174
rlm@0 1175 #+begin_src clojure :results output :exports both
rlm@0 1176 (clojure.pprint/pprint
rlm@0 1177 (pokemon.lpsolve/attack-mode
rlm@0 1178 (pokemon.types/susceptibility
rlm@0 1179 [;; setup
rlm@0 1180 :normal :normal :normal :normal
rlm@0 1181 :ice :ice :ice :ice
rlm@0 1182 :electric :electric :electric
rlm@0 1183 :rock :rock
rlm@0 1184 ;; Spot resistances
rlm@0 1185 :ghost :ground
rlm@0 1186 ;; Pair resistances
rlm@0 1187 :psychic :fighting
rlm@0 1188 :grass :poison
rlm@0 1189 ;; completion
rlm@0 1190 :water])))
rlm@0 1191 #+end_src
rlm@0 1192
rlm@0 1193 #+results:
rlm@0 1194 #+begin_example
rlm@0 1195 {:water 1/2,
rlm@0 1196 :psychic 1/2,
rlm@0 1197 :dragon 1/2,
rlm@0 1198 :fire 1/2,
rlm@0 1199 :ice 1/2,
rlm@0 1200 :grass 1/2,
rlm@0 1201 :ghost 0,
rlm@0 1202 :poison 1/2,
rlm@0 1203 :flying 0,
rlm@0 1204 :normal 0,
rlm@0 1205 :rock 1/2,
rlm@0 1206 :electric 1/4,
rlm@0 1207 :ground 0,
rlm@0 1208 :fighting 1/2,
rlm@0 1209 :dark 0,
rlm@0 1210 :steel 0,
rlm@0 1211 :bug 1/2}
rlm@0 1212 #+end_example
rlm@0 1213
rlm@0 1214 Which makes a particularly beautiful combination which is ineffective
rlm@0 1215 against all defending types.
rlm@0 1216
rlm@0 1217
rlm@0 1218 # #+begin_src clojure :results scalar :exports both
rlm@0 1219 # (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 1220 # #+end_src
rlm@0 1221
rlm@0 1222 # #+results:
rlm@0 1223 # | [: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 1224
rlm@0 1225
rlm@0 1226 Is there anything else that's interesting?
rlm@0 1227
rlm@0 1228 #+begin_src clojure :exports both
rlm@0 1229 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))
rlm@0 1230 #+end_src
rlm@0 1231
rlm@0 1232 #+results:
rlm@0 1233 : INFEASIBLE
rlm@0 1234
rlm@0 1235 #+begin_src clojure :exports both
rlm@0 1236 (pokemon.types/old-school
rlm@0 1237 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))
rlm@0 1238 #+end_src
rlm@0 1239
rlm@0 1240 #+results:
rlm@0 1241 : INFEASIBLE
rlm@0 1242
rlm@0 1243 #+begin_src clojure :exports both
rlm@0 1244 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))
rlm@0 1245 #+end_src
rlm@0 1246
rlm@0 1247 #+results:
rlm@0 1248 : INFEASIBLE
rlm@0 1249
rlm@0 1250 #+begin_src clojure :exports both
rlm@0 1251 (pokemon.types/old-school
rlm@0 1252 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))
rlm@0 1253 #+end_src
rlm@0 1254
rlm@0 1255 #+results:
rlm@0 1256 : INFEASIBLE
rlm@0 1257
rlm@0 1258 #+begin_src clojure :exports both
rlm@0 1259 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))
rlm@0 1260 #+end_src
rlm@0 1261
rlm@0 1262 #+results:
rlm@0 1263 : INFEASIBLE
rlm@0 1264
rlm@0 1265 #+begin_src clojure :exports both
rlm@0 1266 (pokemon.types/old-school
rlm@0 1267 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))
rlm@0 1268 #+end_src
rlm@0 1269
rlm@0 1270 #+results:
rlm@0 1271 : INFEASIBLE
rlm@0 1272
rlm@0 1273 There is no way to produce a defense-type that is weak to all types.
rlm@0 1274 This is probably because there are many types that are completely
rlm@0 1275 immune to some types, such as Flying, which is immune to Ground. A
rlm@0 1276 perfectly weak type could not use any of these types.
rlm@0 1277
rlm@0 1278 * Summary
rlm@0 1279
rlm@14 1280 Overall, the pok\eacute{}mon type system is slanted towards defense
rlm@14 1281 rather than offense. While it is possible to create superior
rlm@11 1282 defensive types and exceptionally weak attack types, it is not
rlm@11 1283 possible to create exceptionally weak defensive types or very powerful
rlm@11 1284 attack types.
rlm@0 1285
rlm@0 1286 Using the =lp_solve= library was more complicated than the best-first
rlm@0 1287 search, but yielded results quickly and efficiently. Expressing the
rlm@0 1288 problem in a linear form does have its drawbacks, however --- it's
rlm@0 1289 hard to ask questions such as "what is the best 3-type defensive combo
rlm@0 1290 in terms of susceptibility?", since susceptibility is not a linear
rlm@0 1291 function of a combo's types. It is also hard to get all the solutions
rlm@0 1292 to a particular problem, such as all the pokemon type combinations of
rlm@0 1293 length 8 which are immortal defense types.
rlm@0 1294
rlm@0 1295 * COMMENT main-program
rlm@0 1296 #+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none
rlm@0 1297 <<intro>>
rlm@0 1298 <<body>>
rlm@0 1299 <<declares>>
rlm@0 1300 <<memory-management>>
rlm@0 1301 <<get-results>>
rlm@0 1302 <<solve>>
rlm@0 1303 <<farmer-example>>
rlm@0 1304 <<lp-solve>>
rlm@0 1305 <<better-farmer>>
rlm@0 1306 <<pokemon-lp>>
rlm@0 1307 <<results>>
rlm@0 1308 <<attack-oriented>>
rlm@0 1309 #+end_src
rlm@0 1310
rlm@0 1311
rlm@0 1312