Lately I’ve been focusing my efforts on teaching. One thing I’m working on is writing a book about cryptography, math and programming that is targeted at high school-aged students. One of my motivators is equity, so I’m licensing it under a creative commons license, and the source code to the book is here, on github.

Another motivator is enthusiasm – I like to convey my enthusiasm for the material to the students I’m working with. One way to do that is to tap into things they’re already enthusiastic about. For the book, it’s the innate fascination we all have about secret codes.

For this blog post, I’ve got a tidbit about graph theory that is motivated by many folks’ fascination with Pokemon Go. Pokemon Go players do a few different things: they walk around their town collecting items at Pokestops, which are associated with landmarks in the real world:

(image credit: Business Insider)

Some of those items are Pokeballs, which are used to capture the Pokemon creatures that also wander around town. You can evolve and power up the Pokemon you catch to make them more powerful. The reason you care about your Pokemon’s power is that in addition to Pokemon and Pokestops, there are Gymnasiums, which are also associated with real-world landmarks, but instead of having items, they’re places where Pokemon can battle each other. I’ll skip past the part about teams because that’s not relevant, but the part that is relevant is that a Gymnasium can have up to ten different Pokemon in it, and when you battle, you can choose six of your Pokemon collection to fight against the ones in the Gymnasium. The question is: “how do you choose which Pokemon to battle?”

It’s a good question because the designers of the game created complex varieties of Pokemon (e.g., Fire, Grass, Electric, Poison, etc), and a complex hierarchy of strengths and weaknesses among them. So, for example, it’s easy to remember that if you’re going up against a Fire-type Pokemon, that a Water-type Pokemon has a strong advantage. On the other hand, Fire has an advantage against Grass and Ice. It’s a lot like rock-paper-scissors, but with over a dozen types instead of just three. Even more complex than the Big Bang Theory’s rock-paper-scissors-lizard-Spock.

Now we’re up to where Graph Theory can help. Just as this link shows the interactions between rocks, paper, scissors, lizards and Spockrpssl

In computer science, the above diagram is called a graph. It’s not the same as the graphs we draw of functions, so it’s kind of a confusing name, but you get used to it. These kinds of graphs have nodes and edges. If the edges have arrows, it’s called a directional graph (digraph for short). What this graph tells us is that an arrow from one node to another means that the node “beats” the one it points to.

We’d like a similar diagram for Pokemon Go. It’s subtly different: instead of a simple “Fire beats grass” relationship, we have “Fire is unusually strong against grass”. Even so, this is important information. With a simple cheatsheet like this, we could go up to any Gymnasium with a decent collection of Pokemon, and do serious damage. Also, we could learn which Pokemon we should add to a Gymnasium to make it stronger. So, how to do this?

I started by Googling for “Pokemon Go rock paper scissors” to get a list of the strengths and weaknesses of Pokemon creature types. This list seemed good for my purposes. I don’t know how accurate or authoritative it is, but that’s not as important as what I did with the information. What I could have done is use an art program to draw the graph. The drawback of this approach is that it is very “brittle”, meaning if I want a different layout I have a lot of work to do, or if the data is wrong, I have do a tedious search through the diagram.

What I did instead is use a tool that is designed to take a definition of a graph as its input, and to create pretty drawings of them. The tool I used is called graphviz, and it’s quite powerful and configurable.

The input to graphviz is called a “dot” file (the filenames end in .dot). Here’s my conversion of the above Pokemon database into a dot file:

digraph Battles {
 node [margin=0 fontsize=24 shape=plaintext ]
 # layout=circo
 Fire -> Steel
 Fire -> Bug
 Fire -> Ice
 Fire -> Grass
 Water -> Fire
 Water -> Ground
 Water -> Rock
 Grass -> Water
 Grass -> Ground
 Grass -> Rock
 Electric -> Water
 Electric -> Flying
 Ground -> Fire
 Ground -> Electric
 Ground -> Poison
 Ground -> Rock
 Ground -> Steel
 Rock -> Fire
 Rock -> Ice
 Rock -> Flying
 Rock -> Bug
 Fighting -> Normal
 Fighting -> Ice
 Fighting -> Rock
 Fighting -> Dark
 Fighting -> Steel
 Flying -> Bug
 Flying -> Fighting
 Flying -> Grass
 Ice -> Grass
 Ice -> Ground
 Ice -> Flying
 Ice -> Dragon
 Poison -> Grass
 Poison -> Fairy
 Psychic -> Fighting
 Psychic -> Poison
 Steel -> Fairy
 Steel -> Ice
 Steel -> Rock
 Bug -> Grass
 Bug -> Psychic
 Bug -> Dark
 Dragon -> Dragon
 Fairy -> Fighting
 Fairy -> Dragon
 Fairy -> Dark
 Ghost -> Psychic
 Ghost -> Ghost
 Dark -> Psychic
 Dark -> Ghost

It’s really simple: to say that Dark Pokemon are strong against Ghost Pokemon I wrote “Dark -> Ghost” and so on. Then I loaded this file into graphviz (with and without the “#” in front of layout), I got these two images:


If you look closely you’ll see they have the same set of relationships, they only differ in how they’re laid out. Pretty cool, huh? So if you encounter a Gymnasium that has a Nidoking (ground/poison), Rapidash (fire), Snorlax (normal) and Gyrados (flying/water) you can use this chart, and know that you could choose a Water, Water, Fighting and Electric Pokemon to defeat them. Note that some Pokemon, like Nidoking, have two types, so you want to choose an opponent that is strong against one or both types, but is not weak against either. In this case, water fills the bill. Water works against fire, then you see that the only thing good against normal is Fighting, and finally electric against flying/water.

A nice follow-on activity, now that we have this graph, is to optimize sequences of Pokemon in Gyms so that it’s as hard as possible to defeat them. You’ll note that our above example had two water-type weaknesses in a row – you’d want to avoid that. After that, you’d like to find, given a set of Pokemon, which ones you can safely trade away, because their strengths are subsumed (dominated in CS-speak) by other Pokemon. And so on — there’s a lot of meat in this graph!