rlm@0: #+TITLE: Breadth-first Search for Effective Pokemon Types
rlm@0: #+AUTHOR:    Robert McIntyre & Dylan Holmes
rlm@0: #+EMAIL:     rlm@mit.edu
rlm@0: #+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"
rlm@0: #+STYLE: <link rel="stylesheet" type="text/css" href="../css/aurellem.css" />
rlm@0: #+OPTIONS:   H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
rlm@0: #+SETUPFILE: ../templates/level-0.org
rlm@0: #+INCLUDE: ../templates/level-0.org
rlm@0: 
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@0: \ldquo{}types\rdquo{} (Rock, Grass, Ice, Psychic, Ground, Bug, Flying,
rlm@0: Fire, Fighting, Dark, Dragon, Poison, Water, Ghost, Normal, Electric,
rlm@0: and Steel) that interact like an extended version of
rlm@0: Rock-Paper-Scissors: for example, the Fire type is strong against the
rlm@0: Grass type but weak against the Water type. In the table below, we've
rlm@0: recorded the relative strengths of each of the types in the
rlm@0: Pok\eacute{}mon type system; the number in each cell indicates how
rlm@0: effective an attack of the type in the row is against a
rlm@0: Pok\eacute{}mon of the type in the column. We call these numbers
rlm@0: /susceptibilities/ because we are interested in the column totals,
rlm@0: which quantify the overall vulnerability of each Pok\eacute{}mon type
rlm@0: (as opposed to the row totals, which quantify the overall
rlm@0: effectiveness of each attack type.)
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@0: susceptibility, and no susceptibility
rlm@0: (immunity). Here is the entire Pok\eacute{}mon type chart.
rlm@0: 
rlm@0: 
rlm@0: 
rlm@0: ** TODO add the pokemon chart in a pretty form
rlm@0:   
rlm@0: * COMMENT Pokemon Table Data 
rlm@0: 
rlm@0: #+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: #+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@0: #+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: #+label: pokemon-matchups-gen-1
rlm@0: #+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@0: * Representing the Data
rlm@0: 
rlm@0: After creating the Pok\eacute{}mon types namespace, we store the table
rlm@0: of susceptibilities 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: 
rlm@0: #+srcname: header
rlm@0: #+begin_src clojure :results silent
rlm@0: (ns pokemon.types
rlm@0:   (:use rlm.ns-rlm))
rlm@0: (rlm.ns-rlm/ns-clone rlm.light-base)
rlm@0: (use 'clojure.set)
rlm@0: #+end_src
rlm@0: 
rlm@0: #+srcname: data(pokemon-table-gen-one=pokemon-table-gen-one, pokemon-table-gen-two=pokemon-table-gen-two) 
rlm@0: #+begin_src clojure :results silent
rlm@0: (in-ns 'pokemon.types)
rlm@0: ;; record type strengths as a vector of vectors
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@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@0: =pokemon-gen-two= is a simple list-of-list 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@0: =defense-strengths= is a more convenient form of =pokemon-gen-two=, with key/value pair access.
rlm@0: 
rlm@0: * Interfacing with the Data
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@0: (defn susceptibility ;; susceptibility-map
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@0: (defn susceptance ;; susceptibility
rlm@0:   "The cumulative susceptibility of the given type combination"
rlm@0:   [types]
rlm@0:   (reduce + (map sqr (vals (susceptibility types)))))
rlm@0: #+end_src
rlm@0: 
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@0: given just 8 possible types is: 17^{8} = 6975757441 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@0: few pokemon-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@0:   "compare two type combinations wrt 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@0:  weaknesses to any other type, is the best type combo in terms of
rlm@0:  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@0: matchups of the original types. Therefore, it's also interesting to see what
rlm@0: type combination was most powerful before those types and new 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@0: types. 
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@0: Many people start out a battle with either a normal pok\eacute{}mon or an
rlm@0: electric pok\eacute{}mon, and 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@0: At the beginning of the pok\eacute{}mon games, players are given a choice
rlm@0: between the Fire pok\eacute{}mon Charmander, the Water pok\eacute{}mon Squirtle, or
rlm@0: the Grass/Poison pok\eacute{}mon 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@0: As can be seen, the Water pok\eacute{}mon 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@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@0: steps of best-first-search."
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: 
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: