view org/types.org @ 8:4f9ef752e2f0

more cleanup and better docstrings for clojure functions
author Robert McIntyre <rlm@mit.edu>
date Wed, 02 Nov 2011 07:01:49 -0700
parents d6b8dab05d9d
children fd38763de457
line wrap: on
line source
1 #+TITLE: Best-First Search for Effective Pokemon Types
2 #+AUTHOR: Robert McIntyre & Dylan Holmes
3 #+EMAIL: rlm@mit.edu
4 #+description: Finding interesting pokemon type combinations through Best-First search in clojure.
5 #+SETUPFILE: ../../aurellem/org/setup.org
6 #+INCLUDE: ../../aurellem/org/level-0.org
8 * The Pok\eacute{}mon Type System
10 The Pok\eacute{}mon type system consists of seventeen different
11 \ldquo{}types\rdquo{} (Rock, Grass, Ice, Psychic, Ground, Bug, Flying,
12 Fire, Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric,
13 and Steel) that interact like an extended version of
14 Rock-Paper-Scissors: for example, the Fire type is strong against the
15 Grass type but weak against the Water type. In the table below, we've
16 recorded the relative strengths of each of the types in the
17 Pok\eacute{}mon type system; the number in each cell indicates how
18 effective an attack of the type in the row is against a
19 Pok\eacute{}mon of the type in the column. We call these numbers
20 /susceptibilities/.
22 In the Pok\eacute{}mon games, only four susceptibility values (two,
23 one, one-half, and zero) occur. These numbers indicate particularly
24 high susceptibility, average susceptibility, particularly low
25 susceptibility, and no susceptibility (immunity).
27 - The suceptability of Flying types /against/ Ground is 0, because Ground
28 attacks cannot hurt Flying pok\eacute{}mon at all. The damage that
29 a Ground type attack normally does is /multiplied/ by 0 when it is
30 uesd against a Flying type pok\eacute{}mon.
32 - The susceptability of Fire types against Water attacks
33 is 2, because Water type attacks are strong against Fire type
34 Pok\eacute{}mon. The damage that a Water type attack normally does
35 is doubled when it is used against a Fire type pok\eacute{}mon.
37 - The susceptability of Water types against Water attacks is
38 $\frac{1}{2}$, because Water type attacks are strong against Water
39 type Pok\eacute{}mon. The damage that a Water type attack normally
40 does is halved when it is used against a Water type
41 pok\eacute{}mon.
43 There are two pok\eacute{}mon type systems in use. The first is the
44 classic system which was used for the very first pok\eacute{}mon
45 games, Red, Yellow, and Blue. This old system was used from 1998 to
46 2000 in America, and is known as the /Generation I Type System/. The
47 modern pok\eacute{}mon type system was introduced in 2000 with the
48 introduction of pok\eacute{}mon Gold and Silver, and has been in use
49 ever since. It is called the /Generation II Type System/.
51 Here are the the definitions of the two type systems.
53 * Generation I and II Type System Data
55 ** Generation II Type System
56 #+label: pokemon-matchups
57 #+tblname: pokemon-table-gen-two
58 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel |
59 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------|
60 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 | 1 | .5 |
61 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 1 | 2 |
62 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | 1 |
63 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 | 1 | 1 |
64 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 | 1 | .5 |
65 | ice | 1 | .5 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |
66 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 | 2 | 2 |
67 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 1 | .5 | .5 | 1 | 1 | 0 |
68 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 | 1 | 2 |
69 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 | 1 | .5 |
70 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 | 0 | .5 |
71 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | .5 | 1 | .5 | 2 | 1 | 1 | .5 | 1 | 2 | .5 |
72 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | .5 |
73 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |
74 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |
75 | dark | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |
76 | steel | 1 | .5 | .5 | .5 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | .5 |
78 The rows are attack types, while the columns are defense types. To
79 see the multiplier for a pok\eacute{}mon attack against a certain type, follow
80 the row for the attack type to the column of the defending type.
82 ** Generation I Type System
83 #+label: pokemon-matchups-gen-1
84 #+tblname: pokemon-table-gen-one
85 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |
86 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|
87 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 |
88 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 |
89 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 |
90 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 |
91 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 |
92 | ice | 1 | 1 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 |
93 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 |
94 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 2 | .5 | .5 | 1 |
95 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 |
96 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 |
97 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 |
98 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | 2 | 1 | .5 | 2 | 1 | 1 | 0 | 1 |
99 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 |
100 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 1 |
101 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
104 This is the old table from Generation I. The differences from
105 Generation II are:
106 - Dark and Steel types are missing (these were introduced in
107 Generation II).
108 - Bug is super-effective against Poison (not-very-effective in
109 Generation II).
110 - Poison is super-effective against Bug (normal in Generation II).
111 - Bug is regularly effective against Ghost (super-effective in
112 Generation II).
113 - Ice is normally effective against Fire, (not-very-effective in
114 Generation II).
115 - Ghost is completely ineffective against Psychic. This is considered
116 to be a programning glitch.
120 * Representing the Data
122 After creating the Pok\eacute{}mon types namespace, we store the
123 tables of susceptibilities above in =pokemon-table-gen-one= and
124 =pokemon-table-gen-two=, each of which is a simple vector of
125 vectors. Because a vector of vectors can be cumbersome, we do not
126 access the tables directly; instead, we use the derivative structures
127 =attack-strengths= and =defense-strengths=, which are functions which
128 return hash-maps associating each row (respectively column) of the
129 table with its corresponding Pok\eacute{}mon type.
132 #+srcname: header
133 #+begin_src clojure :results silent
134 (ns pokemon.types
135 (:use clojure.set)
136 (:use clojure.contrib.combinatorics)
137 (:use clojure.contrib.math)
138 (:use clojure.contrib.def)
139 (:use rlm.rlm-commands))
140 #+end_src
142 #+srcname: data
143 #+begin_src clojure :results silent
144 (in-ns 'pokemon.types)
145 ;; record type strengths as a vector of vectors
146 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two
147 ;; are replaced with the tables above when this file is tangled.
148 (def pokemon-gen-one pokemon-table-gen-one)
149 (def pokemon-gen-two pokemon-table-gen-two)
151 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))
153 (defn attack-strengths []
154 (zipmap
155 (type-names)
156 (map (comp vec rest) pokemon-gen-two)))
158 (defn defense-strengths []
159 (zipmap (type-names)
160 (map
161 (apply juxt (map (attack-strengths) (type-names)))
162 (range (count (type-names))))))
163 #+end_src
165 The two statements
167 #+begin_src clojure :exports code
168 (def pokemon-gen-one pokemon-table-gen-one)
169 (def pokemon-gen-two pokemon-table-gen-two)
170 #+end_src
172 probably look weird. When the actual source file is created, those
173 variables are replaced with the data from the tables above.
175 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.
178 #+begin_src clojure :results output :exports both
179 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
180 #+end_src
182 #+results:
183 #+begin_example
184 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)
185 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)
186 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)
187 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)
188 ("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)
189 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)
190 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)
191 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)
192 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)
193 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)
194 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)
195 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)
196 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)
197 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)
198 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)
199 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)
200 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
201 #+end_example
203 =pokemon-gen-two= is a simple list-of-lists data structure.
205 #+begin_src clojure :results output :exports both
206 (clojure.pprint/pprint (pokemon.types/defense-strengths))
207 #+end_src
209 #+results:
210 #+begin_example
211 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],
212 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],
213 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],
214 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],
215 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],
216 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],
217 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],
218 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],
219 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],
220 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],
221 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],
222 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],
223 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],
224 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],
225 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],
226 :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],
227 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
228 #+end_example
230 =defense-strengths= is a more convenient form of =pokemon-gen-two=,
231 with key/value pair access.
233 * Interfacing with the Data
235 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two
236 types at the same time. For example, Zapdos, the fearsome legendary
237 that can control lightning, has both the Electric and Flying types. A
238 pok\eacute{}mon with more than one type gains the advantages and
239 disadvanteags of both types. The suceptibilitys of each type are
240 multiplied together to produce the hybrid type's susceptibilities. For
241 example, Electric is weak to Ground (susceptibility of 2), but Flying
242 is immune to Ground (suceptibility of 0). Zapdos' type,
243 Electrig/Flying, is immune to Ground because $2 \times 0 = 0$.
245 #+srcname: types
246 #+begin_src clojure :results silent
247 (in-ns 'pokemon.types)
249 (defn multitypes "All combinations of up to n types" [n]
250 (vec
251 (map vec
252 (reduce concat
253 (map (partial combinations (type-names))
254 (range 1 (inc n)))))))
256 (defn susceptibility
257 "Hash-map of the susceptibilities of the given type combination
258 to each type of attack"
259 [pkmn-types]
260 (rlm.map-utils/map-vals
261 clojure.core/rationalize
262 (apply hash-map
263 (interleave (type-names)
264 (apply (partial map *)
265 (map (defense-strengths) pkmn-types))))))
267 (defn susceptance
268 "The cumulative susceptibility of the given type combination"
269 [types]
270 (reduce + (map #(expt % 2) (vals (susceptibility types)))))
271 #+end_src
273 Now we can work out the suceptability of Zapdos automatically.
275 Electric is weak to Ground.
276 #+begin_src clojure :exports both
277 (:ground (pokemon.types/susceptibility [:electric]))
278 #+end_src
280 #+results:
281 : 2
283 Flying is immune to Ground.
284 #+begin_src clojure :exports both
285 (:ground (pokemon.types/susceptibility [:flying]))
286 #+end_src
288 #+results:
289 : 0
291 Together, they are immune to Ground.
292 #+begin_src clojure :exports both
293 (:ground (pokemon.types/susceptibility [:electric :flying]))
294 #+end_src
296 #+results:
297 : 0
302 * Best-First Search
304 I'd like to find type combinations that are interesting, but the total
305 number of combinations gets huge as we begin to consider more
306 types. For example, the total possible number of type combinations
307 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.
308 Therefore, it's prudent to use search.
310 These functions are a simple implementation of best-first search in
311 clojure. The idea to start off with a collection of nodes and some way
312 of finding the best node, and to always expand the best node at every
313 step.
315 #+srcname: search
316 #+begin_src clojure :results silent
317 (in-ns 'pokemon.types)
319 (defn comparatize
320 "Define a comparator which uses the numerical outputs of fn as its criterion.
321 Objects are sorted in increasing numerical order. Objects with the same fn-value
322 are further compared by clojure.core/compare."
323 [fun]
324 (fn [a b]
325 (let [val-a (fun a)
326 val-b (fun b)]
327 (cond
328 ;; if the function cannot differentiate the two values
329 ;; then compare the two values using clojure.core/compare
330 (= val-a val-b) (compare a b)
331 true
332 ;; LOWER values of the function are preferred
333 (compare (- val-a val-b) 0)))))
335 (defn-memo best-first-step [successors [visited unvisited]]
336 (cond (empty? unvisited) nil
337 true
338 (let [best-node (first unvisited)
339 visited* (conj visited best-node)
340 unvisited*
341 (difference
342 (union unvisited (set (successors best-node)))
343 visited*)]
344 (println best-node)
345 [visited* unvisited*])))
347 ;; memoize partial from core so that for example
348 ;; (= (partial + 1) (partial + 1))
349 ;; this way, best first search can take advantage of the memoization
350 ;; of best-first step
351 (undef partial)
352 (def partial (memoize clojure.core/partial))
354 (defn best-first-search
355 "Searches through a network of alternatives, pursuing
356 initially-promising positions first. Comparator defines which
357 positions are more promising, successors produces a list of improved
358 positions from the given position (if any exist), and initial-nodes is
359 a list of starting positions. Returns a lazy sequence of search results
360 [visited-nodes unvisited-nodes], which terminates when
361 there are no remaining unvisited positions."
362 [comparator successors initial-nodes]
363 (let [initial-nodes
364 (apply (partial sorted-set-by comparator) initial-nodes)
365 initial-visited-nodes (sorted-set-by comparator)
366 step (partial best-first-step successors)]
367 (take-while
368 (comp not nil?)
369 (iterate step [initial-visited-nodes initial-nodes]))))
371 #+end_src
374 Now that we have a basic best-first-search, it's convenient to write a
375 few pok\eacute{}mon-type specific convenience functions.
377 #+srcname: pokemon-search
378 #+begin_src clojure :results silent
379 (in-ns 'pokemon.types)
380 (defvar type-compare (comparatize susceptance)
381 "compare two type combinations wrt their susceptibilities")
383 (defn type-successors
384 "Return the set of types that can be made by appending a single type
385 to the given combination."
386 [type]
387 (if (nil? type) '()
388 (set (map (comp vec sort (partial into type)) (multitypes 1)))))
390 (defn immortal?
391 "A type combo is immortal if it is resistant or invulnerable to
392 every pokemon type. This is because that set of types can just be
393 repeated to achieve as low a susceptance as desired"
394 [type]
395 (every? (partial > 1) (vals (susceptibility type))))
397 (defn type-successors*
398 "Stop expanding a type if it's immortal, or if it is longer than or
399 equal to limit-size. Also, only return type additions that are
400 strictly better than the initial type."
401 [limit-size type]
402 (if (or (<= limit-size (count type)) (immortal? type)) '()
403 (set (filter #(< 0 (type-compare type %)) (type-successors type)))))
405 (defn pokemon-type-search
406 "Search among type-combos no greater than length n, limited by limit
407 steps of best-first-search."
408 ([n] (pokemon-type-search n Integer/MAX_VALUE))
409 ([n limit]
410 (first (last
411 (take
412 limit
413 (best-first-search
414 type-compare
415 (partial type-successors* n)
416 (multitypes 1)))))))
418 (defvar immortals
419 (comp (partial filter immortal?) pokemon-type-search)
420 "find all the immortal pokemon types ")
422 #+end_src
424 Because there are so many type combinations, it's important to narrow
425 down the results as much as possible. That is why =type-successors*=
426 only returns types that are actually better than the type it is given.
428 Best-first search can get caught optimizing a single type forever, so
429 it's also important to limit the search space to be finite by setting
430 an upper bound on the length of a type combo.
432 * Results
433 ** The best dual-type combo
435 #+begin_src clojure :results cache verbatim :exports both
436 (first (pokemon.types/pokemon-type-search 2))
437 #+end_src
439 #+results:
440 : [:dark :ghost]
442 Dark and Ghost, which additionally has the property of having no
443 weaknesses to any other type, is the best type combo in terms of
444 susceptance.
446 The Dark and Steel types were introduced many years after
447 pok\eacute{}mon started. In addition to the additional types, the
448 pok\eacute{}mon games gained a few new rules concerning some of the
449 matchups of the original types. Therefore, it's also interesting to see what
450 type combination was most powerful before those types and new rules were introduced.
452 The easiest way to do this with my setup is to just rebind the
453 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since
454 everything that references this variable is a function and we're not
455 doing anything too crazy with lazy-sequences and late-binding, this
456 simple macro will do the job.
458 #+srcname: old-school
459 #+begin_src clojure :results silent
460 (in-ns 'pokemon.types)
462 (defmacro old-school
463 [& forms]
464 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))
465 #+end_src
467 Using the =old-school= macro, it's easy to find answers for the
468 original 15 pokemon types as well as the expanded pokemon types
469 introduced later.
471 #+begin_src clojure :results verbatim :exports both :cache yes
472 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
473 #+end_src
475 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:
476 : [:ghost :psychic]
478 Ghost and Psychic also manages to have no weaknesses to any of the original
479 types, using the old Generation I rules.
481 #+begin_src clojure :results output :exports both
482 (clojure.pprint/pprint
483 (pokemon.types/old-school
484 (pokemon.types/susceptibility [:ghost :psychic])))
485 #+end_src
487 #+results:
488 #+begin_example
489 {:water 1,
490 :psychic 1/2,
491 :dragon 1,
492 :fire 1,
493 :ice 1,
494 :grass 1,
495 :ghost 0,
496 :poison 1/2,
497 :flying 1,
498 :normal 0,
499 :rock 1,
500 :electric 1,
501 :ground 1,
502 :fighting 0,
503 :bug 0}
504 #+end_example
506 ** An Immortal Type
507 It's possible to quickly find an immortal type by giving the search
508 a long enough maximum type length. 50 rounds of search with a max
509 type limit of 10 is enough to find an immortal type.
511 #+begin_src clojure :results scalar :exports both
512 (first (pokemon.types/pokemon-type-search 10 50))
513 #+end_src
515 #+results:
516 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
519 #+begin_src clojure :results output :exports both
520 (clojure.pprint/pprint
521 (pokemon.types/susceptibility
522 [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))
523 #+end_src
525 #+results:
526 #+begin_example
527 {:water 1/4,
528 :psychic 1/4,
529 :dragon 1/2,
530 :fire 1/2,
531 :ice 1/2,
532 :grass 1/8,
533 :ghost 1/2,
534 :poison 0,
535 :flying 1/2,
536 :normal 0,
537 :rock 1/2,
538 :electric 0,
539 :ground 0,
540 :fighting 0,
541 :dark 1/2,
542 :steel 1/32,
543 :bug 1/16}
544 #+end_example
546 ** Explanations for Common Pok\eacute{}mon Strategies
548 Many people start out a battle with either a Normal pok\eacute{}mon or an
549 Electric pok\eacute{}mon. Here's some justification for that choice.
551 #+srcname: weaknesses
552 #+begin_src clojure :results silent
553 (in-ns 'pokemon.types)
554 (defn critical-weaknesses [type]
555 (count (filter #(> % 1) (vals (susceptibility type)))))
556 #+end_src
558 #+begin_src clojure :exports both :results output
559 (clojure.pprint/pprint
560 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
561 #+end_src
563 #+results:
564 #+begin_example
565 ([:normal]
566 [:electric]
567 [:water]
568 [:fighting]
569 [:poison]
570 [:ghost]
571 [:dragon]
572 [:dark]
573 [:fire]
574 [:ground]
575 [:flying]
576 [:psychic]
577 [:bug]
578 [:steel]
579 [:ice]
580 [:grass]
581 [:rock])
582 #+end_example
584 Electric and Normal are among the best types with which to start the
585 game, since they have the fewest weaknesses among all the types.
587 At the beginning of the pok\eacute{}mon games, players are given a choice
588 between the Fire pok\eacute{}mon Charmander, the Water pok\eacute{}mon Squirtle, or
589 the Grass/Poison pok\eacute{}mon Bulbasaur.
591 #+begin_src clojure :exports both :results verbatim
592 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])
593 #+end_src
595 #+results:
596 : ([:water] [:fire] [:grass :poison])
598 As can be seen, the Water pok\eacute{}mon Squirtle is the most solid
599 choice starting out, insofar as susceptance is concerned.
601 ** The Worst Pok\eacute{}mon Types
603 #+srcname: weak-types
604 #+begin_src clojure :results silent
605 (in-ns 'pokemon.types)
607 (defn type-compare-weak
608 "compare first by total number of critical-weaknesses,
609 then by overall susceptance, favoring weaker types."
610 [type-1 type-2]
611 (let [measure (memoize (juxt critical-weaknesses susceptance))]
612 (if (= (measure type-2) (measure type-1))
613 (compare type-2 type-1)
614 (compare (measure type-2) (measure type-1)))))
616 (defn resistant?
617 "might as well get rid of types that are resistant to any type"
618 [type]
619 (not (every? #(< 0 %) (vals (susceptibility type)))))
621 (defn type-successors-weak
622 "Generate ways to weaken the given type combination. Discard type
623 combinations that either strengthen the given type combination or
624 that make it stronger"
625 [limit type]
626 (set (if (<= limit (count type)) '()
627 (filter #(< 0 (type-compare-weak type %))
628 (remove resistant? (type-successors type))))))
630 (defn pokemon-type-search-weak
631 "Search among type-combos no greater than length n, limited by limit
632 steps of best-first-search. Find the weakest type combination
633 possible in terms of susceptance."
634 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))
635 ([n limit]
636 (first (last
637 (take
638 limit
639 (best-first-search
640 type-compare-weak
641 (partial type-successors-weak n)
642 (multitypes 1)))))))
643 #+end_src
646 #+begin_src clojure :results scalar :exports both
647 (first (pokemon.types/pokemon-type-search-weak 1))
648 #+end_src
650 #+results:
651 : [:rock]
653 Poor Rock. It's just not that good a type. Maybe this is why Brock
654 (who has rock pok\eacute{}mon) is the first gym leader in the games.
656 #+begin_src clojure :results scalar cache :exports both
657 (first (pokemon.types/pokemon-type-search-weak 2))
658 #+end_src
660 #+results:
661 : [:grass :ice]
663 # ;;bonus convergently immortal type combo
664 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))
666 #+begin_src clojure :results output :exports both
667 (clojure.pprint/pprint
668 (pokemon.types/susceptibility [:grass :ice]))
669 #+end_src
671 #+results:
672 #+begin_example
673 {:water 1/2,
674 :psychic 1,
675 :dragon 1,
676 :fire 4,
677 :ice 1,
678 :grass 1/2,
679 :ghost 1,
680 :poison 2,
681 :flying 2,
682 :normal 1,
683 :rock 2,
684 :electric 1/2,
685 :ground 1/2,
686 :fighting 2,
687 :dark 1,
688 :steel 2,
689 :bug 2}
690 #+end_example
692 This miserable combination is weak to 6 types and double-weak to
693 Fire. No pok\eacute{}mon in the games actually has this type.
695 * Conclusion
697 Searching for a type that is weak to everything takes a very long time
698 and fails to reveal any results. That's the problem with a search
699 over this large problem space --- if there's an easy solution, the
700 search will find it quickly, but it can be very hard to determine
701 whether there is actually a solution.
703 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in
704 a different way.
708 * COMMENT main program
709 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
710 <<header>>
711 #+end_src
713 ## this is necessary to define pokemon-table inside the source code.
715 #+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
716 <<data>>
717 #+end_src
719 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
720 <<types>>
721 <<search>>
722 <<pokemon-search>>
723 <<old-school>>
724 <<weaknesses>>
725 <<weak-types>>
726 #+end_src