Geometry in Interactive Domains

Coevolution researchers have long known about the issue of intransitive cycles. Such a cycle is epitomized by the game rock-paper-scissors. Namely, there are three strategies a, b and c such that a beats b, b beats c, and in turn c beats a. It is unclear, then, which strategy is "the best." In the absence of other information, there is a sense in which all three of these strategies are equally good. In our geometrical viewpoint, they will show up as lying on a line or a circle, a sort of equipotential curve indicating they are equally, though differently, capable.

An issue which has received less attention is that of overspecialization (also called focusing). This issue can arise when there are four strategies a, b, c and d such that a beats c and loses to d, but b beats d and loses to c. In this case, a can do something that b cannot do (beat c), but simultaneously b can do something which a cannot do (beat d). Put another way, beating c is a skill that a has but b lacks, while beating d is a skill b has but a lacks. In the geometrical viewpoint, this situation shows up as the simplest example of a two-dimensional set of interactions. The issue of overspecialization arises when a search algorithm focuses attention too strongly on one skill at the expense of others. In geometrical language, we say the search algorithm has lost knowledge about some of the dimensions of the problem.

These two issues, intransitivity and overspecialization, represent different, fundamental geometrical pitfalls in navigating any space. Intransitivity represents a curved dimension, which looks straight locally but ultimately loops back on itself. Traveling on such a dimension wastes resources, since no progress is made -- one is going in circles. Overspecialization, by contrast, represents a lack of information: the dimension might be straight and progress maintained on it, but the traveler will miss large portions of the space they are navigating. In a search context, the solutions discovered will be brittle, since the searcher neglected certain important skills.

The Geometry of Arms Races

Unfortunately, arms races tend to be unstable. There are two well-known pitfalls which arise in traditional coevolutionary algorithms and impede continuous progress. One is a winner-take-all situation in which a single individual comes to dominate a population, effectively wiping out all diversity and, in particular, all knowledge of the structure of the problem domain. A sort of premature convergence, winner-take-all typically does not produce a strong solution to the problem. The second pitfall which arises has gone by various names: mediocre stable state; intransitive superiority; cycling. None of these terms have proved to be appropriate, yet the idea behind them is important. This pitfall arises when an algorithm appears to be producing change -- i.e., individuals are changing -- yet, according to some metric of performance, the algorithm no longer progresses. Often one observes oscillations in the metric of performance, indicating the algorithm might be cycling among previously-visited individuals. In general it is not clear whether these are true cycles or quasi-cycles, however.

A third, lesser-known impediment to arms race dynamics relates to the overspecialization issue described above. The problem here is that individuals may race along a particular dimension, ignoring other dimensions of a problem. Relative to one another they may appear to be improving; they may also appear to be improving according to some metric of performance. However, the individuals are becoming more and more overspecialized. One would expect these individuals to be brittle solutions to the problem; while they may have become quite adept at the skill they have been racing, they have achieved this ability at the expense of all other skills. Since this kind of dynamics closely resembles an arms race (and in fact, is how biologists use the term), we will distinguish our ideal coevolutionary dynamics by calling it a progressive arms race. A progressive arms race maintains progress on all dimensions of a game, where an ordinary arms race may not.

Progressive arms races resolve into two components. Firstly, there must be information which shows that improvement is possible and valuable. In a chess club, players want to improve at the game, but may not see how to improve if they do not have appropriate opponents to play against and chess books to read. Secondly, it must be possible for players to improve. Even if players want to improve and have appropriate information suggesting how, they might not be able to adjust their play in order to actually improve at the game. In other words, having good information might ensure progress, but does not enable it; progress requires both.

Stated in geometrical language, these two components of progressive arms races show up respectively as learning the geometry of the domain and learning how to navigate that geometry. The geometry of the domain means the important dimensions or skills of the problem, as discussed in the previous section. Without some knowledge of these dimensions, it is impossible to see how improvement can be made. Therefore, a search algorithm must be sensitive to these dimensions and be able to discover and keep them. However, knowing the dimensions does not guarantee an algorithm is able to move along them. For that, we need an appropriate substrate or representation. In this context, appropriate means that the adjustments which can be made to a current strategy are tuned to the dimensions of the problem: there is at least one adjustment which leads a player to improve on at least one dimension.

To restate it simply, in coevolution the progressive arms race is about simultaneously discovering the geometry of a space and learning how to navigate that space.