Mercurial > pokemon-types
view org/types.org @ 9:fd38763de457
added links for the pokemon
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Wed, 02 Nov 2011 07:35:57 -0700 |
parents | 4f9ef752e2f0 |
children | eedd6897197d |
line wrap: on
line source
1 #+TITLE: Best-First Search for Effective Pokemon Types2 #+AUTHOR: Robert McIntyre & Dylan Holmes3 #+EMAIL: rlm@mit.edu4 #+description: Finding interesting pokemon type combinations through Best-First search in clojure.5 #+SETUPFILE: ../../aurellem/org/setup.org6 #+INCLUDE: ../../aurellem/org/level-0.org8 * The Pok\eacute{}mon Type System10 The Pok\eacute{}mon type system consists of seventeen different11 /types/ (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, Fire,12 Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, and13 Steel) that interact like an extended version of Rock-Paper-Scissors:14 for example, the Fire type is strong against the Grass type but weak15 against the Water type. In the table below, we've recorded the16 relative strengths of each of the types in the Pok\eacute{}mon type17 system; the number in each cell indicates how effective an attack of18 the type in the row is against a Pok\eacute{}mon of the type in the19 column. We call these numbers /susceptibilities/.21 In the Pok\eacute{}mon games, only four susceptibility values (two,22 one, one-half, and zero) occur. These numbers indicate particularly23 high susceptibility, average susceptibility, particularly low24 susceptibility, and no susceptibility (immunity).26 - The suceptability of Flying types /against/ Ground is 0, because Ground27 attacks cannot hurt Flying pok\eacute{}mon at all. The damage that28 a Ground type attack normally does is /multiplied/ by 0 when it is29 uesd against a Flying type pok\eacute{}mon.31 - The susceptability of Fire types against Water attacks32 is 2, because Water type attacks are strong against Fire type33 Pok\eacute{}mon. The damage that a Water type attack normally does34 is doubled when it is used against a Fire type pok\eacute{}mon.36 - The susceptability of Water types against Water attacks is37 $\frac{1}{2}$, because Water type attacks are strong against Water38 type Pok\eacute{}mon. The damage that a Water type attack normally39 does is halved when it is used against a Water type40 pok\eacute{}mon.42 There are two pok\eacute{}mon type systems in use. The first is the43 classic system which was used for the very first pok\eacute{}mon44 games, Red, Yellow, and Blue. This old system was used from 1998 to45 2000 in America, and is known as the /Generation I Type System/. The46 modern pok\eacute{}mon type system was introduced in 2000 with the47 introduction of pok\eacute{}mon Gold and Silver, and has been in use48 ever since. It is called the /Generation II Type System/.50 The definitions of the two Type Systems are included below.52 * Generation I and II Type System Data54 ** Generation II Type System55 #+label: pokemon-matchups56 #+tblname: pokemon-table-gen-two57 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel |58 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------|59 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 | 1 | .5 |60 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 1 | 2 |61 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | 1 |62 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 | 1 | 1 |63 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 | 1 | .5 |64 | ice | 1 | .5 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |65 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 | 2 | 2 |66 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 1 | .5 | .5 | 1 | 1 | 0 |67 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 | 1 | 2 |68 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 | 1 | .5 |69 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 | 0 | .5 |70 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | .5 | 1 | .5 | 2 | 1 | 1 | .5 | 1 | 2 | .5 |71 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | .5 |72 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |73 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | .5 |74 | dark | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | .5 | .5 |75 | steel | 1 | .5 | .5 | .5 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | .5 |77 The rows are attack types, while the columns are defense types. To78 see the multiplier for a pok\eacute{}mon attack against a certain type, follow79 the row for the attack type to the column of the defending type.81 ** Generation I Type System82 #+label: pokemon-matchups-gen-183 #+tblname: pokemon-table-gen-one84 | | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |85 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|86 | normal | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | .5 | 0 | 1 |87 | fire | 1 | .5 | .5 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | .5 |88 | water | 1 | 2 | .5 | 1 | .5 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 2 | 1 | .5 |89 | electric | 1 | 1 | 2 | .5 | .5 | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 1 | .5 |90 | grass | 1 | .5 | 2 | 1 | .5 | 1 | 1 | .5 | 2 | .5 | 1 | .5 | 2 | 1 | .5 |91 | ice | 1 | 1 | .5 | 1 | 2 | .5 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 |92 | fighting | 2 | 1 | 1 | 1 | 1 | 2 | 1 | .5 | 1 | .5 | .5 | .5 | 2 | 0 | 1 |93 | poison | 1 | 1 | 1 | 1 | 2 | 1 | 1 | .5 | .5 | 1 | 1 | 2 | .5 | .5 | 1 |94 | ground | 1 | 2 | 1 | 2 | .5 | 1 | 1 | 2 | 1 | 0 | 1 | .5 | 2 | 1 | 1 |95 | flying | 1 | 1 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | .5 | 1 | 1 |96 | psychic | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | .5 | 1 | 1 | 1 | 1 |97 | bug | 1 | .5 | 1 | 1 | 2 | 1 | .5 | 2 | 1 | .5 | 2 | 1 | 1 | 0 | 1 |98 | rock | 1 | 2 | 1 | 1 | 1 | 2 | .5 | 1 | .5 | 2 | 1 | 2 | 1 | 1 | 1 |99 | ghost | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 1 |100 | dragon | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |103 This is the old table from Generation I. The differences from104 Generation II are:105 - Dark and Steel types are missing (these were introduced in106 Generation II).107 - Bug is super-effective against Poison (not-very-effective in108 Generation II).109 - Poison is super-effective against Bug (normal in Generation II).110 - Bug is regularly effective against Ghost (super-effective in111 Generation II).112 - Ice is normally effective against Fire, (not-very-effective in113 Generation II).114 - Ghost is completely ineffective against Psychic, even though the115 pok\eacute{}mon anime ran [[http://bulbapedia.bulbagarden.net/wiki/EP022][a three-part series]] about how Ghost116 pok\eacute{}mon are the best way to defeat Psychic pok\eacute{}mon,117 and the Red, Blue, and Yellow games each have a character who118 states "The only thing Psychic pok\eacute{}mon fear are Bugs and119 Ghosts!" This is considered to be a programning glitch. Ghost is120 super-effective against Psychic in Generation II.122 * Representing the Data124 After creating the Pok\eacute{}mon types namespace, we store the125 tables of susceptibilities above in =pokemon-table-gen-one= and126 =pokemon-table-gen-two=, each of which is a simple vector of127 vectors. Because a vector of vectors can be cumbersome, we do not128 access the tables directly; instead, we use the derivative structures129 =attack-strengths= and =defense-strengths=, which are functions which130 return hash-maps associating each row (respectively column) of the131 table with its corresponding Pok\eacute{}mon type.134 #+srcname: header135 #+begin_src clojure :results silent136 (ns pokemon.types137 (:use clojure.set)138 (:use clojure.contrib.combinatorics)139 (:use clojure.contrib.math)140 (:use clojure.contrib.def)141 (:use rlm.rlm-commands))142 #+end_src144 #+srcname: data145 #+begin_src clojure :results silent146 (in-ns 'pokemon.types)147 ;; record type strengths as a vector of vectors148 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two149 ;; are replaced with the tables above when this file is tangled.150 (def pokemon-gen-one pokemon-table-gen-one)151 (def pokemon-gen-two pokemon-table-gen-two)153 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))155 (defn attack-strengths []156 (zipmap157 (type-names)158 (map (comp vec rest) pokemon-gen-two)))160 (defn defense-strengths []161 (zipmap (type-names)162 (map163 (apply juxt (map (attack-strengths) (type-names)))164 (range (count (type-names))))))165 #+end_src167 The two statements169 #+begin_src clojure :exports code170 (def pokemon-gen-one pokemon-table-gen-one)171 (def pokemon-gen-two pokemon-table-gen-two)172 #+end_src174 probably look weird. When the actual source file is created, those175 variables are replaced with the data from the tables above.177 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.180 #+begin_src clojure :results output :exports both181 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)182 #+end_src184 #+results:185 #+begin_example186 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)187 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)188 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)189 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)190 ("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)191 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)192 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)193 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)194 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)195 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)196 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)197 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)198 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)199 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)200 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)201 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)202 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))203 #+end_example205 =pokemon-gen-two= is a simple list-of-lists data structure.207 #+begin_src clojure :results output :exports both208 (clojure.pprint/pprint (pokemon.types/defense-strengths))209 #+end_src211 #+results:212 #+begin_example213 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],214 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],215 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],216 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],217 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],218 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],219 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],220 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],221 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],222 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],223 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],224 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],225 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],226 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],227 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],228 :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],229 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}230 #+end_example232 =defense-strengths= is a more convenient form of =pokemon-gen-two=,233 with key/value pair access.235 * Interfacing with the Data237 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two238 types at the same time. For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary239 bird that can control lightning, has both the Electric and Flying240 types. A pok\eacute{}mon with more than one type gains the advantages241 and disadvanteags of both types. The suceptibilitys of each type are242 multiplied together to produce the hybrid type's susceptibilities. For243 example, Electric is weak to Ground (susceptibility of 2), but Flying244 is immune to Ground (suceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,245 Electrig/Flying, is immune to Ground because $2 \times 0 = 0$.247 #+srcname: types248 #+begin_src clojure :results silent249 (in-ns 'pokemon.types)251 (defn multitypes "All combinations of up to n types" [n]252 (vec253 (map vec254 (reduce concat255 (map (partial combinations (type-names))256 (range 1 (inc n)))))))258 (defn susceptibility259 "Hash-map of the susceptibilities of the given type combination260 to each type of attack"261 [pkmn-types]262 (rlm.map-utils/map-vals263 clojure.core/rationalize264 (apply hash-map265 (interleave (type-names)266 (apply (partial map *)267 (map (defense-strengths) pkmn-types))))))269 (defn susceptance270 "The cumulative susceptibility of the given type combination"271 [types]272 (reduce + (map #(expt % 2) (vals (susceptibility types)))))273 #+end_src275 Now we can work out the suceptability of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.277 Electric is weak to Ground.278 #+begin_src clojure :exports both279 (:ground (pokemon.types/susceptibility [:electric]))280 #+end_src282 #+results:283 : 2285 Flying is immune to Ground.286 #+begin_src clojure :exports both287 (:ground (pokemon.types/susceptibility [:flying]))288 #+end_src290 #+results:291 : 0293 Together, they are immune to Ground.294 #+begin_src clojure :exports both295 (:ground (pokemon.types/susceptibility [:electric :flying]))296 #+end_src298 #+results:299 : 0304 * Best-First Search306 I'd like to find type combinations that are interesting, but the total307 number of combinations gets huge as we begin to consider more308 types. For example, the total possible number of type combinations309 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.310 Therefore, it's prudent to use search.312 These functions are a simple implementation of best-first search in313 clojure. The idea to start off with a collection of nodes and some way314 of finding the best node, and to always expand the best node at every315 step.317 #+srcname: search318 #+begin_src clojure :results silent319 (in-ns 'pokemon.types)321 (defn comparatize322 "Define a comparator which uses the numerical outputs of fn as its criterion.323 Objects are sorted in increasing numerical order. Objects with the same fn-value324 are further compared by clojure.core/compare."325 [fun]326 (fn [a b]327 (let [val-a (fun a)328 val-b (fun b)]329 (cond330 ;; if the function cannot differentiate the two values331 ;; then compare the two values using clojure.core/compare332 (= val-a val-b) (compare a b)333 true334 ;; LOWER values of the function are preferred335 (compare (- val-a val-b) 0)))))337 (defn-memo best-first-step [successors [visited unvisited]]338 (cond (empty? unvisited) nil339 true340 (let [best-node (first unvisited)341 visited* (conj visited best-node)342 unvisited*343 (difference344 (union unvisited (set (successors best-node)))345 visited*)]346 (println best-node)347 [visited* unvisited*])))349 ;; memoize partial from core so that for example350 ;; (= (partial + 1) (partial + 1))351 ;; this way, best first search can take advantage of the memoization352 ;; of best-first step353 (undef partial)354 (def partial (memoize clojure.core/partial))356 (defn best-first-search357 "Searches through a network of alternatives, pursuing358 initially-promising positions first. Comparator defines which359 positions are more promising, successors produces a list of improved360 positions from the given position (if any exist), and initial-nodes is361 a list of starting positions. Returns a lazy sequence of search results362 [visited-nodes unvisited-nodes], which terminates when363 there are no remaining unvisited positions."364 [comparator successors initial-nodes]365 (let [initial-nodes366 (apply (partial sorted-set-by comparator) initial-nodes)367 initial-visited-nodes (sorted-set-by comparator)368 step (partial best-first-step successors)]369 (take-while370 (comp not nil?)371 (iterate step [initial-visited-nodes initial-nodes]))))373 #+end_src376 Now that we have a basic best-first-search, it's convenient to write a377 few pok\eacute{}mon-type specific convenience functions.379 #+srcname: pokemon-search380 #+begin_src clojure :results silent381 (in-ns 'pokemon.types)382 (defvar type-compare (comparatize susceptance)383 "compare two type combinations wrt their susceptibilities")385 (defn type-successors386 "Return the set of types that can be made by appending a single type387 to the given combination."388 [type]389 (if (nil? type) '()390 (set (map (comp vec sort (partial into type)) (multitypes 1)))))392 (defn immortal?393 "A type combo is immortal if it is resistant or invulnerable to394 every pokemon type. This is because that set of types can just be395 repeated to achieve as low a susceptance as desired"396 [type]397 (every? (partial > 1) (vals (susceptibility type))))399 (defn type-successors*400 "Stop expanding a type if it's immortal, or if it is longer than or401 equal to limit-size. Also, only return type additions that are402 strictly better than the initial type."403 [limit-size type]404 (if (or (<= limit-size (count type)) (immortal? type)) '()405 (set (filter #(< 0 (type-compare type %)) (type-successors type)))))407 (defn pokemon-type-search408 "Search among type-combos no greater than length n, limited by limit409 steps of best-first-search."410 ([n] (pokemon-type-search n Integer/MAX_VALUE))411 ([n limit]412 (first (last413 (take414 limit415 (best-first-search416 type-compare417 (partial type-successors* n)418 (multitypes 1)))))))420 (defvar immortals421 (comp (partial filter immortal?) pokemon-type-search)422 "find all the immortal pokemon types ")424 #+end_src426 Because there are so many type combinations, it's important to narrow427 down the results as much as possible. That is why =type-successors*=428 only returns types that are actually better than the type it is given.430 Best-first search can get caught optimizing a single type forever, so431 it's also important to limit the search space to be finite by setting432 an upper bound on the length of a type combo.434 * Results435 ** The best dual-type combo437 #+begin_src clojure :results cache verbatim :exports both438 (first (pokemon.types/pokemon-type-search 2))439 #+end_src441 #+results:442 : [:dark :ghost]444 Dark and Ghost, which additionally has the property of having no445 weaknesses to any other type, is the best type combo in terms of446 susceptance.448 The Dark and Steel types were introduced many years after449 pok\eacute{}mon started. In addition to the additional types, the450 pok\eacute{}mon games gained a few new rules concerning some of the451 matchups of the original types. Therefore, it's also interesting to452 see what type combination was most powerful before those types and new453 rules were introduced.455 The easiest way to do this with my setup is to just rebind the456 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since457 everything that references this variable is a function and we're not458 doing anything too crazy with lazy-sequences and late-binding, this459 simple macro will do the job.461 #+srcname: old-school462 #+begin_src clojure :results silent463 (in-ns 'pokemon.types)465 (defmacro old-school466 [& forms]467 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))468 #+end_src470 Using the =old-school= macro, it's easy to find answers for the471 original 15 pokemon types as well as the expanded pokemon types472 introduced later.474 #+begin_src clojure :results verbatim :exports both :cache yes475 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))476 #+end_src478 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:479 : [:ghost :psychic]481 Ghost and Psychic also manages to have no weaknesses to any of the original482 types, using the old Generation I rules.484 #+begin_src clojure :results output :exports both485 (clojure.pprint/pprint486 (pokemon.types/old-school487 (pokemon.types/susceptibility [:ghost :psychic])))488 #+end_src490 #+results:491 #+begin_example492 {:water 1,493 :psychic 1/2,494 :dragon 1,495 :fire 1,496 :ice 1,497 :grass 1,498 :ghost 0,499 :poison 1/2,500 :flying 1,501 :normal 0,502 :rock 1,503 :electric 1,504 :ground 1,505 :fighting 0,506 :bug 0}507 #+end_example509 ** An Immortal Type510 It's possible to quickly find an immortal type by giving the search511 a long enough maximum type length. 50 rounds of search with a max512 type limit of 10 is enough to find an immortal type.514 #+begin_src clojure :results scalar :exports both515 (first (pokemon.types/pokemon-type-search 10 50))516 #+end_src518 #+results:519 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]522 #+begin_src clojure :results output :exports both523 (clojure.pprint/pprint524 (pokemon.types/susceptibility525 [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))526 #+end_src528 #+results:529 #+begin_example530 {:water 1/4,531 :psychic 1/4,532 :dragon 1/2,533 :fire 1/2,534 :ice 1/2,535 :grass 1/8,536 :ghost 1/2,537 :poison 0,538 :flying 1/2,539 :normal 0,540 :rock 1/2,541 :electric 0,542 :ground 0,543 :fighting 0,544 :dark 1/2,545 :steel 1/32,546 :bug 1/16}547 #+end_example549 ** Explanations for Common Pok\eacute{}mon Strategies551 Many people start out a battle with either a Normal pok\eacute{}mon or an552 Electric pok\eacute{}mon. Here's some justification for that choice.554 #+srcname: weaknesses555 #+begin_src clojure :results silent556 (in-ns 'pokemon.types)557 (defn critical-weaknesses [type]558 (count (filter #(> % 1) (vals (susceptibility type)))))559 #+end_src561 #+begin_src clojure :exports both :results output562 (clojure.pprint/pprint563 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))564 #+end_src566 #+results:567 #+begin_example568 ([:normal]569 [:electric]570 [:water]571 [:fighting]572 [:poison]573 [:ghost]574 [:dragon]575 [:dark]576 [:fire]577 [:ground]578 [:flying]579 [:psychic]580 [:bug]581 [:steel]582 [:ice]583 [:grass]584 [:rock])585 #+end_example587 Electric and Normal are among the best types with which to start the588 game, since they have the fewest weaknesses among all the types.590 At the beginning of the pok\eacute{}mon games, players are given a591 choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water592 pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon593 [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].595 #+begin_src clojure :exports both :results verbatim596 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])597 #+end_src599 #+results:600 : ([:water] [:fire] [:grass :poison])602 As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid603 choice starting out, insofar as susceptance is concerned.605 ** The Worst Pok\eacute{}mon Types607 #+srcname: weak-types608 #+begin_src clojure :results silent609 (in-ns 'pokemon.types)611 (defn type-compare-weak612 "compare first by total number of critical-weaknesses,613 then by overall susceptance, favoring weaker types."614 [type-1 type-2]615 (let [measure (memoize (juxt critical-weaknesses susceptance))]616 (if (= (measure type-2) (measure type-1))617 (compare type-2 type-1)618 (compare (measure type-2) (measure type-1)))))620 (defn resistant?621 "might as well get rid of types that are resistant to any type"622 [type]623 (not (every? #(< 0 %) (vals (susceptibility type)))))625 (defn type-successors-weak626 "Generate ways to weaken the given type combination. Discard type627 combinations that either strengthen the given type combination or628 that make it stronger"629 [limit type]630 (set (if (<= limit (count type)) '()631 (filter #(< 0 (type-compare-weak type %))632 (remove resistant? (type-successors type))))))634 (defn pokemon-type-search-weak635 "Search among type-combos no greater than length n, limited by limit636 steps of best-first-search. Find the weakest type combination637 possible in terms of susceptance."638 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))639 ([n limit]640 (first (last641 (take642 limit643 (best-first-search644 type-compare-weak645 (partial type-successors-weak n)646 (multitypes 1)))))))647 #+end_src650 #+begin_src clojure :results scalar :exports both651 (first (pokemon.types/pokemon-type-search-weak 1))652 #+end_src654 #+results:655 : [:rock]657 Poor Rock. It's just not that good a type. Maybe this is why Brock658 (who has rock pok\eacute{}mon) is the first gym leader in the games.660 #+begin_src clojure :results scalar cache :exports both661 (first (pokemon.types/pokemon-type-search-weak 2))662 #+end_src664 #+results:665 : [:grass :ice]667 # ;;bonus convergently immortal type combo668 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))670 #+begin_src clojure :results output :exports both671 (clojure.pprint/pprint672 (pokemon.types/susceptibility [:grass :ice]))673 #+end_src675 #+results:676 #+begin_example677 {:water 1/2,678 :psychic 1,679 :dragon 1,680 :fire 4,681 :ice 1,682 :grass 1/2,683 :ghost 1,684 :poison 2,685 :flying 2,686 :normal 1,687 :rock 2,688 :electric 1/2,689 :ground 1/2,690 :fighting 2,691 :dark 1,692 :steel 2,693 :bug 2}694 #+end_example696 This miserable combination is weak to 6 types and double-weak to697 Fire. No pok\eacute{}mon in the games actually has this type.699 * Conclusion701 Searching for a type that is weak to everything takes a very long time702 and fails to reveal any results. That's the problem with a search703 over this large problem space --- if there's an easy solution, the704 search will find it quickly, but it can be very hard to determine705 whether there is actually a solution.707 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in708 a different way.710 * COMMENT main program711 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none712 <<header>>713 #+end_src715 ## this is necessary to define pokemon-table inside the source code.717 #+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 none718 <<data>>719 #+end_src721 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none722 <<types>>723 <<search>>724 <<pokemon-search>>725 <<old-school>>726 <<weaknesses>>727 <<weak-types>>728 #+end_src