rlm@7: #+TITLE: Best-First Search for Effective Pokemon Types
rlm@0: #+AUTHOR:    Robert McIntyre & Dylan Holmes
rlm@0: #+EMAIL:     rlm@mit.edu
rlm@7: #+description: Finding interesting pokemon type combinations through Best-First search in clojure.
rlm@10: #+keywords: Pokemon, clojure, best-first search, optimization
rlm@4: #+SETUPFILE: ../../aurellem/org/setup.org
rlm@4: #+INCLUDE:   ../../aurellem/org/level-0.org
rlm@0: 
rlm@0: * The Pok\eacute{}mon Type System
rlm@0:   
rlm@0: The Pok\eacute{}mon type system consists of seventeen different
rlm@9: /types/ (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, Fire,
rlm@9: Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, and
rlm@9: Steel) that interact like an extended version of Rock-Paper-Scissors:
rlm@9: for example, the Fire type is strong against the Grass type but weak
rlm@9: against the Water type. In the table below, we've recorded the
rlm@9: relative strengths of each of the types in the Pok\eacute{}mon type
rlm@9: system; the number in each cell indicates how effective an attack of
rlm@9: the type in the row is against a Pok\eacute{}mon of the type in the
rlm@9: column. We call these numbers /susceptibilities/.
rlm@0: 
rlm@0: In the Pok\eacute{}mon games, only four susceptibility values (two,
rlm@0: one, one-half, and zero) occur. These numbers indicate particularly
rlm@0: high susceptibility, average susceptibility, particularly low
rlm@5: susceptibility, and no susceptibility (immunity).
rlm@0: 
rlm@10:  - The susceptibility of Flying types /against/ Ground is 0, because Ground
rlm@5:    attacks cannot hurt Flying pok\eacute{}mon at all. The damage that
rlm@5:    a Ground type attack normally does is  /multiplied/ by 0 when it is
rlm@10:    used against a Flying type pok\eacute{}mon.
rlm@0: 
rlm@10:  - The susceptibility of Fire types against Water attacks
rlm@5:    is 2, because Water type attacks are strong against Fire type
rlm@5:    Pok\eacute{}mon. The damage that a Water type attack normally does
rlm@5:    is doubled when it is used against a Fire type pok\eacute{}mon.
rlm@0: 
rlm@10:  - The susceptibility of Water types against Water attacks is
rlm@5:    $\frac{1}{2}$, because Water type attacks are strong against Water
rlm@5:    type Pok\eacute{}mon. The damage that a Water type attack normally
rlm@5:    does is halved when it is used against a Water type
rlm@5:    pok\eacute{}mon.
rlm@5: 
rlm@5: There are two pok\eacute{}mon type systems in use. The first is the
rlm@5: classic system which was used for the very first pok\eacute{}mon
rlm@5: games, Red, Yellow, and Blue. This old system was used from 1998 to
rlm@5: 2000 in America, and is known as the /Generation I Type System/.  The
rlm@5: modern pok\eacute{}mon type system was introduced in 2000 with the
rlm@5: introduction of pok\eacute{}mon Gold and Silver, and has been in use
rlm@5: ever since.  It is called the /Generation II Type System/.
rlm@5: 
rlm@9: The definitions of the two Type Systems are included below. 
rlm@5: 
rlm@7: * Generation I and II Type System Data 
rlm@0: 
rlm@6: ** Generation II Type System
rlm@0: #+label: pokemon-matchups
rlm@0: #+tblname: pokemon-table-gen-two
rlm@0: |          | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel |
rlm@0: |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------|
rlm@0: | normal   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |   .5 |     0 |      1 |    1 |    .5 |
rlm@0: | fire     |      1 |   .5 |    .5 |        1 |     2 |   2 |        1 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |     .5 |    1 |     2 |
rlm@0: | water    |      1 |    2 |    .5 |        1 |    .5 |   1 |        1 |      1 |      2 |      1 |       1 |   1 |    2 |     1 |     .5 |    1 |     1 |
rlm@0: | electric |      1 |    1 |     2 |       .5 |    .5 |   1 |        1 |      1 |      0 |      2 |       1 |   1 |    1 |     1 |     .5 |    1 |     1 |
rlm@0: | grass    |      1 |   .5 |     2 |        1 |    .5 |   1 |        1 |     .5 |      2 |     .5 |       1 |  .5 |    2 |     1 |     .5 |    1 |    .5 |
rlm@0: | ice      |      1 |   .5 |    .5 |        1 |     2 |  .5 |        1 |      1 |      2 |      2 |       1 |   1 |    1 |     1 |      2 |    1 |    .5 |
rlm@0: | fighting |      2 |    1 |     1 |        1 |     1 |   2 |        1 |     .5 |      1 |     .5 |      .5 |  .5 |    2 |     0 |      1 |    2 |     2 |
rlm@0: | poison   |      1 |    1 |     1 |        1 |     2 |   1 |        1 |     .5 |     .5 |      1 |       1 |   1 |   .5 |    .5 |      1 |    1 |     0 |
rlm@0: | ground   |      1 |    2 |     1 |        2 |    .5 |   1 |        1 |      2 |      1 |      0 |       1 |  .5 |    2 |     1 |      1 |    1 |     2 |
rlm@0: | flying   |      1 |    1 |     1 |       .5 |     2 |   1 |        2 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |      1 |    1 |    .5 |
rlm@0: | psychic  |      1 |    1 |     1 |        1 |     1 |   1 |        2 |      2 |      1 |      1 |      .5 |   1 |    1 |     1 |      1 |    0 |    .5 |
rlm@0: | bug      |      1 |   .5 |     1 |        1 |     2 |   1 |       .5 |     .5 |      1 |     .5 |       2 |   1 |    1 |    .5 |      1 |    2 |    .5 |
rlm@0: | rock     |      1 |    2 |     1 |        1 |     1 |   2 |       .5 |      1 |     .5 |      2 |       1 |   2 |    1 |     1 |      1 |    1 |    .5 |
rlm@0: | ghost    |      0 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       2 |   1 |    1 |     2 |      1 |   .5 |    .5 |
rlm@0: | dragon   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |    1 |     1 |      2 |    1 |    .5 |
rlm@0: | dark     |      1 |    1 |     1 |        1 |     1 |   1 |       .5 |      1 |      1 |      1 |       2 |   1 |    1 |     2 |      1 |   .5 |    .5 |
rlm@0: | steel    |      1 |   .5 |    .5 |       .5 |     1 |   2 |        1 |      1 |      1 |      1 |       1 |   1 |    2 |     1 |      1 |    1 |    .5 |
rlm@0: 
rlm@6: The rows are attack types, while the columns are defense types.  To
rlm@8: see the multiplier for a pok\eacute{}mon attack against a certain type, follow
rlm@6: the row for the attack type to the column of the defending type.
rlm@6: 
rlm@6: ** Generation I Type System
rlm@7: #+label: pokemon-matchups-gen-1 
rlm@7: #+tblname: pokemon-table-gen-one
rlm@0: |          | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |
rlm@0: |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|
rlm@0: | normal   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |   .5 |     0 |      1 |
rlm@0: | fire     |      1 |   .5 |    .5 |        1 |     2 |   2 |        1 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |     .5 |
rlm@0: | water    |      1 |    2 |    .5 |        1 |    .5 |   1 |        1 |      1 |      2 |      1 |       1 |   1 |    2 |     1 |     .5 |
rlm@0: | electric |      1 |    1 |     2 |       .5 |    .5 |   1 |        1 |      1 |      0 |      2 |       1 |   1 |    1 |     1 |     .5 |
rlm@0: | grass    |      1 |   .5 |     2 |        1 |    .5 |   1 |        1 |     .5 |      2 |     .5 |       1 |  .5 |    2 |     1 |     .5 |
rlm@0: | ice      |      1 |    1 |    .5 |        1 |     2 |  .5 |        1 |      1 |      2 |      2 |       1 |   1 |    1 |     1 |      2 |
rlm@0: | fighting |      2 |    1 |     1 |        1 |     1 |   2 |        1 |     .5 |      1 |     .5 |      .5 |  .5 |    2 |     0 |      1 |
rlm@0: | poison   |      1 |    1 |     1 |        1 |     2 |   1 |        1 |     .5 |     .5 |      1 |       1 |   2 |   .5 |    .5 |      1 |
rlm@0: | ground   |      1 |    2 |     1 |        2 |    .5 |   1 |        1 |      2 |      1 |      0 |       1 |  .5 |    2 |     1 |      1 |
rlm@0: | flying   |      1 |    1 |     1 |       .5 |     2 |   1 |        2 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |      1 |
rlm@0: | psychic  |      1 |    1 |     1 |        1 |     1 |   1 |        2 |      2 |      1 |      1 |      .5 |   1 |    1 |     1 |      1 |
rlm@0: | bug      |      1 |   .5 |     1 |        1 |     2 |   1 |       .5 |      2 |      1 |     .5 |       2 |   1 |    1 |     0 |      1 |
rlm@0: | rock     |      1 |    2 |     1 |        1 |     1 |   2 |       .5 |      1 |     .5 |      2 |       1 |   2 |    1 |     1 |      1 |
rlm@0: | ghost    |      0 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       0 |   1 |    1 |     2 |      1 |
rlm@0: | dragon   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |    1 |     1 |      2 |
rlm@0: 
rlm@6: 
rlm@6: This is the old table from Generation I. The differences from
rlm@6: Generation II are: 
rlm@7:  - Dark and Steel types are missing (these were introduced in
rlm@7:    Generation II).
rlm@7:  - Bug is super-effective against Poison (not-very-effective in
rlm@7:    Generation II).
rlm@7:  - Poison is super-effective against Bug (normal in Generation II).
rlm@7:  - Bug is regularly effective against Ghost (super-effective in
rlm@7:    Generation II).
rlm@7:  - Ice is normally effective against Fire, (not-very-effective in
rlm@6:    Generation II).
rlm@9:  - Ghost is completely ineffective against Psychic, even though the
rlm@9:    pok\eacute{}mon anime ran [[http://bulbapedia.bulbagarden.net/wiki/EP022][a three-part series]] about how Ghost
rlm@9:    pok\eacute{}mon are the best way to defeat Psychic pok\eacute{}mon,
rlm@9:    and the Red, Blue, and Yellow games each have a character who
rlm@9:    states "The only thing Psychic pok\eacute{}mon fear are Bugs and
rlm@10:    Ghosts!" This is considered to be a programming glitch. Ghost is
rlm@9:    super-effective against Psychic in Generation II.
rlm@6: 
rlm@0: * Representing the Data
rlm@0: 
rlm@7: After creating the Pok\eacute{}mon types namespace, we store the
rlm@7: tables of susceptibilities above in =pokemon-table-gen-one= and
rlm@0: =pokemon-table-gen-two=, each of which is a simple vector of
rlm@0: vectors. Because a vector of vectors can be cumbersome, we do not
rlm@0: access the tables directly; instead, we use the derivative structures
rlm@0: =attack-strengths= and =defense-strengths=, which are functions which
rlm@0: return hash-maps associating each row (respectively column) of the
rlm@0: table with its corresponding Pok\eacute{}mon type.
rlm@0: 
rlm@0: 
rlm@0: #+srcname: header
rlm@0: #+begin_src clojure :results silent
rlm@0: (ns pokemon.types
rlm@7:   (:use clojure.set)
rlm@7:   (:use clojure.contrib.combinatorics)
rlm@7:   (:use clojure.contrib.math)
rlm@7:   (:use clojure.contrib.def)
rlm@13:   (:use rlm.rlm-commands)
rlm@13:   (:require rlm.map-utils))
rlm@0: #+end_src
rlm@0: 
rlm@7: #+srcname: data 
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: ;; record type strengths as a vector of vectors
rlm@7: ;; the variables pokemon-table-gen-one and pokemon-table-gen-two 
rlm@7: ;; are replaced with the tables above when this file is tangled.
rlm@0: (def pokemon-gen-one pokemon-table-gen-one)
rlm@0: (def pokemon-gen-two pokemon-table-gen-two)
rlm@0: 
rlm@0: (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))
rlm@0: 
rlm@0: (defn attack-strengths []
rlm@0:      (zipmap
rlm@0:       (type-names)
rlm@0:       (map (comp vec rest) pokemon-gen-two))) 
rlm@0: 
rlm@0: (defn defense-strengths []
rlm@0:      (zipmap (type-names)
rlm@0: 	     (map
rlm@0: 	      (apply juxt (map (attack-strengths) (type-names)))
rlm@0: 	      (range (count (type-names))))))
rlm@0: #+end_src
rlm@0: 
rlm@7: The two statements 
rlm@7: 
rlm@7: #+begin_src clojure :exports code
rlm@7: (def pokemon-gen-one pokemon-table-gen-one)
rlm@7: (def pokemon-gen-two pokemon-table-gen-two)
rlm@7: #+end_src
rlm@7: 
rlm@7: probably look weird.  When the actual source file is created, those
rlm@7: variables are replaced with the data from the tables above.
rlm@7: 
rlm@7: See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.
rlm@7: 
rlm@7: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)
rlm@0:  ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)
rlm@0:  ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)
rlm@0:  ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)
rlm@0:  ("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:  ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)
rlm@0:  ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)
rlm@0:  ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)
rlm@0:  ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)
rlm@0:  ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)
rlm@0:  ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)
rlm@0:  ("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:  ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)
rlm@0:  ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)
rlm@0:  ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)
rlm@0:  ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)
rlm@0:  ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
rlm@0: #+end_example
rlm@0: 
rlm@7: =pokemon-gen-two= is a simple list-of-lists data structure.
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint (pokemon.types/defense-strengths))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],
rlm@0:  :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],
rlm@0:  :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],
rlm@0:  :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:  :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],
rlm@0:  :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],
rlm@0:  :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],
rlm@0:  :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],
rlm@0:  :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],
rlm@0:  :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],
rlm@0:  :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],
rlm@0:  :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],
rlm@0:  :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],
rlm@0:  :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],
rlm@0:  :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],
rlm@0:  :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:  :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
rlm@0: #+end_example
rlm@0: 
rlm@7: =defense-strengths= is a more convenient form of =pokemon-gen-two=,
rlm@7: with key/value pair access.
rlm@0: 
rlm@0: * Interfacing with the Data
rlm@7: 
rlm@7: In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two
rlm@9: types at the same time.  For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary
rlm@9: bird that can control lightning, has both the Electric and Flying
rlm@9: types. A pok\eacute{}mon with more than one type gains the advantages
rlm@10: and disadvantages of both types.  The susceptibilities of each type are
rlm@7: multiplied together to produce the hybrid type's susceptibilities. For
rlm@7: example, Electric is weak to Ground (susceptibility of 2), but Flying
rlm@10: is immune to Ground (susceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,
rlm@10: Electric/Flying, is immune to Ground because $2 \times 0 = 0$.
rlm@7: 
rlm@0: #+srcname: types
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: 
rlm@0: (defn multitypes "All combinations of up to n types" [n]
rlm@0:   (vec
rlm@0:    (map vec
rlm@0: 	(reduce concat
rlm@0: 		(map (partial combinations (type-names))
rlm@0: 		     (range 1 (inc n)))))))
rlm@0: 
rlm@7: (defn susceptibility 
rlm@0:   "Hash-map of the susceptibilities of the given type combination 
rlm@0:    to each type of attack"
rlm@0:   [pkmn-types]
rlm@0:   (rlm.map-utils/map-vals
rlm@0:    clojure.core/rationalize 
rlm@0:    (apply hash-map
rlm@0: 	  (interleave (type-names)
rlm@0: 		      (apply (partial map *) 
rlm@0: 			     (map (defense-strengths) pkmn-types))))))
rlm@0:   
rlm@7: (defn susceptance 
rlm@0:   "The cumulative susceptibility of the given type combination"
rlm@0:   [types]
rlm@7:   (reduce + (map #(expt % 2) (vals (susceptibility types)))))
rlm@0: #+end_src
rlm@0: 
rlm@10: Now we can work out the susceptibility of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.
rlm@7: 
rlm@7: Electric is weak to Ground.
rlm@7: #+begin_src clojure :exports both
rlm@7: (:ground (pokemon.types/susceptibility [:electric]))
rlm@7: #+end_src
rlm@7: 
rlm@7: #+results:
rlm@7: : 2
rlm@7: 
rlm@7: Flying is immune to Ground.
rlm@7: #+begin_src clojure :exports both
rlm@7: (:ground (pokemon.types/susceptibility [:flying]))
rlm@7: #+end_src
rlm@7: 
rlm@7: #+results:
rlm@7: : 0
rlm@7: 
rlm@7: Together, they are immune to Ground.
rlm@7: #+begin_src clojure :exports both
rlm@7: (:ground (pokemon.types/susceptibility [:electric :flying]))
rlm@7: #+end_src
rlm@7: 
rlm@7: #+results:
rlm@7: : 0
rlm@7: 
rlm@7: 
rlm@7: 
rlm@7: 
rlm@0: * Best-First Search
rlm@0: 
rlm@0: I'd like to find type combinations that are interesting, but the total
rlm@0: number of combinations gets huge as we begin to consider more
rlm@0: types. For example, the total possible number of type combinations
rlm@7: given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.
rlm@0: Therefore, it's prudent to use search.
rlm@0: 
rlm@0: These functions are a simple implementation of best-first search in
rlm@0: clojure. The idea to start off with a collection of nodes and some way
rlm@0: of finding the best node, and to always expand the best node at every
rlm@0: step.
rlm@0: 
rlm@0: #+srcname: search
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: 
rlm@0: (defn comparatize
rlm@0:   "Define a comparator which uses the numerical outputs of fn as its criterion.
rlm@0:    Objects are sorted in increasing numerical order. Objects with the same fn-value
rlm@0:    are further compared by clojure.core/compare."
rlm@0:   [fun]
rlm@0:   (fn [a b]
rlm@0:     (let [val-a (fun a)
rlm@0:           val-b (fun b)]
rlm@0:       (cond
rlm@0:        ;; if the function cannot differentiate the two values
rlm@0:        ;; then compare the two values using clojure.core/compare
rlm@0:        (= val-a val-b) (compare a b)
rlm@0:        true
rlm@0:        ;; LOWER values of the function are preferred
rlm@0:        (compare (- val-a val-b) 0)))))
rlm@0: 
rlm@0: (defn-memo best-first-step [successors [visited unvisited]]
rlm@0:   (cond (empty? unvisited) nil
rlm@0: 	true
rlm@0: 	(let [best-node (first unvisited)
rlm@0: 	      visited* (conj visited best-node)
rlm@0: 	      unvisited*
rlm@0: 	      (difference
rlm@0: 	       (union unvisited (set (successors best-node)))
rlm@0: 	       visited*)]
rlm@0: 	  (println best-node)
rlm@0: 	  [visited* unvisited*])))
rlm@0: 
rlm@0: ;; memoize partial from core so that for example 
rlm@0: ;; (= (partial + 1) (partial + 1))
rlm@0: ;; this way, best first search can take advantage of the memoization
rlm@0: ;; of best-first step
rlm@0: (undef partial)
rlm@0: (def partial (memoize clojure.core/partial))
rlm@0: 
rlm@0: (defn best-first-search
rlm@0:   "Searches through a network of alternatives, pursuing
rlm@0: initially-promising positions first. Comparator defines which
rlm@0: positions are more promising, successors produces a list of improved
rlm@0: positions from the given position (if any exist), and initial-nodes is
rlm@0: a list of starting positions.  Returns a lazy sequence of search results
rlm@0:  [visited-nodes unvisited-nodes], which terminates when 
rlm@0: there are no remaining unvisited positions."
rlm@0:   [comparator successors initial-nodes]
rlm@0:   (let [initial-nodes
rlm@0: 	(apply (partial sorted-set-by comparator) initial-nodes)
rlm@0: 	initial-visited-nodes (sorted-set-by comparator)
rlm@0: 	step (partial best-first-step successors)]
rlm@0:     (take-while
rlm@0:      (comp not nil?)
rlm@0:      (iterate step [initial-visited-nodes initial-nodes]))))
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: Now that we have a basic best-first-search, it's convenient to write a
rlm@8: few pok\eacute{}mon-type specific convenience functions.
rlm@0: 
rlm@0: #+srcname: pokemon-search
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: (defvar type-compare (comparatize susceptance)
rlm@10:   "compare two type combinations W.R.T. their susceptibilities")
rlm@0: 
rlm@0: (defn type-successors
rlm@0:   "Return the set of types that can be made by appending a single type
rlm@0: to the given combination."
rlm@0:   [type]
rlm@0:   (if (nil? type) '()
rlm@0:       (set (map (comp vec sort (partial into type)) (multitypes 1)))))
rlm@0: 
rlm@0: (defn immortal?
rlm@0:   "A type combo is immortal if it is resistant or invulnerable to
rlm@0:   every pokemon type. This is because that set of types can just be
rlm@0:   repeated to achieve as low a susceptance as desired"
rlm@0:   [type]
rlm@0:   (every? (partial > 1) (vals (susceptibility type))))
rlm@0: 
rlm@0: (defn type-successors*
rlm@0:   "Stop expanding a type if it's immortal, or if it is longer than or
rlm@0: equal to limit-size.  Also, only return type additions that are
rlm@0: strictly better than the initial type."
rlm@0:   [limit-size type]
rlm@0:   (if (or (<= limit-size (count type)) (immortal? type)) '()
rlm@0:       (set (filter #(< 0 (type-compare type %)) (type-successors type)))))
rlm@0: 
rlm@0: (defn pokemon-type-search
rlm@0:   "Search among type-combos no greater than length n, limited by limit
rlm@0: steps of best-first-search."
rlm@0:   ([n] (pokemon-type-search n Integer/MAX_VALUE))
rlm@0:   ([n limit]
rlm@0:      (first (last
rlm@0: 	     (take
rlm@0: 	      limit
rlm@0: 	      (best-first-search
rlm@0: 	       type-compare
rlm@0: 	       (partial type-successors* n)
rlm@0: 	       (multitypes 1)))))))
rlm@0: 	 
rlm@0: (defvar immortals
rlm@0:   (comp (partial filter immortal?) pokemon-type-search)
rlm@0:   "find all the immortal pokemon types ")
rlm@0: 
rlm@0: #+end_src
rlm@0: 
rlm@0: Because there are so many type combinations, it's important to narrow
rlm@0: down the results as much as possible.  That is why =type-successors*=
rlm@0: only returns types that are actually better than the type it is given.
rlm@0: 
rlm@0: Best-first search can get caught optimizing a single type forever, so
rlm@0: it's also important to limit the search space to be finite by setting
rlm@0: an upper bound on the length of a type combo.
rlm@0:   
rlm@0: * Results
rlm@0: ** The best dual-type combo
rlm@0:    
rlm@0: #+begin_src clojure :results cache verbatim :exports both
rlm@0: (first (pokemon.types/pokemon-type-search 2))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : [:dark :ghost]
rlm@0: 
rlm@0: Dark and Ghost, which additionally has the property of having no
rlm@9: weaknesses to any other type, is the best type combo in terms of
rlm@9: susceptance.
rlm@0: 
rlm@0: The Dark and Steel types were introduced many years after
rlm@0: pok\eacute{}mon started. In addition to the additional types, the
rlm@0: pok\eacute{}mon games gained a few new rules concerning some of the
rlm@9: matchups of the original types. Therefore, it's also interesting to
rlm@9: see what type combination was most powerful before those types and new
rlm@9: rules were introduced.
rlm@0: 
rlm@0: The easiest way to do this with my setup is to just rebind the
rlm@0: =pokemon-gen-two= table to the =pokemon-gen-one= table. Since
rlm@0: everything that references this variable is a function and we're not
rlm@0: doing anything too crazy with lazy-sequences and late-binding, this
rlm@0: simple macro will do the job.
rlm@0: 
rlm@0: #+srcname: old-school
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: 
rlm@0: (defmacro old-school
rlm@0:   [& forms]
rlm@0:   `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))
rlm@0: #+end_src
rlm@0: 
rlm@0: Using the =old-school= macro, it's easy to find answers for the
rlm@0: original 15 pokemon types as well as the expanded pokemon types
rlm@0: introduced later.
rlm@0: 
rlm@0: #+begin_src clojure :results verbatim  :exports both :cache yes
rlm@0: (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:
rlm@0: : [:ghost :psychic]
rlm@0: 
rlm@0: Ghost and Psychic also manages to have no weaknesses to any of the original
rlm@8: types, using the old Generation I rules. 
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/old-school
rlm@0:   (pokemon.types/susceptibility [:ghost :psychic])))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1,
rlm@0:  :psychic 1/2,
rlm@0:  :dragon 1,
rlm@0:  :fire 1,
rlm@0:  :ice 1,
rlm@0:  :grass 1,
rlm@0:  :ghost 0,
rlm@0:  :poison 1/2,
rlm@0:  :flying 1,
rlm@0:  :normal 0,
rlm@0:  :rock 1,
rlm@0:  :electric 1,
rlm@0:  :ground 1,
rlm@0:  :fighting 0,
rlm@0:  :bug 0}
rlm@0: #+end_example
rlm@0: 
rlm@0: ** An Immortal Type
rlm@0: It's possible to quickly find an immortal type by giving the search
rlm@0: a long enough maximum type length.  50 rounds of search with a max
rlm@0: type limit of 10 is enough to find an immortal type.
rlm@0: 
rlm@0: #+begin_src clojure :results scalar :exports both
rlm@0: (first (pokemon.types/pokemon-type-search 10 50))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
rlm@0: 
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/susceptibility 
rlm@0:   [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/4,
rlm@0:  :psychic 1/4,
rlm@0:  :dragon 1/2,
rlm@0:  :fire 1/2,
rlm@0:  :ice 1/2,
rlm@0:  :grass 1/8,
rlm@0:  :ghost 1/2,
rlm@0:  :poison 0,
rlm@0:  :flying 1/2,
rlm@0:  :normal 0,
rlm@0:  :rock 1/2,
rlm@0:  :electric 0,
rlm@0:  :ground 0,
rlm@0:  :fighting 0,
rlm@0:  :dark 1/2,
rlm@0:  :steel 1/32,
rlm@0:  :bug 1/16}
rlm@0: #+end_example
rlm@0: 
rlm@0: ** Explanations for Common Pok\eacute{}mon Strategies
rlm@0: 
rlm@8: Many people start out a battle with either a Normal pok\eacute{}mon or an
rlm@8: Electric pok\eacute{}mon. Here's some justification for that choice.
rlm@0: 
rlm@0: #+srcname: weaknesses
rlm@0: #+begin_src clojure  :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: (defn critical-weaknesses [type]
rlm@0:   (count (filter #(> % 1) (vals (susceptibility type)))))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+begin_src clojure :exports both :results output
rlm@0: (clojure.pprint/pprint
rlm@0:  (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: ([:normal]
rlm@0:  [:electric]
rlm@0:  [:water]
rlm@0:  [:fighting]
rlm@0:  [:poison]
rlm@0:  [:ghost]
rlm@0:  [:dragon]
rlm@0:  [:dark]
rlm@0:  [:fire]
rlm@0:  [:ground]
rlm@0:  [:flying]
rlm@0:  [:psychic]
rlm@0:  [:bug]
rlm@0:  [:steel]
rlm@0:  [:ice]
rlm@0:  [:grass]
rlm@0:  [:rock])
rlm@0: #+end_example
rlm@0: 
rlm@0: Electric and Normal are among the best types with which to start the
rlm@0: game, since they have the fewest weaknesses among all the types.
rlm@0: 
rlm@9: At the beginning of the pok\eacute{}mon games, players are given a
rlm@9: choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water
rlm@9: pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon
rlm@9: [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].
rlm@0: 
rlm@0: #+begin_src clojure :exports both :results verbatim
rlm@0: (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : ([:water] [:fire] [:grass :poison])
rlm@0: 
rlm@9: As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid
rlm@0: choice starting out, insofar as susceptance is concerned.
rlm@0: 
rlm@0: ** The Worst Pok\eacute{}mon Types
rlm@0: 
rlm@0: #+srcname: weak-types
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: 
rlm@0: (defn type-compare-weak 
rlm@0:   "compare first by total number of critical-weaknesses,
rlm@0:    then by overall susceptance, favoring weaker types."
rlm@0:   [type-1 type-2]
rlm@0:   (let [measure (memoize (juxt critical-weaknesses susceptance))]
rlm@0:     (if (= (measure type-2) (measure type-1))
rlm@0:       (compare  type-2 type-1)
rlm@0:       (compare (measure type-2) (measure type-1)))))
rlm@0: 
rlm@0: (defn resistant?
rlm@0:   "might as well get rid of types that are resistant to any type"
rlm@0:   [type]
rlm@0:   (not (every? #(< 0 %) (vals (susceptibility type)))))
rlm@0: 
rlm@0: (defn type-successors-weak
rlm@8:   "Generate ways to weaken the given type combination.  Discard type
rlm@8:   combinations that either strengthen the given type combination or
rlm@8:   that make it stronger"
rlm@0:   [limit type]
rlm@0:   (set (if (<= limit (count type)) '()
rlm@0: 	   (filter #(< 0 (type-compare-weak type %))
rlm@0: 		   (remove resistant? (type-successors type))))))
rlm@0: 
rlm@0: (defn pokemon-type-search-weak
rlm@0:   "Search among type-combos no greater than length n, limited by limit
rlm@8:    steps of best-first-search.  Find the weakest type combination
rlm@8:    possible in terms of susceptance."
rlm@0:   ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))
rlm@0:   ([n limit]
rlm@0:      (first (last
rlm@0: 	     (take
rlm@0: 	      limit
rlm@0: 	      (best-first-search
rlm@0: 	       type-compare-weak
rlm@0: 	       (partial type-successors-weak n)
rlm@0: 	       (multitypes 1)))))))
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: #+begin_src clojure :results scalar :exports both
rlm@0: (first (pokemon.types/pokemon-type-search-weak 1))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : [:rock]
rlm@0: 
rlm@0: Poor Rock.  It's just not that good a type.  Maybe this is why Brock
rlm@0: (who has rock pok\eacute{}mon) is the first gym leader in the games.
rlm@0: 
rlm@0: #+begin_src clojure :results scalar cache :exports both
rlm@0: (first (pokemon.types/pokemon-type-search-weak 2))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: : [:grass :ice]
rlm@0: 
rlm@0: # ;;bonus convergently immortal type combo
rlm@0: # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))
rlm@0: 
rlm@0: #+begin_src clojure :results output :exports both
rlm@0: (clojure.pprint/pprint
rlm@0:  (pokemon.types/susceptibility [:grass :ice]))
rlm@0: #+end_src
rlm@0: 
rlm@0: #+results:
rlm@0: #+begin_example
rlm@0: {:water 1/2,
rlm@0:  :psychic 1,
rlm@0:  :dragon 1,
rlm@0:  :fire 4,
rlm@0:  :ice 1,
rlm@0:  :grass 1/2,
rlm@0:  :ghost 1,
rlm@0:  :poison 2,
rlm@0:  :flying 2,
rlm@0:  :normal 1,
rlm@0:  :rock 2,
rlm@0:  :electric 1/2,
rlm@0:  :ground 1/2,
rlm@0:  :fighting 2,
rlm@0:  :dark 1,
rlm@0:  :steel 2,
rlm@0:  :bug 2}
rlm@0: #+end_example
rlm@0: 
rlm@0: This miserable combination is weak to 6 types and double-weak to
rlm@0: Fire.  No pok\eacute{}mon in the games actually has this type. 
rlm@0:  
rlm@0: * Conclusion
rlm@0: 
rlm@0: Searching for a type that is weak to everything takes a very long time
rlm@0: and fails to reveal any results.  That's the problem with a search
rlm@0: over this large problem space --- if there's an easy solution, the
rlm@0: search will find it quickly, but it can be very hard to determine
rlm@0: whether there is actually a solution.
rlm@0: 
rlm@0: In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in
rlm@0: a different way.
rlm@0: 
rlm@0: * COMMENT main program
rlm@0: #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
rlm@0: <<header>>
rlm@0: #+end_src
rlm@0: 
rlm@0: ## this is necessary to define pokemon-table inside the source code.
rlm@0: 
rlm@0: #+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: <<data>>
rlm@0: #+end_src
rlm@0: 
rlm@0: #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none
rlm@0: <<types>>
rlm@0: <<search>>
rlm@0: <<pokemon-search>>
rlm@0: <<old-school>>
rlm@0: <<weaknesses>>
rlm@0: <<weak-types>>
rlm@0: #+end_src
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0:    
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: