The Gopher Grounds: The Optimizers Strike Back

2021

Overview

You are the head product designer at Herb’s Gopher Control Inc., looking to develop the ultimate commercial gopher trap. You decide to design a trap as intricate and powerful as possible, making all your competitors’ traps look like they were designed by children—kindergarteners, without adult supervision. The result is Herb’s Ultimate Gopher Exterminator—H.U.G.E.—which kills 99.9% of all gophers that have the misfortune of entering it. The trap’s configuration of weight sensors and deadly laser beams serves as both a masterpiece of engineering and an ominous threat to any burrowing rodent that dares to enter your property. One night, you bring four H.U.G.E. traps home to deal with a severe gopher problem in your own yard. After a week in operation, the traps only manage to kill a single gopher and leave the remaining three dozen unharmed. How could this be? How could the world’s most advanced gopher trap fail?

What you didn't take into account was the gophers’ intention perception. The gophers in your yard are not the mindless creatures you thought they were, but are cunningly-smart agents capable of assessing the intention of potential traps in front of them. The gophers sense that your device might be a trap, subconsciously realizing that it could have been designed by an external agent with possibly malicious intent. The trap looks too put together—too coherent—to resemble anything found in nature, so the gophers avoid it. Realizing your mistake, you scrap your H.U.G.E. design and return to the drawing board. But how exactly do you optimize your trap’s appeal to gophers without sacrificing its rodent-destroying power?

Last year, our research lab (namely, Cynthia Hom, Amani R. Maina-Kilaas, Kevin Ginta, Cindy Lay, and George D. Montañez) studied the effect of intention perception on virtual gopher trap avoidance. We concluded that the ability to sense intention through the perception of a physical artifact (i.e., gopher trap, fish bait, etc.) confers survival advantages, and developed a formal hypothesis test to assess whether a trap is lethal by looking at its coherence in design. This year, our team decided to test the limits of this hypothesis test by automatically generating virtual gopher traps using genetic algorithms and seeing if the test works in new scenarios.

Background Information

Gophers and Trap Design

We used the same gopher and trap framework as the previous team. Gophers need food to survive, which can only be found as bait inside gopher traps. Each gopher has a hunger level that measures how long it can survive without eating. Thus, gopher death results from either starvation or a trap.

Each trap takes the form of a 4 $\times$ 3 grid. Three of the tiles are fixed for all traps: one at the very bottom of the trap acts as an entrance and senses when the gopher enters; directly above the entrance is a fixed blank floor tile that the gopher can walk across to get to the third fixed tile, which holds the food enticing the gopher to enter the trap. The remaining nine tiles can either be blank floor, laser emitters, or wires meant to connect the laser emitters to the sensor at the entrance. The laser heads and wires can be one of three thicknesses, with elements of greater thickness more likely to kill a gopher. The laser will only be functional if both (1) the thickness of the laser head matches the thickness of every wire piece connecting it to the sensor and (2) the series of wire pieces connects to the sensor at the front; any wire piece disconnected from the sensor serves no function. A wire tile can either be straight or bent at a right angle, and can be rotated by 90º as needed. Laser heads can similarly be rotated by 90º. Accounting for all possible rotations and thicknesses, there is a total of 91 possibilities each of these nine tiles can take. Hence—keeping in mind that the entrance and food tiles are each used exactly once per trap—there is a total of 91⁹ $\approx$ 4.28 $\times$ 10¹⁷ possible traps in this framework.

Coherence and Hypothesis Test

The hypothesis test that last year’s team developed relies on the notion of a coherent connection. There is a coherent connection between two trap tiles if all of the following conditions are met: (1) both tiles contain either a wire or laser head, (2) the thicknesses of the two elements match, and (3) the two elements share an endpoint. Coherence of a trap, therefore, is the number of coherent connections per nonempty (wire or laser head) tile in the trap. More intuitively, a trap that looks purposeful or well put-together will have a higher coherence value than one with unrelated parts arranged seemingly at random.

The hypothesis test, in turn, assesses whether a particular gopher trap was intentionally designed by a human, and therefore more likely to harm gophers. A surprisal value $S$ is calculated by $$S(x)=-\log_{2}\left[|\mathcal{X}|(1+\ln|\mathcal{X}|)\dfrac{p(x)}{F_g(x)^{-1}}\right]$$ where $x$ represents the trap in question, $\mathcal{X}$ is the sample space of traps, $p(x)$ is a probability measure on $\mathcal{X}$, and $F_g(x)$ is the proportion of traps in $\mathcal{X}$ with greater coherence values than $x$. We reject the null hypothesis that the trap was generated at random if $S$ is greater than 13.29 bits, which corresponds to an $\alpha$ level of 0.0001.

Genetic Algorithms

We wanted to conduct the hypothesis test on traps generated by a genetic algorithm. Genetic algorithms are an optimization technique inspired by the biological process of natural selection. A genetic algorithm retains traps with higher fitnesses (as defined by the designer), resulting in the population (hopefully) becoming fitter over time. In our case, the population consists not of biological organisms but of potential solutions to an optimization problem.

