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