5 Experiments

In order to demonstrate how complexification enhances performance, we ran thirty-three 500-generation runs of coevolution in the robot duel domain. Thirteen of these runs were based on the full NEAT method. Complexification was turned off in the remaining 20 runs (although networks were still speciated based on weight differences), in order to see how complexification contributes evolving sophisticated strategies. The competitive coevolution setup is described first, followed by an overview of the dominance tournament method for monitoring progress.

5.1 Competitive Coevolution Setup

The robot duel domain supports highly sophisticated strategies. Thus, the question in such a domain is whether continual coevolution will take place, i.e. whether increasingly sophisticated strategies will appear over the course of evolution. The experiment has to be set up carefully for this process to emerge, and to be able to identify it when it does.

In competitive coevolution, every network should play a sufficient number of games to establish a good measure of fitness. To encourage interesting and sophisticated strategies, networks should play a diverse and high quality sample of possible opponents. One way to accomplish this goal is to evolve two separate populations. In each generation, each population is evaluated against an intelligently chosen sample of networks from the other population. The population currently being evaluated is called the host population, and the population from which opponents are chosen is called the parasite population . The parasites are chosen for their quality and diversity, making host/parasite evolution more efficient and more reliable than one based on random or round robin tournament.

In the experiment, a single fitness evaluation included two competitions, one for the east and one for the west starting position. That way, networks needed to implement general strategies for winning, independent of their starting positions. Host networks received a single fitness point for each win, and no points for losing. If a competition lasted 750 time steps with no winner, the host received zero points.

In selecting the parasites for fitness evaluation, good use can be made of the speciation and fitness sharing that already occur in NEAT. Each host was evaluated against the four highest species' champions. They are good opponents because they are the best of the best species, and they are guaranteed to be diverse because their distance must exceed the threshold $\delta_t$ (section 3). Another eight opponents were chosen randomly from a Hall of Fame composed of all generation champions . The Hall of Fame ensures that existing abilities need to be maintained to obtain a high fitness. Each network was evaluated in 24 games (i.e. 12 opponents, 2 games each), which was found to be effective experimentally. Together speciation, fitness sharing, and Hall of Fame comprise an effective competitive coevolution methodology.

It should be noted that complexification does not depend on the particular coevolution methodology. For example Pareto coevolution could have been used as well, and the advantages of complexification would be the same. However, Pareto coevolution requires every member of one population to play every member of the other, and the running time in this domain would have been prohibitively long.

In order to interpret experimental results, a method is needed for analyzing progress in competitive coevolution. The next section describes such a method.

could have been used as well, and the advantages of complexification would be the same. However, Pareto coevolution requires every member of one population to play every member of the other, and the running time in this domain would have been prohibitively long.

In order to interpret experimental results, a method is needed for analyzing progress in competitive coevolution. The next section describes such a method.

5.2 Monitoring Progress in Competitive Coevolution

A competitive coevolution run returns a record of every generation champion from both populations. The question is, how can a sequence of increasingly sophisticated strategies be identified in this data, if one exists? This section describes the dominance tournament method for monitoring progress in competitive coevolution that allows us to do that.

First we need a method for performing individual comparisons, i.e. whether one strategy is better than another. Because the board configurations can vary between games, champion networks were compared on 144 different food configurations from each side of the board, giving 288 total games for each comparison. The food configurations included the same 9 symmetrical food positions used during training, plus an additional 2 food items, which were placed in one of 12 different positions on the east and west halves of the board. Some starting food positions give an initial advantage to one robot or another, depending on how close they are to the robots' starting positions. Thus, the one who wins the majority of the 288 total games has demonstrated its superiority in many different scenarios, including those beginning with a disadvantage. We say that network $a$ is superior to network $b$ if $a$ wins more games than $b$ out of the 288 total games.

Given this definition of superiority, progress can be tracked. The obvious way to do it is to compare each network to others throughout evolution, finding out whether later strategies can beat more opponents than earlier strategies. For example, used a measure called master tournament, in which the champion of each generation is compared to all other generation champions. Unfortunately, such methods are impractical in a time-intensive domain such as the robot duel competition. Moreover, the master tournament only counts how many strategies can be defeated by each generation champion, without identifying which ones. Thus, it can fail to detect cases where strategies that defeat fewer previous champions are actually superior in a direct comparison. For example, if strategy $A$ defeats 499 out of 500 opponents, and $B$ defeats 498, the master tournament will designate $A$ as superior to $B$ even if $B$ defeats $A$ in a direct comparison. In order to decisively track strategic innovation, we need to identify dominant strategies, i.e. those that defeat all previous dominant strategies. This way, we can make sure that evolution proceeds by developing a progression of strictly more powerful strategies, instead of e.g. switching between alternative ones.

The dominance tournament method of tracking progress in competitive coevolution meets this goal . Let a generation champion be the winner of a 288 game comparison between the host and parasite champions of a single generation. Let $d_j$ be the $j$th dominant strategy to appear over evolution. Dominance is defined recursively starting from the first generation and progressing to the last:

• The first dominant strategy $d_1$ is the generation champion of the first generation;
• dominant strategy $d_j$, where $j>1$, is a generation champion such that for all $i<j$, $d_j$ is superior to $d_i$ (i.e. wins the 288 game comparison with it).

This strict definition of dominance prohibits circularities. For example, $d_4$ must be superior to strategies $d_1$ through $d_3$, $d_3$ superior to both $d_1$ and $d_2$, and $d_2$ superior to $d_1$. We call $d_n$ the $n$th dominant strategy of the run. If a network $c$ exists that, for example, defeats $d_4$ but loses to $d_3$, making the superiority circular, it would not satisfy the second condition and would not be entered into the dominance hierarchy.

The entire process of deriving a dominance hierarchy from a population is a dominance tournament, where competitors play all previous dominant strategies until they either lose a 288 game comparison, or win every comparison to previous dominant strategies, thereby becoming a new dominant strategy. Dominance tournament allows us to identify a sequence of increasingly more sophisticated strategies. It also requires significantly fewer comparisons than the master tournament .

Armed with the appropriate coevolution methodology and a measure of success, we can now ask the question: Does the complexification result in more successful competitive coevolution?