Pokémon Gold and Silver‘s roaming legendary beasts move randomly from route to route instead of sticking to a fixed habitat. By analyzing their behaviour using the math of random walks on graphs, I can finally answer a question that’s bugged me since childhood: what’s the best strategy to find a roaming Pokémon as quickly as possible?

Catching a roaming Pokémon is a graph pursuit game, but in practice the optimal strategy doesn’t involve a chase at all. Raikou and the other roaming Pokémon move every time the player crosses the boundary from one location to another, regardless of how long that takes. So if we repeatedly cross the boundary by taking one step forward and one step back, Raikou will effortlessly speed across the map.

The easiest strategy, then, is to choose a centrally-located location and hop back and forth until Raikou comes to us. The question is what location gives the best results.

Vertices of maximum degree

When left to its own devices, a random walk in a graph G returns to a vertex v every

\frac{2|E(G)|}{\deg(v)}

steps. This suggests that the best place to find Raikou is a vertex of maximum degree on the graph corresponding to the Johto map.

This puts Johto Route 31 as the top candidate, since it’s the only route adjacent to five other routes (Routes 30, 32, 36, 45, and 46) on the roaming Pokémon’s trajectory.

Vertices with minimum average effective resistance

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\in V(G)} T(u, v),

where T(u, v) is the expected time for a random walk starting at u to first reach our vertex v.

How do we compute this value? According to Tetali, we replace all of the edges with 1-ohm resistors and measure the effective resistances R_xy between each pair of nodes x, y in the corresponding electrical network. Then

T(u, v) = \frac{1}{2}\sum_{w\in V(G)} \deg(w) (R_{uv} + R_{vw} - R_{uw}).

It seems very appropriate to use the math of electrical networks to catch the electric-type Raikou! Unfortunately, there’s no references to effective resistance or Tetali’s formula in its Pokédex entry.

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 nifty formula based on the Laplacian matrix of the graph.

Route 31 comes out on top again by this measure: if Raikou starts from a random location, it will come to this route sooner on average than any other single location.

Vertex pairs with minimum average effective resistance

But this still isn’t the final answer. The above calculations assume we’re hopping between a route (where we can catch Raikou) and a town (where we can’t).¹ What if we go to a boundary where either side gives us a chance for an encounter?

There are only four pairs of routes in Johto where this is possible. The expected capture time when straddling one of these special boundaries can be computed using the same kinds of calculations. All four route pairs yield an expected capture time faster than relying on any individual route — enough to dethrone Route 31!

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)]
}

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. Specifically, the calculations were done on the tensor product of K₂ and the graph representing Raikou’s possible moves between the Johto routes. ↩︎