view org/lpsolve.org @ 1:d39a04826cec

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