Mercurial > pokemon-types
view org/types.org @ 22:8992278bf399 tip
typo corrected, thanks to a reader.
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sun, 20 Sep 2015 11:25:30 -0700 |
parents | 0f6ace87343a |
children |
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 #+keywords: Pokemon, clojure, best-first search, optimization6 #+SETUPFILE: ../../aurellem/org/setup.org7 #+INCLUDE: ../../aurellem/org/level-0.org9 * The Pok\eacute{}mon Type System11 The Pok\eacute{}mon type system consists of seventeen different12 /types/ (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, Fire,13 Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, and14 Steel) that interact like an extended version of Rock-Paper-Scissors:15 for example, the Fire type is strong against the Grass type but weak16 against the Water type. In the table below, we've recorded the17 relative strengths of each of the types in the Pok\eacute{}mon type18 system; the number in each cell indicates how effective an attack of19 the type in the row is against a Pok\eacute{}mon of the type in the20 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 particularly24 high susceptibility, average susceptibility, particularly low25 susceptibility, and no susceptibility (immunity).27 - The susceptibility of Flying types /against/ Ground is 0, because Ground28 attacks cannot hurt Flying pok\eacute{}mon at all. The damage that29 a Ground type attack normally does is /multiplied/ by 0 when it is30 used against a Flying type pok\eacute{}mon.32 - The susceptibility of Fire types against Water attacks33 is 2, because Water type attacks are strong against Fire type34 Pok\eacute{}mon. The damage that a Water type attack normally does35 is doubled when it is used against a Fire type pok\eacute{}mon.37 - The susceptibility of Water types against Water attacks is38 $\frac{1}{2}$, because Water type attacks are weak against Water39 type Pok\eacute{}mon. The damage that a Water type attack normally40 does is halved when it is used against a Water type41 pok\eacute{}mon.43 There are two pok\eacute{}mon type systems in use. The first is the44 classic system which was used for the very first pok\eacute{}mon45 games, Red, Yellow, and Blue. This old system was used from 1998 to46 2000 in America, and is known as the /Generation I Type System/. The47 modern pok\eacute{}mon type system was introduced in 2000 with the48 introduction of pok\eacute{}mon Gold and Silver, and has been in use49 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 Data55 ** Generation II Type System56 #+label: pokemon-matchups57 #+tblname: pokemon-table-gen-two58 | | 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. To79 see the multiplier for a pok\eacute{}mon attack against a certain type, follow80 the row for the attack type to the column of the defending type.82 ** Generation I Type System83 #+label: pokemon-matchups-gen-184 #+tblname: pokemon-table-gen-one85 | | 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 from105 Generation II are:106 - Dark and Steel types are missing (these were introduced in107 Generation II).108 - Bug is super-effective against Poison (not-very-effective in109 Generation II).110 - Poison is super-effective against Bug (normal in Generation II).111 - Bug is regularly effective against Ghost (super-effective in112 Generation II).113 - Ice is normally effective against Fire, (not-very-effective in114 Generation II).115 - Ghost is completely ineffective against Psychic, even though the116 pok\eacute{}mon anime ran [[http://bulbapedia.bulbagarden.net/wiki/EP022][a three-part series]] about how Ghost117 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 who119 states "The only thing Psychic pok\eacute{}mon fear are Bugs and120 Ghosts!" This is considered to be a programming glitch. Ghost is121 super-effective against Psychic in Generation II.123 * Representing the Data125 After creating the Pok\eacute{}mon types namespace, we store the126 tables of susceptibilities above in =pokemon-table-gen-one= and127 =pokemon-table-gen-two=, each of which is a simple vector of128 vectors. Because a vector of vectors can be cumbersome, we do not129 access the tables directly; instead, we use the derivative structures130 =attack-strengths= and =defense-strengths=, which are functions which131 return hash-maps associating each row (respectively column) of the132 table with its corresponding Pok\eacute{}mon type.135 #+name: header136 #+begin_src clojure :results silent137 (ns pokemon.types138 (:use clojure.set)139 ;; (:use clojure.contrib.combinatorics)140 (:use clojure.math.combinatorics)141 (:use clojure.math.numeric-tower)142 ;; (:use clojure.contrib.def)143 (:use rlm.rlm-commands)144 (:require rlm.map-utils))145 #+end_src147 #+name: data148 #+begin_src clojure :results silent149 (in-ns 'pokemon.types)150 ;; record type strengths as a vector of vectors151 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two152 ;; are replaced with the tables above when this file is tangled.153 (def pokemon-gen-one pokemon-table-gen-one)154 (def pokemon-gen-two pokemon-table-gen-two)156 (defn type-names []157 (vec (doall (map (comp keyword first) pokemon-gen-two))))159 (defn attack-strengths []160 (zipmap161 (type-names)162 (map (comp vec rest) pokemon-gen-two)))164 (defn defense-strengths []165 (zipmap (type-names)166 (map167 (apply juxt (map (attack-strengths) (type-names)))168 (range (count (type-names))))))169 #+end_src171 The two statements173 #+begin_src clojure :exports code174 (def pokemon-gen-one pokemon-table-gen-one)175 (def pokemon-gen-two pokemon-table-gen-two)176 #+end_src178 probably look weird. When the actual source file is created, those179 variables are replaced with the data from the tables above.181 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.184 #+begin_src clojure :results output :exports both185 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)186 #+end_src188 #+results:189 #+begin_example190 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)191 ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)192 ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)193 ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)194 ("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)195 ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)196 ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)197 ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)198 ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)199 ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)200 ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)201 ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)202 ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)203 ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)204 ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)205 ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)206 ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))207 #+end_example209 =pokemon-gen-two= is a simple list-of-lists data structure.211 #+begin_src clojure :results output :exports both212 (clojure.pprint/pprint (pokemon.types/defense-strengths))213 #+end_src215 #+results:216 #+begin_example217 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],218 :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],219 :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],220 :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],221 :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],222 :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],223 :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],224 :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],225 :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],226 :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],227 :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],228 :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],229 :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],230 :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],231 :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],232 :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],233 :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}234 #+end_example236 =defense-strengths= is a more convenient form of =pokemon-gen-two=,237 with key/value pair access.239 * Interfacing with the Data241 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two242 types at the same time. For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary243 bird that can control lightning, has both the Electric and Flying244 types. A pok\eacute{}mon with more than one type gains the advantages245 and disadvantages of both types. The susceptibilities of each type are246 multiplied together to produce the hybrid type's susceptibilities. For247 example, Electric is weak to Ground (susceptibility of 2), but Flying248 is immune to Ground (susceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,249 Electric/Flying, is immune to Ground because $2 \times 0 = 0$.251 #+name: types252 #+begin_src clojure :results silent253 (in-ns 'pokemon.types)255 (defn multitypes "All combinations of up to n types" [n]256 (vec257 (map vec258 (reduce concat259 (map (partial combinations (type-names))260 (range 1 (inc n)))))))262 (defn susceptibility263 "Hash-map of the susceptibilities of the given type combination264 to each type of attack"265 [pkmn-types]266 (rlm.map-utils/map-vals267 clojure.core/rationalize268 (apply hash-map269 (interleave (type-names)270 (apply (partial map *)271 (map (defense-strengths) pkmn-types))))))273 (defn susceptance274 "The cumulative susceptibility of the given type combination"275 [types]276 (reduce + (map #(expt % 2) (vals (susceptibility types)))))277 #+end_src279 Now we can work out the susceptibility of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.281 Electric is weak to Ground.282 #+begin_src clojure :exports both283 (:ground (pokemon.types/susceptibility [:electric]))284 #+end_src286 #+results:287 : 2289 Flying is immune to Ground.290 #+begin_src clojure :exports both291 (:ground (pokemon.types/susceptibility [:flying]))292 #+end_src294 #+results:295 : 0297 Together, they are immune to Ground.298 #+begin_src clojure :exports both299 (:ground (pokemon.types/susceptibility [:electric :flying]))300 #+end_src302 #+results:303 : 0308 * Best-First Search310 I'd like to find type combinations that are interesting, but the total311 number of combinations gets huge as we begin to consider more312 types. For example, the total possible number of type combinations313 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.314 Therefore, it's prudent to use search.316 These functions are a simple implementation of best-first search in317 clojure. The idea is to start off with a collection of nodes and some318 way of finding the best node, and to always expand the best node at319 every step.321 #+name: search322 #+begin_src clojure :results silent323 (in-ns 'pokemon.types)325 (defn comparatize326 "Define a comparator which uses the numerical outputs of327 fn as its criterion. Objects are sorted in increasing328 numerical order. Objects with the same fn-value are329 further compared by clojure.core/compare."330 [fun]331 (fn [a b]332 (let [val-a (fun a)333 val-b (fun b)]334 (cond335 ;; if the function cannot differentiate the two values336 ;; then compare the two values using clojure.core/compare337 (= val-a val-b) (compare a b)338 true339 ;; LOWER values of the function are preferred340 (compare (- val-a val-b) 0)))))342 (defn best-first-step [successors [visited unvisited]]343 (cond (empty? unvisited) nil344 true345 (let [best-node (first unvisited)346 visited* (conj visited best-node)347 unvisited*348 (difference349 (union unvisited (set (successors best-node)))350 visited*)]351 (println best-node)352 [visited* unvisited*])))353 (alter-var-root #'best-first-step memoize)355 ;; memoize partial from core so that for example356 ;; (= (partial + 1) (partial + 1))357 ;; this way, best first search can take advantage of the memoization358 ;; of best-first step359 (undef partial)360 (def partial (memoize clojure.core/partial))362 (defn best-first-search363 "Searches through a network of alternatives, pursuing364 initially-promising positions first. Comparator defines365 which positions are more promising, successors produces a366 list of improved positions from the given position (if367 any exist), and initial-nodes is a list of starting368 positions. Returns a lazy sequence of search results369 [visited-nodes unvisited-nodes], which terminates when370 there are no remaining unvisited positions."371 [comparator successors initial-nodes]372 (let [initial-nodes373 (apply (partial sorted-set-by comparator) initial-nodes)374 initial-visited-nodes (sorted-set-by comparator)375 step (partial best-first-step successors)]376 (take-while377 (comp not nil?)378 (iterate step [initial-visited-nodes initial-nodes]))))380 #+end_src383 Now that we have a basic best-first-search, it's convenient to write a384 few pok\eacute{}mon-type specific convenience functions.386 #+name: pokemon-search387 #+begin_src clojure :results silent388 (in-ns 'pokemon.types)389 (def type-compare390 "compare two type combinations W.R.T. their susceptibilities"391 (comparatize susceptance))393 (defn type-successors394 "Return the set of types that can be made by appending a395 single type to the given combination."396 [type]397 (if (nil? type) '()398 (set (map (comp vec sort (partial into type)) (multitypes 1)))))400 (defn immortal?401 "A type combo is immortal if it is resistant or402 invulnerable to every pokemon type. This is because that403 set of types can just be repeated to achieve as low a404 susceptance as desired"405 [type]406 (every? (partial > 1) (vals (susceptibility type))))408 (defn type-successors*409 "Stop expanding a type if it's immortal, or if it is410 longer than or equal to limit-size. Also, only return type411 additions that are strictly better than the initial type."412 [limit-size type]413 (if (or (<= limit-size (count type)) (immortal? type)) '()414 (set (filter #(< 0 (type-compare type %))415 (type-successors type)))))417 (defn pokemon-type-search418 "Search among type-combos no greater than length n,419 limited by limit steps of best-first-search."420 ([n] (pokemon-type-search n Integer/MAX_VALUE))421 ([n limit]422 (first (last423 (take424 limit425 (best-first-search426 type-compare427 (partial type-successors* n)428 (multitypes 1)))))))430 (def immortals431 "find all the immortal pokemon types."432 (comp (partial filter immortal?) pokemon-type-search))434 #+end_src436 Because there are so many type combinations, it's important to narrow437 down the results as much as possible. That is why =type-successors*=438 only returns types that are actually better than the type it is given.440 Best-first search can get caught optimizing a single type forever, so441 it's also important to limit the search space to be finite by setting442 an upper bound on the length of a type combo.444 * Results445 ** The best dual-type combo447 #+begin_src clojure :results cache verbatim :exports both448 (first (pokemon.types/pokemon-type-search 2))449 #+end_src451 #+results:452 : [:dark :ghost]454 Dark and Ghost, which additionally has the property of having no455 weaknesses to any other type, is the best type combo in terms of456 susceptance.458 The Dark and Steel types were introduced many years after459 pok\eacute{}mon started. In addition to the additional types, the460 pok\eacute{}mon games gained a few new rules concerning some of the461 matchups of the original types. Therefore, it's also interesting to462 see what type combination was most powerful before those types and new463 rules were introduced.465 The easiest way to do this with my setup is to just rebind the466 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since467 everything that references this variable is a function and we're not468 doing anything too crazy with lazy-sequences and late-binding, this469 simple macro will do the job.471 #+name: old-school472 #+begin_src clojure :results silent473 (in-ns 'pokemon.types)475 (defmacro old-school476 [& forms]477 `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))478 #+end_src480 Using the =old-school= macro, it's easy to find answers for the481 original 15 pokemon types as well as the expanded pokemon types482 introduced later.484 #+begin_src clojure :results verbatim :exports both :cache yes485 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))486 #+end_src488 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:489 : [:ghost :psychic]491 Ghost and Psychic also manages to have no weaknesses to any of the original492 types, using the old Generation I rules.494 #+begin_src clojure :results output :exports both495 (clojure.pprint/pprint496 (pokemon.types/old-school497 (pokemon.types/susceptibility [:ghost :psychic])))498 #+end_src500 #+results:501 #+begin_example502 {:water 1,503 :psychic 1/2,504 :dragon 1,505 :fire 1,506 :ice 1,507 :grass 1,508 :ghost 0,509 :poison 1/2,510 :flying 1,511 :normal 0,512 :rock 1,513 :electric 1,514 :ground 1,515 :fighting 0,516 :bug 0}517 #+end_example519 ** An Immortal Type520 It's possible to quickly find an immortal type by giving the search521 a long enough maximum type length. 50 rounds of search with a max522 type limit of 10 is enough to find an immortal type.524 #+begin_src clojure :results scalar :exports both525 (first (pokemon.types/pokemon-type-search 10 50))526 #+end_src528 #+results:529 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]532 #+begin_src clojure :results output :exports both533 (clojure.pprint/pprint534 (pokemon.types/susceptibility535 [:dragon :fire :flying :ghost :grass :ground536 :steel :steel :water :water]))537 #+end_src539 #+results:540 #+begin_example541 {:water 1/4,542 :psychic 1/4,543 :dragon 1/2,544 :fire 1/2,545 :ice 1/2,546 :grass 1/8,547 :ghost 1/2,548 :poison 0,549 :flying 1/2,550 :normal 0,551 :rock 1/2,552 :electric 0,553 :ground 0,554 :fighting 0,555 :dark 1/2,556 :steel 1/32,557 :bug 1/16}558 #+end_example560 ** Explanations for Common Pok\eacute{}mon Strategies562 Many people start out a battle with either a Normal pok\eacute{}mon or an563 Electric pok\eacute{}mon. Here's some justification for that choice.565 #+name: weaknesses566 #+begin_src clojure :results silent567 (in-ns 'pokemon.types)568 (defn critical-weaknesses [type]569 (count (filter #(> % 1) (vals (susceptibility type)))))570 #+end_src572 #+begin_src clojure :exports both :results output573 (clojure.pprint/pprint574 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))575 #+end_src577 #+results:578 #+begin_example579 ([:normal]580 [:electric]581 [:water]582 [:fighting]583 [:poison]584 [:ghost]585 [:dragon]586 [:dark]587 [:fire]588 [:ground]589 [:flying]590 [:psychic]591 [:bug]592 [:steel]593 [:ice]594 [:grass]595 [:rock])596 #+end_example598 Electric and Normal are among the best types with which to start the599 game, since they have the fewest weaknesses among all the types.601 At the beginning of the pok\eacute{}mon games, players are given a602 choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water603 pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon604 [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].606 #+begin_src clojure :exports both :results verbatim607 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])608 #+end_src610 #+results:611 : ([:water] [:fire] [:grass :poison])613 As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid614 choice starting out, insofar as susceptance is concerned.616 ** The Worst Pok\eacute{}mon Types618 #+name: weak-types619 #+begin_src clojure :results silent620 (in-ns 'pokemon.types)622 (defn type-compare-weak623 "compare first by total number of critical-weaknesses,624 then by overall susceptance, favoring weaker types."625 [type-1 type-2]626 (let [measure (memoize (juxt critical-weaknesses susceptance))]627 (if (= (measure type-2) (measure type-1))628 (compare type-2 type-1)629 (compare (measure type-2) (measure type-1)))))631 (defn resistant?632 "might as well get rid of types that are resistant to any type"633 [type]634 (not (every? #(< 0 %) (vals (susceptibility type)))))636 (defn type-successors-weak637 "Generate ways to weaken the given type combination. Discard type638 combinations that either strengthen the given type combination or639 that make it stronger"640 [limit type]641 (set (if (<= limit (count type)) '()642 (filter #(< 0 (type-compare-weak type %))643 (remove resistant? (type-successors type))))))645 (defn pokemon-type-search-weak646 "Search among type-combos no greater than length n, limited by limit647 steps of best-first-search. Find the weakest type combination648 possible in terms of susceptance."649 ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))650 ([n limit]651 (first (last652 (take653 limit654 (best-first-search655 type-compare-weak656 (partial type-successors-weak n)657 (multitypes 1)))))))658 #+end_src661 #+begin_src clojure :results scalar :exports both662 (first (pokemon.types/pokemon-type-search-weak 1))663 #+end_src665 #+results:666 : [:rock]668 Poor Rock. It's just not that good a type. Maybe this is why Brock669 (who has rock pok\eacute{}mon) is the first gym leader in the games.671 #+begin_src clojure :results scalar cache :exports both672 (first (pokemon.types/pokemon-type-search-weak 2))673 #+end_src675 #+results:676 : [:grass :ice]678 # ;;bonus convergently immortal type combo679 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))681 #+begin_src clojure :results output :exports both682 (clojure.pprint/pprint683 (pokemon.types/susceptibility [:grass :ice]))684 #+end_src686 #+results:687 #+begin_example688 {:water 1/2,689 :psychic 1,690 :dragon 1,691 :fire 4,692 :ice 1,693 :grass 1/2,694 :ghost 1,695 :poison 2,696 :flying 2,697 :normal 1,698 :rock 2,699 :electric 1/2,700 :ground 1/2,701 :fighting 2,702 :dark 1,703 :steel 2,704 :bug 2}705 #+end_example707 This miserable combination is weak to 6 types and double-weak to708 Fire. No pok\eacute{}mon in the games actually has this type.710 * Conclusion712 Searching for a type that is weak to everything takes a very long time713 and fails to reveal any results. That's the problem with a search714 over this large problem space --- if there's an easy solution, the715 search will find it quickly, but it can be very hard to determine716 whether there is actually a solution.718 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in719 a different way.721 * COMMENT main program722 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none723 <<header>>724 #+end_src726 ## this is necessary to define pokemon-table inside the source code.728 #+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 none729 <<data>>730 #+end_src732 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none733 <<types>>734 <<search>>735 <<pokemon-search>>736 <<old-school>>737 <<weaknesses>>738 <<weak-types>>739 #+end_src