view org/types.org @ 12:89462678a932

spell check
author Robert McIntyre <rlm@mit.edu>
date Wed, 02 Nov 2011 10:31:25 -0700
parents eedd6897197d
children e1b7ef479bd1
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 #+keywords: Pokemon, clojure, best-first search, optimization
6 #+SETUPFILE: ../../aurellem/org/setup.org
7 #+INCLUDE: ../../aurellem/org/level-0.org
9 * The Pok\eacute{}mon Type System
11 The Pok\eacute{}mon type system consists of seventeen different
12 /types/ (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, Fire,
13 Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, and
14 Steel) that interact like an extended version of Rock-Paper-Scissors:
15 for example, the Fire type is strong against the Grass type but weak
16 against the Water type. In the table below, we've recorded the
17 relative strengths of each of the types in the Pok\eacute{}mon type
18 system; the number in each cell indicates how effective an attack of
19 the type in the row is against a Pok\eacute{}mon of the type in the
20 column. We call these numbers /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 susceptibility 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 used against a Flying type pok\eacute{}mon.
32 - The susceptibility 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 susceptibility 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 The definitions of the two Type Systems are included below.
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, even though the
116 pok\eacute{}mon anime ran [[http://bulbapedia.bulbagarden.net/wiki/EP022][a three-part series]] about how Ghost
117 pok\eacute{}mon are the best way to defeat Psychic pok\eacute{}mon,
118 and the Red, Blue, and Yellow games each have a character who
119 states "The only thing Psychic pok\eacute{}mon fear are Bugs and
120 Ghosts!" This is considered to be a programming glitch. Ghost is
121 super-effective against Psychic in Generation II.
123 * Representing the Data
125 After creating the Pok\eacute{}mon types namespace, we store the
126 tables of susceptibilities above in =pokemon-table-gen-one= and
127 =pokemon-table-gen-two=, each of which is a simple vector of
128 vectors. Because a vector of vectors can be cumbersome, we do not
129 access the tables directly; instead, we use the derivative structures
130 =attack-strengths= and =defense-strengths=, which are functions which
131 return hash-maps associating each row (respectively column) of the
132 table with its corresponding Pok\eacute{}mon type.
135 #+srcname: header
136 #+begin_src clojure :results silent
137 (ns pokemon.types
138 (:use clojure.set)
139 (:use clojure.contrib.combinatorics)
140 (:use clojure.contrib.math)
141 (:use clojure.contrib.def)
142 (:use rlm.rlm-commands))
143 #+end_src
145 #+srcname: data
146 #+begin_src clojure :results silent
147 (in-ns 'pokemon.types)
148 ;; record type strengths as a vector of vectors
149 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two
150 ;; are replaced with the tables above when this file is tangled.
151 (def pokemon-gen-one pokemon-table-gen-one)
152 (def pokemon-gen-two pokemon-table-gen-two)
154 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))
156 (defn attack-strengths []
157 (zipmap
158 (type-names)
159 (map (comp vec rest) pokemon-gen-two)))
161 (defn defense-strengths []
162 (zipmap (type-names)
163 (map
164 (apply juxt (map (attack-strengths) (type-names)))
165 (range (count (type-names))))))
166 #+end_src
168 The two statements
170 #+begin_src clojure :exports code
171 (def pokemon-gen-one pokemon-table-gen-one)
172 (def pokemon-gen-two pokemon-table-gen-two)
173 #+end_src
175 probably look weird. When the actual source file is created, those
176 variables are replaced with the data from the tables above.
178 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.
181 #+begin_src clojure :results output :exports both
182 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
183 #+end_src
185 #+results:
186 #+begin_example
187 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)
188 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)
189 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)
190 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)
191 ("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)
192 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)
193 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)
194 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)
195 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)
196 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)
197 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)
198 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)
199 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)
200 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)
201 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)
202 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)
203 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
204 #+end_example
206 =pokemon-gen-two= is a simple list-of-lists data structure.
208 #+begin_src clojure :results output :exports both
209 (clojure.pprint/pprint (pokemon.types/defense-strengths))
210 #+end_src
212 #+results:
213 #+begin_example
214 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],
215 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],
216 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],
217 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],
218 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],
219 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],
220 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],
221 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],
222 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],
223 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],
224 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],
225 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],
226 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],
227 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],
228 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],
229 :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],
230 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
231 #+end_example
233 =defense-strengths= is a more convenient form of =pokemon-gen-two=,
234 with key/value pair access.
236 * Interfacing with the Data
238 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two
239 types at the same time. For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary
240 bird that can control lightning, has both the Electric and Flying
241 types. A pok\eacute{}mon with more than one type gains the advantages
242 and disadvantages of both types. The susceptibilities of each type are
243 multiplied together to produce the hybrid type's susceptibilities. For
244 example, Electric is weak to Ground (susceptibility of 2), but Flying
245 is immune to Ground (susceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,
246 Electric/Flying, is immune to Ground because $2 \times 0 = 0$.
248 #+srcname: types
249 #+begin_src clojure :results silent
250 (in-ns 'pokemon.types)
252 (defn multitypes "All combinations of up to n types" [n]
253 (vec
254 (map vec
255 (reduce concat
256 (map (partial combinations (type-names))
257 (range 1 (inc n)))))))
259 (defn susceptibility
260 "Hash-map of the susceptibilities of the given type combination
261 to each type of attack"
262 [pkmn-types]
263 (rlm.map-utils/map-vals
264 clojure.core/rationalize
265 (apply hash-map
266 (interleave (type-names)
267 (apply (partial map *)
268 (map (defense-strengths) pkmn-types))))))
270 (defn susceptance
271 "The cumulative susceptibility of the given type combination"
272 [types]
273 (reduce + (map #(expt % 2) (vals (susceptibility types)))))
274 #+end_src
276 Now we can work out the susceptibility of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.
278 Electric is weak to Ground.
279 #+begin_src clojure :exports both
280 (:ground (pokemon.types/susceptibility [:electric]))
281 #+end_src
283 #+results:
284 : 2
286 Flying is immune to Ground.
287 #+begin_src clojure :exports both
288 (:ground (pokemon.types/susceptibility [:flying]))
289 #+end_src
291 #+results:
292 : 0
294 Together, they are immune to Ground.
295 #+begin_src clojure :exports both
296 (:ground (pokemon.types/susceptibility [:electric :flying]))
297 #+end_src
299 #+results:
300 : 0
305 * Best-First Search
307 I'd like to find type combinations that are interesting, but the total
308 number of combinations gets huge as we begin to consider more
309 types. For example, the total possible number of type combinations
310 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.
311 Therefore, it's prudent to use search.
313 These functions are a simple implementation of best-first search in
314 clojure. The idea to start off with a collection of nodes and some way
315 of finding the best node, and to always expand the best node at every
316 step.
318 #+srcname: search
319 #+begin_src clojure :results silent
320 (in-ns 'pokemon.types)
322 (defn comparatize
323 "Define a comparator which uses the numerical outputs of fn as its criterion.
324 Objects are sorted in increasing numerical order. Objects with the same fn-value
325 are further compared by clojure.core/compare."
326 [fun]
327 (fn [a b]
328 (let [val-a (fun a)
329 val-b (fun b)]
330 (cond
331 ;; if the function cannot differentiate the two values
332 ;; then compare the two values using clojure.core/compare
333 (= val-a val-b) (compare a b)
334 true
335 ;; LOWER values of the function are preferred
336 (compare (- val-a val-b) 0)))))
338 (defn-memo best-first-step [successors [visited unvisited]]
339 (cond (empty? unvisited) nil
340 true
341 (let [best-node (first unvisited)
342 visited* (conj visited best-node)
343 unvisited*
344 (difference
345 (union unvisited (set (successors best-node)))
346 visited*)]
347 (println best-node)
348 [visited* unvisited*])))
350 ;; memoize partial from core so that for example
351 ;; (= (partial + 1) (partial + 1))
352 ;; this way, best first search can take advantage of the memoization
353 ;; of best-first step
354 (undef partial)
355 (def partial (memoize clojure.core/partial))
357 (defn best-first-search
358 "Searches through a network of alternatives, pursuing
359 initially-promising positions first. Comparator defines which
360 positions are more promising, successors produces a list of improved
361 positions from the given position (if any exist), and initial-nodes is
362 a list of starting positions. Returns a lazy sequence of search results
363 [visited-nodes unvisited-nodes], which terminates when
364 there are no remaining unvisited positions."
365 [comparator successors initial-nodes]
366 (let [initial-nodes
367 (apply (partial sorted-set-by comparator) initial-nodes)
368 initial-visited-nodes (sorted-set-by comparator)
369 step (partial best-first-step successors)]
370 (take-while
371 (comp not nil?)
372 (iterate step [initial-visited-nodes initial-nodes]))))
374 #+end_src
377 Now that we have a basic best-first-search, it's convenient to write a
378 few pok\eacute{}mon-type specific convenience functions.
380 #+srcname: pokemon-search
381 #+begin_src clojure :results silent
382 (in-ns 'pokemon.types)
383 (defvar type-compare (comparatize susceptance)
384 "compare two type combinations W.R.T. their susceptibilities")
386 (defn type-successors
387 "Return the set of types that can be made by appending a single type
388 to the given combination."
389 [type]
390 (if (nil? type) '()
391 (set (map (comp vec sort (partial into type)) (multitypes 1)))))
393 (defn immortal?
394 "A type combo is immortal if it is resistant or invulnerable to
395 every pokemon type. This is because that set of types can just be
396 repeated to achieve as low a susceptance as desired"
397 [type]
398 (every? (partial > 1) (vals (susceptibility type))))
400 (defn type-successors*
401 "Stop expanding a type if it's immortal, or if it is longer than or
402 equal to limit-size. Also, only return type additions that are
403 strictly better than the initial type."
404 [limit-size type]
405 (if (or (<= limit-size (count type)) (immortal? type)) '()
406 (set (filter #(< 0 (type-compare type %)) (type-successors type)))))
408 (defn pokemon-type-search
409 "Search among type-combos no greater than length n, limited by limit
410 steps of best-first-search."
411 ([n] (pokemon-type-search n Integer/MAX_VALUE))
412 ([n limit]
413 (first (last
414 (take
415 limit
416 (best-first-search
417 type-compare
418 (partial type-successors* n)
419 (multitypes 1)))))))
421 (defvar immortals
422 (comp (partial filter immortal?) pokemon-type-search)
423 "find all the immortal pokemon types ")
425 #+end_src
427 Because there are so many type combinations, it's important to narrow
428 down the results as much as possible. That is why =type-successors*=
429 only returns types that are actually better than the type it is given.
431 Best-first search can get caught optimizing a single type forever, so
432 it's also important to limit the search space to be finite by setting
433 an upper bound on the length of a type combo.
435 * Results
436 ** The best dual-type combo
438 #+begin_src clojure :results cache verbatim :exports both
439 (first (pokemon.types/pokemon-type-search 2))
440 #+end_src
442 #+results:
443 : [:dark :ghost]
445 Dark and Ghost, which additionally has the property of having no
446 weaknesses to any other type, is the best type combo in terms of
447 susceptance.
449 The Dark and Steel types were introduced many years after
450 pok\eacute{}mon started. In addition to the additional types, the
451 pok\eacute{}mon games gained a few new rules concerning some of the
452 matchups of the original types. Therefore, it's also interesting to
453 see what type combination was most powerful before those types and new
454 rules were introduced.
456 The easiest way to do this with my setup is to just rebind the
457 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since
458 everything that references this variable is a function and we're not
459 doing anything too crazy with lazy-sequences and late-binding, this
460 simple macro will do the job.
462 #+srcname: old-school
463 #+begin_src clojure :results silent
464 (in-ns 'pokemon.types)
466 (defmacro old-school
467 [& forms]
468 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))
469 #+end_src
471 Using the =old-school= macro, it's easy to find answers for the
472 original 15 pokemon types as well as the expanded pokemon types
473 introduced later.
475 #+begin_src clojure :results verbatim :exports both :cache yes
476 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
477 #+end_src
479 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:
480 : [:ghost :psychic]
482 Ghost and Psychic also manages to have no weaknesses to any of the original
483 types, using the old Generation I rules.
485 #+begin_src clojure :results output :exports both
486 (clojure.pprint/pprint
487 (pokemon.types/old-school
488 (pokemon.types/susceptibility [:ghost :psychic])))
489 #+end_src
491 #+results:
492 #+begin_example
493 {:water 1,
494 :psychic 1/2,
495 :dragon 1,
496 :fire 1,
497 :ice 1,
498 :grass 1,
499 :ghost 0,
500 :poison 1/2,
501 :flying 1,
502 :normal 0,
503 :rock 1,
504 :electric 1,
505 :ground 1,
506 :fighting 0,
507 :bug 0}
508 #+end_example
510 ** An Immortal Type
511 It's possible to quickly find an immortal type by giving the search
512 a long enough maximum type length. 50 rounds of search with a max
513 type limit of 10 is enough to find an immortal type.
515 #+begin_src clojure :results scalar :exports both
516 (first (pokemon.types/pokemon-type-search 10 50))
517 #+end_src
519 #+results:
520 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
523 #+begin_src clojure :results output :exports both
524 (clojure.pprint/pprint
525 (pokemon.types/susceptibility
526 [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))
527 #+end_src
529 #+results:
530 #+begin_example
531 {:water 1/4,
532 :psychic 1/4,
533 :dragon 1/2,
534 :fire 1/2,
535 :ice 1/2,
536 :grass 1/8,
537 :ghost 1/2,
538 :poison 0,
539 :flying 1/2,
540 :normal 0,
541 :rock 1/2,
542 :electric 0,
543 :ground 0,
544 :fighting 0,
545 :dark 1/2,
546 :steel 1/32,
547 :bug 1/16}
548 #+end_example
550 ** Explanations for Common Pok\eacute{}mon Strategies
552 Many people start out a battle with either a Normal pok\eacute{}mon or an
553 Electric pok\eacute{}mon. Here's some justification for that choice.
555 #+srcname: weaknesses
556 #+begin_src clojure :results silent
557 (in-ns 'pokemon.types)
558 (defn critical-weaknesses [type]
559 (count (filter #(> % 1) (vals (susceptibility type)))))
560 #+end_src
562 #+begin_src clojure :exports both :results output
563 (clojure.pprint/pprint
564 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
565 #+end_src
567 #+results:
568 #+begin_example
569 ([:normal]
570 [:electric]
571 [:water]
572 [:fighting]
573 [:poison]
574 [:ghost]
575 [:dragon]
576 [:dark]
577 [:fire]
578 [:ground]
579 [:flying]
580 [:psychic]
581 [:bug]
582 [:steel]
583 [:ice]
584 [:grass]
585 [:rock])
586 #+end_example
588 Electric and Normal are among the best types with which to start the
589 game, since they have the fewest weaknesses among all the types.
591 At the beginning of the pok\eacute{}mon games, players are given a
592 choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water
593 pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon
594 [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].
596 #+begin_src clojure :exports both :results verbatim
597 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])
598 #+end_src
600 #+results:
601 : ([:water] [:fire] [:grass :poison])
603 As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid
604 choice starting out, insofar as susceptance is concerned.
606 ** The Worst Pok\eacute{}mon Types
608 #+srcname: weak-types
609 #+begin_src clojure :results silent
610 (in-ns 'pokemon.types)
612 (defn type-compare-weak
613 "compare first by total number of critical-weaknesses,
614 then by overall susceptance, favoring weaker types."
615 [type-1 type-2]
616 (let [measure (memoize (juxt critical-weaknesses susceptance))]
617 (if (= (measure type-2) (measure type-1))
618 (compare type-2 type-1)
619 (compare (measure type-2) (measure type-1)))))
621 (defn resistant?
622 "might as well get rid of types that are resistant to any type"
623 [type]
624 (not (every? #(< 0 %) (vals (susceptibility type)))))
626 (defn type-successors-weak
627 "Generate ways to weaken the given type combination. Discard type
628 combinations that either strengthen the given type combination or
629 that make it stronger"
630 [limit type]
631 (set (if (<= limit (count type)) '()
632 (filter #(< 0 (type-compare-weak type %))
633 (remove resistant? (type-successors type))))))
635 (defn pokemon-type-search-weak
636 "Search among type-combos no greater than length n, limited by limit
637 steps of best-first-search. Find the weakest type combination
638 possible in terms of susceptance."
639 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))
640 ([n limit]
641 (first (last
642 (take
643 limit
644 (best-first-search
645 type-compare-weak
646 (partial type-successors-weak n)
647 (multitypes 1)))))))
648 #+end_src
651 #+begin_src clojure :results scalar :exports both
652 (first (pokemon.types/pokemon-type-search-weak 1))
653 #+end_src
655 #+results:
656 : [:rock]
658 Poor Rock. It's just not that good a type. Maybe this is why Brock
659 (who has rock pok\eacute{}mon) is the first gym leader in the games.
661 #+begin_src clojure :results scalar cache :exports both
662 (first (pokemon.types/pokemon-type-search-weak 2))
663 #+end_src
665 #+results:
666 : [:grass :ice]
668 # ;;bonus convergently immortal type combo
669 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))
671 #+begin_src clojure :results output :exports both
672 (clojure.pprint/pprint
673 (pokemon.types/susceptibility [:grass :ice]))
674 #+end_src
676 #+results:
677 #+begin_example
678 {:water 1/2,
679 :psychic 1,
680 :dragon 1,
681 :fire 4,
682 :ice 1,
683 :grass 1/2,
684 :ghost 1,
685 :poison 2,
686 :flying 2,
687 :normal 1,
688 :rock 2,
689 :electric 1/2,
690 :ground 1/2,
691 :fighting 2,
692 :dark 1,
693 :steel 2,
694 :bug 2}
695 #+end_example
697 This miserable combination is weak to 6 types and double-weak to
698 Fire. No pok\eacute{}mon in the games actually has this type.
700 * Conclusion
702 Searching for a type that is weak to everything takes a very long time
703 and fails to reveal any results. That's the problem with a search
704 over this large problem space --- if there's an easy solution, the
705 search will find it quickly, but it can be very hard to determine
706 whether there is actually a solution.
708 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in
709 a different way.
711 * COMMENT main program
712 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
713 <<header>>
714 #+end_src
716 ## this is necessary to define pokemon-table inside the source code.
718 #+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
719 <<data>>
720 #+end_src
722 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
723 <<types>>
724 <<search>>
725 <<pokemon-search>>
726 <<old-school>>
727 <<weaknesses>>
728 <<weak-types>>
729 #+end_src