How to catch legendary Pokémon with electrical networks

A few years ago, I wrote an article about the graph pursuit game required to catch the legendary trio Raikou, Entei, and Suicune in Pokémon Gold and Silver, but I never fully answered the most important question: what strategy catches the roaming Pokémon fast as possible?

In addition to the graph-theoretic concerns discussed in my previous post, we also need to take into account how long each graph move takes to execute.1 From Violet City, for example, it's much faster to pop to Ecruteak via Routes 36 and 37 than to Azalea Town via Routes 32 and 33.

Two paths may have very different completion times even if they count as the same number of graph moves.
Two paths may have very different completion times even if they count as the same number of graph moves.

The absolute fastest way to complete one graph move is to take a single step across the boundary between two locations; Raikou and the other roaming Pokémon will instantaneously move as soon as we do that. Taking one step back across the boundary will complete another graph move and force our quarry to move again. This is so much faster than navigating from one end of a route to another that it's almost certainly optimal to hop back and forth between two locations and wait for Raikou to come to us.2 The only question is: where?

Intuitively, it seems that we should camp out near a route that's well-connected in some sense, but it's not clear what measure of centrality gives the best answer. High-degree vertices in the "Johto graph" \(G\) seem like good candidates, since we can expect Raikou, when left to its own devices, to return to a vertex \(v\) every \( \frac{2|E(G)|}{\deg(v)} \) steps. This would argue in favour of Johto Route 31, which is adjacent to five other routes (Routes 30, 32, 36, 45, and 46) on the roaming Pokémon's trajectory.

The routes of Johto and Hoenn, coloured according to their corresponding vertex degrees.
The routes of Johto and Hoenn, coloured according to their corresponding vertex degrees.

Of course, we don't intend to leave Raikou to its own devices—we're going to try to catch it whenever it's on our route! If it gets away, it will flee to a random location that can be anywhere on the map, regardless of whether it is adjacent or not. This wrinkle means we're not exactly trying to find the vertex with the fastest return time; we're really trying to minimize $$\frac{1}{|V(G)|}\sum_u T(u, v),$$ where \(T(u, v)\) is the expected time for a random walk starting at \(u\) to first reach our vertex \(v\). This value can be computed using Tetali's formula $$T(u, v) = \frac{1}{2}\sum_{w\in V(G)} \deg(w) (R_{uv} + R_{vw} - R_{uw}),$$ where \(R_{xy}\) is the effective resistance between the points \(x\) and \(y\) if the edges of the graph were all replaced with 1-ohm resistors. Yes, we can use the math of electrical networks to catch the legendary electric-type Raikou!

Effective resistance can be computed by hand using Kirchoff's and Ohm's Laws, but it's much easier to plug it into SageMath, which uses a a nifty formula based on the Laplacian matrix of the graph.3 Somewhat anticlimactically, Route 31 comes out on top with this measure too, but it does tell us that Route 36 is better than Route 42 despite their identical degrees.

Expected capture time when moving between a given route and an adjacent town

But this still isn't the final answer. The above calculations assume you're hopping between a route (where you can catch Raikou) and a town (where you can't). What if you go to the boundary between two routes, where both steps give you a chance for an encounter?

There are only four pairs of routes in Johto where this is possible4. The expected capture time when straddling one of these special boundaries can be computed using the same effective resistance calculations as the above if we merge the vertices \( (u, 0) \) and \( (v, 1) \) corresponding to our location after an even or odd number of steps, respectively. All four route pairs yield an expected capture time5 faster than relying on any individual route — enough to dethrone Route 31!

Expected capture time when moving between adjacent locations

Conclusion

Although Raikou will on average arrive at Route 31 faster than any other route, the best place to catch the roaming legendary Pokémon is the boundary between Johto Routes 36 and 37. Hop back and forth between those two routes, and before you know it, you'll be one step closer to completing your Pokédex!


  1. After all, screen time isn't measured by "number of graph moves executed". ↩︎

  2. This intuition is confirmed when we compute expected capture times later in the post. Hopping back and forth will bring Raikou to you faster than you can traverse a single route end-to-end, much less execute an active graph pursuit strategy. ↩︎

  3. Technically, we're computing the effective resistances in the product graph \( H = G \times K_2 \). That's to take into account the fact that we can only capture Raikou after an even number of steps, assuming we're hopping between a route and a town where wild Pokémon can't be encountered. It's valid to look at random walks on \(H\) instead of \(G\) since the natural homomorphism \(f: H \rightarrow G\) induces a probability-measure-preserving isomorphism between walks with a fixed starting vertex in \(H\) and walks with the corresponding fixed starting vertex in \(G\). ↩︎

  4. Routes that are "adjacent" with respect to Raikou's movement are often separated by a town, cave, or other obstacle that takes longer for the player to traverse. ↩︎

  5. There are actually two expected capture times, shown on the graph as different shades of pink, depending on which route you start on. But if you don't have a Master Ball and Raikou gets away, you've effectively restarted the game from whichever route you had the last encounter on. The relative frequency in which Raikou is encountered on each of the two routes, and therefore the expected capture time of the repeated version of the game, is left as an open problem. ↩︎

Source code

sourcecode.py
G = Graph({ 29: [30, 46], 30: [31], 31: [32, 36, 45, 46], 32: [33, 36], 33: [34], 34: [35], 35: [36], 36: [37], 37: [38, 42], 38: [39, 42], 42: [43, 44], 43: [44], 44: [45], 45: [46] })

R_matrix = G.effective_resistance_matrix()

def R(u, v):
    return R_matrix[G.vertices().index(u)][G.vertices().index(v)]

def hitting_time(u, v):
    return 1/2 * sum(G.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in G.vertices())

def avg_hitting_time(v):
    return mean([hitting_time(u, v) for u in G.vertices()])

{ v: avg_hitting_time(v) for v in G.vertices() }

# account for parity

H = G.tensor_product(graphs.CompleteGraph(2))
R_matrix = H.effective_resistance_matrix()

def R(u, v):
    return R_matrix[H.vertices().index(u)][H.vertices().index(v)]

def hitting_time(u, v):
    return 1/2 * sum(H.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in H.vertices())

def avg_hitting_time(v):
    return mean([hitting_time((u,0),(v,0)) for u in G.vertices()])

{ v: avg_hitting_time(v) for v in G.vertices() }

# Final 

@CachedFunction
def H(routes=None):
    if routes is None:
        return G.tensor_product(graphs.CompleteGraph(2))
    else:
        x, y = routes
        graph = H(None).copy()
        graph.merge_vertices([(x, 0), (y, 1)])
        return graph

@CachedFunction
def R_matrix(routes):
    return H(routes).effective_resistance_matrix()

def hitting_time(routes, u, v):
    H0 = H(routes)
    R = lambda x,y: R_matrix(routes)[H0.vertices().index(x)][H0.vertices().index(y)]
    return 1/2 * sum(H0.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in H0.vertices())

{
  (x, y): mean([ hitting_time((x,y), (u,0), (x,0)) for u in G.vertices() ])
  for (x, y) in [(30,31), (31,30), (35,36), (36,35), (36,37), (37,36), (45,46), (46,45)]
}

References

Related