The N-Strikes-Out Algorithm: A Steady-State Algorithm for Coevolution

We introduce the N-strikes-out algorithm, a simple steady-state genetic algorithm for competitive coevolution. The algorithm can be summarised as follows: Run competitions between randomly chosen individuals, keep track of the number of defeats for each individual, and remove any individual which has been defeated N times. Naive application of the algorithm in 2-population problems leads to severe disengagement. We find that disengagement can be eliminated (for all tasks involving real-valued continuous scores) by determining \´victories\´ and \´defeats\´ between fellow members of the same species, using competitions against a single member of the opposing species as a point of comparison. We apply our algorithm to the "box-grabbing" problem for artificial 3D creatures introduced by Sims. We compare our algorithm with Sims\´ original Last Elite Opponent algorithm, and describe (and explain) different results obtained with two different implementations differing mainly by the harshness of their selection regimes.