Best-First Search for Effective Pokemon Types

aurellem

Written by Robert McIntyre & Dylan Holmes

1 The Pokémon Type System

The Poké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émon type system; the number in each cell indicates how effective an attack of the type in the row is against a Pokémon of the type in the column. We call these numbers susceptibilities.

In the Poké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é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émon.
  • The susceptibility of Fire types against Water attacks is 2, because Water type attacks are strong against Fire type Pokémon. The damage that a Water type attack normally does is doubled when it is used against a Fire type pokémon.
  • The susceptibility of Water types against Water attacks is \(\frac{1}{2}\), because Water type attacks are strong against Water type Pokémon. The damage that a Water type attack normally does is halved when it is used against a Water type pokémon.

There are two pokémon type systems in use. The first is the classic system which was used for the very first poké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émon type system was introduced in 2000 with the introduction of poké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.

2 Generation I and II Type System Data

2.1 Generation II Type System

normalfirewaterelectricgrassicefightingpoisongroundflyingpsychicbugrockghostdragondarksteel
normal111111111111.5011.5
fire1.5.5122111112.51.512
water12.51.5111211121.511
electric112.5.5111021111.511
grass1.521.511.52.51.521.51.5
ice1.5.512.51122111121.5
fighting2111121.51.5.5.520122
poison1111211.5.5111.5.5110
ground1212.5112101.521112
flying111.521211112.5111.5
psychic1111112211.511110.5
bug1.51121.5.51.5211.512.5
rock121112.51.52121111.5
ghost011111111121121.5.5
dragon1111111111111121.5
dark111111.511121121.5.5
steel1.5.5.5121111112111.5

The rows are attack types, while the columns are defense types. To see the multiplier for a pokémon attack against a certain type, follow the row for the attack type to the column of the defending type.

2.2 Generation I Type System

normalfirewaterelectricgrassicefightingpoisongroundflyingpsychicbugrockghostdragon
normal111111111111.501
fire1.5.5122111112.51.5
water12.51.5111211121.5
electric112.5.5111021111.5
grass1.521.511.52.51.521.5
ice11.512.5112211112
fighting2111121.51.5.5.5201
poison1111211.5.5112.5.51
ground1212.5112101.5211
flying111.521211112.511
psychic1111112211.51111
bug1.51121.521.521101
rock121112.51.5212111
ghost011111111101121
dragon111111111111112

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émon anime ran a three-part series about how Ghost pokémon are the best way to defeat Psychic pokémon, and the Red, Blue, and Yellow games each have a character who states "The only thing Psychic pokémon fear are Bugs and Ghosts!" This is considered to be a programming glitch. Ghost is super-effective against Psychic in Generation II.

3 Representing the Data

After creating the Poké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émon type.

(ns pokemon.types
  (:use clojure.set)
;;  (:use clojure.contrib.combinatorics)
  (:use clojure.math.combinatorics)
  (:use clojure.math.numeric-tower)
;;  (:use clojure.contrib.def)
  (:use rlm.rlm-commands)
  (:require rlm.map-utils))
(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))))))

The two statements

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

probably look weird. When the actual source file is created, those variables are replaced with the data from the tables above.

See types.clj to look at the final tangled output.

(clojure.pprint/pprint pokemon.types/pokemon-gen-two)
(("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))

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

(clojure.pprint/pprint (pokemon.types/defense-strengths))
{: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]}

defense-strengths is a more convenient form of pokemon-gen-two, with key/value pair access.

4 Interfacing with the Data

In the pokémon games, a pokémon can have up to two types at the same time. For example, Zapdos, the fearsome legendary bird that can control lightning, has both the Electric and Flying types. A poké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). Zapdos' type, Electric/Flying, is immune to Ground because \(2 \times 0 = 0\).

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

Now we can work out the susceptibility of Zapdos automatically.

Electric is weak to Ground.

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

Flying is immune to Ground.

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

Together, they are immune to Ground.

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

5 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: 178 = 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 is 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.

(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 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*])))
(alter-var-root #'best-first-step memoize)

;; 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]))))

Now that we have a basic best-first-search, it's convenient to write a few pokémon-type specific convenience functions.

(in-ns 'pokemon.types)
(def type-compare
  "compare two type combinations W.R.T. their susceptibilities"
  (comparatize susceptance))

(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)))))))
         
(def immortals
  "find all the immortal pokemon types."
  (comp (partial filter immortal?) pokemon-type-search))

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.

6 Results

6.1 The best dual-type combo

(first (pokemon.types/pokemon-type-search 2))
[: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émon started. In addition to the additional types, the poké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.

(in-ns 'pokemon.types)

(defmacro old-school
  [& forms]
  `(binding [pokemon-gen-two pokemon-gen-one] ~@forms))

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.

(pokemon.types/old-school (first (pokemon.types/pokemon-type-search 2)))
[:ghost :psychic]

Ghost and Psychic also manages to have no weaknesses to any of the original types, using the old Generation I rules.

(clojure.pprint/pprint
 (pokemon.types/old-school
  (pokemon.types/susceptibility [:ghost :psychic])))
{: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}

6.2 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.

(first (pokemon.types/pokemon-type-search 10 50))
[:dragon :fire :flying :ghost :grass :ground :steel :steel :water :water]
(clojure.pprint/pprint
 (pokemon.types/susceptibility 
  [:dragon :fire :flying :ghost :grass :ground 
   :steel :steel :water :water]))
{: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}

6.3 Explanations for Common Pokémon Strategies

Many people start out a battle with either a Normal pokémon or an Electric pokémon. Here's some justification for that choice.

(in-ns 'pokemon.types)
(defn critical-weaknesses [type]
  (count (filter #(> % 1) (vals (susceptibility type)))))
(clojure.pprint/pprint
 (sort-by pokemon.types/critical-weaknesses (pokemon.types/multitypes 1)))
([:normal]
 [:electric]
 [:water]
 [:fighting]
 [:poison]
 [:ghost]
 [:dragon]
 [:dark]
 [:fire]
 [:ground]
 [:flying]
 [:psychic]
 [:bug]
 [:steel]
 [:ice]
 [:grass]
 [:rock])

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émon games, players are given a choice between the Fire pokémon Charmander, the Water pokémon Squirtle, or the Grass/Poison pokémon Bulbasaur.

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

As can be seen, the Water pokémon Squirtle is the most solid choice starting out, insofar as susceptance is concerned.

6.4 The Worst Pokémon Types

(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)))))))
(first (pokemon.types/pokemon-type-search-weak 1))
[:rock]

Poor Rock. It's just not that good a type. Maybe this is why Brock (who has rock pokémon) is the first gym leader in the games.

(first (pokemon.types/pokemon-type-search-weak 2))
[:grass :ice]
(clojure.pprint/pprint
 (pokemon.types/susceptibility [:grass :ice]))
{: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}

This miserable combination is weak to 6 types and double-weak to Fire. No pokémon in the games actually has this type.

7 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 next installment, I'll use lp_solve to solve this problem in a different way.

Date: 2013-09-17 21:43:46 UTC

Author: Robert McIntyre & Dylan Holmes

Org version 7.7 with Emacs version 23

Validate XHTML 1.0