view org/lpsolve.org @ 13:e1b7ef479bd1

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