A genetic algorithm usually begins with a population of elements generated uniformly at random. For each generation of the genetic algorithm, a subset of the population is selected to “reproduce” to fill the next generation's population. Much as organisms of higher fitness in nature are more likely to reproduce (by definition), elements of higher fitness in the genetic algorithm are more likely to contribute to the next generation (by construction). To achieve this, we used a roulette wheel selection process; two elements of the old generation are selected at random, with their probability of selection directly proportional to each element's fitness. These two elements undergo a recombination process in which their information is combined—usually by splicing each element in two and sampling a piece from each element—to produce a new element that contains information from both parents. Finally, we mutate the resulting element by randomly changing a random tile in the style of a genetic point mutation. This element is now fully formed and joins the new generation. The process repeats until the size of the new generation matches that of the old generation. New generations are iteratively created until some threshold is met, usually requiring that one of the elements have a fitness above a specified value or a maximum number of generations is reached. The single element with highest fitness across all generations is then returned. The flowchart below visualizes the entire process of a genetic algorithm:

Experiment

Fitness Functions and Experimental Process

We ran experiments using five fitness functions that each optimize for a different quality. To make comparisons across fitness functions easier, all five output scalar values in the range $[0,1]$. The first is a random fitness function which, as its name implies, assigns a random number in the range $[0,1]$ to each trap. The second is a functional fitness function, which gives greater fitness scores to traps that are more likely to kill a gopher that enters. The third is a coherent fitness function, which is directly proportional to the coherence of the trap as defined above. The fourth is a multiobjective fitness function which optimizes for both function and coherence simultaneously. The fifth and final function is a binary distance fitness function, which assigns greater fitness scores to traps that share tiles with some other trap chosen uniformly at random ahead of time.

For each fitness function, we ran 100 trials that each output a single trap. For each trial, we used a population size of 20 and let the genetic algorithm terminate after 10,000 generations. Every time a new trap was produced in an intermediate step of a trial, we logged the trap in a database so we could construct a probability distribution of the traps over the sample space. We then conducted the hypothesis test on each of the 100 generated traps to see whether it would sense that it was not designed by a human. For each trap, we calculated $F_g(x)$ using a Good-Turing estimation of our logged probability distribution, and let $p(x)$ be one over the size of the sample space.

The code used for the entire project is available here.

Results

While running the experiments, we immediately noticed that the genetic algorithm generated traps of high lethality more quickly than traps of high coherence. We are investigating why this is the case, though we speculate that the sample space contains more functional traps than coherent ones, resulting in a higher probability of finding a functional one than a coherent one through uniform random sampling. The experimental results raise further questions surrounding the relationship between coherence and lethality, which are discussed later.

The image below shows representative traps generated using the five fitness functions:

Representative Traps for Each Fitness Function

The random fitness function produced traps that are indistinguishable from uniform randomly generated traps, which was unsurprising. This is evidence that the genetic algorithm itself does not inject any information into its products; rather, a targeted fitness function is necessary to achieve useful results. The traps generated using the binary distance fitness function also appear as if they had been generated uniformly at random. Recall that the binary distance fitness function measures how many tiles differ between the trap in question and a pre-specified goal trap. This result makes sense intuitively, since while the fitness value provides structure and direction, it does not align the direction in any meaningful way. Merely having structure in a fitness function isn't enough; the structure must be directed in a target-oriented way to be helpful.

The traps generated using the other three fitness functions tell a different story. The functional-fitness generated traps—including the one pictured above—may appear as though they were generated uniformly at random, but an inspection of the data says otherwise. All of the functional-fitness generated traps killed 100% of the gophers that entered in our 5000 test simulations. How did this happen with such incoherent designs? To understand, one should examine the entrance of the trap pictured above and notice the two laser heads connected to the sensor. They are pointed directly at the path from the entrance of the trap to the food in the middle and are activated immediately after the gopher enters, leaving no time for the gopher to escape. The other trap tiles serve absolutely no function; they do not prevent these two laser heads from killing the gopher, however, so the algorithm has no reason to get rid of them. The result is a collection of incoherent yet deadly traps. Gophers with intention perception are especially prone to fall prey to these traps, as the incoherent designs trick them into thinking traps were not designed by humans and are therefore not lethal.

The traps generated by the coherent fitness function tell an opposite story. Many feature long unbroken strands of matching laser wires resulting in coherent-looking designs. Although coherent, these traps are overall poor at killing gophers. Consider the coherently generated trap in the above image. Although it features a coherent design and two laser heads, it is incapable of killing any gophers. Notice how the laser head at the top of the trap is not connected to the sensor and is therefore useless, and the laser head that is connected to the sensor is pointed away from the gopher’s path. 88% of the traps generated did not kill a single gopher in the 5000 test simulations, and the overall kill rate across all traps is a meager 7%. In light of the results from functional-fitness generated traps, this is not incredibly surprising; those results demonstrated that function does not imply coherence, so it is not too surprising to see such a weak correlation in the other direction. The fact that there were some lethal traps generated by the coherent fitness function might suggest some relationship between the two quantities, however; further research into this relationship is needed.

