#+TITLE: Best-First Search for Effective Pokemon Types

 #+AUTHOR:    Robert McIntyre & Dylan Holmes

 #+EMAIL:     rlm@mit.edu

 #+description: Finding interesting pokemon type combinations through Best-First search in clojure.

 #+keywords: Pokemon, clojure, best-first search, optimization

 #+SETUPFILE: ../../aurellem/org/setup.org

 #+INCLUDE:   ../../aurellem/org/level-0.org

 

 * The Pok\eacute{}mon Type System

   

 The Pok\eacute{}mon type system consists of seventeen different

 /types/ (Rock, Grass, Ice, Psychic, Ground, Bug, Flying, Fire,

 Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric, and

 Steel) that interact like an extended version of Rock-Paper-Scissors:

 for example, the Fire type is strong against the Grass type but weak

 against the Water type. In the table below, we've recorded the

 relative strengths of each of the types in the Pok\eacute{}mon type

 system; the number in each cell indicates how effective an attack of

 the type in the row is against a Pok\eacute{}mon of the type in the

 column. We call these numbers /susceptibilities/.

 

 In the Pok\eacute{}mon games, only four susceptibility values (two,

 one, one-half, and zero) occur. These numbers indicate particularly

 high susceptibility, average susceptibility, particularly low

 susceptibility, and no susceptibility (immunity).

 

  - The susceptibility of Flying types /against/ Ground is 0, because Ground

    attacks cannot hurt Flying pok\eacute{}mon at all. The damage that

    a Ground type attack normally does is  /multiplied/ by 0 when it is

    used against a Flying type pok\eacute{}mon.

 

  - The susceptibility of Fire types against Water attacks

    is 2, because Water type attacks are strong against Fire type

    Pok\eacute{}mon. The damage that a Water type attack normally does

    is doubled when it is used against a Fire type pok\eacute{}mon.

 

  - The susceptibility of Water types against Water attacks is

    $\frac{1}{2}$, because Water type attacks are strong against Water

    type Pok\eacute{}mon. The damage that a Water type attack normally

    does is halved when it is used against a Water type

    pok\eacute{}mon.

 

 There are two pok\eacute{}mon type systems in use. The first is the

 classic system which was used for the very first pok\eacute{}mon

 games, Red, Yellow, and Blue. This old system was used from 1998 to

 2000 in America, and is known as the /Generation I Type System/.  The

 modern pok\eacute{}mon type system was introduced in 2000 with the

 introduction of pok\eacute{}mon Gold and Silver, and has been in use

 ever since.  It is called the /Generation II Type System/.

 

 The definitions of the two Type Systems are included below. 

 

 * Generation I and II Type System Data 

 

 ** Generation II Type System

 #+label: pokemon-matchups

 #+tblname: pokemon-table-gen-two

 |          | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon | dark | steel |

 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------+------+-------|

 | normal   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |   .5 |     0 |      1 |    1 |    .5 |

 | fire     |      1 |   .5 |    .5 |        1 |     2 |   2 |        1 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |     .5 |    1 |     2 |

 | water    |      1 |    2 |    .5 |        1 |    .5 |   1 |        1 |      1 |      2 |      1 |       1 |   1 |    2 |     1 |     .5 |    1 |     1 |

 | electric |      1 |    1 |     2 |       .5 |    .5 |   1 |        1 |      1 |      0 |      2 |       1 |   1 |    1 |     1 |     .5 |    1 |     1 |

 | grass    |      1 |   .5 |     2 |        1 |    .5 |   1 |        1 |     .5 |      2 |     .5 |       1 |  .5 |    2 |     1 |     .5 |    1 |    .5 |

 | ice      |      1 |   .5 |    .5 |        1 |     2 |  .5 |        1 |      1 |      2 |      2 |       1 |   1 |    1 |     1 |      2 |    1 |    .5 |

 | fighting |      2 |    1 |     1 |        1 |     1 |   2 |        1 |     .5 |      1 |     .5 |      .5 |  .5 |    2 |     0 |      1 |    2 |     2 |

 | poison   |      1 |    1 |     1 |        1 |     2 |   1 |        1 |     .5 |     .5 |      1 |       1 |   1 |   .5 |    .5 |      1 |    1 |     0 |

 | ground   |      1 |    2 |     1 |        2 |    .5 |   1 |        1 |      2 |      1 |      0 |       1 |  .5 |    2 |     1 |      1 |    1 |     2 |

 | flying   |      1 |    1 |     1 |       .5 |     2 |   1 |        2 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |      1 |    1 |    .5 |

 | psychic  |      1 |    1 |     1 |        1 |     1 |   1 |        2 |      2 |      1 |      1 |      .5 |   1 |    1 |     1 |      1 |    0 |    .5 |

 | bug      |      1 |   .5 |     1 |        1 |     2 |   1 |       .5 |     .5 |      1 |     .5 |       2 |   1 |    1 |    .5 |      1 |    2 |    .5 |

 | rock     |      1 |    2 |     1 |        1 |     1 |   2 |       .5 |      1 |     .5 |      2 |       1 |   2 |    1 |     1 |      1 |    1 |    .5 |

 | ghost    |      0 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       2 |   1 |    1 |     2 |      1 |   .5 |    .5 |

 | dragon   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |    1 |     1 |      2 |    1 |    .5 |

 | dark     |      1 |    1 |     1 |        1 |     1 |   1 |       .5 |      1 |      1 |      1 |       2 |   1 |    1 |     2 |      1 |   .5 |    .5 |

 | steel    |      1 |   .5 |    .5 |       .5 |     1 |   2 |        1 |      1 |      1 |      1 |       1 |   1 |    2 |     1 |      1 |    1 |    .5 |

 

 The rows are attack types, while the columns are defense types.  To

 see the multiplier for a pok\eacute{}mon attack against a certain type, follow

 the row for the attack type to the column of the defending type.

 

 ** Generation I Type System

 #+label: pokemon-matchups-gen-1 

 #+tblname: pokemon-table-gen-one

 |          | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |

 |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|

 | normal   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |   .5 |     0 |      1 |

 | fire     |      1 |   .5 |    .5 |        1 |     2 |   2 |        1 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |     .5 |

 | water    |      1 |    2 |    .5 |        1 |    .5 |   1 |        1 |      1 |      2 |      1 |       1 |   1 |    2 |     1 |     .5 |

 | electric |      1 |    1 |     2 |       .5 |    .5 |   1 |        1 |      1 |      0 |      2 |       1 |   1 |    1 |     1 |     .5 |

 | grass    |      1 |   .5 |     2 |        1 |    .5 |   1 |        1 |     .5 |      2 |     .5 |       1 |  .5 |    2 |     1 |     .5 |

 | ice      |      1 |    1 |    .5 |        1 |     2 |  .5 |        1 |      1 |      2 |      2 |       1 |   1 |    1 |     1 |      2 |

 | fighting |      2 |    1 |     1 |        1 |     1 |   2 |        1 |     .5 |      1 |     .5 |      .5 |  .5 |    2 |     0 |      1 |

 | poison   |      1 |    1 |     1 |        1 |     2 |   1 |        1 |     .5 |     .5 |      1 |       1 |   2 |   .5 |    .5 |      1 |

 | ground   |      1 |    2 |     1 |        2 |    .5 |   1 |        1 |      2 |      1 |      0 |       1 |  .5 |    2 |     1 |      1 |

 | flying   |      1 |    1 |     1 |       .5 |     2 |   1 |        2 |      1 |      1 |      1 |       1 |   2 |   .5 |     1 |      1 |

 | psychic  |      1 |    1 |     1 |        1 |     1 |   1 |        2 |      2 |      1 |      1 |      .5 |   1 |    1 |     1 |      1 |

 | bug      |      1 |   .5 |     1 |        1 |     2 |   1 |       .5 |      2 |      1 |     .5 |       2 |   1 |    1 |     0 |      1 |

 | rock     |      1 |    2 |     1 |        1 |     1 |   2 |       .5 |      1 |     .5 |      2 |       1 |   2 |    1 |     1 |      1 |

 | ghost    |      0 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       0 |   1 |    1 |     2 |      1 |

 | dragon   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |    1 |     1 |      2 |

 

 

 This is the old table from Generation I. The differences from

 Generation II are: 

  - Dark and Steel types are missing (these were introduced in

    Generation II).

  - Bug is super-effective against Poison (not-very-effective in

    Generation II).

  - Poison is super-effective against Bug (normal in Generation II).

  - Bug is regularly effective against Ghost (super-effective in

    Generation II).

  - Ice is normally effective against Fire, (not-very-effective in

    Generation II).

  - Ghost is completely ineffective against Psychic, even though the

    pok\eacute{}mon anime ran [[http://bulbapedia.bulbagarden.net/wiki/EP022][a three-part series]] about how Ghost

    pok\eacute{}mon are the best way to defeat Psychic pok\eacute{}mon,

    and the Red, Blue, and Yellow games each have a character who

    states "The only thing Psychic pok\eacute{}mon fear are Bugs and

    Ghosts!" This is considered to be a programming glitch. Ghost is

    super-effective against Psychic in Generation II.

 

 * Representing the Data

 

 After creating the Pok\eacute{}mon types namespace, we store the

 tables of susceptibilities above in =pokemon-table-gen-one= and

 =pokemon-table-gen-two=, each of which is a simple vector of

 vectors. Because a vector of vectors can be cumbersome, we do not

 access the tables directly; instead, we use the derivative structures

 =attack-strengths= and =defense-strengths=, which are functions which

 return hash-maps associating each row (respectively column) of the

 table with its corresponding Pok\eacute{}mon type.

 

 

 #+srcname: header

 #+begin_src clojure :results silent

 (ns pokemon.types

   (:use clojure.set)

   (:use clojure.contrib.combinatorics)

   (:use clojure.contrib.math)

   (:use clojure.contrib.def)

   (:use rlm.rlm-commands))

 #+end_src

 

 #+srcname: data 

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 ;; record type strengths as a vector of vectors

 ;; the variables pokemon-table-gen-one and pokemon-table-gen-two 

 ;; are replaced with the tables above when this file is tangled.

 (def pokemon-gen-one pokemon-table-gen-one)

 (def pokemon-gen-two pokemon-table-gen-two)

 

 (defn type-names [] (vec (doall (map (comp keyword first) pokemon-gen-two))))

 

 (defn attack-strengths []

      (zipmap

       (type-names)

       (map (comp vec rest) pokemon-gen-two))) 

 

 (defn defense-strengths []

      (zipmap (type-names)

 	     (map

 	      (apply juxt (map (attack-strengths) (type-names)))

 	      (range (count (type-names))))))

 #+end_src

 

 The two statements 

 

 #+begin_src clojure :exports code

 (def pokemon-gen-one pokemon-table-gen-one)

 (def pokemon-gen-two pokemon-table-gen-two)

 #+end_src

 

 probably look weird.  When the actual source file is created, those

 variables are replaced with the data from the tables above.

 

 See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.

 

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint pokemon.types/pokemon-gen-two)

 #+end_src

 

 #+results:

 #+begin_example

 (("normal" 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0 1 1 0.5)

  ("fire" 1 0.5 0.5 1 2 2 1 1 1 1 1 2 0.5 1 0.5 1 2)

  ("water" 1 2 0.5 1 0.5 1 1 1 2 1 1 1 2 1 0.5 1 1)

  ("electric" 1 1 2 0.5 0.5 1 1 1 0 2 1 1 1 1 0.5 1 1)

  ("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)

  ("ice" 1 0.5 0.5 1 2 0.5 1 1 2 2 1 1 1 1 2 1 0.5)

  ("fighting" 2 1 1 1 1 2 1 0.5 1 0.5 0.5 0.5 2 0 1 2 2)

  ("poison" 1 1 1 1 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 0)

  ("ground" 1 2 1 2 0.5 1 1 2 1 0 1 0.5 2 1 1 1 2)

  ("flying" 1 1 1 0.5 2 1 2 1 1 1 1 2 0.5 1 1 1 0.5)

  ("psychic" 1 1 1 1 1 1 2 2 1 1 0.5 1 1 1 1 0 0.5)

  ("bug" 1 0.5 1 1 2 1 0.5 0.5 1 0.5 2 1 1 0.5 1 2 0.5)

  ("rock" 1 2 1 1 1 2 0.5 1 0.5 2 1 2 1 1 1 1 0.5)

  ("ghost" 0 1 1 1 1 1 1 1 1 1 2 1 1 2 1 0.5 0.5)

  ("dragon" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0.5)

  ("dark" 1 1 1 1 1 1 0.5 1 1 1 2 1 1 2 1 0.5 0.5)

  ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))

 #+end_example

 

 =pokemon-gen-two= is a simple list-of-lists data structure.

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint (pokemon.types/defense-strengths))

 #+end_src

 

 #+results:

 #+begin_example

 {:water [1 0.5 0.5 2 2 0.5 1 1 1 1 1 1 1 1 1 1 0.5],

  :psychic [1 1 1 1 1 1 0.5 1 1 1 0.5 2 1 2 1 2 1],

  :dragon [1 0.5 0.5 0.5 0.5 2 1 1 1 1 1 1 1 1 2 1 1],

  :fire [1 0.5 2 1 0.5 0.5 1 1 2 1 1 0.5 2 1 1 1 0.5],

  :ice [1 2 1 1 1 0.5 2 1 1 1 1 1 2 1 1 1 2],

  :grass [1 2 0.5 0.5 0.5 2 1 2 0.5 2 1 2 1 1 1 1 1],

  :ghost [0 1 1 1 1 1 0 0.5 1 1 1 0.5 1 2 1 2 1],

  :poison [1 1 1 1 0.5 1 0.5 0.5 2 1 2 0.5 1 1 1 1 1],

  :flying [1 1 1 2 0.5 2 0.5 1 0 1 1 0.5 2 1 1 1 1],

  :normal [1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1],

  :rock [0.5 0.5 2 1 2 1 2 0.5 2 0.5 1 1 1 1 1 1 2],

  :electric [1 1 1 0.5 1 1 1 1 2 0.5 1 1 1 1 1 1 0.5],

  :ground [1 1 2 0 2 2 1 0.5 1 1 1 1 0.5 1 1 1 1],

  :fighting [1 1 1 1 1 1 1 1 1 2 2 0.5 0.5 1 1 0.5 1],

  :dark [1 1 1 1 1 1 2 1 1 1 0 2 1 0.5 1 0.5 1],

  :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],

  :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}

 #+end_example

 

 =defense-strengths= is a more convenient form of =pokemon-gen-two=,

 with key/value pair access.

 

 * Interfacing with the Data

 

 In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two

 types at the same time.  For example, [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]], the fearsome legendary

 bird that can control lightning, has both the Electric and Flying

 types. A pok\eacute{}mon with more than one type gains the advantages

 and disadvantages of both types.  The susceptibilities of each type are

 multiplied together to produce the hybrid type's susceptibilities. For

 example, Electric is weak to Ground (susceptibility of 2), but Flying

 is immune to Ground (susceptibility of 0). [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos']] type,

 Electric/Flying, is immune to Ground because $2 \times 0 = 0$.

 

 #+srcname: types

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 

 (defn multitypes "All combinations of up to n types" [n]

   (vec

    (map vec

 	(reduce concat

 		(map (partial combinations (type-names))

 		     (range 1 (inc n)))))))

 

 (defn susceptibility 

   "Hash-map of the susceptibilities of the given type combination 

    to each type of attack"

   [pkmn-types]

   (rlm.map-utils/map-vals

    clojure.core/rationalize 

    (apply hash-map

 	  (interleave (type-names)

 		      (apply (partial map *) 

 			     (map (defense-strengths) pkmn-types))))))

   

 (defn susceptance 

   "The cumulative susceptibility of the given type combination"

   [types]

   (reduce + (map #(expt % 2) (vals (susceptibility types)))))

 #+end_src

 

 Now we can work out the susceptibility of [[http://bulbapedia.bulbagarden.net/wiki/Zapdos][Zapdos]] automatically.

 

 Electric is weak to Ground.

 #+begin_src clojure :exports both

 (:ground (pokemon.types/susceptibility [:electric]))

 #+end_src

 

 #+results:

 : 2

 

 Flying is immune to Ground.

 #+begin_src clojure :exports both

 (:ground (pokemon.types/susceptibility [:flying]))

 #+end_src

 

 #+results:

 : 0

 

 Together, they are immune to Ground.

 #+begin_src clojure :exports both

 (:ground (pokemon.types/susceptibility [:electric :flying]))

 #+end_src

 

 #+results:

 : 0

 

 

 

 

 * Best-First Search

 

 I'd like to find type combinations that are interesting, but the total

 number of combinations gets huge as we begin to consider more

 types. For example, the total possible number of type combinations

 given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.

 Therefore, it's prudent to use search.

 

 These functions are a simple implementation of best-first search in

 clojure. The idea to start off with a collection of nodes and some way

 of finding the best node, and to always expand the best node at every

 step.

 

 #+srcname: search

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 

 (defn comparatize

   "Define a comparator which uses the numerical outputs of fn as its criterion.

    Objects are sorted in increasing numerical order. Objects with the same fn-value

    are further compared by clojure.core/compare."

   [fun]

   (fn [a b]

     (let [val-a (fun a)

           val-b (fun b)]

       (cond

        ;; if the function cannot differentiate the two values

        ;; then compare the two values using clojure.core/compare

        (= val-a val-b) (compare a b)

        true

        ;; LOWER values of the function are preferred

        (compare (- val-a val-b) 0)))))

 

 (defn-memo best-first-step [successors [visited unvisited]]

   (cond (empty? unvisited) nil

 	true

 	(let [best-node (first unvisited)

 	      visited* (conj visited best-node)

 	      unvisited*

 	      (difference

 	       (union unvisited (set (successors best-node)))

 	       visited*)]

 	  (println best-node)

 	  [visited* unvisited*])))

 

 ;; memoize partial from core so that for example 

 ;; (= (partial + 1) (partial + 1))

 ;; this way, best first search can take advantage of the memoization

 ;; of best-first step

 (undef partial)

 (def partial (memoize clojure.core/partial))

 

 (defn best-first-search

   "Searches through a network of alternatives, pursuing

 initially-promising positions first. Comparator defines which

 positions are more promising, successors produces a list of improved

 positions from the given position (if any exist), and initial-nodes is

 a list of starting positions.  Returns a lazy sequence of search results

  [visited-nodes unvisited-nodes], which terminates when 

 there are no remaining unvisited positions."

   [comparator successors initial-nodes]

   (let [initial-nodes

 	(apply (partial sorted-set-by comparator) initial-nodes)

 	initial-visited-nodes (sorted-set-by comparator)

 	step (partial best-first-step successors)]

     (take-while

      (comp not nil?)

      (iterate step [initial-visited-nodes initial-nodes]))))

 

 #+end_src

 

 

 Now that we have a basic best-first-search, it's convenient to write a

 few pok\eacute{}mon-type specific convenience functions.

 

 #+srcname: pokemon-search

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 (defvar type-compare (comparatize susceptance)

   "compare two type combinations W.R.T. their susceptibilities")

 

 (defn type-successors

   "Return the set of types that can be made by appending a single type

 to the given combination."

   [type]

   (if (nil? type) '()

       (set (map (comp vec sort (partial into type)) (multitypes 1)))))

 

 (defn immortal?

   "A type combo is immortal if it is resistant or invulnerable to

   every pokemon type. This is because that set of types can just be

   repeated to achieve as low a susceptance as desired"

   [type]

   (every? (partial > 1) (vals (susceptibility type))))

 

 (defn type-successors*

   "Stop expanding a type if it's immortal, or if it is longer than or

 equal to limit-size.  Also, only return type additions that are

 strictly better than the initial type."

   [limit-size type]

   (if (or (<= limit-size (count type)) (immortal? type)) '()

       (set (filter #(< 0 (type-compare type %)) (type-successors type)))))

 

 (defn pokemon-type-search

   "Search among type-combos no greater than length n, limited by limit

 steps of best-first-search."

   ([n] (pokemon-type-search n Integer/MAX_VALUE))

   ([n limit]

      (first (last

 	     (take

 	      limit

 	      (best-first-search

 	       type-compare

 	       (partial type-successors* n)

 	       (multitypes 1)))))))

 	 

 (defvar immortals

   (comp (partial filter immortal?) pokemon-type-search)

   "find all the immortal pokemon types ")

 

 #+end_src

 

 Because there are so many type combinations, it's important to narrow

 down the results as much as possible.  That is why =type-successors*=

 only returns types that are actually better than the type it is given.

 

 Best-first search can get caught optimizing a single type forever, so

 it's also important to limit the search space to be finite by setting

 an upper bound on the length of a type combo.

   

 * Results

 ** The best dual-type combo

    

 #+begin_src clojure :results cache verbatim :exports both

 (first (pokemon.types/pokemon-type-search 2))

 #+end_src

 

 #+results:

 : [:dark :ghost]

 

 Dark and Ghost, which additionally has the property of having no

 weaknesses to any other type, is the best type combo in terms of

 susceptance.

 

 The Dark and Steel types were introduced many years after

 pok\eacute{}mon started. In addition to the additional types, the

 pok\eacute{}mon games gained a few new rules concerning some of the

 matchups of the original types. Therefore, it's also interesting to

 see what type combination was most powerful before those types and new

 rules were introduced.

 

 The easiest way to do this with my setup is to just rebind the

 =pokemon-gen-two= table to the =pokemon-gen-one= table. Since

 everything that references this variable is a function and we're not

 doing anything too crazy with lazy-sequences and late-binding, this

 simple macro will do the job.

 

 #+srcname: old-school

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 

 (defmacro old-school

   [& forms]

   `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))

 #+end_src

 

 Using the =old-school= macro, it's easy to find answers for the

 original 15 pokemon types as well as the expanded pokemon types

 introduced later.

 

 #+begin_src clojure :results verbatim  :exports both :cache yes

 (pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))

 #+end_src

 

 #+results[f43470fdf460ed546e9c57879abc9eda56da129f]:

 : [:ghost :psychic]

 

 Ghost and Psychic also manages to have no weaknesses to any of the original

 types, using the old Generation I rules. 

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/old-school

   (pokemon.types/susceptibility [:ghost :psychic])))

 #+end_src

 

 #+results:

 #+begin_example

 {:water 1,

  :psychic 1/2,

  :dragon 1,

  :fire 1,

  :ice 1,

  :grass 1,

  :ghost 0,

  :poison 1/2,

  :flying 1,

  :normal 0,

  :rock 1,

  :electric 1,

  :ground 1,

  :fighting 0,

  :bug 0}

 #+end_example

 

 ** An Immortal Type

 It's possible to quickly find an immortal type by giving the search

 a long enough maximum type length.  50 rounds of search with a max

 type limit of 10 is enough to find an immortal type.

 

 #+begin_src clojure :results scalar :exports both

 (first (pokemon.types/pokemon-type-search 10 50))

 #+end_src

 

 #+results:

 : [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]

 

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/susceptibility 

   [:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]))

 #+end_src

 

 #+results:

 #+begin_example

 {:water 1/4,

  :psychic 1/4,

  :dragon 1/2,

  :fire 1/2,

  :ice 1/2,

  :grass 1/8,

  :ghost 1/2,

  :poison 0,

  :flying 1/2,

  :normal 0,

  :rock 1/2,

  :electric 0,

  :ground 0,

  :fighting 0,

  :dark 1/2,

  :steel 1/32,

  :bug 1/16}

 #+end_example

 

 ** Explanations for Common Pok\eacute{}mon Strategies

 

 Many people start out a battle with either a Normal pok\eacute{}mon or an

 Electric pok\eacute{}mon. Here's some justification for that choice.

 

 #+srcname: weaknesses

 #+begin_src clojure  :results silent

 (in-ns 'pokemon.types)

 (defn critical-weaknesses [type]

   (count (filter #(> % 1) (vals (susceptibility type)))))

 #+end_src

 

 #+begin_src clojure :exports both :results output

 (clojure.pprint/pprint

  (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))

 #+end_src

 

 #+results:

 #+begin_example

 ([:normal]

  [:electric]

  [:water]

  [:fighting]

  [:poison]

  [:ghost]

  [:dragon]

  [:dark]

  [:fire]

  [:ground]

  [:flying]

  [:psychic]

  [:bug]

  [:steel]

  [:ice]

  [:grass]

  [:rock])

 #+end_example

 

 Electric and Normal are among the best types with which to start the

 game, since they have the fewest weaknesses among all the types.

 

 At the beginning of the pok\eacute{}mon games, players are given a

 choice between the Fire pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Charmander][Charmander]], the Water

 pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]], or the Grass/Poison pok\eacute{}mon

 [[http://bulbapedia.bulbagarden.net/wiki/Bulbasaur][Bulbasaur]].

 

 #+begin_src clojure :exports both :results verbatim

 (sort-by pokemon.types/susceptance [[:fire] [:water] [:grass :poison]])

 #+end_src

 

 #+results:

 : ([:water] [:fire] [:grass :poison])

 

 As can be seen, the Water pok\eacute{}mon [[http://bulbapedia.bulbagarden.net/wiki/Squirtle][Squirtle]] is the most solid

 choice starting out, insofar as susceptance is concerned.

 

 ** The Worst Pok\eacute{}mon Types

 

 #+srcname: weak-types

 #+begin_src clojure :results silent

 (in-ns 'pokemon.types)

 

 (defn type-compare-weak 

   "compare first by total number of critical-weaknesses,

    then by overall susceptance, favoring weaker types."

   [type-1 type-2]

   (let [measure (memoize (juxt critical-weaknesses susceptance))]

     (if (= (measure type-2) (measure type-1))

       (compare  type-2 type-1)

       (compare (measure type-2) (measure type-1)))))

 

 (defn resistant?

   "might as well get rid of types that are resistant to any type"

   [type]

   (not (every? #(< 0 %) (vals (susceptibility type)))))

 

 (defn type-successors-weak

   "Generate ways to weaken the given type combination.  Discard type

   combinations that either strengthen the given type combination or

   that make it stronger"

   [limit type]

   (set (if (<= limit (count type)) '()

 	   (filter #(< 0 (type-compare-weak type %))

 		   (remove resistant? (type-successors type))))))

 

 (defn pokemon-type-search-weak

   "Search among type-combos no greater than length n, limited by limit

    steps of best-first-search.  Find the weakest type combination

    possible in terms of susceptance."

   ([n] (pokemon-type-search-weak n Integer/MAX_VALUE))

   ([n limit]

      (first (last

 	     (take

 	      limit

 	      (best-first-search

 	       type-compare-weak

 	       (partial type-successors-weak n)

 	       (multitypes 1)))))))

 #+end_src

 

 

 #+begin_src clojure :results scalar :exports both

 (first (pokemon.types/pokemon-type-search-weak 1))

 #+end_src

 

 #+results:

 : [:rock]

 

 Poor Rock.  It's just not that good a type.  Maybe this is why Brock

 (who has rock pok\eacute{}mon) is the first gym leader in the games.

 

 #+begin_src clojure :results scalar cache :exports both

 (first (pokemon.types/pokemon-type-search-weak 2))

 #+end_src

 

 #+results:

 : [:grass :ice]

 

 # ;;bonus convergently immortal type combo

 # (susceptance (vec (concat (repeat 150 :water) (repeat 50 :poison) (repeat 50 :steel) [:ghost :normal :flying :ground :dark])))

 

 #+begin_src clojure :results output :exports both

 (clojure.pprint/pprint

  (pokemon.types/susceptibility [:grass :ice]))

 #+end_src

 

 #+results:

 #+begin_example

 {:water 1/2,

  :psychic 1,

  :dragon 1,

  :fire 4,

  :ice 1,

  :grass 1/2,

  :ghost 1,

  :poison 2,

  :flying 2,

  :normal 1,

  :rock 2,

  :electric 1/2,

  :ground 1/2,

  :fighting 2,

  :dark 1,

  :steel 2,

  :bug 2}

 #+end_example

 

 This miserable combination is weak to 6 types and double-weak to

 Fire.  No pok\eacute{}mon in the games actually has this type. 

  

 * Conclusion

 

 Searching for a type that is weak to everything takes a very long time

 and fails to reveal any results.  That's the problem with a search

 over this large problem space --- if there's an easy solution, the

 search will find it quickly, but it can be very hard to determine

 whether there is actually a solution.

 

 In the [[./lpsolve.org][next installment]], I'll use =lp_solve= to solve this problem in

 a different way.

 

 * COMMENT main program

 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none

 <<header>>

 #+end_src

 

 ## this is necessary to define pokemon-table inside the source code.

 

 #+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

 <<data>>

 #+end_src

 

 #+begin_src clojure :noweb yes :tangle ../src/pokemon/types.clj :exports none

 <<types>>

 <<search>>

 <<pokemon-search>>

 <<old-school>>

 <<weaknesses>>

 <<weak-types>>

 #+end_src