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