How to catch legendary Pokémon (in theory)

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.

Jigglypuff can always be found on Route 46.

The legendary Entei, Raikou, and SuicuneI'm including Suicune in this list since it roamed in the original Gold and Silver, but its behaviour is different from the others in Pokémon Crystal, HeartGold, and SoulSilver. 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.The game of cops and robbers on graphs. Anthony Bonato and Richard Nowakowski (2011). 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 problemMeyniel’s conjecture on the cop number: A survey. Journal of Combinatorics 3(2). William Baird and Anthony Bonato (2012). 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 nn-vertex, mm-edge graph can be expected to spend deg(v)2m\frac{\deg(v)}{2m} of its time at each location vv,Random walks on graphs: A survey. Combinatorics, Paul Erdős is Eighty. László Lovász (1993). and to visit the whole graph after at most roughly 4n3/274n^3/27 steps.A tight upper bound on the cover time for random walks on graphs. Random Structures & Algorithms 6(1). Uriel Feige (1995). 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.

Professor Elm ponders some results and conjectures about graph pursuit games

Recently, Peter Winkler and Natasha Komarov found a strategy for general graphs which gives a better bound on the expected capture time.Capturing the drunk robber on a graph. The Electronic Journal of Combinatorics. Natasha Komarov and Peter Winkler (2014). 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)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.Capture time in variants of cops & robbers games. Natasha Komarov (2013). It is an open question to find a general bound for the "randomly greedy" strategy's expected performance that would prove her right.