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