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