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; for example, Jigglypuff can always be found on 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. Catching this roaming Pokémon would be an interesting challenge.
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?
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. On a cycle, for example a robber can give a single cop the run-around, but will be caught if two cops work together.
Unfortunately, the graph corresponding to the Pokémon region of Johto contains a long cycle as an isometric subgraph, so its cop number is at least two. 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 n locations on an arbitrary map after roughly 4n3/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.
A good place to start is the “greedy” strategy I originally used: at each step, move closer to the robber’s current position. At each step, let’s say that the robber has at most Δ choices of adjacent places to run to. Since Entei moves randomly, it has at least a 1/Δ chance of moving towards the trainer. If the trainer starts d steps away, she only needs to get lucky d/2 times before crossing paths with Entei. The capture time follows a probability distribution bounded by the negative binomial distribution and has expectation E[capture time] ≤ Δ⋅d/2. In the grand scheme of things, this isn’t too bad — especially if Δ 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 better than the above Δd/2 bound when the graph has vertices with large degree, and is essentially best possible on certain graphs.
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.
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.
The solution for the particular game played in Pokémon is a little anticlimactic: since the roaming legendaries are forced to move when the player character changes locations — regardless of how little time that takes — the optimal strategy is to hop back and forth between two routes and let your target come to you! The expected capture time can be found with the theory of random walks on graphs, and is inversely proportional to the number of routes adjacent to the place you wait.