How to catch legendary Pokémon

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. 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.

Pokémon box-art mascots Charizard, Blastoise, Pikachu, Lugia, and Ho-Oh
Pokémon box-art mascots Charizard, Blastoise, Pikachu, Lugia, and Ho-Oh

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.

Jigglypuff can always be found on Route 46, but Entei moves from route to route.
Jigglypuff can always be found on Route 46, but Entei moves from route to route.

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 [1] and enough prior work to fill a book [2]. 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.

Professor Elm ponders some results and conjectures about graph pursuit games
Professor Elm ponders some results and conjectures about graph pursuit games

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 nn locations on an arbitrary map after roughly 4n3/274n^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 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 1Δ\frac{1}{\Delta} chance that Entei moves towards me. If I start at a distance of \ell steps away from Entei and get lucky 2\frac{\ell}{2} times, I’ll have caught up — so using a negative binomial distribution bound, E[capture time]Δ2\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 [3]. 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)n + o(n), where nn is the number of locations on the map. This is essentially best possible on certain graphs, and is better than the above Δ2\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)n + o(n) expected capture time [4]. 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. Meyniel’s conjecture on the cop number: A survey. Journal of Combinatorics 3(2). William Baird and Anthony Bonato (2012). ↩︎

  2. The game of cops and robbers on graphs. Anthony Bonato and Richard Nowakowski (2011). ↩︎

  3. Capturing the Drunk Robber on a Graph. The Electronic Journal of Combinatorics. Natasha Komarov and Peter Winkler (2014). ↩︎

  4. Capture time in variants of cops & robbers games. Natasha Komarov (2013). ↩︎