1.1 --- a/org/types.org	Wed Nov 02 05:53:43 2011 -0700
     1.2 +++ b/org/types.org	Wed Nov 02 06:48:40 2011 -0700
     1.3 @@ -1,6 +1,7 @@
     1.4 -#+TITLE: Breadth-first Search for Effective Pokemon Types
     1.5 +#+TITLE: Best-First Search for Effective Pokemon Types
     1.6  #+AUTHOR:    Robert McIntyre & Dylan Holmes
     1.7  #+EMAIL:     rlm@mit.edu
     1.8 +#+description: Finding interesting pokemon type combinations through Best-First search in clojure.
     1.9  #+SETUPFILE: ../../aurellem/org/setup.org
    1.10  #+INCLUDE:   ../../aurellem/org/level-0.org
    1.11  
    1.12 @@ -49,7 +50,7 @@
    1.13  
    1.14  Here are the the definitions of the two type systems.
    1.15  
    1.16 -* The Pok\eacute{}mon Type Systems 
    1.17 +* Generation I and II Type System Data 
    1.18  
    1.19  ** Generation II Type System
    1.20  #+label: pokemon-matchups
    1.21 @@ -79,7 +80,8 @@
    1.22  the row for the attack type to the column of the defending type.
    1.23  
    1.24  ** Generation I Type System
    1.25 -#+label: pokemon-matchups-gen-1 +tblname: pokemon-table-gen-one
    1.26 +#+label: pokemon-matchups-gen-1 
    1.27 +#+tblname: pokemon-table-gen-one
    1.28  |          | normal | fire | water | electric | grass | ice | fighting | poison | ground | flying | psychic | bug | rock | ghost | dragon |
    1.29  |----------+--------+------+-------+----------+-------+-----+----------+--------+--------+--------+---------+-----+------+-------+--------|
    1.30  | normal   |      1 |    1 |     1 |        1 |     1 |   1 |        1 |      1 |      1 |      1 |       1 |   1 |   .5 |     0 |      1 |
    1.31 @@ -101,12 +103,14 @@
    1.32  
    1.33  This is the old table from Generation I. The differences from
    1.34  Generation II are: 
    1.35 - - Dark and Steel are missing.
    1.36 - - Bug is super-effective against Poison.
    1.37 - - Poison is super-effective against Bug.
    1.38 - - Bug is regularly effective against Ghost (instead of
    1.39 -   super-effective like in Generation II).
    1.40 - - Ice is normally effective against Fire, (it's not-very-effective in
    1.41 + - Dark and Steel types are missing (these were introduced in
    1.42 +   Generation II).
    1.43 + - Bug is super-effective against Poison (not-very-effective in
    1.44 +   Generation II).
    1.45 + - Poison is super-effective against Bug (normal in Generation II).
    1.46 + - Bug is regularly effective against Ghost (super-effective in
    1.47 +   Generation II).
    1.48 + - Ice is normally effective against Fire, (not-very-effective in
    1.49     Generation II).
    1.50   - Ghost is completely ineffective against Psychic. This is considered
    1.51     to be a programning glitch.
    1.52 @@ -115,8 +119,8 @@
    1.53  
    1.54  * Representing the Data
    1.55  
    1.56 -After creating the Pok\eacute{}mon types namespace, we store the table
    1.57 -of susceptibilities in =pokemon-table-gen-one= and
    1.58 +After creating the Pok\eacute{}mon types namespace, we store the
    1.59 +tables of susceptibilities above in =pokemon-table-gen-one= and
    1.60  =pokemon-table-gen-two=, each of which is a simple vector of
    1.61  vectors. Because a vector of vectors can be cumbersome, we do not
    1.62  access the tables directly; instead, we use the derivative structures
    1.63 @@ -125,19 +129,22 @@
    1.64  table with its corresponding Pok\eacute{}mon type.
    1.65  
    1.66  
    1.67 -
    1.68  #+srcname: header
    1.69  #+begin_src clojure :results silent
    1.70  (ns pokemon.types
    1.71 -  (:use rlm.ns-rlm))
    1.72 -(rlm.ns-rlm/ns-clone rlm.light-base)
    1.73 -(use 'clojure.set)
    1.74 +  (:use clojure.set)
    1.75 +  (:use clojure.contrib.combinatorics)
    1.76 +  (:use clojure.contrib.math)
    1.77 +  (:use clojure.contrib.def)
    1.78 +  (:use rlm.rlm-commands))
    1.79  #+end_src
    1.80  
    1.81 -#+srcname: data(pokemon-table-gen-one=pokemon-table-gen-one, pokemon-table-gen-two=pokemon-table-gen-two) 
    1.82 +#+srcname: data 
    1.83  #+begin_src clojure :results silent
    1.84  (in-ns 'pokemon.types)
    1.85  ;; record type strengths as a vector of vectors
    1.86 +;; the variables pokemon-table-gen-one and pokemon-table-gen-two 
    1.87 +;; are replaced with the tables above when this file is tangled.
    1.88  (def pokemon-gen-one pokemon-table-gen-one)
    1.89  (def pokemon-gen-two pokemon-table-gen-two)
    1.90  
    1.91 @@ -155,6 +162,19 @@
    1.92  	      (range (count (type-names))))))
    1.93  #+end_src
    1.94  
    1.95 +The two statements 
    1.96 +
    1.97 +#+begin_src clojure :exports code
    1.98 +(def pokemon-gen-one pokemon-table-gen-one)
    1.99 +(def pokemon-gen-two pokemon-table-gen-two)
   1.100 +#+end_src
   1.101 +
   1.102 +probably look weird.  When the actual source file is created, those
   1.103 +variables are replaced with the data from the tables above.
   1.104 +
   1.105 +See [[../src/pokemon/types.clj][types.clj]] to look at the final tangled output.
   1.106 +
   1.107 +
   1.108  #+begin_src clojure :results output :exports both
   1.109  (clojure.pprint/pprint pokemon.types/pokemon-gen-two)
   1.110  #+end_src
   1.111 @@ -180,7 +200,7 @@
   1.112   ("steel" 1 0.5 0.5 0.5 1 2 1 1 1 1 1 1 2 1 1 1 0.5))
   1.113  #+end_example
   1.114  
   1.115 -=pokemon-gen-two= is a simple list-of-list data structure.
   1.116 +=pokemon-gen-two= is a simple list-of-lists data structure.
   1.117  
   1.118  #+begin_src clojure :results output :exports both
   1.119  (clojure.pprint/pprint (pokemon.types/defense-strengths))
   1.120 @@ -207,9 +227,21 @@
   1.121   :bug [1 2 1 1 0.5 1 0.5 1 0.5 2 1 1 2 1 1 1 1]}
   1.122  #+end_example
   1.123  
   1.124 -=defense-strengths= is a more convenient form of =pokemon-gen-two=, with key/value pair access.
   1.125 +=defense-strengths= is a more convenient form of =pokemon-gen-two=,
   1.126 +with key/value pair access.
   1.127  
   1.128  * Interfacing with the Data
   1.129 +
   1.130 +In the pok\eacute{}mon games, a pok\eacute{}mon can have up to two
   1.131 +types at the same time.  For example, Zapdos, the fearsome legendary
   1.132 +that can control lightning, has both the Electric and Flying types. A
   1.133 +pok\eacute{}mon with more than one type gains the advantages and
   1.134 +disadvanteags of both types.  The suceptibilitys of each type are
   1.135 +multiplied together to produce the hybrid type's susceptibilities. For
   1.136 +example, Electric is weak to Ground (susceptibility of 2), but Flying
   1.137 +is immune to Ground (suceptibility of 0). Zapdos' type,
   1.138 +Electrig/Flying, is immune to Ground because $2 \times 0 = 0$.
   1.139 +
   1.140  #+srcname: types
   1.141  #+begin_src clojure :results silent
   1.142  (in-ns 'pokemon.types)
   1.143 @@ -221,7 +253,7 @@
   1.144  		(map (partial combinations (type-names))
   1.145  		     (range 1 (inc n)))))))
   1.146  
   1.147 -(defn susceptibility ;; susceptibility-map
   1.148 +(defn susceptibility 
   1.149    "Hash-map of the susceptibilities of the given type combination 
   1.150     to each type of attack"
   1.151    [pkmn-types]
   1.152 @@ -232,18 +264,47 @@
   1.153  		      (apply (partial map *) 
   1.154  			     (map (defense-strengths) pkmn-types))))))
   1.155    
   1.156 -(defn susceptance ;; susceptibility
   1.157 +(defn susceptance 
   1.158    "The cumulative susceptibility of the given type combination"
   1.159    [types]
   1.160 -  (reduce + (map sqr (vals (susceptibility types)))))
   1.161 +  (reduce + (map #(expt % 2) (vals (susceptibility types)))))
   1.162  #+end_src
   1.163  
   1.164 +Now we can work out the suceptability of Zapdos automatically.
   1.165 +
   1.166 +Electric is weak to Ground.
   1.167 +#+begin_src clojure :exports both
   1.168 +(:ground (pokemon.types/susceptibility [:electric]))
   1.169 +#+end_src
   1.170 +
   1.171 +#+results:
   1.172 +: 2
   1.173 +
   1.174 +Flying is immune to Ground.
   1.175 +#+begin_src clojure :exports both
   1.176 +(:ground (pokemon.types/susceptibility [:flying]))
   1.177 +#+end_src
   1.178 +
   1.179 +#+results:
   1.180 +: 0
   1.181 +
   1.182 +Together, they are immune to Ground.
   1.183 +#+begin_src clojure :exports both
   1.184 +(:ground (pokemon.types/susceptibility [:electric :flying]))
   1.185 +#+end_src
   1.186 +
   1.187 +#+results:
   1.188 +: 0
   1.189 +
   1.190 +
   1.191 +
   1.192 +
   1.193  * Best-First Search
   1.194  
   1.195  I'd like to find type combinations that are interesting, but the total
   1.196  number of combinations gets huge as we begin to consider more
   1.197  types. For example, the total possible number of type combinations
   1.198 -given just 8 possible types is: 17^{8} = 6975757441 combinations.
   1.199 +given just 8 possible types is: 17^{8} = 6,975,757,441 combinations.
   1.200  Therefore, it's prudent to use search.
   1.201  
   1.202  These functions are a simple implementation of best-first search in