Mercurial > pokemon-types

comparison org/types.org @ 0:e03d363ed9a9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial committ for pokemon types report
author Robert McIntyre <rlm@mit.edu>
date Sun, 16 Oct 2011 06:57:42 -0700
parents
children 55bba4805393
comparison
equal deleted inserted replaced
-1:000000000000 0:e03d363ed9a9
1 #+TITLE: Breadth-first Search for Effective Pokemon Types
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
9
10
11 * The Pok\eacute{}mon Type System
12
13 The Pok\eacute{}mon type system consists of seventeen different
14 \ldquo{}types\rdquo{} (Rock, Grass, Ice, Psychic, Ground, Bug, Flying,
15 Fire, Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric,
16 and Steel) that interact like an extended version of
17 Rock-Paper-Scissors: for example, the Fire type is strong against the
18 Grass type but weak against the Water type. In the table below, we've
19 recorded the relative strengths of each of the types in the
20 Pok\eacute{}mon type system; the number in each cell indicates how
21 effective an attack of the type in the row is against a
22 Pok\eacute{}mon of the type in the column. We call these numbers
23 /susceptibilities/ because we are interested in the column totals,
24 which quantify the overall vulnerability of each Pok\eacute{}mon type
25 (as opposed to the row totals, which quantify the overall
26 effectiveness of each attack type.)
27
28 In the Pok\eacute{}mon games, only four susceptibility values (two,
29 one, one-half, and zero) occur. These numbers indicate particularly
30 high susceptibility, average susceptibility, particularly low
31 susceptibility, and no susceptibility
32 (immunity). Here is the entire Pok\eacute{}mon type chart.
33
34
35
36 ** TODO add the pokemon chart in a pretty form
37
38 * COMMENT Pokemon Table Data
39
40 #+caption: The rows are attack types, while the columns are defense types. To see the multiplier for a pokemon attack against a certain type, follow the row for the attack type to the column of the defending type.
41 #+label: pokemon-matchups
42 #+tblname: pokemon-table-gen-two
43 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel |
44 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------|
45 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 | 1 | .5 |
46 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 1 | 2 |
47 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | 1 |
48 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 | 1 | 1 |
49 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 | 1 | .5 |
50 | ice | 1 | .5 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |
51 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 | 2 | 2 |
52 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 1 | .5 | .5 | 1 | 1 | 0 |
53 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 | 1 | 2 |
54 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 | 1 | .5 |
55 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 | 0 | .5 |
56 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | .5 | 1 | .5 | 2 | 1 | 1 | .5 | 1 | 2 | .5 |
57 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | .5 |
58 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |
59 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |
60 | dark | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |
61 | steel | 1 | .5 | .5 | .5 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | .5 |
62
63 #+caption: this is the old table from generation 1. The differences are: dark and ghost are missing, Bus is super against Poison, Poison is super against Bug, Bug is regularly effective against Ghost, and Ice is normally effective against Fire. Ghost is not effective against psychic.
64 #+label: pokemon-matchups-gen-1
65 #+tblname: pokemon-table-gen-one
66 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |
67 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|
68 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 |
69 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 |
70 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 |
71 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 |
72 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 |
73 | ice | 1 | 1 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 |
74 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 |
75 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 2 | .5 | .5 | 1 |
76 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 |
77 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 |
78 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 |
79 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | 2 | 1 | .5 | 2 | 1 | 1 | 0 | 1 |
80 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 |
81 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 1 |
82 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
83
84 * Representing the Data
85
86 After creating the Pok\eacute{}mon types namespace, we store the table
87 of susceptibilities in =pokemon-table-gen-one= and
88 =pokemon-table-gen-two=, each of which is a simple vector of
89 vectors. Because a vector of vectors can be cumbersome, we do not
90 access the tables directly; instead, we use the derivative structures
91 =attack-strengths= and =defense-strengths=, which are functions which
92 return hash-maps associating each row (respectively column) of the
93 table with its corresponding Pok\eacute{}mon type.
94
95
96
97 #+srcname: header
98 #+begin_src clojure :results silent
99 (ns pokemon.types
100 (:use rlm.ns-rlm))
101 (rlm.ns-rlm/ns-clone rlm.light-base)
102 (use 'clojure.set)
103 #+end_src
104
105 #+srcname: data(pokemon-table-gen-one=pokemon-table-gen-one, pokemon-table-gen-two=pokemon-table-gen-two)
106 #+begin_src clojure :results silent
107 (in-ns 'pokemon.types)
108 ;; record type strengths as a vector of vectors
109 (def pokemon-gen-one pokemon-table-gen-one)
110 (def pokemon-gen-two pokemon-table-gen-two)
111
112 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))
113
114 (defn attack-strengths []
115 (zipmap
116 (type-names)
117 (map (comp vec rest) pokemon-gen-two)))
118
119 (defn defense-strengths []
120 (zipmap (type-names)
121 (map
122 (apply juxt (map (attack-strengths) (type-names)))
123 (range (count (type-names))))))
124 #+end_src
125
126 #+begin_src clojure :results output :exports both
127 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
128 #+end_src
129
130 #+results:
131 #+begin_example
132 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)
133 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)
134 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)
135 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)
136 ("grass" 1 0.5 2 1 0.5 1 1 0.5 2 0.5 1 0.5 2 1 0.5 1 0.5)
137 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)
138 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)
139 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)
140 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)
141 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)
142 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)
143 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)
144 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)
145 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)
146 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)
147 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)
148 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
149 #+end_example
150
151 =pokemon-gen-two= is a simple list-of-list data structure.
152
153 #+begin_src clojure :results output :exports both
154 (clojure.pprint/pprint (pokemon.types/defense-strengths))
155 #+end_src
156
157 #+results:
158 #+begin_example
159 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],
160 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],
161 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],
162 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],
163 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],
164 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],
165 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],
166 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],
167 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],
168 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],
169 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],
170 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],
171 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],
172 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],
173 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],
174 :steel [0.5 2 1 1 0.5 0.5 2 0 2 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5],
175 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
176 #+end_example
177
178 =defense-strengths= is a more convenient form of =pokemon-gen-two=, with key/value pair access.
179
180 * Interfacing with the Data
181 #+srcname: types
182 #+begin_src clojure :results silent
183 (in-ns 'pokemon.types)
184
185 (defn multitypes "All combinations of up to n types" [n]
186 (vec
187 (map vec
188 (reduce concat
189 (map (partial combinations (type-names))
190 (range 1 (inc n)))))))
191
192 (defn susceptibility ;; susceptibility-map
193 "Hash-map of the susceptibilities of the given type combination
194 to each type of attack"
195 [pkmn-types]
196 (rlm.map-utils/map-vals
197 clojure.core/rationalize
198 (apply hash-map
199 (interleave (type-names)
200 (apply (partial map *)
201 (map (defense-strengths) pkmn-types))))))
202
203 (defn susceptance ;; susceptibility
204 "The cumulative susceptibility of the given type combination"
205 [types]
206 (reduce + (map sqr (vals (susceptibility types)))))
207 #+end_src
208
209 * Best-First Search
210
211 I'd like to find type combinations that are interesting, but the total
212 number of combinations gets huge as we begin to consider more
213 types. For example, the total possible number of type combinations
214 given just 8 possible types is: 17^{8} = 6975757441 combinations.
215 Therefore, it's prudent to use search.
216
217 These functions are a simple implementation of best-first search in
218 clojure. The idea to start off with a collection of nodes and some way
219 of finding the best node, and to always expand the best node at every
220 step.
221
222 #+srcname: search
223 #+begin_src clojure :results silent
224 (in-ns 'pokemon.types)
225
226 (defn comparatize
227 "Define a comparator which uses the numerical outputs of fn as its criterion.
228 Objects are sorted in increasing numerical order. Objects with the same fn-value
229 are further compared by clojure.core/compare."
230 [fun]
231 (fn [a b]
232 (let [val-a (fun a)
233 val-b (fun b)]
234 (cond
235 ;; if the function cannot differentiate the two values
236 ;; then compare the two values using clojure.core/compare
237 (= val-a val-b) (compare a b)
238 true
239 ;; LOWER values of the function are preferred
240 (compare (- val-a val-b) 0)))))
241
242 (defn-memo best-first-step [successors [visited unvisited]]
243 (cond (empty? unvisited) nil
244 true
245 (let [best-node (first unvisited)
246 visited* (conj visited best-node)
247 unvisited*
248 (difference
249 (union unvisited (set (successors best-node)))
250 visited*)]
251 (println best-node)
252 [visited* unvisited*])))
253
254 ;; memoize partial from core so that for example
255 ;; (= (partial + 1) (partial + 1))
256 ;; this way, best first search can take advantage of the memoization
257 ;; of best-first step
258 (undef partial)
259 (def partial (memoize clojure.core/partial))
260
261 (defn best-first-search
262 "Searches through a network of alternatives, pursuing
263 initially-promising positions first. Comparator defines which
264 positions are more promising, successors produces a list of improved
265 positions from the given position (if any exist), and initial-nodes is
266 a list of starting positions. Returns a lazy sequence of search results
267 [visited-nodes unvisited-nodes], which terminates when
268 there are no remaining unvisited positions."
269 [comparator successors initial-nodes]
270 (let [initial-nodes
271 (apply (partial sorted-set-by comparator) initial-nodes)
272 initial-visited-nodes (sorted-set-by comparator)
273 step (partial best-first-step successors)]
274 (take-while
275 (comp not nil?)
276 (iterate step [initial-visited-nodes initial-nodes]))))
277
278 #+end_src
279
280
281 Now that we have a basic best-first-search, it's convenient to write a
282 few pokemon-type specific convenience functions.
283
284 #+srcname: pokemon-search
285 #+begin_src clojure :results silent
286 (in-ns 'pokemon.types)
287 (defvar type-compare (comparatize susceptance)
288 "compare two type combinations wrt their susceptibilities")
289
290 (defn type-successors
291 "Return the set of types that can be made by appending a single type
292 to the given combination."
293 [type]
294 (if (nil? type) '()
295 (set (map (comp vec sort (partial into type)) (multitypes 1)))))
296
297 (defn immortal?
298 "A type combo is immortal if it is resistant or invulnerable to
299 every pokemon type. This is because that set of types can just be
300 repeated to achieve as low a susceptance as desired"
301 [type]
302 (every? (partial > 1) (vals (susceptibility type))))
303
304 (defn type-successors*
305 "Stop expanding a type if it's immortal, or if it is longer than or
306 equal to limit-size. Also, only return type additions that are
307 strictly better than the initial type."
308 [limit-size type]
309 (if (or (<= limit-size (count type)) (immortal? type)) '()
310 (set (filter #(< 0 (type-compare type %)) (type-successors type)))))
311
312 (defn pokemon-type-search
313 "Search among type-combos no greater than length n, limited by limit
314 steps of best-first-search."
315 ([n] (pokemon-type-search n Integer/MAX_VALUE))
316 ([n limit]
317 (first (last
318 (take
319 limit
320 (best-first-search
321 type-compare
322 (partial type-successors* n)
323 (multitypes 1)))))))
324
325 (defvar immortals
326 (comp (partial filter immortal?) pokemon-type-search)
327 "find all the immortal pokemon types ")
328
329 #+end_src
330
331 Because there are so many type combinations, it's important to narrow
332 down the results as much as possible. That is why =type-successors*=
333 only returns types that are actually better than the type it is given.
334
335 Best-first search can get caught optimizing a single type forever, so
336 it's also important to limit the search space to be finite by setting
337 an upper bound on the length of a type combo.
338
339 * Results
340 ** The best dual-type combo
341
342 #+begin_src clojure :results cache verbatim :exports both
343 (first (pokemon.types/pokemon-type-search 2))
344 #+end_src
345
346 #+results:
347 : [:dark :ghost]
348
349 Dark and Ghost, which additionally has the property of having no
350 weaknesses to any other type, is the best type combo in terms of
351 susceptance.
352
353 The Dark and Steel types were introduced many years after
354 pok\eacute{}mon started. In addition to the additional types, the
355 pok\eacute{}mon games gained a few new rules concerning some of the
356 matchups of the original types. Therefore, it's also interesting to see what
357 type combination was most powerful before those types and new rules were introduced.
358
359 The easiest way to do this with my setup is to just rebind the
360 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since
361 everything that references this variable is a function and we're not
362 doing anything too crazy with lazy-sequences and late-binding, this
363 simple macro will do the job.
364
365 #+srcname: old-school
366 #+begin_src clojure :results silent
367 (in-ns 'pokemon.types)
368
369 (defmacro old-school
370 [& forms]
371 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))
372 #+end_src
373
374 Using the =old-school= macro, it's easy to find answers for the
375 original 15 pokemon types as well as the expanded pokemon types
376 introduced later.
377
378 #+begin_src clojure :results verbatim :exports both :cache yes
379 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
380 #+end_src
381
382 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:
383 : [:ghost :psychic]
384
385 Ghost and Psychic also manages to have no weaknesses to any of the original
386 types.
387
388 #+begin_src clojure :results output :exports both
389 (clojure.pprint/pprint
390 (pokemon.types/old-school
391 (pokemon.types/susceptibility [:ghost :psychic])))
392 #+end_src
393
394 #+results:
395 #+begin_example
396 {:water 1,
397 :psychic 1/2,
398 :dragon 1,
399 :fire 1,
400 :ice 1,
401 :grass 1,
402 :ghost 0,
403 :poison 1/2,
404 :flying 1,
405 :normal 0,
406 :rock 1,
407 :electric 1,
408 :ground 1,
409 :fighting 0,
410 :bug 0}
411 #+end_example
412
413 ** An Immortal Type
414 It's possible to quickly find an immortal type by giving the search
415 a long enough maximum type length. 50 rounds of search with a max
416 type limit of 10 is enough to find an immortal type.
417
418 #+begin_src clojure :results scalar :exports both
419 (first (pokemon.types/pokemon-type-search 10 50))
420 #+end_src
421
422 #+results:
423 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
424
425
426 #+begin_src clojure :results output :exports both
427 (clojure.pprint/pprint
428 (pokemon.types/susceptibility
429 [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))
430 #+end_src
431
432 #+results:
433 #+begin_example
434 {:water 1/4,
435 :psychic 1/4,
436 :dragon 1/2,
437 :fire 1/2,
438 :ice 1/2,
439 :grass 1/8,
440 :ghost 1/2,
441 :poison 0,
442 :flying 1/2,
443 :normal 0,
444 :rock 1/2,
445 :electric 0,
446 :ground 0,
447 :fighting 0,
448 :dark 1/2,
449 :steel 1/32,
450 :bug 1/16}
451 #+end_example
452
453 ** Explanations for Common Pok\eacute{}mon Strategies
454
455 Many people start out a battle with either a normal pok\eacute{}mon or an
456 electric pok\eacute{}mon, and here's some justification for that choice.
457
458 #+srcname: weaknesses
459 #+begin_src clojure :results silent
460 (in-ns 'pokemon.types)
461 (defn critical-weaknesses [type]
462 (count (filter #(> % 1) (vals (susceptibility type)))))
463 #+end_src
464
465 #+begin_src clojure :exports both :results output
466 (clojure.pprint/pprint
467 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
468 #+end_src
469
470 #+results:
471 #+begin_example
472 ([:normal]
473 [:electric]
474 [:water]
475 [:fighting]
476 [:poison]
477 [:ghost]
478 [:dragon]
479 [:dark]
480 [:fire]
481 [:ground]
482 [:flying]
483 [:psychic]
484 [:bug]
485 [:steel]
486 [:ice]
487 [:grass]
488 [:rock])
489 #+end_example
490
491 Electric and Normal are among the best types with which to start the
492 game, since they have the fewest weaknesses among all the types.
493
494 At the beginning of the pok\eacute{}mon games, players are given a choice
495 between the Fire pok\eacute{}mon Charmander, the Water pok\eacute{}mon Squirtle, or
496 the Grass/Poison pok\eacute{}mon Bulbasaur.
497
498 #+begin_src clojure :exports both :results verbatim
499 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])
500 #+end_src
501
502 #+results:
503 : ([:water] [:fire] [:grass :poison])
504
505 As can be seen, the Water pok\eacute{}mon Squirtle is the most solid
506 choice starting out, insofar as susceptance is concerned.
507
508 ** The Worst Pok\eacute{}mon Types
509
510 #+srcname: weak-types
511 #+begin_src clojure :results silent
512 (in-ns 'pokemon.types)
513
514 (defn type-compare-weak
515 "compare first by total number of critical-weaknesses,
516 then by overall susceptance, favoring weaker types."
517 [type-1 type-2]
518 (let [measure (memoize (juxt critical-weaknesses susceptance))]
519 (if (= (measure type-2) (measure type-1))
520 (compare type-2 type-1)
521 (compare (measure type-2) (measure type-1)))))
522
523 (defn resistant?
524 "might as well get rid of types that are resistant to any type"
525 [type]
526 (not (every? #(< 0 %) (vals (susceptibility type)))))
527
528 (defn type-successors-weak
529 [limit type]
530 (set (if (<= limit (count type)) '()
531 (filter #(< 0 (type-compare-weak type %))
532 (remove resistant? (type-successors type))))))
533
534 (defn pokemon-type-search-weak
535 "Search among type-combos no greater than length n, limited by limit
536 steps of best-first-search."
537 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))
538 ([n limit]
539 (first (last
540 (take
541 limit
542 (best-first-search
543 type-compare-weak
544 (partial type-successors-weak n)
545 (multitypes 1)))))))
546 #+end_src
547
548
549 #+begin_src clojure :results scalar :exports both
550 (first (pokemon.types/pokemon-type-search-weak 1))
551 #+end_src
552
553 #+results:
554 : [:rock]
555
556 Poor Rock. It's just not that good a type. Maybe this is why Brock
557 (who has rock pok\eacute{}mon) is the first gym leader in the games.
558
559 #+begin_src clojure :results scalar cache :exports both
560 (first (pokemon.types/pokemon-type-search-weak 2))
561 #+end_src
562
563 #+results:
564 : [:grass :ice]
565
566 # ;;bonus convergently immortal type combo
567 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))
568
569 #+begin_src clojure :results output :exports both
570 (clojure.pprint/pprint
571 (pokemon.types/susceptibility [:grass :ice]))
572 #+end_src
573
574 #+results:
575 #+begin_example
576 {:water 1/2,
577 :psychic 1,
578 :dragon 1,
579 :fire 4,
580 :ice 1,
581 :grass 1/2,
582 :ghost 1,
583 :poison 2,
584 :flying 2,
585 :normal 1,
586 :rock 2,
587 :electric 1/2,
588 :ground 1/2,
589 :fighting 2,
590 :dark 1,
591 :steel 2,
592 :bug 2}
593 #+end_example
594
595 This miserable combination is weak to 6 types and double-weak to
596 Fire. No pok\eacute{}mon in the games actually has this type.
597
598 * Conclusion
599
600 Searching for a type that is weak to everything takes a very long time
601 and fails to reveal any results. That's the problem with a search
602 over this large problem space --- if there's an easy solution, the
603 search will find it quickly, but it can be very hard to determine
604 whether there is actually a solution.
605
606 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in
607 a different way.
608
609
610 * COMMENT main program
611 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
612 <<header>>
613 #+end_src
614
615 ## this is necessary to define pokemon-table inside the source code.
616
617 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :var pokemon-table-gen-one=pokemon-table-gen-one :var pokemon-table-gen-two=pokemon-table-gen-two :exports none
618 <<data>>
619 #+end_src
620
621 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
622 <<types>>
623 <<search>>
624 <<pokemon-search>>
625 <<old-school>>
626 <<weaknesses>>
627 <<weak-types>>
628 #+end_src
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646