Competitive Coevolution

A cheetah is fast because gazelles are fast. Gazelles are fast because cheetahs are fast. Neither population decided to improve; each was forced to by the other. This is competitive coevolution — evolution driven not by a static environment but by an adversary that is itself evolving.

The biologist Leigh Van Valen captured it in 1973 with what he called the Red Queen hypothesis: in a co-evolutionary race, every species must keep running just to stay in the same place relative to its rivals. Stop improving, and you fall behind. There is no optimal resting point.

What makes this remarkable from a computational standpoint is the structure it creates. Two populations locked in mutual pressure tend to produce strategies of ever-increasing sophistication — not because anyone planned it, but because each side's progress immediately raises the bar for the other. The result is an open-ended escalation that evolutionary computation and game-playing AI exploit deliberately.

Below, two populations — predators and prey — compete across generations. Each individual has a single numerical trait (its speed). Each generation, predators hunt prey: a predator catches a prey if its speed exceeds the prey's speed by less than a threshold. Survivors reproduce with small random mutations.

<!-- {{c_intro}} -->
<div class="controls">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="gen-label">{{lbl_generation}} <b id="gen-num">0</b></span>
</div>
<div class="chart-wrap">
  <canvas id="chart" width="560" height="200"></canvas>
</div>
<div class="populations">
  <div class="pop-box predator">
    <div class="pop-title">{{lbl_predators}}</div>
    <div class="pop-stat">{{lbl_avg_speed}} <b id="pred-avg">—</b></div>
    <div id="pred-dots" class="dots"></div>
  </div>
  <div class="pop-box prey">
    <div class="pop-title">{{lbl_prey}}</div>
    <div class="pop-stat">{{lbl_avg_speed}} <b id="prey-avg">—</b></div>
    <div id="prey-dots" class="dots"></div>
  </div>
</div>
<div id="status" class="status"></div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.gen-label { font-size: .9rem; color: #555; margin-left: auto; }
/* {{c_chart}} */
.chart-wrap { background: #f4f7fa; border-radius: 10px; padding: .4rem; margin-bottom: .6rem; }
canvas { display: block; max-width: 100%; }
/* {{c_pop_boxes}} */
.populations { display: flex; gap: .6rem; }
.pop-box { flex: 1; border-radius: 10px; padding: .5rem .7rem; }
.pop-box.predator { background: #fff0f0; border: 1px solid #f2b8b8; }
.pop-box.prey { background: #f0f7ff; border: 1px solid #b3d3f5; }
.pop-title { font-weight: 700; font-size: .85rem; margin-bottom: .2rem; }
.predator .pop-title { color: #b91c1c; }
.prey .pop-title { color: #1d4ed8; }
.pop-stat { font-size: .8rem; color: #444; margin-bottom: .35rem; }
/* {{c_dots}} */
.dots { display: flex; flex-wrap: wrap; gap: 3px; }
.dot { width: 10px; height: 10px; border-radius: 50%; }
.predator .dot { background: #e63946; }
.prey .dot { background: #2563eb; }
.status { font-size: .85rem; font-weight: 600; color: #555; min-height: 1.2em; margin-top: .4rem; }

// Code not found

Watch how both populations' average speeds climb over time. Neither converges to a fixed value — they chase each other in an endless escalation. This is the hallmark of competitive coevolution: the fitness landscape itself keeps shifting because your opponent keeps improving.

Competitive coevolution sounds simple — two populations improving against each other — but it conceals several deep difficulties.

• Cycling. A strategy that beats the current champion may itself be beaten by a strategy the champion used to defeat three generations ago. The population can orbit endlessly without making genuine progress.
• Forgetting. When a superior predator strategy drives all prey below a certain speed extinct, the memory of how to defeat fast prey disappears. A new fast-prey mutation later finds the predator population unprepared.
• Disengagement. If one side gets too far ahead, the other stops providing useful selection pressure. Prey that all get caught immediately offer no information about which predator strategy is better — the signal vanishes.
• The shifting landscape. Unlike static optimization, there is no fixed fitness function to climb. Each population's fitness is defined relative to the other, so the landscape reshapes every generation.

These pathologies have precise analogues in game theory: finding a Nash equilibrium in a two-player zero-sum game is the stable counterpart of what coevolution is trying to reach — but coevolution often cycles around it without converging. Population size, mutation rate, and selection pressure all interact to determine whether the arms race produces genuine innovation or just noise.

The arms-race structure appears wherever two adaptive systems push against each other:

• Game-playing AI. AlphaGo and its successors were trained partly by self-play — a form of competitive coevolution where the system competes against past versions of itself. Each stronger version raises the bar for the next.
• Cybersecurity. Malware evolves to evade detectors; detectors evolve to catch new malware. Neither side is static, and each advance by one side immediately pressures the other.
• Drug resistance. Bacteria evolve resistance to antibiotics; researchers develop new antibiotics. The Red Queen runs in hospitals as surely as on the savanna.
• Program synthesis and adversarial testing. A program generator and a test-suite generator can be pitted against each other: the generator tries to produce programs that pass all tests; the test suite tries to find a failing input. Each side sharpens the other.

In all these cases the co-evolutionary structure is both the problem and the solution: the very pressure that makes the race hard is what drives both sides to become more capable than either could alone.

Competitive coevolution is the Red Queen in algorithmic form: run as fast as you can, and your opponent runs just as fast. The race never ends, but it is not futile — the escalation is precisely what produces cheetah speed, immune diversity, game-playing champions, and robust security systems.

The next time you hear that an AI defeated a human champion at chess or Go, remember that the champion it trained against was also an AI — one that kept improving specifically because the first one did. That mutual pressure, generation after generation, is competitive coevolution at work, and it is one of the most powerful forces in both nature and computation.