# How to catch legendary Pokémon

## Graph pursuit games in Gold and Silver

The year was 2000, a few years after Nintendo made Pokémon Red and Blue.1 I was in grade 7, and had spent much of the last few years finding, capturing, training, and battling every Pokémon I could.2 Finally, I had caught all 150 available species and completed my Pokédex, and I desperately wanted Nintendo to make more.

That Christmas, I got my wish. My 12-year-old eyes lit up when I unwrapped Pokémon Silver at my grandparents' house: Colour graphics! A whole new world to explore! And a hundred new Pokémon! As soon as I could escape from present-opening, I raced downstairs and started playing. By the time it was time to leave at the end of the week, I already had four badges — and then, on the car ride home, I encountered a new legendary Pokémon with a very unique quality.

Normally, each species of Pokémon can be found in a handful of fixed habitats. If you want to catch Abra, you go to Route 24; if you're looking for Jigglypuff, head to Route 46.3 But this new encounter, the legendary beast Entei, didn't stay put. It ran away as soon as I stumbled across it, and moved to a different route every time I stepped into a new location. It looked like I would have to chase Entei across the world map repeatedly, gradually whittling down its health and throwing Pokéballs over dozens of encounters.

Months passed, and though I had long since beaten the rest of the game, I still hadn't succeeded in catching Entei. I had spent hours chasing it around the world map, only to have it run away each time I threw a Pokéball at it. Exasperated, I wondered: What strategy would catch the roaming Pokémon as quickly as possible?

### Cops and robbers

Since the 1970s, mathematicians have studied graph pursuit games like this one. Classically, researchers have asked how many "cops" it takes to guarantee the capture of an evasive "robber" travelling around a graph. Depending on the graph, many cops might be needed to catch a clever robber.

The cops-and-robbers game is a fascinating and accessible research area with a deep open problem and enough prior work to fill a book. It’s known, for example, the exact conditions under which a lone pursuer can back the target into a corner and when the target can evade capture indefinitely.

Unfortunately, the graph corresponding to the Pokémon region of Johto contains a long cycle as an isometric subgraph, so it is not a cop-win graph. In other words, it's possible that a roaming Pokémon could theoretically evade a single Pokémon trainer forever! But there's still hope. The legendary beasts don't devote their movements to avoiding a little kid,4 so the assumption of perfect play doesn't apply to our game of cops and robbers. We might be able to use their random behaviour to find a strategy to capture them in a short amount of time.

How did I come across Entei in the first place? As it turns out, a roaming Pokémon can be expected to visit each of the $$n$$ locations on an arbitrary map after roughly $$4n^3/27$$ steps. So any trainer who isn't actively trying to avoid Entei should end up bumping into it eventually — and an intelligent trainer should be able to do much better.

The first place to start is the "greedy" strategy I originally tried as a kid: every time Entei moves, check the map, and move to any route that gets me closer to them. After Raikou makes its random move, the distance between us could be unchanged (with Raikou’s move offsetting mine), or it could go down by one, or it could go down by two in the lucky $$\frac{1}{\Delta}$$ chance that Raikou moves towards me. If I start at a distance of $$\ell$$ steps away from Raikou and get lucky $$\frac{\ell}{2}$$ times, I’ll have caught up — so using a negative binomial distribution bound, $$\text{E[capture time]} \leq \frac{\Delta \ell}{2}$$.

In the grand scheme of things, this isn’t too bad — especially if $$\Delta$$ is low. But it still takes a frustratingly large time for a 12-year-old, and in general it’s possible to do better.

Recently, Peter Winkler and Natasha Komarov found a strategy for general graphs which gives a better bound on the expected capture time. Somewhat counterintuitively, it involves aiming for where the robber was — rather than his current location — until the cop is very close to catching him. The Komarov-Winkler strategy has an expected capture time of $$n + o(n)$$, where $$n$$ is the number of locations on the map. This is essentially best possible on certain graphs, and is better than the above $$\frac{\Delta \ell}{2}$$ bound when the graph has vertices with large degree.

For graphs without high-degree vertices — like the Pokémon world map — it is possible that a simpler solution could beat the Komarov-Winkler strategy. The problem is: simpler strategies may not be simpler to analyse. In her PhD thesis, Natasha wondered whether a greedy algorithm with random tiebreakers could guarantee $$n + o(n)$$ expected capture time. It is an open question to find a general bound for the "randomly greedy" strategy's expected performance that would prove her right.

### Conclusion

Nintendo has embedded an interesting mathematical problem in the Pokémon video game series: to catch the roaming legendary Pokémon, trainers play a variant of the cops-and-robbers graph pursuit game. We've seen a few strategies for the game on general graphs, but still haven't found an answer to the question I asked as a Pokémon-obsessed 12-year-old. In a future post, I'll provide closure for my younger self, and explain how we can compute the best strategy for a particular graph. Until then, may all your video games contain interesting mathematics!

1. Red and Blue, the first installments of the video game series to be released outside of Japan, kicked off a multimedia franchise that now includes a trading card game, TV series, all sorts of merchandise, and even aircraft↩︎

2. I spent even more time thinking about Pokémon, which is why large swaths of my brain are now irrevocably committed to knowing Pokémon evolutionary lines and type advantages↩︎

3. If you want to find a Zubat, walk around anywhere. They'll find you. ↩︎

4. Fair enough; I’m sure they have better things to do than devoting their movements to avoiding a little kid. ↩︎