Mercurial > pokemon-types
view org/lpsolve.org @ 22:8992278bf399 tip
typo corrected, thanks to a reader.
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sun, 20 Sep 2015 11:25:30 -0700 |
parents | f88b7d2c25d9 |
children |
line wrap: on
line source
1 #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization2 #+author: Robert McIntyre & Dylan Holmes3 #+EMAIL: rlm@mit.edu4 #+description: Using Lpsolve to find effective pokemon types in clojure.5 #+keywords: Pokemon, clojure, linear optimization, lp_solve, LpSolve6 #+SETUPFILE: ../../aurellem/org/setup.org7 #+INCLUDE: ../../aurellem/org/level-0.org9 * Introduction10 This post continues the [[./types.org][previous one]] about pok\eacute{}mon types.11 Pok\eacute{}mon is a game in which adorable creatures battle each12 other using fantastic attacks. It was made into a several gameboy13 games that all share the same battle system. Every pok\eacute{}mon in14 the gameboy game has one or two /types/, such as Ground, Fire, Water,15 etc. Every pok\eacute{}mon attack has exactly one type. Certain16 defending types are weak or strong to other attacking types. For17 example, Water attacks are strong against Fire pok\eacute{}mon, while18 Electric attacks are weak against Ground Pok\eacute{}mon. In the19 games, attacks can be either twice as effective as normal (Water20 vs. Fire), neutrally effective (Normal vs. Normal), half as effective21 (Fire vs. Water), or not effective at all (Electric vs. Ground). We22 represent these strengths and weaknesses as the numbers 2, 1,23 $\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to24 another.26 If a pokemon has two types, then the strengths and weakness of each27 type are /multiplied/ together. Thus Electric (2x weak to Ground)28 combined with Flying (immune to Ground (0x)) is immune to Ground.29 Fire (2x weak to Water) combined with Water (1/2x resistant to Water)30 is neutral to Water. If both types are resistant to another type, then31 the combination is doubly-resistant (1/4x) to that type. If both types32 are weak to a certain type then the combination is double-weak (4x) to33 that type.35 In the [[./types.org][previous post]], we used the best-first search algorithm to find36 the most effective Pok\eacute{}mon type combinations. Afterwards, we37 realized that we could transform this search problem into a /linear38 optimization problem/. This conversion offers several advantages:39 first, search algorithms are comparatively slow, whereas linear40 optimization algorithms are extremely fast; second, it is difficult to41 determine whether a search problem has any solution, whereas it is42 straightforward to determine whether a linear optimization problem has43 any solution; finally, because systems of linear equations are so44 common, many programming languages have linear equation solvers45 written for them.47 In this article, we will:48 - Solve a simple linear optimization problem in C :: We demonstrate49 how to use the linear programming C library, =lp_solve=, to50 solve a simple linear optimization problem.51 - Incorporate a C library into Clojure :: We will show how we gave52 Clojure access to the linear programming C library, =lp_solve=.53 - Find effective Pokemon types using linear programming :: Building54 on our earlier code, we answer some questions that were55 impossible to answer using best-first search.56 - Present our results :: We found some cool examples and learned a lot57 about the pok\eacute{}mon type system as a whole.60 ** Immortal Types62 In the game, pok\eacute{}mon can have either one type or two types. If63 this restriction is lifted, is there any combination of types that is64 resistant to all types? I call such a combination an /Immortal Type/,65 since if that type's pattern was repeated over and over again towards66 infinity, the resulting type would be immune to all attack types.68 * Linear Programming70 Linear programming is the process of finding an optimal solution to a71 linear equation of several variables which are constrained by some linear72 inequalities.74 ** The Farmer's Problem76 Let's solve the Farmer's Problem, an example linear programming problem77 borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm.80 #+BEGIN_QUOTE81 *The Farmer's Problem:* Suppose a farmer has 75 acres on which to82 plant two crops: wheat and barley. To produce these crops, it costs83 the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat84 and $210 per acre for the barley. The farmer has $15000 available for85 expenses. But after the harvest, the farmer must store the crops while86 awaiting favorable market conditions. The farmer has storage space87 for 4000 bushels. Each acre yields an average of 110 bushels of wheat88 or 30 bushels of barley. If the net profit per bushel of wheat (after89 all expenses have been subtracted) is $1.30 and for barley is $2.00,90 how should the farmer plant the 75 acres to maximize profit?91 #+END_QUOTE93 The Farmer's Problem is to maximize profit subject to constraints on94 available farmland, funds for expenses, and storage space.96 | | Wheat | Barley | Maximum total |97 |----------+----------------------+---------------------+--------------|98 | / | < | > | <> |99 | Farmland | \(w\) acres | \(b\) acres | 75 acres |100 | Expense | $120 per acre | $210 per acre | $15000 |101 | Storage | 110 bushels per acre | 30 bushels per acre | 4000 bushels |102 |----------+----------------------+---------------------+--------------|103 | Profit | $1.30 per bushel | $2.00 per bushel | |105 ** Solution using LP Solve106 In a new file, =farmer.lp=, we list the variables and constraints107 of our problem using LP Solve syntax.109 #+begin_src lpsolve :tangle ../lp/farmer.lp110 /* Maximize Total Profit */111 max: +143 wheat +60 barley;114 /* -------- Constraints --------*/116 /* the farmer can't spend more money than he has */117 +120 wheat +210 barley <= 15000;119 /* the harvest has to fit in his storage space */120 +110 wheat +30 barley <= 4000;122 /* he can't use more acres than he owns */123 +wheat +barley <= 75;124 #+end_src126 Running the =lp_solve= program on =farmer.lp= yields the following output.128 #+begin_src sh :exports both :results scalar129 lp_solve ~/proj/pokemon-types/lp/farmer.lp130 #+end_src132 #+results:133 :134 : Value of objective function: 6315.62500000135 :136 : Actual values of the variables:137 : wheat 21.875138 : barley 53.125141 This shows that the farmer can maximize his profit by planting 21.875142 of the available acres with wheat and the remaining 53.125 acres with143 barley; by doing so, he will make $6315.62(5) in profit.145 * Incorporating =lp_solve= into Clojure147 There is a [[http://lpsolve.sourceforge.net/5.5/Java/README.html][Java API]] written by Juergen Ebert which enables Java148 programs to use =lp_solve=. Although Clojure can use this Java API149 directly, the interaction between Java, C, and Clojure is clumsy:151 ** The Farmer's Problem in Clojure153 We are going to solve the same problem involving wheat and barley,154 that we did above, but this time using clojure and the =lp_solve= API.156 #+name: intro157 #+begin_src clojure :results silent158 (ns pokemon.lpsolve159 (:import lpsolve.LpSolve)160 (:require pokemon.types)161 ;;(:require incanter.core)162 (:require rlm.map-utils))163 #+end_src165 The =lp_solve= Java interface is available from the same site as166 =lp_solve= itself, http://lpsolve.sourceforge.net/ Using it is the167 same as many other =C= programs. There are excellent instructions to168 get set up. The short version is that you must call Java with169 =-Djava.library.path=/path/to/lpsolve/libraries= and also add the170 libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For171 example, in my =.bashrc= file, I have the line172 =LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=. If everything173 is set-up correctly,175 #+name: body176 #+begin_src clojure :results verbatim :exports both177 (import 'lpsolve.LpSolve)178 #+end_src180 #+results:181 : lpsolve.LpSolve183 should run with no problems.185 ** Making a DSL to talk with LpSolve186 *** Problems187 Since we are using a =C= wrapper, we have to deal with manual memory188 management for the =C= structures which are wrapped by the =LpSolve=189 object. Memory leaks in =LpSolve= instances can crash the JVM, so it's190 very important to get it right. Also, the Java wrapper follows the191 =C= tradition closely and defines many =static final int= constants192 for the different states of the =LpSolve= instance instead of using Java193 enums. The calling convention for adding rows and columns to194 the constraint matrix is rather complicated and must be done column by195 column or row by row, which can be error prone. Finally, I'd like to196 gather all the important output information from the =LpSolve= instance197 into a final, immutable structure.199 In summary, the issues I'd like to address are:201 - reliable memory management202 - functional interface to =LpSolve=203 - intelligible, immutable output205 To deal with these issues I'll create four functions for interfacing206 with =LpSolve=208 #+name: declares209 #+begin_src clojure :results silent210 (in-ns 'pokemon.lpsolve)212 ;; deal with automatic memory management for LpSolve instance.213 (declare linear-program)215 ;; functional interface to LpSolve216 (declare lp-solve)218 ;; immutable output from lp-solve219 (declare solve get-results)220 #+end_src223 *** Memory Management225 Every instance of =LpSolve= must be manually garbage collected via a226 call to =deleteLP=. I use a non-hygienic macro similar to =with-open=227 to ensure that =deleteLP= is always called.229 #+name: memory-management230 #+begin_src clojure :results silent231 (in-ns 'pokemon.lpsolve)232 (defmacro linear-program233 "solve a linear programming problem using LpSolve syntax.234 within the macro, the variable =lps= is bound to the LpSolve instance."235 [& statements]236 (list 'let '[lps (LpSolve/makeLp 0 0)]237 (concat '(try)238 statements239 ;; always free the =C= data structures.240 '((finally (.deleteLp lps))))))241 #+end_src244 The macro captures the variable =lps= within its body, providing for a245 convenient way to access the object using any of the methods of the246 =LpSolve= API without having to worry about when to call247 =deleteLP=.249 *** Sensible Results250 The =linear-program= macro deletes the actual =lps= object once it is251 done working, so it's important to collect the important results and252 add return them in an immutable structure at the end.254 #+name: get-results255 #+begin_src clojure :results silent256 (in-ns 'pokemon.lpsolve)258 (defrecord LpSolution259 [objective-value260 optimal-values261 variable-names262 solution263 status264 model])266 (defn model267 "Returns a textual representation of the problem suitable for268 direct input to the =lp_solve= program (lps format)"269 [#^LpSolve lps]270 (let [target (java.io.File/createTempFile "lps" ".lp")]271 (.writeLp lps (.getPath target))272 (slurp target)))274 (defn results275 "Given an LpSolve object, solves the object and returns a map of the276 essential values which compose the solution."277 [#^LpSolve lps]278 (locking lps279 (let [status (solve lps)280 number-of-variables (.getNcolumns lps)281 optimal-values (double-array number-of-variables)282 optimal-values (do (.getVariables lps optimal-values)283 (seq optimal-values))284 variable-names285 (doall286 ;; The doall is necessary since the lps object might287 ;; soon be deleted.288 (map289 #(.getColName lps (inc %))290 (range number-of-variables)))291 model (model lps)]292 (LpSolution.293 (.getObjective lps)294 optimal-values295 variable-names296 (zipmap variable-names optimal-values)297 status298 model))))300 #+end_src302 Here I've created an object called =LpSolution= which stores the303 important results from a session with =lp_solve=. Of note is the304 =model= function which returns the problem in a form that can be305 solved by other linear programming packages.307 *** Solution Status of an LpSolve Object309 #+name: solve310 #+begin_src clojure :results silent311 (in-ns 'pokemon.lpsolve)313 (defn static-integer?314 "does the field represent a static integer constant?"315 [#^java.lang.reflect.Field field]316 (and (java.lang.reflect.Modifier/isStatic (.getModifiers field))317 (integer? (.get field nil))))319 (defn integer-constants [class]320 (filter static-integer? (.getFields class)))322 (defn constant-map323 "Takes a class and creates a map of the static constant integer324 fields with their names. This helps with C wrappers where they have325 just defined a bunch of integer constants instead of enums."326 [class]327 (let [integer-fields (integer-constants class)]328 (into (sorted-map)329 (zipmap (map #(.get % nil) integer-fields)330 (map #(.getName %) integer-fields)))))332 (alter-var-root #'constant-map memoize)334 (defn solve335 "Solve an instance of LpSolve and return a string representing the336 status of the computation. Will only solve a particular LpSolve337 instance once."338 [#^LpSolve lps]339 ((constant-map LpSolve)340 (.solve lps)))342 #+end_src344 The =.solve= method of an =LpSolve= object only returns an integer code345 to specify the status of the computation. The =solve= method here346 uses reflection to look up the actual name of the status code and347 returns a more helpful status message that is also resistant to348 changes in the meanings of the code numbers.350 *** The Farmer Example in Clojure, Pass 1352 Now we can implement a nicer version of the examples from the353 [[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less354 line-by-line translation of the Java code from that example.356 #+name: farmer-example357 #+begin_src clojure :results silent358 (in-ns 'pokemon.lpsolve)359 (defn farmer-example []360 (linear-program361 (results362 (doto lps363 ;; name the columns364 (.setColName 1 "wheat")365 (.setColName 2 "barley")366 (.setAddRowmode true)367 ;; row 1 : 120x + 210y <= 15000368 (.addConstraintex 2369 (double-array [120 210])370 (int-array [1 2])371 LpSolve/LE372 15e3)373 ;; row 2 : 110x + 30y <= 4000374 (.addConstraintex 2375 (double-array [110 30])376 (int-array [1 2])377 LpSolve/LE378 4e3)379 ;; ;; row 3 : x + y <= 75380 (.addConstraintex 2381 (double-array [1 1])382 (int-array [1 2])383 LpSolve/LE384 75)385 (.setAddRowmode false)387 ;; add constraints388 (.setObjFnex 2389 (double-array [143 60])390 (int-array [1 2]))392 ;; set this as a maximization problem393 (.setMaxim)))))395 #+end_src397 #+begin_src clojure :results output :exports both398 (clojure.pprint/pprint399 (:solution (pokemon.lpsolve/farmer-example)))400 #+end_src402 #+results:403 : {"barley" 53.12499999999999, "wheat" 21.875}406 And it works as expected!408 *** The Farmer Example in Clojure, Pass 2409 We don't have to worry about memory management anymore, and the farmer410 example is about half as long as the example from the =LpSolve=411 website, but we can still do better. Solving linear problems is all412 about the constraint matrix $A$ , the objective function $c$, and the413 right-hand-side $b$, plus whatever other options one cares to set for414 the particular instance of =lp_solve=. Why not make a version of415 =linear-program= that takes care of initialization?419 #+name: lp-solve420 #+begin_src clojure :results silent421 (in-ns 'pokemon.lpsolve)422 (defn initialize-lpsolve-row-oriented423 "fill in an lpsolve instance using a constraint matrix =A=, the424 objective function =c=, and the right-hand-side =b="425 [#^lpsolve.LpSolve lps A b c]426 ;; set the name of the last column to _something_427 ;; this appears to be necessary to ensure proper initialization.428 (.setColName lps (count c) (str "C" (count c)))430 ;; This is the recommended way to "fill-in" an lps instance from the431 ;; documentation. First, set row mode, then set the objective432 ;; function, then set each row of the problem, and then turn off row433 ;; mode.434 (.setAddRowmode lps true)435 (.setObjFnex lps (count c)436 (double-array c)437 (int-array (range 1 (inc (count c)))))438 (dorun439 (for [n (range (count A))]440 (let [row (nth A n)441 row-length (int (count row))]442 (.addConstraintex lps443 row-length444 (double-array row)445 (int-array (range 1 (inc row-length)))446 LpSolve/LE447 (double (nth b n))))))448 (.setAddRowmode lps false)449 lps)452 (defmacro lp-solve453 "by default:,454 minimize (* c x), subject to (<= (* A x) b),455 using continuous variables. You may set any number of456 other options as in the LpSolve API."457 [A b c & lp-solve-forms]458 ;; assume that A is a vector of vectors459 (concat460 (list 'linear-program461 (list 'initialize-lpsolve-row-oriented 'lps A b c))462 `~lp-solve-forms))463 #+end_src465 Now, we can use a much more functional approach to solving the466 farmer's problem:468 #+name: better-farmer469 #+begin_src clojure :results silent470 (in-ns 'pokemon.lpsolve)471 (defn better-farmer-example []472 (lp-solve [[120 210]473 [110 30]474 [1 1]]475 [15000476 4000477 75]478 [143 60]479 (.setColName lps 1 "wheat")480 (.setColName lps 2 "barley")481 (.setMaxim lps)482 (results lps)))483 #+end_src485 #+begin_src clojure :exports both :results verbatim486 (vec (:solution (pokemon.lpsolve/better-farmer-example)))487 #+end_src489 #+results:490 : [["barley" 53.12499999999999] ["wheat" 21.875]]492 Notice that both the inputs to =better-farmer-example= and the results493 are immutable.495 * Using LpSolve to find Immortal Types496 ** Converting the Pok\eacute{}mon problem into a linear form497 How can the original question about pok\eacute{}mon types be converted498 into a linear problem?500 Pokemon types can be considered to be vectors of numbers representing501 their susceptances to various attacking types, so Water might look502 something like this.504 #+begin_src clojure :results scalar :exports both505 (:water (pokemon.types/defense-strengths))506 #+end_src508 #+results:509 : [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5]511 Where the numbers represent the susceptibility of Water to the512 attacking types in the following order:514 #+begin_src clojure :results output :exports both515 (clojure.pprint/pprint516 (pokemon.types/type-names))517 #+end_src519 #+results:520 #+begin_example521 [:normal522 :fire523 :water524 :electric525 :grass526 :ice527 :fighting528 :poison529 :ground530 :flying531 :psychic532 :bug533 :rock534 :ghost535 :dragon536 :dark537 :steel]538 #+end_example541 So, for example, Water is resistant (x0.5) against Fire, which is542 the second element in the list.544 To combine types, these sorts of vectors are multiplied together545 pair-wise to yield the resulting combination.547 Unfortunately, we need some way to add two type vectors together548 instead of multiplying them if we want to solve the problem with549 =lp_solve=. Taking the log of the vector does just the trick.551 If we make a matrix with each column being the log (base 2) of the552 susceptance of each type, then finding an immortal type corresponds to553 setting each constraint (the $b$ vector) to -1 (since log_2(1/2) = -1)554 and setting the constraint vector $c$ to all ones, which means that we555 want to find the immortal type which uses the least amount of types.557 #+name: pokemon-lp558 #+begin_src clojure :results silent559 (in-ns 'pokemon.lpsolve)561 (defn log-clamp-matrix [matrix]562 ;; we have to clamp the Infinities to a more reasonable negative563 ;; value because lp_solve does not play well with infinities in its564 ;; constraint matrix.565 (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %)566 (map #(/ (Math/log %) (Math/log 2)) row)))567 (apply mapv vector ;; transpose568 matrix)))570 ;; constraint matrices571 (defn log-defense-matrix []572 (log-clamp-matrix573 (doall (map (pokemon.types/defense-strengths)574 (pokemon.types/type-names)))))576 (defn log-attack-matrix []577 (apply mapv vector (log-defense-matrix)))579 ;; target vectors580 (defn all-resistant []581 (doall (map (constantly -1) (pokemon.types/type-names))))583 (defn all-weak []584 (doall (map (constantly 1) (pokemon.types/type-names))))586 (defn all-neutral []587 (doall (map (constantly 0) (pokemon.types/type-names))))589 ;; objective functions590 (defn number-of-types []591 (doall (map (constantly 1) (pokemon.types/type-names))))593 (defn set-constraints594 "sets all the constraints for an lpsolve instance to the given595 constraint. =constraint= here is one of the LpSolve constants such596 as LpSolve/EQ."597 [#^LpSolve lps constraint]598 (dorun (map (fn [index] (.setConstrType lps index constraint))599 ;; ONE based indexing!!!600 (range 1 (inc (.getNrows lps))))))602 (defn set-discrete603 "sets every variable in an lps problem to be a discrete rather than604 continuous variable"605 [#^LpSolve lps]606 (dorun (map (fn [index] (.setInt lps index true))607 ;; ONE based indexing!!!608 (range 1 (inc (.getNcolumns lps))))))610 (defn set-variable-names611 "sets the variable names of the problem given a vector of names"612 [#^LpSolve lps names]613 (dorun614 (keep-indexed615 (fn [index name]616 (.setColName lps (inc index) (str name)))617 ;; ONE based indexing!!!618 names)))620 (defn poke-solve621 ([poke-matrix target objective-function constraint min-num-types]622 ;; must have at least one type623 (let [poke-matrix624 (concat poke-matrix625 [(map (constantly 1)626 (range (count (first poke-matrix))))])627 target (concat target [min-num-types])]628 (lp-solve poke-matrix target objective-function629 (set-constraints lps constraint)630 ;; must have more than min-num-types631 (.setConstrType lps (count target) LpSolve/GE)632 (set-discrete lps)633 (set-variable-names lps (pokemon.types/type-names))634 (results lps))))635 ([poke-matrix target objective-function constraint]636 ;; at least one type637 (poke-solve poke-matrix target objective-function constraint 1)))639 (defn solution640 "If the results of an lpsolve operation are feasible, returns the641 results. Otherwise, returns the error."642 [results]643 (if (not (= (:status results) "OPTIMAL"))644 (:status results)645 (:solution results)))646 #+end_src648 With this, we are finally able to get some results.650 ** Results651 #+name: results652 #+begin_src clojure :results silent653 (in-ns 'pokemon.lpsolve)655 (defn best-defense-type656 "finds a type combination which is resistant to all attacks."657 []658 (poke-solve659 (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE))661 (defn worst-attack-type662 "finds the attack type which is not-very-effective against all pure663 defending types (each single defending type is resistant to this664 attack combination"665 []666 (poke-solve667 (log-attack-matrix) (all-resistant) (number-of-types) LpSolve/LE))669 (defn worst-defense-type670 "finds a defending type that is weak to all single attacking types."671 []672 (poke-solve673 (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE))675 (defn best-attack-type676 "finds an attack type which is super effective against all single677 defending types"678 []679 (poke-solve680 (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE))682 (defn solid-defense-type683 "finds a defense type which is either neutral or resistant to all684 single attacking types"685 []686 (poke-solve687 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE))689 (defn solid-attack-type690 "finds an attack type which is either neutral or super-effective to691 all single attacking types."692 []693 (poke-solve694 (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE))696 (defn weak-defense-type697 "finds a defense type which is either neutral or weak to all single698 attacking types"699 []700 (poke-solve701 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE))703 (defn neutral-defense-type704 "finds a defense type which is perfectly neutral to all attacking705 types."706 []707 (poke-solve708 (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ))710 #+end_src712 *** Strongest Attack/Defense Combinations714 #+begin_src clojure :results output :exports both715 (clojure.pprint/pprint716 (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type)))717 #+end_src719 #+results:720 #+begin_example721 {":normal" 0.0,722 ":ground" 1.0,723 ":poison" 2.0,724 ":flying" 1.0,725 ":fighting" 0.0,726 ":dragon" 0.0,727 ":fire" 0.0,728 ":dark" 1.0,729 ":ice" 0.0,730 ":steel" 1.0,731 ":ghost" 0.0,732 ":electric" 0.0,733 ":bug" 0.0,734 ":psychic" 0.0,735 ":grass" 0.0,736 ":water" 2.0,737 ":rock" 0.0}738 #+end_example740 # #+results-old: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]]744 This is the immortal type combination we've been looking for. By745 combining Steel, Water, Poison, and three types which each have complete746 immunities to various other types, we've created a type that is resistant to747 all attacking types.749 #+begin_src clojure :results output :exports both750 (clojure.pprint/pprint751 (pokemon.types/susceptibility752 [:poison :poison :water :water :steel :ground :flying :dark]))753 #+end_src755 #+results:756 #+begin_example757 {:water 1/2,758 :psychic 0,759 :dragon 1/2,760 :fire 1/2,761 :ice 1/2,762 :grass 1/2,763 :ghost 1/4,764 :poison 0,765 :flying 1/2,766 :normal 1/2,767 :rock 1/2,768 :electric 0,769 :ground 0,770 :fighting 1/2,771 :dark 1/4,772 :steel 1/8,773 :bug 1/8}774 #+end_example776 # #+results-old: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}780 Cool!782 #+begin_src clojure :results output :exports both783 (clojure.pprint/pprint784 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))785 #+end_src787 #+results:788 #+begin_example789 {":normal" 0.0,790 ":ground" 0.0,791 ":poison" 0.0,792 ":flying" 0.0,793 ":fighting" 0.0,794 ":dragon" 0.0,795 ":fire" 0.0,796 ":dark" 1.0,797 ":ice" 0.0,798 ":steel" 0.0,799 ":ghost" 1.0,800 ":electric" 0.0,801 ":bug" 0.0,802 ":psychic" 0.0,803 ":grass" 0.0,804 ":water" 0.0,805 ":rock" 0.0}806 #+end_example808 Dark and Ghost are the best dual-type combo, and are resistant or809 neutral to all types.811 #+begin_src clojure :results output :exports both812 (clojure.pprint/pprint813 (pokemon.types/old-school814 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))))815 #+end_src817 #+results:818 #+begin_example819 {":normal" 0.0,820 ":ground" 0.0,821 ":poison" 0.0,822 ":flying" 0.0,823 ":fighting" 0.0,824 ":dragon" 0.0,825 ":fire" 0.0,826 ":ice" 0.0,827 ":ghost" 1.0,828 ":electric" 0.0,829 ":bug" 0.0,830 ":psychic" 1.0,831 ":grass" 0.0,832 ":water" 0.0,833 ":rock" 0.0}834 #+end_example836 Ghost and Psychic are a powerful dual type combo in the original games,837 due to a glitch which made Psychic immune to Ghost type attacks, even838 though the game claims that Ghost is strong against Psychic.840 #+begin_src clojure :results verbatim :exports both841 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))842 #+end_src844 #+results:845 : INFEASIBLE847 #+begin_src clojure :results verbatim :exports both848 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))849 #+end_src851 #+results:852 : INFEASIBLE855 #+begin_src clojure :results verbatim :exports both856 (pokemon.types/old-school857 (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)))858 #+end_src860 #+results:861 : INFEASIBLE864 #+begin_src clojure :results output :exports both865 (clojure.pprint/pprint866 (pokemon.types/old-school867 (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type))))868 #+end_src870 #+results:871 #+begin_example872 {":normal" 0.0,873 ":ground" 0.0,874 ":poison" 0.0,875 ":flying" 0.0,876 ":fighting" 0.0,877 ":dragon" 1.0,878 ":fire" 0.0,879 ":ice" 0.0,880 ":ghost" 0.0,881 ":electric" 0.0,882 ":bug" 0.0,883 ":psychic" 0.0,884 ":grass" 0.0,885 ":water" 0.0,886 ":rock" 0.0}887 #+end_example889 The best attacking type combination is Dragon from the original games.890 It is neutral against all the original types except for Dragon, which891 it is strong against. There is no way to make an attacking type that892 is strong against every type, or even one that is strong or neutral893 against every type, in the new games.896 *** Weakest Attack/Defense Combinations898 #+begin_src clojure :results output :exports both899 (clojure.pprint/pprint900 (pokemon.types/old-school901 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))))902 #+end_src904 #+results:905 #+begin_example906 {":normal" 5.0,907 ":ground" 0.0,908 ":poison" 0.0,909 ":flying" 0.0,910 ":fighting" 0.0,911 ":dragon" 0.0,912 ":fire" 1.0,913 ":ice" 2.0,914 ":ghost" 1.0,915 ":electric" 1.0,916 ":bug" 1.0,917 ":psychic" 0.0,918 ":grass" 3.0,919 ":water" 2.0,920 ":rock" 0.0}921 #+end_example923 # #+results-old: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]]926 #+begin_src clojure :results output :exports both927 (clojure.pprint/pprint928 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))929 #+end_src931 #+results:932 #+begin_example933 {":normal" 4.0,934 ":ground" 1.0,935 ":poison" 1.0,936 ":flying" 0.0,937 ":fighting" 1.0,938 ":dragon" 0.0,939 ":fire" 0.0,940 ":dark" 0.0,941 ":ice" 4.0,942 ":steel" 0.0,943 ":ghost" 1.0,944 ":electric" 3.0,945 ":bug" 0.0,946 ":psychic" 1.0,947 ":grass" 1.0,948 ":water" 1.0,949 ":rock" 2.0}950 #+end_example952 # #+results-old: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]]956 This is an extremely interesting type combination, in that it uses957 quite a few types.959 #+begin_src clojure :results verbatim :exports both960 (reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type))))961 #+end_src963 #+results:964 : 20.0966 20 types is the /minimum/ number of types before the attacking967 combination is not-very-effective or worse against all defending968 types. This would probably have been impossible to discover using969 best-first search, since it involves such an intricate type970 combination.972 It's so interesting that it takes 20 types to make an attack type that973 is weak to all types that the combination merits further974 investigation.976 Unfortunately, all of the tools that we've written so far are focused977 on defense type combinations. However, it is possible to make every978 tool attack-oriented via a simple macro.980 #+name: attack-oriented981 #+begin_src clojure :results silent982 (in-ns 'pokemon.lpsolve)984 (defmacro attack-mode [& forms]985 `(let [attack-strengths# pokemon.types/attack-strengths986 defense-strengths# pokemon.types/defense-strengths]987 (binding [pokemon.types/attack-strengths988 defense-strengths#989 pokemon.types/defense-strengths990 attack-strengths#]991 ~@forms)))992 #+end_src994 Now all the tools from =pokemon.types= will work for attack995 combinations.997 #+begin_src clojure :results output :exports both998 (clojure.pprint/pprint999 (pokemon.types/susceptibility [:water]))1000 #+end_src1002 #+results:1003 #+begin_example1004 {:water 1/2,1005 :psychic 1,1006 :dragon 1,1007 :fire 1/2,1008 :ice 1/2,1009 :grass 2,1010 :ghost 1,1011 :poison 1,1012 :flying 1,1013 :normal 1,1014 :rock 1,1015 :electric 2,1016 :ground 1,1017 :fighting 1,1018 :dark 1,1019 :steel 1/2,1020 :bug 1}1021 #+end_example1024 #+begin_src clojure :results output :exports both1025 (clojure.pprint/pprint1026 (pokemon.lpsolve/attack-mode1027 (pokemon.types/susceptibility [:water])))1028 #+end_src1030 #+results:1031 #+begin_example1032 {:water 1/2,1033 :psychic 1,1034 :dragon 1/2,1035 :fire 2,1036 :ice 1,1037 :grass 1/2,1038 :ghost 1,1039 :poison 1,1040 :flying 1,1041 :normal 1,1042 :rock 2,1043 :electric 1,1044 :ground 2,1045 :fighting 1,1046 :dark 1,1047 :steel 1,1048 :bug 1}1049 #+end_example1051 Now =pokemon.types/susceptibility= reports the /attack-type/1052 combination's effectiveness against other types.1054 The 20 type combo achieves its goal in a very clever way.1056 First, it weakens its effectiveness to other types at the expense of1057 making it very strong against flying.1059 #+begin_src clojure :results output :exports both1060 (clojure.pprint/pprint1061 (pokemon.lpsolve/attack-mode1062 (pokemon.types/susceptibility1063 [:normal :normal :normal :normal1064 :ice :ice :ice :ice1065 :electric :electric :electric1066 :rock :rock])))1067 #+end_src1069 #+results:1070 #+begin_example1071 {:water 1/2,1072 :psychic 1,1073 :dragon 2,1074 :fire 1/4,1075 :ice 1/4,1076 :grass 2,1077 :ghost 0,1078 :poison 1,1079 :flying 512,1080 :normal 1,1081 :rock 1/16,1082 :electric 1/8,1083 :ground 0,1084 :fighting 1/4,1085 :dark 1,1086 :steel 1/1024,1087 :bug 4}1088 #+end_example1090 Then, it removes it's strengths against Flying, Normal, and Fighting1091 by adding Ghost and Ground.1093 #+begin_src clojure :results output :exports both1094 (clojure.pprint/pprint1095 (pokemon.lpsolve/attack-mode1096 (pokemon.types/susceptibility1097 [:normal :normal :normal :normal1098 :ice :ice :ice :ice1099 :electric :electric :electric1100 :rock :rock1101 ;; Spot resistances1102 :ghost :ground])))1103 #+end_src1105 #+results:1106 #+begin_example1107 {:water 1/2,1108 :psychic 2,1109 :dragon 2,1110 :fire 1/2,1111 :ice 1/4,1112 :grass 1,1113 :ghost 0,1114 :poison 2,1115 :flying 0,1116 :normal 0,1117 :rock 1/8,1118 :electric 1/4,1119 :ground 0,1120 :fighting 1/4,1121 :dark 1/2,1122 :steel 1/1024,1123 :bug 2}1124 #+end_example1126 Adding the pair Psychic and Fighting takes care of its strength1127 against Psychic and makes it ineffective against Dark, which is immune1128 to Psychic.1130 Adding the pair Grass and Poison makes takes care of its strength1131 against poison and makes it ineffective against Steel, which is immune1132 to poison.1134 #+begin_src clojure :results output :exports both1135 (clojure.pprint/pprint1136 (pokemon.lpsolve/attack-mode1137 (pokemon.types/susceptibility1138 [;; setup1139 :normal :normal :normal :normal1140 :ice :ice :ice :ice1141 :electric :electric :electric1142 :rock :rock1143 ;; Spot resistances1144 :ghost :ground1145 ;; Pair resistances1146 :psychic :fighting1147 :grass :poison])))1148 #+end_src1150 #+results:1151 #+begin_example1152 {:water 1,1153 :psychic 1/2,1154 :dragon 1,1155 :fire 1/4,1156 :ice 1/2,1157 :grass 1,1158 :ghost 0,1159 :poison 1/2,1160 :flying 0,1161 :normal 0,1162 :rock 1/4,1163 :electric 1/4,1164 :ground 0,1165 :fighting 1/2,1166 :dark 0,1167 :steel 0,1168 :bug 1/2}1169 #+end_example1171 Can you see the final step?1173 It's adding the Water type, which is weak against Water, Dragon, and1174 Grass and strong against Rock and Fire.1176 #+begin_src clojure :results output :exports both1177 (clojure.pprint/pprint1178 (pokemon.lpsolve/attack-mode1179 (pokemon.types/susceptibility1180 [;; setup1181 :normal :normal :normal :normal1182 :ice :ice :ice :ice1183 :electric :electric :electric1184 :rock :rock1185 ;; Spot resistances1186 :ghost :ground1187 ;; Pair resistances1188 :psychic :fighting1189 :grass :poison1190 ;; completion1191 :water])))1192 #+end_src1194 #+results:1195 #+begin_example1196 {:water 1/2,1197 :psychic 1/2,1198 :dragon 1/2,1199 :fire 1/2,1200 :ice 1/2,1201 :grass 1/2,1202 :ghost 0,1203 :poison 1/2,1204 :flying 0,1205 :normal 0,1206 :rock 1/2,1207 :electric 1/4,1208 :ground 0,1209 :fighting 1/2,1210 :dark 0,1211 :steel 0,1212 :bug 1/2}1213 #+end_example1215 Which makes a particularly beautiful combination which is ineffective1216 against all defending types.1219 # #+begin_src clojure :results scalar :exports both1220 # (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])))))1221 # #+end_src1223 # #+results: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] |1227 Is there anything else that's interesting?1229 #+begin_src clojure :exports both1230 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))1231 #+end_src1233 #+results:1234 : INFEASIBLE1236 #+begin_src clojure :exports both1237 (pokemon.types/old-school1238 (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)))1239 #+end_src1241 #+results:1242 : INFEASIBLE1244 #+begin_src clojure :exports both1245 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))1246 #+end_src1248 #+results:1249 : INFEASIBLE1251 #+begin_src clojure :exports both1252 (pokemon.types/old-school1253 (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)))1254 #+end_src1256 #+results:1257 : INFEASIBLE1259 #+begin_src clojure :exports both1260 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))1261 #+end_src1263 #+results:1264 : INFEASIBLE1266 #+begin_src clojure :exports both1267 (pokemon.types/old-school1268 (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)))1269 #+end_src1271 #+results:1272 : INFEASIBLE1274 There is no way to produce a defense-type that is weak to all types.1275 This is probably because there are many types that are completely1276 immune to some types, such as Flying, which is immune to Ground. A1277 perfectly weak type could not use any of these types.1279 * Summary1281 Overall, the pok\eacute{}mon type system is slanted towards defense1282 rather than offense. While it is possible to create superior1283 defensive types and exceptionally weak attack types, it is not1284 possible to create exceptionally weak defensive types or very powerful1285 attack types.1287 Using the =lp_solve= library was more complicated than the best-first1288 search, but yielded results quickly and efficiently. Expressing the1289 problem in a linear form does have its drawbacks, however --- it's1290 hard to ask questions such as "what is the best 3-type defensive combo1291 in terms of susceptibility?", since susceptibility is not a linear1292 function of a combo's types. It is also hard to get all the solutions1293 to a particular problem, such as all the pokemon type combinations of1294 length 8 which are immortal defense types.1296 * COMMENT main-program1297 #+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none1298 <<intro>>1299 <<body>>1300 <<declares>>1301 <<memory-management>>1302 <<get-results>>1303 <<solve>>1304 <<farmer-example>>1305 <<lp-solve>>1306 <<better-farmer>>1307 <<pokemon-lp>>1308 <<results>>1309 <<attack-oriented>>1310 #+end_src