How to catch legendary Pokémon

Pokémon Gold and Silver introduced the roaming legendary beasts: three one-of-a-kind Pokémon that move from route to route instead of sticking to a fixed habitat. Catching a roaming Pokémon amounts to winning a graph pursuit game — so what can we learn about it from the latest mathematical results?

To review the Pokémon mechanics, each species can normally 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.

The legendary Entei, Raikou, and Suicune1 are different. There’s only one of each species, each situated on a random route. Each time the player character moves to a new location, the roaming Pokémon each move to a randomly-selected route adjacent to the one they were just on. In graph theory terms, the player and Pokémon are engaged in a pursuit game where the Pokémon’s strategy follows a random walk.

The study of graph pursuit games is a fascinating and active area of research. 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; there is a deep open problem about the worst-case cop numbers of large graphs.

Because the graph corresponding to the Pokémon region of Johto contains a long cycle as an isometric subgraph, its cop number is more than one — in other words, it’s possible that a roaming Pokémon could theoretically evade a lone Pokémon trainer forever! Fortunately, the legendary beasts play randomly, not perfectly, so the worst-case scenario doesn’t apply.

A random walk in an arbitrary $n$-vertex, $m$-edge graph can be expected to spend $\deg(v)/(2m)$ of its time at each location $v$, and to visit the whole graph after at most 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 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/\Delta$ chance that Entei moves towards me. If I start at a distance of $\ell$ steps away from Entei and get lucky $\ell/2$ times, I’ll have caught up — so using a negative binomial distribution bound,

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 their 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 $\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.