annotate org/types.org @ 10:eedd6897197d

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