The year was 2000, a few years after Nintendo made Pokémon Red and Blue. I was in grade 7, and had spent much of the last few years finding, capturing, training, and battling every Pokémon I could. 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. 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, 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
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 Entei makes its random move, the distance between us could be unchanged (with Entei’s move offsetting mine), or it could go down by one, or it could go down by two in the lucky
In the grand scheme of things, this isn’t too bad — especially if
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
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
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!
Meyniel’s conjecture on the cop number: A survey. Journal of Combinatorics 3(2). William Baird and Anthony Bonato (2012). ↩︎
The game of cops and robbers on graphs. Anthony Bonato and Richard Nowakowski (2011). ↩︎
Capturing the Drunk Robber on a Graph. The Electronic Journal of Combinatorics. Natasha Komarov and Peter Winkler (2014). ↩︎
Capture time in variants of cops & robbers games. Natasha Komarov (2013). ↩︎