Pursuer, Evader
I won a contest in my Computer Science II course. I’ll admit it though: I cheated.
For a homework assignment, we were given graphs where vertices represented cities and edges were railroads between them. An evader would move between the cities, trying to avoid capture by one or several pursuers; if the evader and a pursuer ended up in the same city at the end of a turn, the game ended as a pursuer victory. The evader won if it survived a certain number of turns. Our assignment was to program a strategy for the evader and another for the pursuers.
For the contest, each pursuer strategy was competed against every evader strategy on each of 9 graphs (including one of mine, a painstakingly recreated Risk! board). Since some strategies relied on random numbers, there were 100 trials between each strategy pair on each map, for a total of 8,820,000 chases.
The scoreboard summarizes the results. My evader did not rank, but my pursuer ranked first overall with an average rank of 1.8 over the nine graphs. I ended up winning as one of two “Best Student Submissions,” with honorable mentions for “Creative Writing,” “Most Lines of Pursuer Code,” and “Technically within the Rules but… We’re Changing them for Next Year.” I was given a handsome block puzzle that appears to be called a Victory Cube.
But, as I mentioned, I cheated.
Implementation
The strategies were functions compiled into the same executable and run in the same memory space. The assignment came with a prewritten tick() function, which evaluates the evader’s strategy, followed by the pursuer’s. The strategy functions return a player’s decision to move to another city, or remain in the current one.
It is important to note that moves are not actually carried out until all decisions have been made. This effectively means that all players move simultaneously.
While programming my strategies, I cleaned up the provided code and added comments so I could better understand how it was working. You can download the cleaned code and my strategy files.
Evader Strategy
My evader was “psychic”: It simply called each pursuer’s strategy function and determined where it was planning on moving. I think that a similar strategy was used the year before, but mine took an extra precaution against randomization: it seeds the random number generator before calling the pursuer function, then reseeds it afterwards, so that the pursuer will make the same decision again when the tick() function legitimately calls it.
Once the evader knows where each pursuer is planning on moving, it looks at all adjacent cities and eliminates the ones that pursuers will be moving in to. If there is a safe route, it goes there (randomly picking between multiple choices).
My friend Alex came up with a clever way of doing this for the pursuer. Since the pursuer’s code was called after the evader’s, his strategy unwound the stack to find the evader’s decision.
Pursuer Strategy
The pursuer strategy is based on the protozoan parasite Toxoplasma gondii, which induces a condition in rats and mice known as toxoplasmosis. The effect is that they are drawn suicidally towards cats, who obviously kill and eat the rodents — all so the parasite can pass to a new host and reproduce.
Interestingly, about a third of the population of the U.S. carries the parasite. It has been linked to increased risk taking behavior, slowed reaction times, feelings of insecurity and paranoia, neuroticism, and schizophrenia.
The pursuer strategy looks up the address of the evader’s function and patches it so that a parasitic function is called instead. This function moves the evader towards the closest pursuer, who is of course moving in the opposite direction. The chase ends quickly — in the contest, it took at most 3 moves to capture the prey.