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.
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 (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.
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 is superior to network
if
wins more games than
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 defeats 499 out of 500 opponents, and
defeats 498, the master tournament will designate
as superior to
even if
defeats
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 be the
th dominant strategy to appear over evolution.
Dominance is defined recursively starting from the first
generation and progressing to the last:
This strict definition of dominance prohibits circularities.
For example,
must be superior to strategies
through
,
superior to both
and
, and
superior to
.
We call
the
th dominant strategy of the run.
If a network
exists that, for example,
defeats
but loses to
, 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?