Mercurial > pokemon-types
changeset 0:e03d363ed9a9
initial committ for pokemon types report
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Sun, 16 Oct 2011 06:57:42 -0700 |
| parents | |
| children | d39a04826cec |
| files | org/lpsolve.org org/types.org |
| diffstat | 2 files changed, 2033 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/org/lpsolve.org Sun Oct 16 06:57:42 2011 -0700 1.3 @@ -0,0 +1,1387 @@ 1.4 +#+title: Discovering Effective Pokemon Types Using Linear Optimization 1.5 +#+author: Robert McIntyre & Dylan Holmes 1.6 +#+EMAIL: rlm@mit.edu 1.7 +#+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js" 1.8 +#+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" /> 1.9 +#+OPTIONS: H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t 1.10 +#+SETUPFILE: ../templates/level-0.org 1.11 +#+INCLUDE: ../templates/level-0.org 1.12 + 1.13 + 1.14 + 1.15 +* Introduction 1.16 +In the [[./types.org][previous post]], we used the best-first search algorithm to 1.17 +locate the most effective Pok\eacute{}mon type 1.18 +combinations. Afterwards, we realized that we could transform this 1.19 +search problem into a /linear optimization problem/. This conversion 1.20 +offered several advantages: first, search algorithms are comparatively 1.21 +slow, whereas linear optimization algorithms are extremely fast; 1.22 +second, it is difficult to determine whether a search problem has any 1.23 +solution, whereas it is straightforward to determine whether a linear 1.24 +optimization problem has any solution; finally, because systems of 1.25 +linear equations are so common, many programming languages have linear 1.26 +equation solvers written for them. 1.27 + 1.28 +In this article, we will 1.29 + - Solve a simple linear optimization problem in C :: We demonstrate 1.30 + how to use the linear programming C library, =lp_solve=, to 1.31 + solve a simple linear 1.32 + optimization problem. 1.33 + - Incorporate a C library into Clojure :: We will show how we gave 1.34 + Clojure access to the linear programming C library, =lp_solve=. 1.35 + - Find effective Pokemon types using linear programming :: Building 1.36 + on our earlier code, (...) 1.37 +- Present our results :: (!) 1.38 + 1.39 +#which can be represented and solved as a system of linear equations. 1.40 + 1.41 +* COMMENT 1.42 +This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 1.43 +Pok\eacute{}mon is a game in which adorable creatures battle each 1.44 +other using fantastic attacks. It was made into a several gameboy 1.45 +games that all share the same battle system. Every pok\eacute{}mon in the 1.46 +gameboy game has one or two /types/, such as Ground, Fire, Water, 1.47 +etc. Every pok\eacute{}mon attack has exactly one type. Certain defending 1.48 +types are weak or strong to other attacking types. For example, Water 1.49 +attacks are strong against Fire pok\eacute{}mon, while Electric attacks are 1.50 +weak against Ground Pok\eacute{}mon. In the games, attacks can be either 1.51 +twice as effective as normal (Water vs. Fire), neutrally effective 1.52 +(Normal vs. Normal), half as effective (Fire vs. Water), or not 1.53 +effective at all (Electric vs. Ground). Thus the range of defense 1.54 +values for a particular type is the set 0, 1/2, 1, 2. These are 1.55 +referred to in the game as being immune, resistant, neutral, and 1.56 +weak, respectively. I call them the /susceptance/ of one type to another. 1.57 + 1.58 +If a pokemon has two types, then the strengths and weakness of each 1.59 +type are /multiplied/ together. Thus Electric (2x weak to Ground) 1.60 +combined with Flying (immune to Ground (0x)) is immune to 1.61 +Ground. Fire (2x weak to Water) combined with Water (1/2x resistant 1.62 +to Water) is neutral to Water. If both types are resistant to another 1.63 +type, then the combination is doubly-resistant (1/4x) to that type. If 1.64 +both types are weak to a certain type then the combination is 1.65 +double-weak (4x) to that type. 1.66 + 1.67 +** Immortal Types 1.68 + 1.69 +In the game, pok\eacute{}mon can have either one type, or two types. If this 1.70 +restriction is lifted, is there any combination of types that is 1.71 +resistant to all types? I call such a combination an /Immortal Type/, 1.72 +since if that type's pattern was repeated over and over again towards 1.73 +infinity, the resulting type would be immune to all attack types. 1.74 + 1.75 +* Linear Programming 1.76 + 1.77 +** Terminology 1.78 +Linear programming is the process of finding an optimal solution to a 1.79 +linear equation of several variables which are constrained by some linear 1.80 +inequalities. 1.81 + 1.82 +In linear programming terminology, the function to be extremized is 1.83 +the /objective function/. 1.84 + 1.85 +** COMMENT 1.86 +First, we'll give a small example of a linear optimization problem, 1.87 +and show how it can be solved with Clojure and =lp_solve=. Then, 1.88 +we'll show how finding immortal pok\eacute{}mon types can be converted 1.89 +into a linear problem suitable for solving in the same way. 1.90 + 1.91 +** The Farmer's Problem 1.92 + 1.93 +Let's solve the Farmer's Problem, a typical linear programming problem 1.94 +borrowed from http://lpsolve.sourceforge.net/5.5/formulate.htm. 1.95 + 1.96 + 1.97 +#+BEGIN_QUOTE 1.98 +*The Farmer's Problem:* Suppose a farmer has 75 acres on which to 1.99 +plant two crops: wheat and barley. To produce these crops, it costs 1.100 +the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat 1.101 +and $210 per acre for the barley. The farmer has $15000 available for 1.102 +expenses. But after the harvest, the farmer must store the crops while 1.103 +awaiting favorable market conditions. The farmer has storage space 1.104 +for 4000 bushels. Each acre yields an average of 110 bushels of wheat 1.105 +or 30 bushels of barley. If the net profit per bushel of wheat (after 1.106 +all expenses have been subtracted) is $1.30 and for barley is $2.00, 1.107 +how should the farmer plant the 75 acres to maximize profit? 1.108 +#+END_QUOTE 1.109 + 1.110 +The Farmer's Problem is to maximize profit subject to constraints on 1.111 +available farmland, funds for expenses, and storage space. 1.112 + 1.113 +| | Wheat | Barley | Maximum total | 1.114 +|----------+----------------------+---------------------+--------------| 1.115 +| / | < | > | <> | 1.116 +| Farmland | \(w\) acres | \(b\) acres | 75 acres | 1.117 +| Expense | $120 per acre | $210 per acre | $15000 | 1.118 +| Storage | 110 bushels per acre | 30 bushels per acre | 4000 bushels | 1.119 +|----------+----------------------+---------------------+--------------| 1.120 +| Profit | $1.30 per bushel | $2.00 per bushel | | 1.121 + 1.122 +*** COMMENT 1.123 +can be represented as a linear optimization 1.124 + problem. In this form, it is a problem with two variables\mdash{}the number of 1.125 + acres of wheat, \(w\), and the number of acres of barley, \(b\). The 1.126 + aim is to maximize profit, which 1.127 + 1.128 + subject to three constraints: the farmer can't spend more money 1.129 +than he has, the farmer can't use more acres than he owns, and the harvest has 1.130 +to fit in his storage space. 1.131 + 1.132 +We can express these constraints succinctly using matrix 1.133 +notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\), 1.134 +we want to maximize the expression \(143 w + 60 b\) subject to 1.135 + 1.136 +\( 1.137 +\begin{cases} 1.138 +120 w + 210 b & \leq & 1500\\ 1.139 +110 w + 30 b & \leq & 4000\\ 1.140 +1 w + 1 w & \leq & 75 1.141 +\end{cases} 1.142 +\) 1.143 + 1.144 +#\(\begin{bmatrix}120&210\\110&30\\1 & 1.145 +#1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix} 1.146 +#\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\) 1.147 + 1.148 + 1.149 +** Solution using LP Solve 1.150 +#(LP solve is available at http://www.example.com.) 1.151 +In a new file, =farmer.lp=, we list the variables and constraints 1.152 +of our problem using LP Solve syntax. 1.153 + 1.154 +#+begin_src lpsolve :tangle farmer.lp 1.155 +/* Maximize Total Profit */ 1.156 +max: +143 wheat +60 barley; 1.157 + 1.158 + 1.159 +/* -------- Constraints --------*/ 1.160 + 1.161 +/* the farmer can't spend more money than he has */ 1.162 ++120 wheat +210 barley <= 15000; 1.163 + 1.164 +/* the harvest has to fit in his storage space */ 1.165 ++110 wheat +30 barley <= 4000; 1.166 + 1.167 +/* he can't use more acres than he owns */ 1.168 ++wheat +barley <= 75; 1.169 +#+end_src 1.170 + 1.171 + 1.172 +#This is a set of linear equations ideal for solving using a program like 1.173 +#=lp_solve=. In Linear Algebra terms we are maximizing the linear function 1.174 + 1.175 +#\(\text{profit} = 143\text{ wheat} + 60\text{ barley}\), subject to the constraints 1.176 + 1.177 +#Ax <= b, 1.178 + 1.179 +#where A is [120 210 110 30 1 1], x is [wheat barley] and b is [15000 1.180 +#4000 75]. 1.181 + 1.182 +Running the =lp_solve= program on =farmer.lp= yields the following output. 1.183 + 1.184 +#+begin_src sh :exports both :results scalar 1.185 +~/roBin/lpsolve/lp_solve ~/aurellem/src/pokemon/farmer.lp 1.186 +#+end_src 1.187 + 1.188 +#+results: 1.189 +: 1.190 +: Value of objective function: 6315.62500000 1.191 +: 1.192 +: Actual values of the variables: 1.193 +: wheat 21.875 1.194 +: barley 53.125 1.195 + 1.196 +This shows that the farmer can maximize his profit by planting 21.875 1.197 +of the available acres with wheat and the remaining 53.125 acres with 1.198 +barley; by doing so, he will make $6315.62(5) in profit. 1.199 + 1.200 + 1.201 +#The farmer can make a profit of $6315.62 by planting 21.875 acres of 1.202 +#his land with wheat and the other 53.125 acres of his land with barley. 1.203 + 1.204 +* Incorporating =lp_solve= into Clojure 1.205 + 1.206 +There is a Java API available which enables Java programs to use Lp 1.207 +Solve. Although Clojure can use this Java API directly, the 1.208 +interaction between Java, C, and Clojure is clumsy: 1.209 + 1.210 + 1.211 +The Java API for LP Solve makes it possible to use Lp Solve algorithms 1.212 +within Java. Although Clojure can use this Java API directly, 1.213 + 1.214 + 1.215 +** The Farmer's Problem in Clojure 1.216 +We are going to solve the same problem involving wheat and barley, 1.217 +that we did above, but this time using clojure and the lpsolve API. 1.218 + 1.219 +#Because we ultimately intend to use Lp Solve to find optimal Pokemon type combinations. 1.220 +# we want to solve linear optimization problems within Clojure, the language 1.221 + 1.222 +** Setup 1.223 +=lp_solve= is a crufty =C= program which already comes with a JNI 1.224 +interface written by Juergen Ebert. It's API is not 1.225 +particularly friendly from a functional/immutable perspective, but 1.226 +with a little work, we can build something that works great with 1.227 +clojure. 1.228 + 1.229 +#+srcname: intro 1.230 +#+begin_src clojure :results silent 1.231 +(ns pokemon.lpsolve 1.232 + (:use rlm.ns-rlm)) 1.233 +(rlm.ns-rlm/ns-clone rlm.light-base) 1.234 +(use 'clojure.set) 1.235 +(import 'lpsolve.LpSolve) 1.236 +(use '[clojure [pprint :only [pprint]]]) 1.237 +#+end_src 1.238 + 1.239 +The LpSolve Java interface is available from the same site as 1.240 +=lp_solve= itself, http://lpsolve.sourceforge.net/ 1.241 +Using it is the same as many other =C= 1.242 +programs. There are excellent instructions to get set 1.243 +up. The short version is that you must call Java with 1.244 +=-Djava.library.path=/path/to/lpsolve/libraries= and also add the 1.245 +libraries to your export =LD_LIBRARY_PATH= if you are using Linux. For 1.246 +example, in my =.bashrc= file, I have the line 1.247 +=LD_LIBRARY_PATH=$HOME/roBin/lpsolve:$LD_LIBRARY_PATH=. 1.248 +If everything is set-up correctly, 1.249 + 1.250 +#+srcname: body 1.251 +#+begin_src clojure :results verbatim :exports both 1.252 +(import 'lpsolve.LpSolve) 1.253 +#+end_src 1.254 + 1.255 +#+results: body 1.256 +: lpsolve.LpSolve 1.257 + 1.258 +should run with no problems. 1.259 + 1.260 +** Making a DSL to talk with LpSolve 1.261 +*** Problems 1.262 +Since we are using a =C= wrapper, we have to deal with manual memory 1.263 +management for the =C= structures which are wrapped by the =LpSolve= 1.264 +object. Memory leaks in =LpSolve= instances can crash the JVM, so it's 1.265 +very important to get it right. Also, the Java wrapper follows the 1.266 +=C= tradition closely and defines many =static final int= constants 1.267 +for the different states of the =LpSolve= instance instead of using Java 1.268 +enums. The calling convention for adding rows and columns to 1.269 +the constraint matrix is rather complicated and must be done column by 1.270 +column or row by row, which can be error prone. Finally, I'd like to 1.271 +gather all the important output information from the =LpSolve= instance 1.272 +into a final, immutable structure. 1.273 + 1.274 +In summary, the issues I'd like to address are: 1.275 + 1.276 +- reliable memory management 1.277 +- functional interface to =LpSolve= 1.278 +- intelligible, immutable output 1.279 + 1.280 +To deal with these issues I'll create four functions for interfacing 1.281 +with =LpSolve= 1.282 + 1.283 +#+srcname: declares 1.284 +#+begin_src clojure :results silent 1.285 +(in-ns 'pokemon.lpsolve) 1.286 + 1.287 +;; deal with automatic memory management for LpSolve instance. 1.288 +(declare linear-program) 1.289 + 1.290 +;; functional interface to LpSolve 1.291 +(declare lp-solve) 1.292 + 1.293 +;; immutable output from lp-solve 1.294 +(declare solve get-results) 1.295 +#+end_src 1.296 + 1.297 +*** Memory Management 1.298 + 1.299 +Every instance of =LpSolve= must be manually garbage collected via a 1.300 +call to =deleteLP=. I use a non-hygienic macro similar to =with-open= 1.301 +to ensure that =deleteLP= is always called. 1.302 + 1.303 +#+srcname: memory-management 1.304 +#+begin_src clojure :results silent 1.305 +(in-ns 'pokemon.lpsolve) 1.306 +(defmacro linear-program 1.307 + "solve a linear programming problem using LpSolve syntax. 1.308 + within the macro, the variable =lps= is bound to the LpSolve instance." 1.309 + [& statements] 1.310 + (list 'let '[lps (LpSolve/makeLp 0 0)] 1.311 + (concat '(try) 1.312 + statements 1.313 + ;; always free the =C= data structures. 1.314 + '((finally (.deleteLp lps)))))) 1.315 +#+end_src 1.316 + 1.317 + 1.318 +The macro captures the variable =lps= within its body, providing for a 1.319 +convenient way to access the object using any of the methods of the 1.320 +=LpSolve= API without having to worry about when to call 1.321 +=deleteLP=. 1.322 + 1.323 +*** Sensible Results 1.324 +The =linear-program= macro deletes the actual =lps= object once it is 1.325 +done working, so it's important to collect the important results and 1.326 +add return them in an immutable structure at the end. 1.327 + 1.328 +#+srcname: get-results 1.329 +#+begin_src clojure :results silent 1.330 +(in-ns 'pokemon.lpsolve) 1.331 + 1.332 +(defrecord LpSolution 1.333 + [objective-value 1.334 + optimal-values 1.335 + variable-names 1.336 + solution 1.337 + status 1.338 + model]) 1.339 + 1.340 +(defn model 1.341 + "Returns a textual representation of the problem suitable for 1.342 + direct input to the =lp_solve= program (lps format)" 1.343 + [#^LpSolve lps] 1.344 + (let [target (java.io.File/createTempFile "lps" ".lp")] 1.345 + (.writeLp lps (.getPath target)) 1.346 + (slurp target))) 1.347 + 1.348 +(defn results 1.349 + "given an LpSolve object, solves the object and returns a map of the 1.350 + essential values which compose the solution." 1.351 + [#^LpSolve lps] 1.352 + (locking lps 1.353 + (let [status (solve lps) 1.354 + number-of-variables (.getNcolumns lps) 1.355 + optimal-values (double-array number-of-variables) 1.356 + optimal-values (do (.getVariables lps optimal-values) 1.357 + (seq optimal-values)) 1.358 + variable-names 1.359 + (doall ;; the doall is necessary since the lps object might 1.360 + ;; soon be deleted 1.361 + (map 1.362 + #(.getColName lps (inc %)) 1.363 + (range number-of-variables))) 1.364 + model (model lps)] 1.365 + (LpSolution. 1.366 + (.getObjective lps) 1.367 + optimal-values 1.368 + variable-names 1.369 + (zipmap variable-names optimal-values) 1.370 + status 1.371 + model)))) 1.372 + 1.373 +#+end_src 1.374 + 1.375 +Here I've created an object called =LpSolution= which stores the 1.376 +important results from a session with =lp_solve=. Of note is the 1.377 +=model= function which returns the problem in a form that can be 1.378 +solved by other linear programming packages. 1.379 + 1.380 +*** Solution Status of an LpSolve Object 1.381 + 1.382 +#+srcname: solve 1.383 +#+begin_src clojure :results silent 1.384 +(in-ns 'pokemon.lpsolve) 1.385 + 1.386 +(defn static-integer? 1.387 + "does the field represent a static integer constant?" 1.388 + [#^java.lang.reflect.Field field] 1.389 + (and (java.lang.reflect.Modifier/isStatic (.getModifiers field)) 1.390 + (integer? (.get field nil)))) 1.391 + 1.392 +(defn integer-constants [class] 1.393 + (filter static-integer? (.getFields class))) 1.394 + 1.395 +(defn-memo constant-map 1.396 + "Takes a class and creates a map of the static constant integer 1.397 + fields with their names. This helps with C wrappers where they have 1.398 + just defined a bunch of integer constants instead of enums" 1.399 + [class] 1.400 + (let [integer-fields (integer-constants class)] 1.401 + (into (sorted-map) 1.402 + (zipmap (map #(.get % nil) integer-fields) 1.403 + (map #(.getName %) integer-fields))))) 1.404 + 1.405 +(defn solve 1.406 + "Solve an instance of LpSolve and return a string representing the 1.407 + status of the computation. Will only solve a particular LpSolve 1.408 + instance once." 1.409 + [#^LpSolve lps] 1.410 + ((constant-map LpSolve) 1.411 + (.solve lps))) 1.412 + 1.413 +#+end_src 1.414 + 1.415 +The =.solve= method of an =LpSolve= object only returns an integer code 1.416 +to specify the status of the computation. The =solve= method here 1.417 +uses reflection to look up the actual name of the status code and 1.418 +returns a more helpful status message that is also resistant to 1.419 +changes in the meanings of the code numbers. 1.420 + 1.421 +*** The Farmer Example in Clojure, Pass 1 1.422 + 1.423 +Now we can implement a nicer version of the examples from the 1.424 +[[http://lpsolve.sourceforge.net/][=lp\_solve= website]]. The following is a more or less 1.425 +line-by-line translation of the Java code from that example. 1.426 + 1.427 +#+srcname: farmer-example 1.428 +#+begin_src clojure :results silent 1.429 +(in-ns 'pokemon.lpsolve) 1.430 +(defn farmer-example [] 1.431 + (linear-program 1.432 + (results 1.433 + (doto lps 1.434 + ;; name the columns 1.435 + (.setColName 1 "wheat") 1.436 + (.setColName 2 "barley") 1.437 + (.setAddRowmode true) 1.438 + ;; row 1 : 120x + 210y <= 15000 1.439 + (.addConstraintex 2 1.440 + (double-array [120 210]) 1.441 + (int-array [1 2]) 1.442 + LpSolve/LE 1.443 + 15e3) 1.444 + ;; row 2 : 110x + 30y <= 4000 1.445 + (.addConstraintex 2 1.446 + (double-array [110 30]) 1.447 + (int-array [1 2]) 1.448 + LpSolve/LE 1.449 + 4e3) 1.450 + ;; ;; row 3 : x + y <= 75 1.451 + (.addConstraintex 2 1.452 + (double-array [1 1]) 1.453 + (int-array [1 2]) 1.454 + LpSolve/LE 1.455 + 75) 1.456 + (.setAddRowmode false) 1.457 + 1.458 + ;; add constraints 1.459 + (.setObjFnex 2 1.460 + (double-array [143 60]) 1.461 + (int-array [1 2])) 1.462 + 1.463 + ;; set this as a maximization problem 1.464 + (.setMaxim))))) 1.465 + 1.466 +#+end_src 1.467 + 1.468 +#+begin_src clojure :results output :exports both 1.469 +(clojure.pprint/pprint 1.470 + (:solution (pokemon.lpsolve/farmer-example))) 1.471 +#+end_src 1.472 + 1.473 +#+results: 1.474 +: {"barley" 53.12499999999999, "wheat" 21.875} 1.475 + 1.476 +And it works as expected! 1.477 + 1.478 +*** The Farmer Example in Clojure, Pass 2 1.479 +We don't have to worry about memory management anymore, and the farmer 1.480 +example is about half as long as the example from the =LpSolve= 1.481 +website, but we can still do better. Solving linear problems is all 1.482 +about the constraint matrix $A$ , the objective function $c$, and the 1.483 +right-hand-side $b$, plus whatever other options one cares to set for 1.484 +the particular instance of =lp_solve=. Why not make a version of 1.485 +=linear-program= that takes care of initialization? 1.486 + 1.487 + 1.488 + 1.489 +#+srcname: lp-solve 1.490 +#+begin_src clojure :results silent 1.491 +(in-ns 'pokemon.lpsolve) 1.492 +(defn initialize-lpsolve-row-oriented 1.493 + "fill in an lpsolve instance using a constraint matrix =A=, the 1.494 + objective function =c=, and the right-hand-side =b=" 1.495 + [#^LpSolve lps A b c] 1.496 + ;; set the name of the last column to _something_ 1.497 + ;; this appears to be necessary to ensure proper initialization. 1.498 + (.setColName lps (count c) (str "C" (count c))) 1.499 + 1.500 + ;; This is the recommended way to "fill-in" an lps instance from the 1.501 + ;; documentation. First, set row mode, then set the objective 1.502 + ;; function, then set each row of the problem, and then turn off row 1.503 + ;; mode. 1.504 + (.setAddRowmode lps true) 1.505 + (.setObjFnex lps (count c) 1.506 + (double-array c) 1.507 + (int-array (range 1 (inc (count c))))) 1.508 + (dorun 1.509 + (for [n (range (count A))] 1.510 + (let [row (nth A n) 1.511 + row-length (int (count row))] 1.512 + (.addConstraintex lps 1.513 + row-length 1.514 + (double-array row) 1.515 + (int-array (range 1 (inc row-length))) 1.516 + LpSolve/LE 1.517 + (double (nth b n)))))) 1.518 + (.setAddRowmode lps false) 1.519 + lps) 1.520 + 1.521 + 1.522 +(defmacro lp-solve 1.523 + "by default:, 1.524 + minimize (* c x), subject to (<= (* A x) b), 1.525 + using continuous variables. You may set any number of 1.526 + other options as in the LpSolve API." 1.527 + [A b c & lp-solve-forms] 1.528 + ;; assume that A is a vector of vectors 1.529 + (concat 1.530 + (list 'linear-program 1.531 + (list 'initialize-lpsolve-row-oriented 'lps A b c)) 1.532 + `~lp-solve-forms)) 1.533 + #+end_src 1.534 + 1.535 +Now, we can use a much more functional approach to solving the 1.536 +farmer's problem: 1.537 + 1.538 +#+srcname: better-farmer 1.539 +#+begin_src clojure :results silent 1.540 +(in-ns 'pokemon.lpsolve) 1.541 +(defn better-farmer-example [] 1.542 + (lp-solve [[120 210] 1.543 + [110 30] 1.544 + [1 1]] 1.545 + [15000 1.546 + 4000 1.547 + 75] 1.548 + [143 60] 1.549 + (.setColName lps 1 "wheat") 1.550 + (.setColName lps 2 "barley") 1.551 + (.setMaxim lps) 1.552 + (results lps))) 1.553 +#+end_src 1.554 + 1.555 +#+begin_src clojure :exports both :results verbatim 1.556 +(vec (:solution (pokemon.lpsolve/better-farmer-example))) 1.557 +#+end_src 1.558 + 1.559 +#+results: 1.560 +: [["barley" 53.12499999999999] ["wheat" 21.875]] 1.561 + 1.562 +Notice that both the inputs to =better-farmer-example= and the results 1.563 +are immutable. 1.564 + 1.565 +* Using LpSolve to find Immortal Types 1.566 +** Converting the Pokemon problem into a linear form 1.567 +How can the original question about pok\eacute{}mon types be converted 1.568 +into a linear problem? 1.569 + 1.570 +Pokemon types can be considered to be vectors of numbers representing 1.571 +their susceptances to various attacking types, so Water might look 1.572 +something like this. 1.573 + 1.574 +#+begin_src clojure :results scalar :exports both 1.575 +(:water (pokemon.types/defense-strengths)) 1.576 +#+end_src 1.577 + 1.578 +#+results: 1.579 +: [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5] 1.580 + 1.581 +Where the numbers represent the susceptibility of Water to the 1.582 +attacking types in the following order: 1.583 + 1.584 +#+begin_src clojure :results output :exports both 1.585 +(clojure.pprint/pprint 1.586 + (pokemon.types/type-names)) 1.587 +#+end_src 1.588 + 1.589 +#+results: 1.590 +#+begin_example 1.591 +[:normal 1.592 + :fire 1.593 + :water 1.594 + :electric 1.595 + :grass 1.596 + :ice 1.597 + :fighting 1.598 + :poison 1.599 + :ground 1.600 + :flying 1.601 + :psychic 1.602 + :bug 1.603 + :rock 1.604 + :ghost 1.605 + :dragon 1.606 + :dark 1.607 + :steel] 1.608 +#+end_example 1.609 + 1.610 + 1.611 +So, for example, Water is /resistant/ (x0.5) against Fire, which is 1.612 +the second element in the list. 1.613 + 1.614 +To combine types, these sorts of vectors are multiplied together 1.615 +pair-wise to yield the resulting combination. 1.616 + 1.617 +Unfortunately, we need some way to add two type vectors together 1.618 +instead of multiplying them if we want to solve the problem with 1.619 +=lp_solve=. Taking the log of the vector does just the trick. 1.620 + 1.621 +If we make a matrix with each column being the log (base 2) of the 1.622 +susceptance of each type, then finding an immortal type corresponds to 1.623 +setting each constraint (the $b$ vector) to -1 (since log_2(1/2) = -1) 1.624 +and setting the constraint vector $c$ to all ones, which means that we 1.625 +want to find the immortal type which uses the least amount of types. 1.626 + 1.627 +#+srcname: pokemon-lp 1.628 +#+begin_src clojure :results silent 1.629 +(in-ns 'pokemon.lpsolve) 1.630 + 1.631 +(require 'pokemon.types) 1.632 +(require 'incanter.core) 1.633 + 1.634 +(defn log-clamp-matrix [matrix] 1.635 + ;; we have to clamp the Infinities to a more reasonable negative 1.636 + ;; value because lp_solve does not play well with infinities in its 1.637 + ;; constraint matrix. 1.638 + (map (fn [row] (map #(if (= Double/NEGATIVE_INFINITY %) -1e3 %) row)) 1.639 + (incanter.core/log2 1.640 + (incanter.core/trans 1.641 + matrix)))) 1.642 + 1.643 +;; constraint matrices 1.644 +(defn log-defense-matrix [] 1.645 + (log-clamp-matrix 1.646 + (doall (map (pokemon.types/defense-strengths) 1.647 + (pokemon.types/type-names))))) 1.648 + 1.649 +(defn log-attack-matrix [] 1.650 + (incanter.core/trans (log-defense-matrix))) 1.651 + 1.652 +;; target vectors 1.653 +(defn all-resistant [] 1.654 + (doall (map (constantly -1) (pokemon.types/type-names)))) 1.655 + 1.656 +(defn all-weak [] 1.657 + (doall (map (constantly 1) (pokemon.types/type-names)))) 1.658 + 1.659 +(defn all-neutral [] 1.660 + (doall (map (constantly 0) (pokemon.types/type-names)))) 1.661 + 1.662 + 1.663 +;; objective functions 1.664 +(defn number-of-types [] 1.665 + (doall (map (constantly 1) (pokemon.types/type-names)))) 1.666 + 1.667 +(defn set-constraints 1.668 + "sets all the constraints for an lpsolve instance to the given 1.669 + constraint. =constraint= here is one of the LpSolve constants such 1.670 + as LpSolve/EQ." 1.671 + [#^LpSolve lps constraint] 1.672 + (dorun (map (fn [index] (.setConstrType lps index constraint)) 1.673 + ;; ONE based indexing!!! 1.674 + (range 1 (inc (.getNrows lps)))))) 1.675 + 1.676 + 1.677 +(defn set-discrete 1.678 + "sets every variable in an lps problem to be a discrete rather than 1.679 + continuous variable" 1.680 + [#^LpSolve lps] 1.681 + (dorun (map (fn [index] (.setInt lps index true)) 1.682 + ;; ONE based indexing!!! 1.683 + (range 1 (inc (.getNcolumns lps)))))) 1.684 + 1.685 +(defn set-variable-names 1.686 + "sets the variable names of the problem given a vector of names" 1.687 + [#^LpSolve lps names] 1.688 + (dorun 1.689 + (map (fn [[index name]] 1.690 + (.setColName lps (inc index) (str name))) 1.691 + ;; ONE based indexing!!! 1.692 + (indexed names)))) 1.693 + 1.694 +(defn poke-solve 1.695 + ([poke-matrix target objective-function constraint min-num-types] 1.696 + ;; must have at least one type 1.697 + (let [poke-matrix 1.698 + (concat poke-matrix 1.699 + [(map (constantly 1) 1.700 + (range (count (first poke-matrix))))]) 1.701 + target (concat target [min-num-types])] 1.702 + (lp-solve poke-matrix target objective-function 1.703 + (set-constraints lps constraint) 1.704 + ;; must have more than min-num-types 1.705 + (.setConstrType lps (count target) LpSolve/GE) 1.706 + (set-discrete lps) 1.707 + (set-variable-names lps (pokemon.types/type-names)) 1.708 + (results lps)))) 1.709 + ([poke-matrix target objective-function constraint] 1.710 + ;; at least one type 1.711 + (poke-solve poke-matrix target objective-function constraint 1))) 1.712 + 1.713 +(defn solution 1.714 + "If the results of an lpsolve operation are feasible, returns the 1.715 + results. Otherwise, returns the error." 1.716 + [results] 1.717 + (if (not (= (:status results) "OPTIMAL")) 1.718 + (:status results) 1.719 + (:solution results))) 1.720 + 1.721 +#+end_src 1.722 + 1.723 +With this, we are finally able to get some results. 1.724 + 1.725 +** Results 1.726 +#+srcname: results 1.727 +#+begin_src clojure :results silent 1.728 +(in-ns 'pokemon.lpsolve) 1.729 + 1.730 +(defn best-defense-type 1.731 + "finds a type combination which is resistant to all attacks." 1.732 + [] 1.733 + (poke-solve 1.734 + (log-defense-matrix) (all-resistant) (number-of-types) LpSolve/LE)) 1.735 + 1.736 +(defn worst-attack-type 1.737 + "finds the attack type which is not-very-effective against all pure 1.738 + defending types (each single defending type is resistant to this 1.739 + attack combination" 1.740 + [] 1.741 + (poke-solve 1.742 + (log-attack-matrix) (all-resistant) (number-of-types) LpSolve/LE)) 1.743 + 1.744 +(defn worst-defense-type 1.745 + "finds a defending type that is weak to all single attacking types." 1.746 + [] 1.747 + (poke-solve 1.748 + (log-defense-matrix) (all-weak) (number-of-types) LpSolve/GE)) 1.749 + 1.750 +(defn best-attack-type 1.751 + "finds an attack type which is super effective against all single 1.752 +defending types" 1.753 + [] 1.754 + (poke-solve 1.755 + (log-attack-matrix) (all-weak) (number-of-types) LpSolve/GE)) 1.756 + 1.757 +(defn solid-defense-type 1.758 + "finds a defense type which is either neutral or resistant to all 1.759 + single attacking types" 1.760 + [] 1.761 + (poke-solve 1.762 + (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/LE)) 1.763 + 1.764 +(defn solid-attack-type 1.765 + "finds an attack type which is either neutral or super-effective to 1.766 + all single attacking types." 1.767 + [] 1.768 + (poke-solve 1.769 + (log-attack-matrix) (all-neutral) (number-of-types) LpSolve/GE)) 1.770 + 1.771 +(defn weak-defense-type 1.772 + "finds a defense type which is either neutral or weak to all single 1.773 + attacking types" 1.774 + [] 1.775 + (poke-solve 1.776 + (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/GE)) 1.777 + 1.778 +(defn neutral-defense-type 1.779 + "finds a defense type which is perfectly neutral to all attacking 1.780 + types." 1.781 + [] 1.782 + (poke-solve 1.783 + (log-defense-matrix) (all-neutral) (number-of-types) LpSolve/EQ)) 1.784 + 1.785 +#+end_src 1.786 + 1.787 +*** Strongest Attack/Defense Combinations 1.788 + 1.789 +#+begin_src clojure :results output :exports both 1.790 +(clojure.pprint/pprint 1.791 + (pokemon.lpsolve/solution (pokemon.lpsolve/best-defense-type))) 1.792 +#+end_src 1.793 + 1.794 +#+results: 1.795 +#+begin_example 1.796 +{":normal" 0.0, 1.797 + ":ground" 1.0, 1.798 + ":poison" 2.0, 1.799 + ":flying" 1.0, 1.800 + ":fighting" 0.0, 1.801 + ":dragon" 0.0, 1.802 + ":fire" 0.0, 1.803 + ":dark" 1.0, 1.804 + ":ice" 0.0, 1.805 + ":steel" 1.0, 1.806 + ":ghost" 0.0, 1.807 + ":electric" 0.0, 1.808 + ":bug" 0.0, 1.809 + ":psychic" 0.0, 1.810 + ":grass" 0.0, 1.811 + ":water" 2.0, 1.812 + ":rock" 0.0} 1.813 +#+end_example 1.814 + 1.815 +# #+results-old: 1.816 +# : [[":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]] 1.817 + 1.818 + 1.819 +This is the immortal type combination we've been looking for. By 1.820 +combining Steel, Water, Poison, and three types which each have complete 1.821 +immunities to various other types, we've created a type that is resistant to 1.822 +all attacking types. 1.823 + 1.824 +#+begin_src clojure :results output :exports both 1.825 +(clojure.pprint/pprint 1.826 + (pokemon.types/susceptibility 1.827 + [:poison :poison :water :water :steel :ground :flying :dark])) 1.828 +#+end_src 1.829 + 1.830 +#+results: 1.831 +#+begin_example 1.832 +{:water 1/2, 1.833 + :psychic 0, 1.834 + :dragon 1/2, 1.835 + :fire 1/2, 1.836 + :ice 1/2, 1.837 + :grass 1/2, 1.838 + :ghost 1/4, 1.839 + :poison 0, 1.840 + :flying 1/2, 1.841 + :normal 1/2, 1.842 + :rock 1/2, 1.843 + :electric 0, 1.844 + :ground 0, 1.845 + :fighting 1/2, 1.846 + :dark 1/4, 1.847 + :steel 1/8, 1.848 + :bug 1/8} 1.849 +#+end_example 1.850 + 1.851 +# #+results-old: 1.852 +# : {: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} 1.853 + 1.854 + 1.855 +Cool! 1.856 + 1.857 +#+begin_src clojure :results output :exports both 1.858 +(clojure.pprint/pprint 1.859 + (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type))) 1.860 +#+end_src 1.861 + 1.862 +#+results: 1.863 +#+begin_example 1.864 +{":normal" 0.0, 1.865 + ":ground" 0.0, 1.866 + ":poison" 0.0, 1.867 + ":flying" 0.0, 1.868 + ":fighting" 0.0, 1.869 + ":dragon" 0.0, 1.870 + ":fire" 0.0, 1.871 + ":dark" 1.0, 1.872 + ":ice" 0.0, 1.873 + ":steel" 0.0, 1.874 + ":ghost" 1.0, 1.875 + ":electric" 0.0, 1.876 + ":bug" 0.0, 1.877 + ":psychic" 0.0, 1.878 + ":grass" 0.0, 1.879 + ":water" 0.0, 1.880 + ":rock" 0.0} 1.881 +#+end_example 1.882 + 1.883 +Dark and Ghost are the best dual-type combo, and are resistant or 1.884 +neutral to all types. 1.885 + 1.886 +#+begin_src clojure :results output :exports both 1.887 +(clojure.pprint/pprint 1.888 + (pokemon.types/old-school 1.889 + (pokemon.lpsolve/solution (pokemon.lpsolve/solid-defense-type)))) 1.890 +#+end_src 1.891 + 1.892 +#+results: 1.893 +#+begin_example 1.894 +{":normal" 0.0, 1.895 + ":ground" 0.0, 1.896 + ":poison" 0.0, 1.897 + ":flying" 0.0, 1.898 + ":fighting" 0.0, 1.899 + ":dragon" 0.0, 1.900 + ":fire" 0.0, 1.901 + ":ice" 0.0, 1.902 + ":ghost" 1.0, 1.903 + ":electric" 0.0, 1.904 + ":bug" 0.0, 1.905 + ":psychic" 1.0, 1.906 + ":grass" 0.0, 1.907 + ":water" 0.0, 1.908 + ":rock" 0.0} 1.909 +#+end_example 1.910 + 1.911 +Ghost and Psychic are a powerful dual type combo in the original games, 1.912 +due to a glitch which made Psychic immune to Ghost type attacks, even 1.913 +though the game claims that Ghost is strong to Psychic. 1.914 + 1.915 +#+begin_src clojure :results verbatim :exports both 1.916 +(pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type)) 1.917 +#+end_src 1.918 + 1.919 +#+results: 1.920 +: INFEASIBLE 1.921 + 1.922 +#+begin_src clojure :results verbatim :exports both 1.923 +(pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type)) 1.924 +#+end_src 1.925 + 1.926 +#+results: 1.927 +: INFEASIBLE 1.928 + 1.929 + 1.930 +#+begin_src clojure :results verbatim :exports both 1.931 +(pokemon.types/old-school 1.932 + (pokemon.lpsolve/solution (pokemon.lpsolve/best-attack-type))) 1.933 +#+end_src 1.934 + 1.935 +#+results: 1.936 +: INFEASIBLE 1.937 + 1.938 + 1.939 +#+begin_src clojure :results output :exports both 1.940 +(clojure.pprint/pprint 1.941 + (pokemon.types/old-school 1.942 + (pokemon.lpsolve/solution (pokemon.lpsolve/solid-attack-type)))) 1.943 +#+end_src 1.944 + 1.945 +#+results: 1.946 +#+begin_example 1.947 +{":normal" 0.0, 1.948 + ":ground" 0.0, 1.949 + ":poison" 0.0, 1.950 + ":flying" 0.0, 1.951 + ":fighting" 0.0, 1.952 + ":dragon" 1.0, 1.953 + ":fire" 0.0, 1.954 + ":ice" 0.0, 1.955 + ":ghost" 0.0, 1.956 + ":electric" 0.0, 1.957 + ":bug" 0.0, 1.958 + ":psychic" 0.0, 1.959 + ":grass" 0.0, 1.960 + ":water" 0.0, 1.961 + ":rock" 0.0} 1.962 +#+end_example 1.963 + 1.964 +The best attacking type combination is strangely Dragon from the 1.965 +original games. It is neutral against all the original types except 1.966 +for Dragon, which it is strong against. There is no way to make an 1.967 +attacking type that is strong against every type, or even one that is 1.968 +strong or neutral against every type, in the new games. 1.969 + 1.970 + 1.971 +*** Weakest Attack/Defense Combinations 1.972 + 1.973 +#+begin_src clojure :results output :exports both 1.974 +(clojure.pprint/pprint 1.975 + (pokemon.types/old-school 1.976 + (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type)))) 1.977 +#+end_src 1.978 + 1.979 +#+results: 1.980 +#+begin_example 1.981 +{":normal" 5.0, 1.982 + ":ground" 0.0, 1.983 + ":poison" 0.0, 1.984 + ":flying" 0.0, 1.985 + ":fighting" 0.0, 1.986 + ":dragon" 0.0, 1.987 + ":fire" 1.0, 1.988 + ":ice" 2.0, 1.989 + ":ghost" 1.0, 1.990 + ":electric" 1.0, 1.991 + ":bug" 1.0, 1.992 + ":psychic" 0.0, 1.993 + ":grass" 3.0, 1.994 + ":water" 2.0, 1.995 + ":rock" 0.0} 1.996 +#+end_example 1.997 + 1.998 +# #+results-old: 1.999 +# : [[":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]] 1.1000 + 1.1001 +#+begin_src clojure :results output :exports both 1.1002 +(clojure.pprint/pprint 1.1003 + (pokemon.lpsolve/solution (pokemon.lpsolve/worst-attack-type))) 1.1004 +#+end_src 1.1005 + 1.1006 +#+results: 1.1007 +#+begin_example 1.1008 +{":normal" 4.0, 1.1009 + ":ground" 1.0, 1.1010 + ":poison" 1.0, 1.1011 + ":flying" 0.0, 1.1012 + ":fighting" 1.0, 1.1013 + ":dragon" 0.0, 1.1014 + ":fire" 0.0, 1.1015 + ":dark" 0.0, 1.1016 + ":ice" 4.0, 1.1017 + ":steel" 0.0, 1.1018 + ":ghost" 1.0, 1.1019 + ":electric" 3.0, 1.1020 + ":bug" 0.0, 1.1021 + ":psychic" 1.0, 1.1022 + ":grass" 1.0, 1.1023 + ":water" 1.0, 1.1024 + ":rock" 2.0} 1.1025 +#+end_example 1.1026 + 1.1027 +# #+results-old: 1.1028 +# : [[":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]] 1.1029 + 1.1030 + 1.1031 +This is an extremely interesting type combination, in that it uses 1.1032 +quite a few types. 1.1033 + 1.1034 +#+begin_src clojure :results verbatim :exports both 1.1035 +(reduce + (vals (:solution (pokemon.lpsolve/worst-attack-type)))) 1.1036 +#+end_src 1.1037 + 1.1038 +#+results: 1.1039 +: 20.0 1.1040 + 1.1041 +20 types is the /minimum/ number of types before the attacking 1.1042 +combination is not-very-effective or worse against all defending 1.1043 +types. This would probably have been impossible to discover using 1.1044 +best-first search, since it involves such an intricate type 1.1045 +combination. 1.1046 + 1.1047 +It's so interesting that it takes 20 types to make an attack type that 1.1048 +is weak to all types that the combination merits further investigation. 1.1049 + 1.1050 +Unfortunately, all of the tools that we've written so far are focused 1.1051 +on defense type combinations. However, it is possible to make every 1.1052 +tool attack-oriented via a simple macro. 1.1053 + 1.1054 +#+srcname: attack-oriented 1.1055 +#+begin_src clojure :results silent 1.1056 +(in-ns 'pokemon.lpsolve) 1.1057 + 1.1058 +(defmacro attack-mode [& forms] 1.1059 + `(let [attack-strengths# pokemon.types/attack-strengths 1.1060 + defense-strengths# pokemon.types/defense-strengths] 1.1061 + (binding [pokemon.types/attack-strengths 1.1062 + defense-strengths# 1.1063 + pokemon.types/defense-strengths 1.1064 + attack-strengths#] 1.1065 + ~@forms))) 1.1066 +#+end_src 1.1067 + 1.1068 +Now all the tools from =pokemon.types= will work for attack 1.1069 +combinations. 1.1070 + 1.1071 +#+begin_src clojure :results output :exports both 1.1072 +(clojure.pprint/pprint 1.1073 + (pokemon.types/susceptibility [:water])) 1.1074 +#+end_src 1.1075 + 1.1076 +#+results: 1.1077 +#+begin_example 1.1078 +{:water 1/2, 1.1079 + :psychic 1, 1.1080 + :dragon 1, 1.1081 + :fire 1/2, 1.1082 + :ice 1/2, 1.1083 + :grass 2, 1.1084 + :ghost 1, 1.1085 + :poison 1, 1.1086 + :flying 1, 1.1087 + :normal 1, 1.1088 + :rock 1, 1.1089 + :electric 2, 1.1090 + :ground 1, 1.1091 + :fighting 1, 1.1092 + :dark 1, 1.1093 + :steel 1/2, 1.1094 + :bug 1} 1.1095 +#+end_example 1.1096 + 1.1097 + 1.1098 +#+begin_src clojure :results output :exports both 1.1099 +(clojure.pprint/pprint 1.1100 + (pokemon.lpsolve/attack-mode 1.1101 + (pokemon.types/susceptibility [:water]))) 1.1102 +#+end_src 1.1103 + 1.1104 +#+results: 1.1105 +#+begin_example 1.1106 +{:water 1/2, 1.1107 + :psychic 1, 1.1108 + :dragon 1/2, 1.1109 + :fire 2, 1.1110 + :ice 1, 1.1111 + :grass 1/2, 1.1112 + :ghost 1, 1.1113 + :poison 1, 1.1114 + :flying 1, 1.1115 + :normal 1, 1.1116 + :rock 2, 1.1117 + :electric 1, 1.1118 + :ground 2, 1.1119 + :fighting 1, 1.1120 + :dark 1, 1.1121 + :steel 1, 1.1122 + :bug 1} 1.1123 +#+end_example 1.1124 + 1.1125 +Now =pokemon.types/susceptibility= reports the /attack-type/ 1.1126 +combination's effectiveness against other types. 1.1127 + 1.1128 +The 20 type combo achieves its goal in a very clever way. 1.1129 + 1.1130 +First, it weakens its effectiveness to other types at the expense of 1.1131 +making it very strong against flying. 1.1132 + 1.1133 +#+begin_src clojure :results output :exports both 1.1134 +(clojure.pprint/pprint 1.1135 + (pokemon.lpsolve/attack-mode 1.1136 + (pokemon.types/susceptibility 1.1137 + [:normal :normal :normal :normal 1.1138 + :ice :ice :ice :ice 1.1139 + :electric :electric :electric 1.1140 + :rock :rock]))) 1.1141 +#+end_src 1.1142 + 1.1143 +#+results: 1.1144 +#+begin_example 1.1145 +{:water 1/2, 1.1146 + :psychic 1, 1.1147 + :dragon 2, 1.1148 + :fire 1/4, 1.1149 + :ice 1/4, 1.1150 + :grass 2, 1.1151 + :ghost 0, 1.1152 + :poison 1, 1.1153 + :flying 512, 1.1154 + :normal 1, 1.1155 + :rock 1/16, 1.1156 + :electric 1/8, 1.1157 + :ground 0, 1.1158 + :fighting 1/4, 1.1159 + :dark 1, 1.1160 + :steel 1/1024, 1.1161 + :bug 4} 1.1162 +#+end_example 1.1163 + 1.1164 +Then, it removes it's strengths against Flying, Normal, and Fighting 1.1165 +by adding Ghost and Ground. 1.1166 + 1.1167 +#+begin_src clojure :results output :exports both 1.1168 +(clojure.pprint/pprint 1.1169 + (pokemon.lpsolve/attack-mode 1.1170 + (pokemon.types/susceptibility 1.1171 + [:normal :normal :normal :normal 1.1172 + :ice :ice :ice :ice 1.1173 + :electric :electric :electric 1.1174 + :rock :rock 1.1175 + ;; Spot resistances 1.1176 + :ghost :ground]))) 1.1177 +#+end_src 1.1178 + 1.1179 +#+results: 1.1180 +#+begin_example 1.1181 +{:water 1/2, 1.1182 + :psychic 2, 1.1183 + :dragon 2, 1.1184 + :fire 1/2, 1.1185 + :ice 1/4, 1.1186 + :grass 1, 1.1187 + :ghost 0, 1.1188 + :poison 2, 1.1189 + :flying 0, 1.1190 + :normal 0, 1.1191 + :rock 1/8, 1.1192 + :electric 1/4, 1.1193 + :ground 0, 1.1194 + :fighting 1/4, 1.1195 + :dark 1/2, 1.1196 + :steel 1/1024, 1.1197 + :bug 2} 1.1198 +#+end_example 1.1199 + 1.1200 +Adding the pair Psychic and Fighting takes care of its strength 1.1201 +against Psychic and makes it ineffective against Dark, which is immune 1.1202 +to Psychic. 1.1203 + 1.1204 +Adding the pair Grass and Poison makes takes care of its strength 1.1205 +against poison and makes it ineffective against Steel, which is immune 1.1206 +to poison. 1.1207 + 1.1208 +#+begin_src clojure :results output :exports both 1.1209 +(clojure.pprint/pprint 1.1210 + (pokemon.lpsolve/attack-mode 1.1211 + (pokemon.types/susceptibility 1.1212 + [;; setup 1.1213 + :normal :normal :normal :normal 1.1214 + :ice :ice :ice :ice 1.1215 + :electric :electric :electric 1.1216 + :rock :rock 1.1217 + ;; Spot resistances 1.1218 + :ghost :ground 1.1219 + ;; Pair resistances 1.1220 + :psychic :fighting 1.1221 + :grass :poison]))) 1.1222 +#+end_src 1.1223 + 1.1224 +#+results: 1.1225 +#+begin_example 1.1226 +{:water 1, 1.1227 + :psychic 1/2, 1.1228 + :dragon 1, 1.1229 + :fire 1/4, 1.1230 + :ice 1/2, 1.1231 + :grass 1, 1.1232 + :ghost 0, 1.1233 + :poison 1/2, 1.1234 + :flying 0, 1.1235 + :normal 0, 1.1236 + :rock 1/4, 1.1237 + :electric 1/4, 1.1238 + :ground 0, 1.1239 + :fighting 1/2, 1.1240 + :dark 0, 1.1241 + :steel 0, 1.1242 + :bug 1/2} 1.1243 +#+end_example 1.1244 + 1.1245 +Can you see the final step? 1.1246 + 1.1247 +It's adding the Water type, which is weak against Water and Dragon and 1.1248 +strong against Rock and Fire. 1.1249 + 1.1250 +#+begin_src clojure :results output :exports both 1.1251 +(clojure.pprint/pprint 1.1252 + (pokemon.lpsolve/attack-mode 1.1253 + (pokemon.types/susceptibility 1.1254 + [;; setup 1.1255 + :normal :normal :normal :normal 1.1256 + :ice :ice :ice :ice 1.1257 + :electric :electric :electric 1.1258 + :rock :rock 1.1259 + ;; Spot resistances 1.1260 + :ghost :ground 1.1261 + ;; Pair resistances 1.1262 + :psychic :fighting 1.1263 + :grass :poison 1.1264 + ;; completion 1.1265 + :water]))) 1.1266 +#+end_src 1.1267 + 1.1268 +#+results: 1.1269 +#+begin_example 1.1270 +{:water 1/2, 1.1271 + :psychic 1/2, 1.1272 + :dragon 1/2, 1.1273 + :fire 1/2, 1.1274 + :ice 1/2, 1.1275 + :grass 1/2, 1.1276 + :ghost 0, 1.1277 + :poison 1/2, 1.1278 + :flying 0, 1.1279 + :normal 0, 1.1280 + :rock 1/2, 1.1281 + :electric 1/4, 1.1282 + :ground 0, 1.1283 + :fighting 1/2, 1.1284 + :dark 0, 1.1285 + :steel 0, 1.1286 + :bug 1/2} 1.1287 +#+end_example 1.1288 + 1.1289 +Which makes a particularly beautiful combination which is ineffective 1.1290 +against all defending types. 1.1291 + 1.1292 + 1.1293 +# #+begin_src clojure :results scalar :exports both 1.1294 +# (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]))))) 1.1295 +# #+end_src 1.1296 + 1.1297 +# #+results: 1.1298 +# | [: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] | 1.1299 + 1.1300 + 1.1301 +Is there anything else that's interesting? 1.1302 + 1.1303 +#+begin_src clojure :exports both 1.1304 +(pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type)) 1.1305 +#+end_src 1.1306 + 1.1307 +#+results: 1.1308 +: INFEASIBLE 1.1309 + 1.1310 +#+begin_src clojure :exports both 1.1311 +(pokemon.types/old-school 1.1312 + (pokemon.lpsolve/solution (pokemon.lpsolve/worst-defense-type))) 1.1313 +#+end_src 1.1314 + 1.1315 +#+results: 1.1316 +: INFEASIBLE 1.1317 + 1.1318 +#+begin_src clojure :exports both 1.1319 +(pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type)) 1.1320 +#+end_src 1.1321 + 1.1322 +#+results: 1.1323 +: INFEASIBLE 1.1324 + 1.1325 +#+begin_src clojure :exports both 1.1326 +(pokemon.types/old-school 1.1327 + (pokemon.lpsolve/solution (pokemon.lpsolve/weak-defense-type))) 1.1328 +#+end_src 1.1329 + 1.1330 +#+results: 1.1331 +: INFEASIBLE 1.1332 + 1.1333 +#+begin_src clojure :exports both 1.1334 +(pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type)) 1.1335 +#+end_src 1.1336 + 1.1337 +#+results: 1.1338 +: INFEASIBLE 1.1339 + 1.1340 +#+begin_src clojure :exports both 1.1341 +(pokemon.types/old-school 1.1342 + (pokemon.lpsolve/solution (pokemon.lpsolve/neutral-defense-type))) 1.1343 +#+end_src 1.1344 + 1.1345 +#+results: 1.1346 +: INFEASIBLE 1.1347 + 1.1348 +There is no way to produce a defense-type that is weak to all types. 1.1349 +This is probably because there are many types that are completely 1.1350 +immune to some types, such as Flying, which is immune to Ground. A 1.1351 +perfectly weak type could not use any of these types. 1.1352 + 1.1353 +* Summary 1.1354 + 1.1355 +Overall, the pok\eacute{}mon type system is slanted more towards defense 1.1356 +rather than offense. While it is possible to create superior 1.1357 +defensive types and exceptionally weak attack types, it is not possible to 1.1358 +create exceptionally weak defensive types or very powerful attack 1.1359 +types. 1.1360 + 1.1361 +Using the =lp_solve= library was more complicated than the best-first 1.1362 +search, but yielded results quickly and efficiently. Expressing the 1.1363 +problem in a linear form does have its drawbacks, however --- it's 1.1364 +hard to ask questions such as "what is the best 3-type defensive combo 1.1365 +in terms of susceptibility?", since susceptibility is not a linear 1.1366 +function of a combo's types. It is also hard to get all the solutions 1.1367 +to a particular problem, such as all the pokemon type combinations of 1.1368 +length 8 which are immortal defense types. 1.1369 + 1.1370 + 1.1371 +* COMMENT main-program 1.1372 +#+begin_src clojure :tangle ../src/pokemon/lpsolve.clj :noweb yes :exports none 1.1373 +<<intro>> 1.1374 +<<body>> 1.1375 +<<declares>> 1.1376 +<<memory-management>> 1.1377 +<<get-results>> 1.1378 +<<solve>> 1.1379 +<<farmer-example>> 1.1380 +<<lp-solve>> 1.1381 +<<better-farmer>> 1.1382 +<<pokemon-lp>> 1.1383 +<<results>> 1.1384 +<<attack-oriented>> 1.1385 +#+end_src 1.1386 + 1.1387 + 1.1388 +* COMMENT Stuff to do. 1.1389 +** TODO fix namespaces to not use rlm.light-base 1.1390 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/org/types.org Sun Oct 16 06:57:42 2011 -0700 2.3 @@ -0,0 +1,646 @@ 2.4 +#+TITLE: Breadth-first Search for Effective Pokemon Types 2.5 +#+AUTHOR: Robert McIntyre & Dylan Holmes 2.6 +#+EMAIL: rlm@mit.edu 2.7 +#+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js" 2.8 +#+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" /> 2.9 +#+OPTIONS: H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t 2.10 +#+SETUPFILE: ../templates/level-0.org 2.11 +#+INCLUDE: ../templates/level-0.org 2.12 + 2.13 + 2.14 +* The Pok\eacute{}mon Type System 2.15 + 2.16 +The Pok\eacute{}mon type system consists of seventeen different 2.17 +\ldquo{}types\rdquo{} (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, 2.18 +Fire, Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, 2.19 +and Steel) that interact like an extended version of 2.20 +Rock-Paper-Scissors: for example, the Fire type is strong against the 2.21 +Grass type but weak against the Water type. In the table below, we've 2.22 +recorded the relative strengths of each of the types in the 2.23 +Pok\eacute{}mon type system; the number in each cell indicates how 2.24 +effective an attack of the type in the row is against a 2.25 +Pok\eacute{}mon of the type in the column. We call these numbers 2.26 +/susceptibilities/ because we are interested in the column totals, 2.27 +which quantify the overall vulnerability of each Pok\eacute{}mon type 2.28 +(as opposed to the row totals, which quantify the overall 2.29 +effectiveness of each attack type.) 2.30 + 2.31 +In the Pok\eacute{}mon games, only four susceptibility values (two, 2.32 +one, one-half, and zero) occur. These numbers indicate particularly 2.33 +high susceptibility, average susceptibility, particularly low 2.34 +susceptibility, and no susceptibility 2.35 +(immunity). Here is the entire Pok\eacute{}mon type chart. 2.36 + 2.37 + 2.38 + 2.39 +** TODO add the pokemon chart in a pretty form 2.40 + 2.41 +* COMMENT Pokemon Table Data 2.42 + 2.43 +#+caption: The rows are attack types, while the columns are defense types. To see the multiplier for a pokemon attack against a certain type, follow the row for the attack type to the column of the defending type. 2.44 +#+label: pokemon-matchups 2.45 +#+tblname: pokemon-table-gen-two 2.46 +| | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel | 2.47 +|----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------| 2.48 +| normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 | 1 | .5 | 2.49 +| fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 1 | 2 | 2.50 +| water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | 1 | 2.51 +| electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 | 1 | 1 | 2.52 +| grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 | 1 | .5 | 2.53 +| ice | 1 | .5 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 2.54 +| fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 | 2 | 2 | 2.55 +| poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 1 | .5 | .5 | 1 | 1 | 0 | 2.56 +| ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 | 1 | 2 | 2.57 +| flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 | 1 | .5 | 2.58 +| psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 | 0 | .5 | 2.59 +| bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | .5 | 1 | .5 | 2 | 1 | 1 | .5 | 1 | 2 | .5 | 2.60 +| rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | .5 | 2.61 +| ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 | 2.62 +| dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 2.63 +| dark | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 | 2.64 +| steel | 1 | .5 | .5 | .5 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | .5 | 2.65 + 2.66 +#+caption: this is the old table from generation 1. The differences are: dark and ghost are missing, Bus is super against Poison, Poison is super against Bug, Bug is regularly effective against Ghost, and Ice is normally effective against Fire. Ghost is not effective against psychic. 2.67 +#+label: pokemon-matchups-gen-1 2.68 +#+tblname: pokemon-table-gen-one 2.69 +| | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | 2.70 +|----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------| 2.71 +| normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 | 2.72 +| fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2.73 +| water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 | 2.74 +| electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 | 2.75 +| grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 | 2.76 +| ice | 1 | 1 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 2.77 +| fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 | 2.78 +| poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 2 | .5 | .5 | 1 | 2.79 +| ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 | 2.80 +| flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 | 2.81 +| psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 | 2.82 +| bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | 2 | 1 | .5 | 2 | 1 | 1 | 0 | 1 | 2.83 +| rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 2.84 +| ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 1 | 2.85 +| dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2.86 + 2.87 +* Representing the Data 2.88 + 2.89 +After creating the Pok\eacute{}mon types namespace, we store the table 2.90 +of susceptibilities in =pokemon-table-gen-one= and 2.91 +=pokemon-table-gen-two=, each of which is a simple vector of 2.92 +vectors. Because a vector of vectors can be cumbersome, we do not 2.93 +access the tables directly; instead, we use the derivative structures 2.94 +=attack-strengths= and =defense-strengths=, which are functions which 2.95 +return hash-maps associating each row (respectively column) of the 2.96 +table with its corresponding Pok\eacute{}mon type. 2.97 + 2.98 + 2.99 + 2.100 +#+srcname: header 2.101 +#+begin_src clojure :results silent 2.102 +(ns pokemon.types 2.103 + (:use rlm.ns-rlm)) 2.104 +(rlm.ns-rlm/ns-clone rlm.light-base) 2.105 +(use 'clojure.set) 2.106 +#+end_src 2.107 + 2.108 +#+srcname: data(pokemon-table-gen-one=pokemon-table-gen-one, pokemon-table-gen-two=pokemon-table-gen-two) 2.109 +#+begin_src clojure :results silent 2.110 +(in-ns 'pokemon.types) 2.111 +;; record type strengths as a vector of vectors 2.112 +(def pokemon-gen-one pokemon-table-gen-one) 2.113 +(def pokemon-gen-two pokemon-table-gen-two) 2.114 + 2.115 +(defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two)))) 2.116 + 2.117 +(defn attack-strengths [] 2.118 + (zipmap 2.119 + (type-names) 2.120 + (map (comp vec rest) pokemon-gen-two))) 2.121 + 2.122 +(defn defense-strengths [] 2.123 + (zipmap (type-names) 2.124 + (map 2.125 + (apply juxt (map (attack-strengths) (type-names))) 2.126 + (range (count (type-names)))))) 2.127 +#+end_src 2.128 + 2.129 +#+begin_src clojure :results output :exports both 2.130 +(clojure.pprint/pprint pokemon.types/pokemon-gen-two) 2.131 +#+end_src 2.132 + 2.133 +#+results: 2.134 +#+begin_example 2.135 +(("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5) 2.136 + ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2) 2.137 + ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1) 2.138 + ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1) 2.139 + ("grass" 1 0.5 2 1 0.5 1 1 0.5 2 0.5 1 0.5 2 1 0.5 1 0.5) 2.140 + ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5) 2.141 + ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2) 2.142 + ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0) 2.143 + ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2) 2.144 + ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5) 2.145 + ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5) 2.146 + ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5) 2.147 + ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5) 2.148 + ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5) 2.149 + ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5) 2.150 + ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5) 2.151 + ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5)) 2.152 +#+end_example 2.153 + 2.154 +=pokemon-gen-two= is a simple list-of-list data structure. 2.155 + 2.156 +#+begin_src clojure :results output :exports both 2.157 +(clojure.pprint/pprint (pokemon.types/defense-strengths)) 2.158 +#+end_src 2.159 + 2.160 +#+results: 2.161 +#+begin_example 2.162 +{:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5], 2.163 + :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1], 2.164 + :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1], 2.165 + :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5], 2.166 + :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2], 2.167 + :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1], 2.168 + :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1], 2.169 + :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1], 2.170 + :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1], 2.171 + :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1], 2.172 + :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2], 2.173 + :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5], 2.174 + :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1], 2.175 + :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1], 2.176 + :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1], 2.177 + :steel [0.5 2 1 1 0.5 0.5 2 0 2 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5], 2.178 + :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]} 2.179 +#+end_example 2.180 + 2.181 +=defense-strengths= is a more convenient form of =pokemon-gen-two=, with key/value pair access. 2.182 + 2.183 +* Interfacing with the Data 2.184 +#+srcname: types 2.185 +#+begin_src clojure :results silent 2.186 +(in-ns 'pokemon.types) 2.187 + 2.188 +(defn multitypes "All combinations of up to n types" [n] 2.189 + (vec 2.190 + (map vec 2.191 + (reduce concat 2.192 + (map (partial combinations (type-names)) 2.193 + (range 1 (inc n))))))) 2.194 + 2.195 +(defn susceptibility ;; susceptibility-map 2.196 + "Hash-map of the susceptibilities of the given type combination 2.197 + to each type of attack" 2.198 + [pkmn-types] 2.199 + (rlm.map-utils/map-vals 2.200 + clojure.core/rationalize 2.201 + (apply hash-map 2.202 + (interleave (type-names) 2.203 + (apply (partial map *) 2.204 + (map (defense-strengths) pkmn-types)))))) 2.205 + 2.206 +(defn susceptance ;; susceptibility 2.207 + "The cumulative susceptibility of the given type combination" 2.208 + [types] 2.209 + (reduce + (map sqr (vals (susceptibility types))))) 2.210 +#+end_src 2.211 + 2.212 +* Best-First Search 2.213 + 2.214 +I'd like to find type combinations that are interesting, but the total 2.215 +number of combinations gets huge as we begin to consider more 2.216 +types. For example, the total possible number of type combinations 2.217 +given just 8 possible types is: 17^{8} = 6975757441 combinations. 2.218 +Therefore, it's prudent to use search. 2.219 + 2.220 +These functions are a simple implementation of best-first search in 2.221 +clojure. The idea to start off with a collection of nodes and some way 2.222 +of finding the best node, and to always expand the best node at every 2.223 +step. 2.224 + 2.225 +#+srcname: search 2.226 +#+begin_src clojure :results silent 2.227 +(in-ns 'pokemon.types) 2.228 + 2.229 +(defn comparatize 2.230 + "Define a comparator which uses the numerical outputs of fn as its criterion. 2.231 + Objects are sorted in increasing numerical order. Objects with the same fn-value 2.232 + are further compared by clojure.core/compare." 2.233 + [fun] 2.234 + (fn [a b] 2.235 + (let [val-a (fun a) 2.236 + val-b (fun b)] 2.237 + (cond 2.238 + ;; if the function cannot differentiate the two values 2.239 + ;; then compare the two values using clojure.core/compare 2.240 + (= val-a val-b) (compare a b) 2.241 + true 2.242 + ;; LOWER values of the function are preferred 2.243 + (compare (- val-a val-b) 0))))) 2.244 + 2.245 +(defn-memo best-first-step [successors [visited unvisited]] 2.246 + (cond (empty? unvisited) nil 2.247 + true 2.248 + (let [best-node (first unvisited) 2.249 + visited* (conj visited best-node) 2.250 + unvisited* 2.251 + (difference 2.252 + (union unvisited (set (successors best-node))) 2.253 + visited*)] 2.254 + (println best-node) 2.255 + [visited* unvisited*]))) 2.256 + 2.257 +;; memoize partial from core so that for example 2.258 +;; (= (partial + 1) (partial + 1)) 2.259 +;; this way, best first search can take advantage of the memoization 2.260 +;; of best-first step 2.261 +(undef partial) 2.262 +(def partial (memoize clojure.core/partial)) 2.263 + 2.264 +(defn best-first-search 2.265 + "Searches through a network of alternatives, pursuing 2.266 +initially-promising positions first. Comparator defines which 2.267 +positions are more promising, successors produces a list of improved 2.268 +positions from the given position (if any exist), and initial-nodes is 2.269 +a list of starting positions. Returns a lazy sequence of search results 2.270 + [visited-nodes unvisited-nodes], which terminates when 2.271 +there are no remaining unvisited positions." 2.272 + [comparator successors initial-nodes] 2.273 + (let [initial-nodes 2.274 + (apply (partial sorted-set-by comparator) initial-nodes) 2.275 + initial-visited-nodes (sorted-set-by comparator) 2.276 + step (partial best-first-step successors)] 2.277 + (take-while 2.278 + (comp not nil?) 2.279 + (iterate step [initial-visited-nodes initial-nodes])))) 2.280 + 2.281 +#+end_src 2.282 + 2.283 + 2.284 +Now that we have a basic best-first-search, it's convenient to write a 2.285 +few pokemon-type specific convenience functions. 2.286 + 2.287 +#+srcname: pokemon-search 2.288 +#+begin_src clojure :results silent 2.289 +(in-ns 'pokemon.types) 2.290 +(defvar type-compare (comparatize susceptance) 2.291 + "compare two type combinations wrt their susceptibilities") 2.292 + 2.293 +(defn type-successors 2.294 + "Return the set of types that can be made by appending a single type 2.295 +to the given combination." 2.296 + [type] 2.297 + (if (nil? type) '() 2.298 + (set (map (comp vec sort (partial into type)) (multitypes 1))))) 2.299 + 2.300 +(defn immortal? 2.301 + "A type combo is immortal if it is resistant or invulnerable to 2.302 + every pokemon type. This is because that set of types can just be 2.303 + repeated to achieve as low a susceptance as desired" 2.304 + [type] 2.305 + (every? (partial > 1) (vals (susceptibility type)))) 2.306 + 2.307 +(defn type-successors* 2.308 + "Stop expanding a type if it's immortal, or if it is longer than or 2.309 +equal to limit-size. Also, only return type additions that are 2.310 +strictly better than the initial type." 2.311 + [limit-size type] 2.312 + (if (or (<= limit-size (count type)) (immortal? type)) '() 2.313 + (set (filter #(< 0 (type-compare type %)) (type-successors type))))) 2.314 + 2.315 +(defn pokemon-type-search 2.316 + "Search among type-combos no greater than length n, limited by limit 2.317 +steps of best-first-search." 2.318 + ([n] (pokemon-type-search n Integer/MAX_VALUE)) 2.319 + ([n limit] 2.320 + (first (last 2.321 + (take 2.322 + limit 2.323 + (best-first-search 2.324 + type-compare 2.325 + (partial type-successors* n) 2.326 + (multitypes 1))))))) 2.327 + 2.328 +(defvar immortals 2.329 + (comp (partial filter immortal?) pokemon-type-search) 2.330 + "find all the immortal pokemon types ") 2.331 + 2.332 +#+end_src 2.333 + 2.334 +Because there are so many type combinations, it's important to narrow 2.335 +down the results as much as possible. That is why =type-successors*= 2.336 +only returns types that are actually better than the type it is given. 2.337 + 2.338 +Best-first search can get caught optimizing a single type forever, so 2.339 +it's also important to limit the search space to be finite by setting 2.340 +an upper bound on the length of a type combo. 2.341 + 2.342 +* Results 2.343 +** The best dual-type combo 2.344 + 2.345 +#+begin_src clojure :results cache verbatim :exports both 2.346 +(first (pokemon.types/pokemon-type-search 2)) 2.347 +#+end_src 2.348 + 2.349 +#+results: 2.350 +: [:dark :ghost] 2.351 + 2.352 +Dark and Ghost, which additionally has the property of having no 2.353 + weaknesses to any other type, is the best type combo in terms of 2.354 + susceptance. 2.355 + 2.356 +The Dark and Steel types were introduced many years after 2.357 +pok\eacute{}mon started. In addition to the additional types, the 2.358 +pok\eacute{}mon games gained a few new rules concerning some of the 2.359 +matchups of the original types. Therefore, it's also interesting to see what 2.360 +type combination was most powerful before those types and new rules were introduced. 2.361 + 2.362 +The easiest way to do this with my setup is to just rebind the 2.363 +=pokemon-gen-two= table to the =pokemon-gen-one= table. Since 2.364 +everything that references this variable is a function and we're not 2.365 +doing anything too crazy with lazy-sequences and late-binding, this 2.366 +simple macro will do the job. 2.367 + 2.368 +#+srcname: old-school 2.369 +#+begin_src clojure :results silent 2.370 +(in-ns 'pokemon.types) 2.371 + 2.372 +(defmacro old-school 2.373 + [& forms] 2.374 + `(binding [pokemon-gen-two pokemon-gen-one] ~@forms)) 2.375 +#+end_src 2.376 + 2.377 +Using the =old-school= macro, it's easy to find answers for the 2.378 +original 15 pokemon types as well as the expanded pokemon types 2.379 +introduced later. 2.380 + 2.381 +#+begin_src clojure :results verbatim :exports both :cache yes 2.382 +(pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2))) 2.383 +#+end_src 2.384 + 2.385 +#+results[f43470fdf460ed546e9c57879abc9eda56da129f]: 2.386 +: [:ghost :psychic] 2.387 + 2.388 +Ghost and Psychic also manages to have no weaknesses to any of the original 2.389 +types. 2.390 + 2.391 +#+begin_src clojure :results output :exports both 2.392 +(clojure.pprint/pprint 2.393 + (pokemon.types/old-school 2.394 + (pokemon.types/susceptibility [:ghost :psychic]))) 2.395 +#+end_src 2.396 + 2.397 +#+results: 2.398 +#+begin_example 2.399 +{:water 1, 2.400 + :psychic 1/2, 2.401 + :dragon 1, 2.402 + :fire 1, 2.403 + :ice 1, 2.404 + :grass 1, 2.405 + :ghost 0, 2.406 + :poison 1/2, 2.407 + :flying 1, 2.408 + :normal 0, 2.409 + :rock 1, 2.410 + :electric 1, 2.411 + :ground 1, 2.412 + :fighting 0, 2.413 + :bug 0} 2.414 +#+end_example 2.415 + 2.416 +** An Immortal Type 2.417 +It's possible to quickly find an immortal type by giving the search 2.418 +a long enough maximum type length. 50 rounds of search with a max 2.419 +type limit of 10 is enough to find an immortal type. 2.420 + 2.421 +#+begin_src clojure :results scalar :exports both 2.422 +(first (pokemon.types/pokemon-type-search 10 50)) 2.423 +#+end_src 2.424 + 2.425 +#+results: 2.426 +: [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water] 2.427 + 2.428 + 2.429 +#+begin_src clojure :results output :exports both 2.430 +(clojure.pprint/pprint 2.431 + (pokemon.types/susceptibility 2.432 + [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water])) 2.433 +#+end_src 2.434 + 2.435 +#+results: 2.436 +#+begin_example 2.437 +{:water 1/4, 2.438 + :psychic 1/4, 2.439 + :dragon 1/2, 2.440 + :fire 1/2, 2.441 + :ice 1/2, 2.442 + :grass 1/8, 2.443 + :ghost 1/2, 2.444 + :poison 0, 2.445 + :flying 1/2, 2.446 + :normal 0, 2.447 + :rock 1/2, 2.448 + :electric 0, 2.449 + :ground 0, 2.450 + :fighting 0, 2.451 + :dark 1/2, 2.452 + :steel 1/32, 2.453 + :bug 1/16} 2.454 +#+end_example 2.455 + 2.456 +** Explanations for Common Pok\eacute{}mon Strategies 2.457 + 2.458 +Many people start out a battle with either a normal pok\eacute{}mon or an 2.459 +electric pok\eacute{}mon, and here's some justification for that choice. 2.460 + 2.461 +#+srcname: weaknesses 2.462 +#+begin_src clojure :results silent 2.463 +(in-ns 'pokemon.types) 2.464 +(defn critical-weaknesses [type] 2.465 + (count (filter #(> % 1) (vals (susceptibility type))))) 2.466 +#+end_src 2.467 + 2.468 +#+begin_src clojure :exports both :results output 2.469 +(clojure.pprint/pprint 2.470 + (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1))) 2.471 +#+end_src 2.472 + 2.473 +#+results: 2.474 +#+begin_example 2.475 +([:normal] 2.476 + [:electric] 2.477 + [:water] 2.478 + [:fighting] 2.479 + [:poison] 2.480 + [:ghost] 2.481 + [:dragon] 2.482 + [:dark] 2.483 + [:fire] 2.484 + [:ground] 2.485 + [:flying] 2.486 + [:psychic] 2.487 + [:bug] 2.488 + [:steel] 2.489 + [:ice] 2.490 + [:grass] 2.491 + [:rock]) 2.492 +#+end_example 2.493 + 2.494 +Electric and Normal are among the best types with which to start the 2.495 +game, since they have the fewest weaknesses among all the types. 2.496 + 2.497 +At the beginning of the pok\eacute{}mon games, players are given a choice 2.498 +between the Fire pok\eacute{}mon Charmander, the Water pok\eacute{}mon Squirtle, or 2.499 +the Grass/Poison pok\eacute{}mon Bulbasaur. 2.500 + 2.501 +#+begin_src clojure :exports both :results verbatim 2.502 +(sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]]) 2.503 +#+end_src 2.504 + 2.505 +#+results: 2.506 +: ([:water] [:fire] [:grass :poison]) 2.507 + 2.508 +As can be seen, the Water pok\eacute{}mon Squirtle is the most solid 2.509 +choice starting out, insofar as susceptance is concerned. 2.510 + 2.511 +** The Worst Pok\eacute{}mon Types 2.512 + 2.513 +#+srcname: weak-types 2.514 +#+begin_src clojure :results silent 2.515 +(in-ns 'pokemon.types) 2.516 + 2.517 +(defn type-compare-weak 2.518 + "compare first by total number of critical-weaknesses, 2.519 + then by overall susceptance, favoring weaker types." 2.520 + [type-1 type-2] 2.521 + (let [measure (memoize (juxt critical-weaknesses susceptance))] 2.522 + (if (= (measure type-2) (measure type-1)) 2.523 + (compare type-2 type-1) 2.524 + (compare (measure type-2) (measure type-1))))) 2.525 + 2.526 +(defn resistant? 2.527 + "might as well get rid of types that are resistant to any type" 2.528 + [type] 2.529 + (not (every? #(< 0 %) (vals (susceptibility type))))) 2.530 + 2.531 +(defn type-successors-weak 2.532 + [limit type] 2.533 + (set (if (<= limit (count type)) '() 2.534 + (filter #(< 0 (type-compare-weak type %)) 2.535 + (remove resistant? (type-successors type)))))) 2.536 + 2.537 +(defn pokemon-type-search-weak 2.538 + "Search among type-combos no greater than length n, limited by limit 2.539 +steps of best-first-search." 2.540 + ([n] (pokemon-type-search-weak n Integer/MAX_VALUE)) 2.541 + ([n limit] 2.542 + (first (last 2.543 + (take 2.544 + limit 2.545 + (best-first-search 2.546 + type-compare-weak 2.547 + (partial type-successors-weak n) 2.548 + (multitypes 1))))))) 2.549 +#+end_src 2.550 + 2.551 + 2.552 +#+begin_src clojure :results scalar :exports both 2.553 +(first (pokemon.types/pokemon-type-search-weak 1)) 2.554 +#+end_src 2.555 + 2.556 +#+results: 2.557 +: [:rock] 2.558 + 2.559 +Poor Rock. It's just not that good a type. Maybe this is why Brock 2.560 +(who has rock pok\eacute{}mon) is the first gym leader in the games. 2.561 + 2.562 +#+begin_src clojure :results scalar cache :exports both 2.563 +(first (pokemon.types/pokemon-type-search-weak 2)) 2.564 +#+end_src 2.565 + 2.566 +#+results: 2.567 +: [:grass :ice] 2.568 + 2.569 +# ;;bonus convergently immortal type combo 2.570 +# (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark]))) 2.571 + 2.572 +#+begin_src clojure :results output :exports both 2.573 +(clojure.pprint/pprint 2.574 + (pokemon.types/susceptibility [:grass :ice])) 2.575 +#+end_src 2.576 + 2.577 +#+results: 2.578 +#+begin_example 2.579 +{:water 1/2, 2.580 + :psychic 1, 2.581 + :dragon 1, 2.582 + :fire 4, 2.583 + :ice 1, 2.584 + :grass 1/2, 2.585 + :ghost 1, 2.586 + :poison 2, 2.587 + :flying 2, 2.588 + :normal 1, 2.589 + :rock 2, 2.590 + :electric 1/2, 2.591 + :ground 1/2, 2.592 + :fighting 2, 2.593 + :dark 1, 2.594 + :steel 2, 2.595 + :bug 2} 2.596 +#+end_example 2.597 + 2.598 +This miserable combination is weak to 6 types and double-weak to 2.599 +Fire. No pok\eacute{}mon in the games actually has this type. 2.600 + 2.601 +* Conclusion 2.602 + 2.603 +Searching for a type that is weak to everything takes a very long time 2.604 +and fails to reveal any results. That's the problem with a search 2.605 +over this large problem space --- if there's an easy solution, the 2.606 +search will find it quickly, but it can be very hard to determine 2.607 +whether there is actually a solution. 2.608 + 2.609 +In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in 2.610 +a different way. 2.611 + 2.612 + 2.613 +* COMMENT main program 2.614 +#+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none 2.615 +<<header>> 2.616 +#+end_src 2.617 + 2.618 +## this is necessary to define pokemon-table inside the source code. 2.619 + 2.620 +#+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :var pokemon-table-gen-one=pokemon-table-gen-one :var pokemon-table-gen-two=pokemon-table-gen-two :exports none 2.621 +<<data>> 2.622 +#+end_src 2.623 + 2.624 +#+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none 2.625 +<<types>> 2.626 +<<search>> 2.627 +<<pokemon-search>> 2.628 +<<old-school>> 2.629 +<<weaknesses>> 2.630 +<<weak-types>> 2.631 +#+end_src 2.632 + 2.633 + 2.634 + 2.635 + 2.636 + 2.637 + 2.638 + 2.639 + 2.640 + 2.641 + 2.642 + 2.643 + 2.644 + 2.645 + 2.646 + 2.647 + 2.648 + 2.649 +