Tips for Locating Pokemons

Pokemon Go is popular. Often you see children holding a smart phone, sometimes with their parents, looking for a monster in this game. What makes the game fascinating is in the cute, but also in the wild.

Uncertainty is the king here.

The GPS signals received by the smart phones can pinpoint where the player is (let's call it Location A), but not where the monster is (let's call it Location B). When the monster is around, the game will prompt you about their existence. However, such prompts cannot tell you directly the exact location B. The distance between A and B is, to a large extent, unknown. According to my son's experience, such a distance is very random, varying while the smart phone is probing for the monster: sometimes close, sometimes farther away.

If you are not afraid of some maths, please read on, how we came up with some hypotheses and verify them until we were close to the truth.

As mentioned earlier, we assumed initially that the location of the monster (B) is drifting, which was our first null hypothesis. While we encountered a monster and knew its location, instead of caught it immediately, we walked in all directions North, East, South, West, by some 200 meters from this location, until the monster disappeared from the "radar". We then noted down the locations, and tracked back to where we had started (location B). In this way, suppose the hypothesis was true, that the monster's location drifts, then we should not see it always at the same location (B) and miss it at the other same locations. After several experiments, it was established that the monster stayed around the same place. It did drift slightly due to the drifts of GPS signals, but those small drifting errors were tolerable. Therefore, we rejected the null hypothesis, and concluded that once the monster is found, it won't leave its nest.

According to some videos on YouTube!, once born Pokemon will last 15 minutes for your search. My son's encounters had demonstrated the fact hundreds of times, so it did not require any further experiments.

Next, we came up with another null hypothesis, that the distance between the Pokemon and where the smartphone warns its existence is constant. After several experiments, we found that's not true: the pokemon might be next to you, or it might be rather far. This distance is another random variable! We had to reject this null hypothesis again.

Oh well, could we fully solve this problem? I suggested to reverse engineer the Pokemon Go app in order to understand the truth from its source code. However, my son rejected this suggestion immediately because it could be against the copyright protection and might not be ethical. So we had to resort to external observations.

Taking out a piece of paper, I drew two circles around A and B. Suppose that the radius of these circles is RA and RB respectively, then the two circles intersect each other only when RA + RB > AB, where AB is the distance between A and B. Let's call the two intersecting points C and D. Without loss of generality, on the intersecting point C, we assumed that Pokemon Go would report the appearance of the monster, while the monster would disappear when it was outside the circle of B. Then C became a boundary point. The appearance and disappearance of a monster were two observable events, from which we could reduce the uncertainty as long as we could mark C up in the map.

A simple corollary followed. Let's take a random direction to walk from C, until we reached another boundary point (i.e., where the monster appeared and disappeared), marking it up as D. Now, took the midpoint between C and D, and drew a vertical line across this midpoint, the monster should be on this line. According to this conclusion, we had found three monster consecutively, very lucky! Indeed, not all by the luck :-)

A further question was, could we determine the location of the monster from C and D? Not yet. Although we had guessed the direction roughly, it still took quite some unnecessary steps. If only we could have another hint, the problem would have been fully solved. Suppose that we could find another boundary point, E, where the monster appeared/disappeared, then the monster should lurk at a place with equal distance to C, D, and E. This is called the circumcenter of the triangle CDE.

Our follow-on experiments confirmed this finding, and it worked every time ! My son was extremely happy, while I thought that the theoretical answer could be made even more practical, if only computer could compute and mark the circumcenter of the three marked points in the map. Fortunately, Google Map API has the marker feature for this functionality. Adapting an open-source project on GitHub, I was able to engineer a solution after overcoming a few technical obstacles. Worth to mention was the fact that the Earth is round ! The geolocations obtained from the GPS API concern latitude and longitude, rather than X-Y coordinates, making it a bit tricky to compute the circumcenter. Furthermore, the circumcenter computed from the triangle CDE was not visible on the map, instead, it was below the surface of the Earth and we needed to lift it up onto the surface using the radius of the Earth, and to convert the result back to latitude and longitude for the Google Map marker.

If you are interested in these software engineering details, please consult the code base https://github.com/yijunyu/pokemon-compass.

The moral of these experiments is teaching my son the scientific method for approximating the truth, which is never far away if we keep trying. I am also hoping to learn a thing or two in my research to reduce the uncertainty of tracking airplanes using live blackboxes. Stay tuned!

Chinese translation.


Email: y.yu@open.ac.uk Office: +44 (0) 1908 6 55562