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:

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 Spock

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!