The traps generated by the multiobjective fitness function exhibit traits of both the functionally and coherently generated traps, which is not surprising. These traps are on average 35% less lethal than the functionally generated traps and 22% less coherent than the coherently generated traps; all the traps generated using the multiobjective fitness function, however, exhibit functionality and coherence, which cannot be said of any the traps of the other groups.

Testing the Hypothesis Test: Assuming a Uniform Distribution

The bar plot below shows the proportion of the traps generated with each fitness function that the hypothesis test determined to be designed with intention, using a (now misspecified) uniform probability distribution on the space of possible traps:

A few observations should be noted. When dividing the trap-generating processes into those that were designed with the goal of producing coherence and those that were not, the hypothesis tests correctly determines which traps were not even with a misspecified distribution, with 100% accuracy. The tests do miss some that were, though, as the multiobjective results show. For all of the coherence-optimized traps, they were correctly identified as being the products of goal-oriented design, even though that signal was filtered through secondary processes (namely, a genetic algorithm). Comparing these findings with the results of Hom et al., we see that the hypothesis tests can identify a signal of design for coherence, whether implemented by direct or indirect means. In fact, none of the products of processes that didn't optimize for coherence were mistaken: no functional, random, or binary distance trap was determined to be the product of intention. Thus, while missing many examples of indirect human design (namely, for functional traps), the tests are reliable for identifying intentional design of coherence-producing processes.

We see that every trap generated using the coherent fitness function is determined to be the product of intentional design (specifically, intended for coherence). This is unsurprising, as the test assumes coherence is a reliable signal of intentional design in this context, and the process was crafted with the goal of producing coherence. Similarly, 77% of the traps generated using the multiobjective fitness function (which optimized both functionality and coherence), are classified as being the products of intention. Furthermore, the test determines that all of the traps generated using the functional fitness function are not intentionally designed, and since the gophers correlate lack of coherence with safety, the gophers enter the fatal traps at high rates. Although it is true that the traps were not directly human-designed, they are decidedly unsafe for gophers with their uniform 100% lethality rate. This mistaking lack-of-coherence with lack-of-lethal-intention is costly for the gophers, and will not confer a survival advantage—it will, in fact will confer a disadvantage. The traps generated by the other three fitness functions were all correctly classified by the hypothesis test.

An interesting follow-up question is whether a coherence-based hypothesis test could be used to differentiate direct human design from indirect human design, namely, for differentiating between traps created directly by people and those created indirectly through the genetic algorithm process. If humans produce traps with regularly higher amounts of coherence, then by raising the cutoff threshold for the test above 13.29 bits one could possibly produce such a test. An open research question is: does there exist a threshold for this test which would separate direct human-designed traps from indirect human-designed (genetic algorithm) traps, based on coherence? This is a question we will explore in the future.

Revising the Hypothesis Test: Estimated Distributions

Based on our findings, a gopher using intention perception with a misspecified distribution would be easily tricked into entering lethal traps. Would knowing a better-estimated distribution on the space of traps, based on the observed frequencies of each process producing certain types of traps, help gophers to avoid death? We tested this next.

To do so, we altered the hypothesis test by using a different probability distribution for the $p(x)$ calculation. Instead of simply using $1/|\mathcal{X}|$, we estimate $p(x)$ using Good-Turing estimation of the probability distributions of the traps we logged during the experiments. To test this new model, we ran three more groups of simulations for the multiobjective traps: one in which gophers use the old misspecified hypothesis test to determine whether to enter a trap, one in which gophers use the new hypothesis test to determine whether to enter a trap, and one where the gophers have no intention perception at all. The results were surprising—the corrected intention-perception model provided either virtually no survival advantage or even a slight disadvantage. The “lack of coherence = lack of intention” mistake is unaffected by having a better estimate of the generating probability distribution.

A notable difference in the data, however, is the cause of death across the simulations. Gophers using the misspecified model more often died of starvation, whereas gophers using the new model more often died from being zapped by a laser beam. Overall, the results of the new intention tests were more similar to those of the no intention tests than the old intention ones. The below stack plots of the results from the multiobjective test demonstrate this relationship. They show that by changing the trap-generating process one can break the correlation between coherence and lethality, rendering decision-making based on the equivalence of coherence with lethality faulty. The gophers die in greater numbers as a result.

Stack Plots of Intention Simulation Results

Authors

Nick Grisanti

Sadie Zhao

Anshul Kamath

George Montañez

Acknowledgements

Special thanks to Anami Maina-Kilaas, Cynthia Hom, Kevin Ginta, and Cindy Lay for designing the gopher trap framework used in this project. This research was supported in part by the National Science Foundation under Grant No. 1950885. Any opinions, findings or conclusions expressed are the authors' alone, and do not necessarily reflect the views of the National Science Foundation.