view org/types.org @ 13:e1b7ef479bd1

minor edits
author Robert McIntyre <rlm@mit.edu>
date Sun, 05 Feb 2012 11:11:07 -0700
parents eedd6897197d
children da4c47650d38
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 (:require rlm.map-utils))
144 #+end_src
146 #+srcname: data
147 #+begin_src clojure :results silent
148 (in-ns 'pokemon.types)
149 ;; record type strengths as a vector of vectors
150 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two
151 ;; are replaced with the tables above when this file is tangled.
152 (def pokemon-gen-one pokemon-table-gen-one)
153 (def pokemon-gen-two pokemon-table-gen-two)
155 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))
157 (defn attack-strengths []
158 (zipmap
159 (type-names)
160 (map (comp vec rest) pokemon-gen-two)))
162 (defn defense-strengths []
163 (zipmap (type-names)
164 (map
165 (apply juxt (map (attack-strengths) (type-names)))
166 (range (count (type-names))))))
167 #+end_src
169 The two statements
171 #+begin_src clojure :exports code
172 (def pokemon-gen-one pokemon-table-gen-one)
173 (def pokemon-gen-two pokemon-table-gen-two)
174 #+end_src
176 probably look weird. When the actual source file is created, those
177 variables are replaced with the data from the tables above.
179 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.
182 #+begin_src clojure :results output :exports both
183 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
184 #+end_src
186 #+results:
187 #+begin_example
188 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)
189 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)
190 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)
191 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)
192 ("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)
193 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)
194 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)
195 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)
196 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)
197 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)
198 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)
199 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)
200 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)
201 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)
202 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)
203 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)
204 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
205 #+end_example
207 =pokemon-gen-two= is a simple list-of-lists data structure.
209 #+begin_src clojure :results output :exports both
210 (clojure.pprint/pprint (pokemon.types/defense-strengths))
211 #+end_src
213 #+results:
214 #+begin_example
215 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],
216 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],
217 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],
218 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],
219 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],
220 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],
221 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],
222 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],
223 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],
224 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],
225 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],
226 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],
227 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],
228 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],
229 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],
230 :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],
231 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
232 #+end_example
234 =defense-strengths= is a more convenient form of =pokemon-gen-two=,
235 with key/value pair access.
237 * Interfacing with the Data
239 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two
240 types at the same time. For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary
241 bird that can control lightning, has both the Electric and Flying
242 types. A pok\eacute{}mon with more than one type gains the advantages
243 and disadvantages of both types. The susceptibilities of each type are
244 multiplied together to produce the hybrid type's susceptibilities. For
245 example, Electric is weak to Ground (susceptibility of 2), but Flying
246 is immune to Ground (susceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,
247 Electric/Flying, is immune to Ground because $2 \times 0 = 0$.
249 #+srcname: types
250 #+begin_src clojure :results silent
251 (in-ns 'pokemon.types)
253 (defn multitypes "All combinations of up to n types" [n]
254 (vec
255 (map vec
256 (reduce concat
257 (map (partial combinations (type-names))
258 (range 1 (inc n)))))))
260 (defn susceptibility
261 "Hash-map of the susceptibilities of the given type combination
262 to each type of attack"
263 [pkmn-types]
264 (rlm.map-utils/map-vals
265 clojure.core/rationalize
266 (apply hash-map
267 (interleave (type-names)
268 (apply (partial map *)
269 (map (defense-strengths) pkmn-types))))))
271 (defn susceptance
272 "The cumulative susceptibility of the given type combination"
273 [types]
274 (reduce + (map #(expt % 2) (vals (susceptibility types)))))
275 #+end_src
277 Now we can work out the susceptibility of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.
279 Electric is weak to Ground.
280 #+begin_src clojure :exports both
281 (:ground (pokemon.types/susceptibility [:electric]))
282 #+end_src
284 #+results:
285 : 2
287 Flying is immune to Ground.
288 #+begin_src clojure :exports both
289 (:ground (pokemon.types/susceptibility [:flying]))
290 #+end_src
292 #+results:
293 : 0
295 Together, they are immune to Ground.
296 #+begin_src clojure :exports both
297 (:ground (pokemon.types/susceptibility [:electric :flying]))
298 #+end_src
300 #+results:
301 : 0
306 * Best-First Search
308 I'd like to find type combinations that are interesting, but the total
309 number of combinations gets huge as we begin to consider more
310 types. For example, the total possible number of type combinations
311 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.
312 Therefore, it's prudent to use search.
314 These functions are a simple implementation of best-first search in
315 clojure. The idea to start off with a collection of nodes and some way
316 of finding the best node, and to always expand the best node at every
317 step.
319 #+srcname: search
320 #+begin_src clojure :results silent
321 (in-ns 'pokemon.types)
323 (defn comparatize
324 "Define a comparator which uses the numerical outputs of fn as its criterion.
325 Objects are sorted in increasing numerical order. Objects with the same fn-value
326 are further compared by clojure.core/compare."
327 [fun]
328 (fn [a b]
329 (let [val-a (fun a)
330 val-b (fun b)]
331 (cond
332 ;; if the function cannot differentiate the two values
333 ;; then compare the two values using clojure.core/compare
334 (= val-a val-b) (compare a b)
335 true
336 ;; LOWER values of the function are preferred
337 (compare (- val-a val-b) 0)))))
339 (defn-memo best-first-step [successors [visited unvisited]]
340 (cond (empty? unvisited) nil
341 true
342 (let [best-node (first unvisited)
343 visited* (conj visited best-node)
344 unvisited*
345 (difference
346 (union unvisited (set (successors best-node)))
347 visited*)]
348 (println best-node)
349 [visited* unvisited*])))
351 ;; memoize partial from core so that for example
352 ;; (= (partial + 1) (partial + 1))
353 ;; this way, best first search can take advantage of the memoization
354 ;; of best-first step
355 (undef partial)
356 (def partial (memoize clojure.core/partial))
358 (defn best-first-search
359 "Searches through a network of alternatives, pursuing
360 initially-promising positions first. Comparator defines which
361 positions are more promising, successors produces a list of improved
362 positions from the given position (if any exist), and initial-nodes is
363 a list of starting positions. Returns a lazy sequence of search results
364 [visited-nodes unvisited-nodes], which terminates when
365 there are no remaining unvisited positions."
366 [comparator successors initial-nodes]
367 (let [initial-nodes
368 (apply (partial sorted-set-by comparator) initial-nodes)
369 initial-visited-nodes (sorted-set-by comparator)
370 step (partial best-first-step successors)]
371 (take-while
372 (comp not nil?)
373 (iterate step [initial-visited-nodes initial-nodes]))))
375 #+end_src
378 Now that we have a basic best-first-search, it's convenient to write a
379 few pok\eacute{}mon-type specific convenience functions.
381 #+srcname: pokemon-search
382 #+begin_src clojure :results silent
383 (in-ns 'pokemon.types)
384 (defvar type-compare (comparatize susceptance)
385 "compare two type combinations W.R.T. their susceptibilities")
387 (defn type-successors
388 "Return the set of types that can be made by appending a single type
389 to the given combination."
390 [type]
391 (if (nil? type) '()
392 (set (map (comp vec sort (partial into type)) (multitypes 1)))))
394 (defn immortal?
395 "A type combo is immortal if it is resistant or invulnerable to
396 every pokemon type. This is because that set of types can just be
397 repeated to achieve as low a susceptance as desired"
398 [type]
399 (every? (partial > 1) (vals (susceptibility type))))
401 (defn type-successors*
402 "Stop expanding a type if it's immortal, or if it is longer than or
403 equal to limit-size. Also, only return type additions that are
404 strictly better than the initial type."
405 [limit-size type]
406 (if (or (<= limit-size (count type)) (immortal? type)) '()
407 (set (filter #(< 0 (type-compare type %)) (type-successors type)))))
409 (defn pokemon-type-search
410 "Search among type-combos no greater than length n, limited by limit
411 steps of best-first-search."
412 ([n] (pokemon-type-search n Integer/MAX_VALUE))
413 ([n limit]
414 (first (last
415 (take
416 limit
417 (best-first-search
418 type-compare
419 (partial type-successors* n)
420 (multitypes 1)))))))
422 (defvar immortals
423 (comp (partial filter immortal?) pokemon-type-search)
424 "find all the immortal pokemon types ")
426 #+end_src
428 Because there are so many type combinations, it's important to narrow
429 down the results as much as possible. That is why =type-successors*=
430 only returns types that are actually better than the type it is given.
432 Best-first search can get caught optimizing a single type forever, so
433 it's also important to limit the search space to be finite by setting
434 an upper bound on the length of a type combo.
436 * Results
437 ** The best dual-type combo
439 #+begin_src clojure :results cache verbatim :exports both
440 (first (pokemon.types/pokemon-type-search 2))
441 #+end_src
443 #+results:
444 : [:dark :ghost]
446 Dark and Ghost, which additionally has the property of having no
447 weaknesses to any other type, is the best type combo in terms of
448 susceptance.
450 The Dark and Steel types were introduced many years after
451 pok\eacute{}mon started. In addition to the additional types, the
452 pok\eacute{}mon games gained a few new rules concerning some of the
453 matchups of the original types. Therefore, it's also interesting to
454 see what type combination was most powerful before those types and new
455 rules were introduced.
457 The easiest way to do this with my setup is to just rebind the
458 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since
459 everything that references this variable is a function and we're not
460 doing anything too crazy with lazy-sequences and late-binding, this
461 simple macro will do the job.
463 #+srcname: old-school
464 #+begin_src clojure :results silent
465 (in-ns 'pokemon.types)
467 (defmacro old-school
468 [& forms]
469 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))
470 #+end_src
472 Using the =old-school= macro, it's easy to find answers for the
473 original 15 pokemon types as well as the expanded pokemon types
474 introduced later.
476 #+begin_src clojure :results verbatim :exports both :cache yes
477 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
478 #+end_src
480 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:
481 : [:ghost :psychic]
483 Ghost and Psychic also manages to have no weaknesses to any of the original
484 types, using the old Generation I rules.
486 #+begin_src clojure :results output :exports both
487 (clojure.pprint/pprint
488 (pokemon.types/old-school
489 (pokemon.types/susceptibility [:ghost :psychic])))
490 #+end_src
492 #+results:
493 #+begin_example
494 {:water 1,
495 :psychic 1/2,
496 :dragon 1,
497 :fire 1,
498 :ice 1,
499 :grass 1,
500 :ghost 0,
501 :poison 1/2,
502 :flying 1,
503 :normal 0,
504 :rock 1,
505 :electric 1,
506 :ground 1,
507 :fighting 0,
508 :bug 0}
509 #+end_example
511 ** An Immortal Type
512 It's possible to quickly find an immortal type by giving the search
513 a long enough maximum type length. 50 rounds of search with a max
514 type limit of 10 is enough to find an immortal type.
516 #+begin_src clojure :results scalar :exports both
517 (first (pokemon.types/pokemon-type-search 10 50))
518 #+end_src
520 #+results:
521 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
524 #+begin_src clojure :results output :exports both
525 (clojure.pprint/pprint
526 (pokemon.types/susceptibility
527 [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))
528 #+end_src
530 #+results:
531 #+begin_example
532 {:water 1/4,
533 :psychic 1/4,
534 :dragon 1/2,
535 :fire 1/2,
536 :ice 1/2,
537 :grass 1/8,
538 :ghost 1/2,
539 :poison 0,
540 :flying 1/2,
541 :normal 0,
542 :rock 1/2,
543 :electric 0,
544 :ground 0,
545 :fighting 0,
546 :dark 1/2,
547 :steel 1/32,
548 :bug 1/16}
549 #+end_example
551 ** Explanations for Common Pok\eacute{}mon Strategies
553 Many people start out a battle with either a Normal pok\eacute{}mon or an
554 Electric pok\eacute{}mon. Here's some justification for that choice.
556 #+srcname: weaknesses
557 #+begin_src clojure :results silent
558 (in-ns 'pokemon.types)
559 (defn critical-weaknesses [type]
560 (count (filter #(> % 1) (vals (susceptibility type)))))
561 #+end_src
563 #+begin_src clojure :exports both :results output
564 (clojure.pprint/pprint
565 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
566 #+end_src
568 #+results:
569 #+begin_example
570 ([:normal]
571 [:electric]
572 [:water]
573 [:fighting]
574 [:poison]
575 [:ghost]
576 [:dragon]
577 [:dark]
578 [:fire]
579 [:ground]
580 [:flying]
581 [:psychic]
582 [:bug]
583 [:steel]
584 [:ice]
585 [:grass]
586 [:rock])
587 #+end_example
589 Electric and Normal are among the best types with which to start the
590 game, since they have the fewest weaknesses among all the types.
592 At the beginning of the pok\eacute{}mon games, players are given a
593 choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water
594 pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon
595 [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].
597 #+begin_src clojure :exports both :results verbatim
598 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])
599 #+end_src
601 #+results:
602 : ([:water] [:fire] [:grass :poison])
604 As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid
605 choice starting out, insofar as susceptance is concerned.
607 ** The Worst Pok\eacute{}mon Types
609 #+srcname: weak-types
610 #+begin_src clojure :results silent
611 (in-ns 'pokemon.types)
613 (defn type-compare-weak
614 "compare first by total number of critical-weaknesses,
615 then by overall susceptance, favoring weaker types."
616 [type-1 type-2]
617 (let [measure (memoize (juxt critical-weaknesses susceptance))]
618 (if (= (measure type-2) (measure type-1))
619 (compare type-2 type-1)
620 (compare (measure type-2) (measure type-1)))))
622 (defn resistant?
623 "might as well get rid of types that are resistant to any type"
624 [type]
625 (not (every? #(< 0 %) (vals (susceptibility type)))))
627 (defn type-successors-weak
628 "Generate ways to weaken the given type combination. Discard type
629 combinations that either strengthen the given type combination or
630 that make it stronger"
631 [limit type]
632 (set (if (<= limit (count type)) '()
633 (filter #(< 0 (type-compare-weak type %))
634 (remove resistant? (type-successors type))))))
636 (defn pokemon-type-search-weak
637 "Search among type-combos no greater than length n, limited by limit
638 steps of best-first-search. Find the weakest type combination
639 possible in terms of susceptance."
640 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))
641 ([n limit]
642 (first (last
643 (take
644 limit
645 (best-first-search
646 type-compare-weak
647 (partial type-successors-weak n)
648 (multitypes 1)))))))
649 #+end_src
652 #+begin_src clojure :results scalar :exports both
653 (first (pokemon.types/pokemon-type-search-weak 1))
654 #+end_src
656 #+results:
657 : [:rock]
659 Poor Rock. It's just not that good a type. Maybe this is why Brock
660 (who has rock pok\eacute{}mon) is the first gym leader in the games.
662 #+begin_src clojure :results scalar cache :exports both
663 (first (pokemon.types/pokemon-type-search-weak 2))
664 #+end_src
666 #+results:
667 : [:grass :ice]
669 # ;;bonus convergently immortal type combo
670 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))
672 #+begin_src clojure :results output :exports both
673 (clojure.pprint/pprint
674 (pokemon.types/susceptibility [:grass :ice]))
675 #+end_src
677 #+results:
678 #+begin_example
679 {:water 1/2,
680 :psychic 1,
681 :dragon 1,
682 :fire 4,
683 :ice 1,
684 :grass 1/2,
685 :ghost 1,
686 :poison 2,
687 :flying 2,
688 :normal 1,
689 :rock 2,
690 :electric 1/2,
691 :ground 1/2,
692 :fighting 2,
693 :dark 1,
694 :steel 2,
695 :bug 2}
696 #+end_example
698 This miserable combination is weak to 6 types and double-weak to
699 Fire. No pok\eacute{}mon in the games actually has this type.
701 * Conclusion
703 Searching for a type that is weak to everything takes a very long time
704 and fails to reveal any results. That's the problem with a search
705 over this large problem space --- if there's an easy solution, the
706 search will find it quickly, but it can be very hard to determine
707 whether there is actually a solution.
709 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in
710 a different way.
712 * COMMENT main program
713 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
714 <<header>>
715 #+end_src
717 ## this is necessary to define pokemon-table inside the source code.
719 #+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
720 <<data>>
721 #+end_src
723 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
724 <<types>>
725 <<search>>
726 <<pokemon-search>>
727 <<old-school>>
728 <<weaknesses>>
729 <<weak-types>>
730 #+end_src