\documentclass[jair,11pt]{article}
\usepackage{jair}

%\usepackage{theapa}
%\usepackage[sort&compress]{natbib}
\usepackage[sort&compress,longnamesfirst]{natbib} 

\citestyle{nntrueapa}

%\usepackage{nnonecolumn}      % Research paper defaults, single column
%%\usepackage{nntwocolumn}        % Research paper defaults, double column
%\usepackage{times}              % Selects the Times Roman font
%\usepackage{fancyhdr}           % Support for to-appear macros
%%\usepackage{natbib}             % Bibliography and citation package
%\usepackage[sort&compress]{natbib}

\usepackage{amssymb,amsmath}
 
%\newcommand{\hyperrefoptions}{pdftex,%
%linkbordercolor={0 0 0},%
%citebordercolor={0 0 0},%
%urlbordercolor={0 0 0},%
%}

%\PassOptionsToPackage{draft}{hyperref} 
%\PassOptionsToPackage{linkcolor=white}{hyperref} 
%\PassOptionsToPackage{linkcolor=white}{hyperref}

\input{nnmacros}

%\hypersetup{backref,  
%pdfpagemode=FullScreen,  
%colorlinks=false} 

%-- Number of words: 10705 (1882 unique)

%% You can override the style definitions here if you need to squeeze
%% more text in within page limits, or you prefer wider margins, etc.
%\setlength{\textheight}{9in}
%\setlength{\topmargin}{0in}
%\setlength{\textwidth}{3.5in}
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\evensidemargin}{0.0in} % only used in twoside style

%\usepackage[sort&compress]{natbib}

%\scribbledraft

%\jairheading{1}{1993}{1-15}{6/91}{9/91}
\jairheading{21}{2004}{63-100}{8/03}{2/04}
\ShortHeadings{Competitive Coevolution through Evolutionary Complexification}
{Stanley \& Miikkulainen}
\firstpageno{63}

\begin{document}


\title{Competitive Coevolution through Evolutionary Complexification}


\author{\name Kenneth O. Stanley \email kstanley@cs.utexas.edu \\
       \name Risto Miikkulainen \email risto@cs.utexas.edu \\
       \addr Department of Computer Sciences\\
       The University of Texas at Austin\\
       Austin, TX 78712 ~USA
%       \AND
%       \name Mark D. Johnston \email johnston@stsci.edu \\
%       \addr Space Telescope Science Institute,
%       3700 San Martin Drive,\\
%       Baltimore, MD 21218 USA
%       \AND
%       \name Philip Laird \email laird@ptolemy.arc.nasa.gov \\
%       \addr NASA Ames Research Center,
%       AI Research Branch, Mail Stop: 269-2,\\
%       Moffett Field, CA  94035 USA}
}

%\author{{\bf Kenneth O. Stanley and Risto Miikkulainen}\\
%        Department of Computer Sciences\\
%        The University of Texas at Austin\\
%        Austin, TX 78712 ~USA\\
%        \{kstanley, risto\}@cs.utexas.edu\\
%Draft 
%        \\
%        Technical Report TR-AI-???\\
%Technical Report UT-AI-TR-02-298\\
%       }

%\date{December, 2002}

\maketitle

%   \thispagestyle{fancy}
%   \chead{\vspace{0.05in} \large \em Draft --- do not distribute}
%   \cfoot{}

%\thispagestyle{fancy}
%\headrulewidth 0pt
%\lfoot{\vspace{0.1in}
%{\em Draft --- do not distribute}}
%\cfoot{}

\begin{abstract}

Two major goals in machine learning are 
the discovery and improvement of solutions 
to complex problems.
%Risto 03
%of complex multidimensional
%solutions and continual improvement of existing
%solutions.  
In this paper, we argue that \emph{complexification}, 
i.e.\ the incremental elaboration of solutions through adding new structure, 
achieves both these goals.   We demonstrate the power of 
complexification through the NeuroEvolution of Augmenting
Topologies (NEAT) method, which evolves increasingly complex neural network
architectures.  NEAT is applied to an open-ended coevolutionary
robot duel domain where robot controllers compete head to head.
Because the robot duel domain supports a wide range of 
%sophisticated 
strategies, and because coevolution benefits from an escalating arms race,
it serves as a suitable testbed for 
studying complexification.
%observing the
%effect of evolving increasingly complex controllers.
%The result is an arms race of increasingly sophisticated strategies.
%The result is that an arms race takes place in which
%increasingly sophisticated strategies continually arise.
When compared to the evolution of networks with fixed structure,
complexifying 
evolution
%networks 
discovers significantly more sophisticated strategies.
The results suggest that 
%in order to realize the
%Added 03 - changed
in order to 
%Risto 03
%reliably 
discover and improve complex solutions, evolution,
and search in general, should be allowed to complexify as
well as optimize.
%full potential of evolution, and search in general, solutions must be 
%allowed to complexify as well as optimize.

\end{abstract}

\section{Introduction}
%\section{INTRODUCTION}

Evolutionary Computation (EC) is a class of algorithms
that can be applied to open-ended learning problems in Artificial
Intelligence. Traditionally, such algorithms evolve fixed-length genomes
under the assumption that the space of the genome is sufficient 
to encode the solution.  A genome containing $n$ genes
encodes a single point in an $n$-dimensional search space.  
In many cases, a solution is known to exist somewhere in that space.
For example, the global maximum of a function of three arguments
\emph{must} exist in the three dimensional space defined by those
arguments.  Thus, a genome of three genes can encode the
location of the maximum.

However, many common structures are defined by an 
indefinite number of parameters.  In particular, those 
solution types that can contain a variable number of parts 
can be represented by any number of
parameters above some minimum.  For example, the number of parts in 
neural networks, cellular automata, and electronic
circuits can vary \cite{stanley:ec02,mitchell:evca96,miller:jgpem00_1}.
In fact, theoretically two neural networks with different numbers of 
connections and nodes can represent the same function \cite{cybenko:mcss89}.  
Thus, it is not clear what number of
genes is appropriate for solving a particular problem.  
Researchers evolving fixed-length genotypes must use heuristics 
to estimate \emph{a priori} the appropriate number of genes 
to encode such structures.
% risto: I think this para ends more strongly if we don't talk about
% small networks: such a heuristic contradicts the idea that there is
% an appropriate topology for a problem and we need to find it.

A major obstacle to using fixed-length encodings is that
heuristically determining the appropriate number of genes
becomes impossible for very complex problems.  For example,
how many nodes and connections are necessary for a neural network that
controls a ping-pong playing robot?  Or, how many bits are needed
in the neighborhood function of a cellular automaton that performs 
information compression?  The answers to these questions can hardly be
based on empirical experience or analytic methods, since little is known
about the solutions.  One possible approach is to simply make the
genome extremely large, so that the space it encodes is extremely
large and a solution is likely to lie somewhere within.  Yet
the larger the genome, the higher dimensional the space that
evolution needs to search.  Even if a ping-pong playing robot lies
somewhere in the 10,000 dimensional space of a 10,000 gene genome, 
searching such a space may take prohibitively long.

Even more problematic are open-ended problems where phenotypes are meant
to improve indefinitely and there is no known final solution.
For example, in competitive games,
estimating the complexity of the ``best'' possible player is difficult
because such an estimate implicitly assumes that no better
player can exist, which we cannot always know.  
Moreover, many artificial
life domains are aimed at evolving increasingly complex artificial
creatures for as long as possible \cite{maley:gecco99}.
Such continual evolution is difficult with a fixed
genome for two reasons: 
(1) When a good strategy is found in a fixed-length genome, the entire
representational space of the genome is used to encode it.
Thus, the only way to improve it is to \emph{alter} the
strategy, thereby sacrificing some of the functionality
learned over previous generations.    
(2) Fixing the size of the genome in
such domains arbitrarily fixes the maximum complexity of evolved 
creatures, defeating the purpose of the experiment.

In this paper, we argue that
structured phenotypes can be evolved effectively by starting evolution with a
population of small, simple genomes and systematically elaborating on them
over generations by adding new genes.
%Added 03-2
Each new gene expands the search space, adding a new dimension that
previously did not exist.
That way, evolution begins
searching in a small easily-optimized space, and adds new dimensions
as necessary.  This approach is more likely to discover highly
complex phenotypes than an approach that begins searching directly
in the intractably large space of complete solutions.  In fact,
natural evolution utilizes this strategy, occasionally
adding new genes that lead to increased phenotypic 
complexity \nocite{martin:an99} (Martin 1999; Section \ref{sec:background}).  
In biology, this process 
%Added 03-2
of incremental elaboration
is called \emph{complexification}, which is why
we use this term to describe our approach as well.

In evolutionary computation, complexification refers to
expanding the dimensionality of the search space
while preserving the values of the majority of dimensions.
In other words, complexification
\emph{elaborates} on the existing strategy by adding new structure
without changing the existing representation.  
Thus the strategy does not only become different, but 
the number of possible
responses to situations it can generate increases (Figure \ref{fg:elab}).

\begin{figure}
  \centering
%\vspace{-0.5in}
\pspic[\psline]{400pt}{!}{alter_elab2}        
%\vspace{-3.5in}
  \titledcaption[\psline]{fg:elab}
  {Alteration vs. elaboration example}
  {
The dark robot must evolve to avoid the lighter robot,
which attempts to cause a collision.    
In the alteration scenario (top), the dark robot first evolves
a strategy to go around the left side of the opponent.  However,
the strategy fails in a future generation when the opponent
begins moving to the left.  Thus, the dark robot alters its strategy
by evolving the tendency to move right instead of left.
However, when the light robot later moves right, the new, altered,
strategy fails because the dark robot did not retain its old ability to
move left.  In the elaboration scenario (bottom), the original
strategy of moving left also fails.  However, instead of altering 
the strategy, it is \emph{elaborated} by adding a new ability to
move right as well.  Thus, when the opponent
later moves right, the dark robot still has the ability to avoid it by
using its original strategy.  Elaboration is necessary for a
coevolutionary arms race to emerge and it can be achieved through
complexification.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

In the EC domain of neuroevolution 
(i.e.\ evolving neural networks), complexification means adding nodes
and connections to already-functioning neural networks.
This is the main idea behind NEAT (NeuroEvolution of
Augmenting Topologies; Stanley and Miikkulainen
2002b,c,d),\nocite{stanley:ec02} the method described in this paper.
NEAT begins by evolving networks without any hidden nodes.
Over many generations, new hidden nodes and connections
are added, complexifying the space of potential solutions.
In this way, more complex strategies elaborate on
simpler strategies, focusing search on solutions
that are likely to maintain existing capabilities.

Expanding the length of the size of the genome has been
found effective in previous work
\cite{cliff:adaptbehav93,koza:ijcai95,harvey:phd93,lindgren:snaf01}.
NEAT advances this idea by making it possible to 
search a wide range of increasingly complex
network topologies simultaneously.
This process is based on three technical components:
(1) Keeping track of which genes match up with which
among differently sized genomes throughout evolution;
(2) speciating the population so that solutions
of differing complexity can exist independently; and
(3) starting evolution with a uniform population of small networks.
These components work together in complexifying solutions
as part of the evolutionary process.  
%[Because it can speciate the population based on topological
%and historical similarity, NEAT is the first complexifying
%system capable of maintaining search in several distinct and 
%simultaneously complexifying spaces.] %Insert?
% risto: I don't think we need it; we don't need to explain the NEAT
% method in detail in the intro , and the ``advances this idea''
% already makes the point at the level appropriate for the intro.
In prior work, NEAT
has been shown to solve challenging reinforcement
learning problems more efficiently than other neuroevolution
methods (Stanley and Miikkulainen 2002b,c,d).  The focus of these studies was on optimizing a given fitness function
through complexifying evolution.

In this paper, we focus on open-ended problems that have no explicit
fitness function; instead, fitness depends on comparisons with other
agents that are also evolving.  The goal is to discover creative
solutions beyond a designer's ability to define a fitness function.  It is
difficult to continually improve solutions in such
\emph{coevolutionary} domains because evolution tends to oscillate
between idiosyncratic yet uninteresting solutions
\cite{floreano:ec97}.  Complexification encourages continuing
innovation by elaborating on existing solutions.

In order to demonstrate the power of complexification in coevolution,
NEAT is applied to the competitive robot control domain of \emph{Robot
  Duel}.  There is no known optimal strategy in the domain but there
is substantial room to come up with increasingly sophisticated
strategies.  The main results were that (1) evolution did complexify
when possible, (2) complexification led to elaboration, and (3)
significantly more sophisticated and successful strategies were
evolved with complexification than without it.  These results imply
that complexification allows establishing a coevolutionary arms race
that achieves a significantly higher level of sophistication than is
otherwise possible.

We begin by reviewing biological support for complexification,
as well as past work in coevolution, followed by a description
of the NEAT method, and experimental results.

\section{Background} \label{sec:background}

%Risto read
The natural process of
complexification has led to 
important biological innovations. 
Its most natural application in EC
is in competitive coevolution, as will be
reviewed below.

\subsection{Complexification in Nature} \label{sec:nature}

Mutation in nature not only results in optimizing existing structures:
New genes are occasionally
added to the genome, allowing evolution to perform a complexifying
function over and above optimization.
In addition, complexification is protected in nature
in that interspecies mating is prohibited.  Such speciation creates
important dynamics differing from standard GAs.  In this section,
we discuss these characteristics of natural evolution
as a basis for our approach to utilizing them computationally in 
genetic algorithms.

\emph{Gene duplication} is a special kind of mutation in which one or more
parental genes are copied into an offspring's genome more than once.
The offspring then has redundant genes expressing the same
proteins.
Gene duplication has been responsible for key innovations in
overall body morphology over the course of natural evolution
\cite{amores:science98,carroll:nature95,force:genetics99,martin:an99}.

A major gene duplication event occurred around the time that
vertebrates separated from invertebrates.  The evidence for this
duplication centers around \emph{HOX genes}, which determine
the fate of cells along the anterior-posterior axis of embryos.
%Added 03 - ``developmental'' -> ``development''
HOX genes are crucial in shaping the overall pattern of development
in embryos.  In fact, differences in HOX gene regulation explain
a great deal of 
the diversity among
arthropods and tetrapods \cite{carroll:nature95}.
%a great deal of arthropod and tetrapod diversity
%%results from regulatory differences in such genes
%%\cite{carroll:nature95}.     
%Done: cite correctly Holland et al. 1994; Sidow 1996; Nadeau and
%Sankoff 1997; Spring 1997; Postlethwait et al. 1998
%from martin paper. 
%\emcite{amores:science98} 
%Many researchers have noted that 
%explain that 
%Risto read
Invertebrates have a single
HOX cluster while vertebrates have four,
suggesting that
cluster duplication significantly contributed to elaborations in
vertebrate body-plans \cite{amores:science98,holland:ds94,sidow:cogd96,nadeau:genetics97,postlethwait:ng98}.
The additional HOX genes took on new roles
in regulating how vertebrate anterior-posterior axis develops,
considerably increasing body-plan complexity.
Although \emcite{martin:an99} argues that the additional clusters
can be explained by many single gene duplications
accumulating over generations, as opposed to massive whole-genome
duplications, researchers agree that gene duplication in some form contributed 
significantly to body-plan elaboration.

A detailed account of how duplicate genes can take on novel roles
was given by \emcite{force:genetics99}: Base pair mutations
in the generations following duplication
\emph{partition} the initially redundant regulatory roles of genes
into separate classes.  Thus, the embryo develops in the same way,
but the genes that determine the overall body-plan
are confined to more specific roles, since there
are more of them.
The partitioning phase completes when redundant clusters of genes are
separated enough so that they no longer produce identical proteins
at the same time.
%Once this partitioning phase
%%separates duplicate genes enough that they no longer
%%% the same steps in development,
%%% %sufficiently separates
%%% %the regulatory roles of duplicated clusters,                              
After partitioning, mutations within the duplicated cluster of genes
affect different steps in development than mutations
within the original cluster.  In other words, 
%the opportunities for
%mutation increase through duplication because
duplication creates more
points at which mutations can occur.
In this manner, developmental processes complexify.

%Added 03
Gene duplication is a possible explanation how natural evolution indeed expanded 
the size of genomes throughout evolution, and provides inspiration
for adding new genes to artificial genomes as well.  
In fact, gene duplication motivated \emcite{koza:ijcai95} to allow
entire functions in genetic programs to be duplicated through
a single mutation, and later differentiated through further 
mutations.  
When evolving neural networks, this process means adding
%For the purposes of evolving increasingly complex
%neural networks, rather than duplicating functions or 
%segments of genes, we wish to add 
new neurons and connections
to the networks.

In order to implement this idea in
artificial evolutionary systems, we are faced with
two major challenges.  First, such systems evolve differently sized
and
shaped network topologies, which can be difficult to cross over
without 
losing information.
For example, depending on when new structure was added,
%in the ancestral histories of two different genomes, 
the same
gene may exist at different positions, or conversely, different genes
may exist at the same position.  Thus, artificial crossover may 
%lose essential
%network structure 
disrupt evolved topologies    
through misalignment.
Second, with variable-length genomes, it may be difficult to
find innovative solutions. Optimizing many genes takes longer than
optimizing only a few, meaning that more complex networks
may be eliminated from the population before they have a sufficient
opportunity to be optimized.

%The system we will describe in section \ref{sec:neat} addresses
%both challenges through analogy with biology's own solutions.  
%This section concludes with an explanation of
%how biological systems manage the evolution of variable-length
%genomes.

However, biological evolution also operates on variable-length
genomes, and these problems did not stop complexification in nature.      
How are these problems avoided in biological evolution?
First, nature has a mechanism
for aligning genes with their counterparts during crossover,
so that data is not lost nor obscured.
This alignment process has been
most clearly observed in \emph{E. coli} \cite{sigal:jmb72,radding:arg82}.
A special protein called \emph{RecA} takes a
single strand of DNA and aligns it with another strand
at genes that express the same traits, which
%Added 03- footnote
are called \emph{homologous genes}.
%DONE: alter response to explain lack of linkage learning discussion
%\footnote{Gene linkage learning,
%or the reordering of genomes where genes in the same building block
%are grouped together, is concerned with a similar concept to
%gene homology; it is important in linkage learning that when
%crossover occurs genes being added to a genome represent 
%alleles of the same genes as they are replacing \cite{harik:foga96}.}   
%The second strand is still attached to its original complementary
%strand,      %which is displaced by the newly annealed strand.  For a
%brief                  %time there is a ternary complex of 3 strands
%before the old                    %complementary strand is displaced.  
This process is called \emph{synapsis}.
%In experiments in vitro, researchers have found that
%RecA protein does not complete the process of synapsis
%on fragments of DNA that are not homologous \cite{radding:arg82}.

Second, innovations in nature are protected through speciation.
Organisms with significantly divergent genomes never mate
because they are in different species.
%Added 03- trying to make clearer
If any organism could mate with any other, organisms with
initially larger, less-fit genomes would be forced to compete
for mates with their simpler, more fit counterparts.
As a result, the larger, more innovative genomes would  
fail to produce offspring and disappear from the population.  
In contrast, in a speciated population, organisms with larger 
genomes compete for mates among their
own species, instead of with the population at large.  
That way, organisms that may initially have lower fitness than
the general population still have a chance to reproduce, giving 
novel concepts a chance to realize their potential without
being prematurely eliminated.
%Added 03
Because speciation benefits the evolution of diverse populations,
a variety of speciation methods have been employed in EC
\cite{goldberg:icga87,mahfoud:phd95,ryan:agp94}.
%Speciation also protects
%innovation, because it allows organisms to compete primarily within
%their own niches, instead of with the population at large.

It turns out complexification is
also possible in evolutionary
computation if abstractions of synapsis and speciation are made
part of the genetic algorithm.  The NEAT method (section
\ref{sec:neat}) is an implementation of this idea:
The genome is complexified by adding new genes
which in turn encode new
structure in the phenotype, as in biological evolution.  

Complexification is especially powerful in open-ended domains
where the goal is to continually generate more sophisticated
strategies.  Competitive coevolution is a particularly important
such domain, as will be reviewed in the next section.

\subsection{Competitive Coevolution}

%In order to demonstrate complexification, a domain is needed
%that is not easily framed as an optimization problem.
%The problem must encompass more than finding a local
%or global optimum in a fixed finite-dimensional space,
%because such a problem can be solved through 
%a suitably enumerated set of known parameters.
%The point of complexification is that it is not only 
%the \emph{location} of an optimum in space that must 
%be discovered, but also \emph{what the dimensions are}
%that describe that space.  Thus we seek a domain of
%unknown or unbounded dimensionality.  Competitive
%coevolution can fill this role.

In competitive coevolution, individual fitness is evaluated 
through competition with other individuals in the
population, rather than through an absolute fitness measure.
In other words, fitness signifies only the relative strengths
of solutions;
%two or more populations of indiv
%iduals
%evolve simultaneously in an environment
%where an increased
an increased fitness in one solution leads to a decreased 
fitness for another.  
Ideally, competing solutions
will continually outdo one another, leading to an
"arms race" of increasingly better 
solutions \cite{dawkins:prsl79,rosin:phd,vanvalin:et73}.  
%Added 03
Competitive coevolution has traditionally 
been used in two kinds of problems.
First, it can be used to
evolve interactive behaviors that 
are difficult to evolve in terms of an absolute fitness function.
For example, \emcite{sims:alife4}
evolved simulated 3D creatures that attempted to capture a ball     
before an opponent did, resulting in 
a variety of effective interactive strategies.   Second, coevolution can be used to
gain insight into the dynamics of game-theoretic problems.
%study interesting game-theoretic scenarios.  
For example,
\emcite{lindgren:snaf01} coevolved iterated Prisoner's Dilemma strategies
in order to 
demonstrate how they correspond to stages in natural evolution. 

Whatever the goal of 
a competitive coevolution experiment, interesting strategies will
only evolve if the arms race continues for a significant number of generations.
In practice, it is difficult to establish such an arms race.
Evolution tends to find the simplest solutions
that can win, meaning that strategies can switch back and forth
between different idiosyncratic yet uninteresting variations
\cite{floreano:ec97,darwen:phd96,rosin:ec97}.
%In response to the problem of strategic oscillation 
%in competitive coevolution, 
Several methods have been developed 
to encourage the arms race \cite{rosin:ec97,angeline:icga93,ficici:ecal01,noble:gecco01}.  
For example, a "hall of fame" or a collection
of past good strategies can be used
to ensure that current strategies remain competitive against
earlier strategies.
Recently, Ficici and Pollack (2001) and Noble and Watson (2001)
\nocite{ficici:ecal01,noble:gecco01} introduced a
promising method called \emph{Pareto coevolution}, which 
finds the best learners and the best teachers in two
populations by casting coevolution as a multiobjective optimization
problem.  This information enables choosing the best 
individuals to reproduce, as well as maintaining an 
informative and diverse set of opponents.  

Although such techniques allow sustaining the
arms race longer, they do not
directly encourage \emph{continual coevolution}, i.e.\ creating
new solutions that maintain existing capabilities.  
For example, no matter how well selection is performed, or
how well competitors are chosen, 
if the search space is fixed, a limit will
eventually be reached.
%Added 03 - simplified sentence
Also, it
may occasionally be easier to escape a local optimum by adding a new
dimension to the search space than 
by searching for a new path through
the original space.
%by
%jumping back out into the same space that led
%to the optimum in the first place.
%Muchtime is wasted evaluating solutions that are deficient in
%this way.
%or support elaboration on strategies
%that have already been discovered.  
%the fundamental problem of eventual stagnation.

%lindgren:snaf01, sims:alife4, code wars ref???

For these reasons,
complexification is a natural technique for establishing
a coevolutionary arms race.
Complexification elaborates
strategies by adding new dimensions to the search space.
Thus, progress can be made indefinitely long:
Even if a global optimum is
reached in the search space of solutions, new dimensions can be
added, opening up a higher-dimensional space 
where even better optima may exist.

%Therefore, competitive coevolution is an appropriate
%domain for testing the performance of complexification.
%Of course, a suitable competitive coevolution domain
%with potential for strategic sophistication is necessary.
%For this reason, 
To test this idea experimentally, we chose a robot duel domain that
combines predator/prey interaction and food foraging 
in a novel head-to-head competition (Section \ref{sec:duel}).
We use this domain to demonstrate how NEAT uses
complexification to continually elaborate solutions.
The next section reviews the NEAT neuroevolution method, followed by
%\footnote{A more comprehensive description of the NEAT
%method is given by \emcite{stanley:gecco02_1,stanley:utcstr01}.}
a description of the robot duel domain and a discussion
of the results.

\section{NeuroEvolution of Augmenting Topologies (NEAT)} \label{sec:neat}
%\section{NEUROEVOLUTION OF AUGMENTING TOPOLOGIES (NEAT)} \label{sec:neat}
%%NIPS EDIT
%NEAT is a method based on the above three solutions.
%We begin by explaining the genetic encoding used in NEAT,
%and continue by describing the components that specifically
%address each issue.

%NEAT uses a direct encoding scheme, meaning that every
%connection and node is represented directly in the
%genome.  \emcite{braun:annga93} comment that
%indirect encoding requires ``more detailed knowledge of genetic and
%neural mechanisms.''  In other words, because indirect encodings
%do not directly map to their phenotypes, they implicitly restrict
%the search to the class of topologies to which they can be expanded.
%At this early stage in TWEANN research, since we dot not
%have a formal specification of the class of topologies
%that are necessary for a fruitful search, indirect encoding is
%not the best choice at this time.

%\vspace{-0.05in}

The NEAT method of evolving artificial neural networks
combines the usual search for appropriate network weights with
complexification of the network structure.
%leverages the evolution of structure
%to increase efficiency.  
This approach is highly effective, as shown e.g.\ in comparison
to other neuroevolution (NE) methods in the double pole 
balancing benchmark task \cite{stanley:ec02,stanley:cec02nopress,stanley:gecco02_1}. 
% NEAT outperforms
%other neuroevolution (NE) methods, e.g.\ on the benchmark 
%double pole balancing task by a
%factor of five \cite{stanley:ec02,stanley:cec02nopress,stanley:gecco02_1}.
The NEAT method consists of solutions to three fundamental challenges
in evolving neural network topology:
(1) What kind of genetic representation would allow
disparate topologies to crossover in a meaningful way?
 %\cite{radcliffe:nca93,whitley:gaecs95}?
Our solution is to use historical markings to line
up genes with the same origin.
(2) How can topological innovation that needs a few generations to
optimize be protected so that it does not disappear from the
population
prematurely?
Our solution is to separate each innovation into
a different species.
(3) How can topologies be minimized \emph{throughout evolution}
so the most efficient solutions will be discovered?
%Added 03 - changed 
Our solution is to start from a minimal structure and 
add nodes and connections incrementally.
%grow
%only when necessary.
In this section, we explain how each of these solutions is 
implemented in NEAT.

\subsection{Genetic Encoding}
%\subsection{GENETIC ENCODING}

\begin{figure}
  \centering
%  \pspic[\psline]{\oneplotwidth}{!}{genome-fig}
\pspic[\psline]{450pt}{!}{genome-fig_redone2-bwv2}        
  \titledcaption[\psline]{fg:genome}
  {A NEAT genotype to phenotype mapping example}
  {
   A genotype is depicted that produces the shown phenotype.
There are 3 input nodes, one hidden, and one output node,
and seven connection definitions, one of which is recurrent.
The second gene is disabled, so the connection 
that it specifies (between nodes 2 and 4) is not expressed 
in the phenotype.  In order to allow complexification,
genome length is unbounded.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

%NIPS edit
%NEAT's genetic encoding scheme is designed to allow corresponding genes
%to be easily lined up when two genomes crossover during
%mating.  
%Genomes in NEAT are linear representations of network connectivity 
Evolving structure requires a flexible genetic encoding.
In order to allow structures to complexify, their representations
must be dynamic and expandable.
%NEAT is designed specifically to address the three challenges 
%raised in the introduction.
Each genome in NEAT includes a list of
\emph{connection genes}, each of which refers to two
\emph{node genes} being connected. 
(Figure \ref{fg:genome}).
Each connection gene specifies the in-node, the out-node, the
weight of the connection, whether or not the connection gene is
expressed (an enable bit), and an \emph{innovation number}, which 
allows finding corresponding genes during crossover.

\begin{figure}
  \centering
%  \pspic[\psline]{\oneplotwidth}{!}{structmutes-figure}
\pspic[\psline]{340pt}{!}{ij-structmutes-figure-bwv2}       
  \titledcaption[\psline]{fg:structmutes}
  {The two types of structural mutation in NEAT}
  {
   Both types, adding a connection and adding a node, are illustrated with the
   genes above their phenotypes.  
   The top number in each genome is the \emph{innovation number}
   of that gene.  The bottom two numbers denote the two nodes
   connected by that gene.  The weight of the connection, also
   encoded in the gene, is not shown.  The symbol \emph{DIS}
   means that the gene is disabled, and therefore not expressed
   in the network.  The figure shows how connection genes are appended
  to the genome
   when a new connection and a new
   node is added to the network.
   Assuming the depicted mutations occurred one after the other,
   the genes would be assigned increasing innovation numbers
   as the figure illustrates, thereby allowing NEAT to keep an implicit history
   of the origin of every gene in the population.    
   \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

Mutation in NEAT can change both connection weights and 
network structures.  
Connection weights mutate 
as in any NE system, with each connection
either perturbed or not.  Structural
mutations, 
which form the basis of complexification,
occur in two ways (Figure \ref{fg:structmutes}).
%NIPS edit
Each mutation expands the size of the genome
by adding gene(s).  
In the \emph{add connection} mutation, a single
new connection gene is added connecting two previously
unconnected nodes.  
In the \emph{add node} mutation, an existing connection
is split and
the new node placed where the old connection used to be.
The old connection is disabled and two new connections are
added to the genome.  
%This method of
%adding nodes was chosen in order to integrate new nodes
%immediately into the network.
%Added 03 
The connection between the first node in the chain and the new node
is given a weight of one, and the connection between the
new node and the last node in the chain is given the same weight
as the connection being split.  Splitting the connection
in this way introduces a nonlinearity (i.e.\ sigmoid function) 
where there was none before.
When initialized in this way, this nonlinearity changes the function
only slightly, and 
the new node is
immediately integrated 
into the network. 
%%Through mutation, genomes of varying
%%sizes are created, sometimes with 
%%completely different
%%connections specified at the same positions.  
%How can NE cross them
%changed ``in a sensible way'' to ``sensibly''
%over sensibly?  The next section explains how
%NEAT addresses this problem.
%Added 03
Old behaviors encoded in the preexisting network structure
are not destroyed and remain qualitatively
the same, while the new structure provides an opportunity
to elaborate on these original behaviors.

Through mutation, the genomes in NEAT will 
gradually get larger.  Genomes of varying
sizes will result, sometimes with 
different
connections at the same positions.  
%Added 03 - rephrased 
Crossover must be able to recombine networks
with differing topologies, which can be difficult \cite{radcliffe:nca93}.   
%A difficult problem for crossover,
%with numerous differing topologies and weight combinations,
%is an inevitable result of allowing genomes to grow unbounded.
The next section explains how
NEAT addresses this problem.

\subsection{Tracking Genes through Historical Markings}

%In order to perform crossover, the system must be able to tell
It turns out that the historical origin of each gene can be used to tell 
us exactly 
which genes match up 
between \emph{any} individuals in the population.
Two genes with the same historical origin
represent the same structure 
(although possibly with different weights), since they were both derived
from the same ancestral gene at some point in the past. 
Thus, all a system needs to do 
is to keep track of the historical origin of every gene in the system.

Tracking the historical origins requires very little computation.  
Whenever a new gene appears (through structural mutation),
a \emph{global innovation number} is incremented
and assigned to that gene.  
The innovation numbers thus represent a
chronology of every gene in the system.  As an example,
% \ref{fg:structmutes}.  
let us say the two mutations in Figure \ref{fg:structmutes} 
occurred one after another in the system.  
The new connection gene 
created in the first mutation is assigned the number $7$, and the 
two new connection genes added during the new node mutation are
assigned the numbers $8$ and $9$.  
In the future, whenever these genomes crossover,
the offspring will inherit the same innovation
numbers on each gene.
Thus, the historical
origin of every gene in the system is known throughout evolution.

A possible problem is that the same structural innovation
will receive different innovation numbers in the same 
generation if it occurs by chance more than once.
However, by keeping a list of the innovations that occurred 
in the current generation, it is possible to ensure that
when the same structure arises more than once through independent 
mutations in the same generation, each identical mutation is 
assigned the same innovation number.  
%Added 03
Through extensive experimentation,
we established
that resetting the list every generation as opposed to
keeping a growing list of mutations throughout evolution is sufficient
to prevent an explosion of innovation numbers.   
%Thus, there is no resultant 
%explosion of innovation numbers. 

\begin{figure}
  \centering
  \pspic[\psline]{330pt}{!}{matchup-fig-bwv2}
%\pspic[\psline]{!}{!}{ij-matchup-fig}      
  \titledcaption[\psline]{fg:matchup}
  {Matching up genomes for different network topologies using innovation numbers}
  {
    Although Parent 1 and Parent 2 look different, their innovation
    numbers (shown at the top of each gene) tell us that several of their genes match up 
    even without topological analysis.
%%NIPS edit
A new structure
    that combines the overlapping parts of the two parents as
    well as their different parts can be created in crossover.  In this case,
    equal fitnesses are assumed, so the disjoint and excess genes from
    both parents are inherited randomly.  
Otherwise they would be inherited from the more fit parent.
The disabled genes may
    become enabled again in future generations: There is a preset
    chance that an inherited gene is disabled if it is disabled in
    either parent.
%%End NIPS edit
%%The system can 
%%    actually tell which parts of each structure match up even 
%%    though it would not be obvious by just looking at the networks
%%    themselves (without the node numbers).  
%% Parent 2 has some more
% %   recent innovations, labeled ``excess'' in the diagram.  
%    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

Through innovation numbers,
the system now knows exactly which genes match up with which
(Figure \ref{fg:matchup}).  
Genes that do not match are either \emph{disjoint}
or \emph{excess},
depending on whether they occur within or outside the range
of the other parent's innovation numbers.
When crossing over, the genes
with the same innovation numbers are
lined up and are randomly chosen for the offspring genome.  
Genes that do not match are inherited
from the more fit parent,
or if they are equally fit, from both parents randomly. 
%Added 03 
%Thus, when fitnesses differ, all the disjoint and excess
%genes come from the more fit parent, and matching genes
%are selected randomly from either parent. 
Disabled genes have a 25\% chance of being reenabled during
crossover, allowing networks to make use of older genes 
once again.\footnote{See Appendix A for specific mating
parameters used in the experiments in this paper.}  
  
%or both parents, in the case
%of equivalent fitnesses. 

Historical markings allow NEAT to 
perform crossover without the need for expensive topological analysis.
Genomes of different organizations and sizes stay
compatible throughout evolution, and the problem of comparing
different topologies is essentially avoided. 
This methodology allows NEAT to complexify structure while
still maintaining genetic compatibility.
%s essential in order to complexify structure. 
However, it turns
out that a population of varying complexities cannot maintain
topological innovations on its own.
Because smaller structures optimize faster than larger structures, 
and adding nodes and connections usually initially decreases
the fitness of the network, recently
augmented structures have little hope of 
surviving more than one generation
even though the innovations
they represent might be crucial towards solving the task
in the long run.  The solution is to protect innovation
by speciating the population, as explained in the next section.

\subsection{Protecting Innovation through Speciation} \label{subsec:spec}
%\subsection{PROTECTING INNOVATION THROUGH SPECIATION} \label{subsec:spec}

NEAT speciates the population
%protecting innovative
%structures from immediate extinction.
%When the population is speciated, 
so that
individuals compete
primarily within their own niches instead of with the
population at large.  This way, topological innovations are protected 
%in a new
%niche where they 
and
have time to optimize their structure
before they have to compete with other niches in the population.
%Added 03
In addition, speciation prevents bloating of genomes: Species with smaller
genomes survive as long as their fitness is competitive,
ensuring that small networks are not replaced by larger ones unnecessarily.
%Original stuff;
Protecting innovation through speciation follows the 
philosophy that new ideas must be given time to reach their potential 
before they are eliminated.  
%through competition within the niche.  
%Mahfoud \cite{mahfoud:phd95} provides a comprehensive
%overview of speciation methods.  
%Speciation is commonly
%used in multimodal function optimization and in coevolution
%of modular systems, where its main
%function is to preserve diversity \cite{mahfoud:phd95,potter:collaborative}.
%We bring the idea to
%TWEANNs, where its main task is to protect innovation, thereby
%allowing complexification.  
%%In addition
%%to protecting innovation, it is possible to prevent 
%%extremely incompatible structures from mating with each other
%%by controlling the amount of interspecies mating.  
%%Thus,
%%for skeptics of crossover in TWEANNs \cite{angeline:ieeenn93},
%%we provide a compromise: Use historical markings to 
%%line up genomes precisely when they are compatible but
%%avoid crossover between genomes that are incompatible.

%NIPS EDIT
%%removed ``basic'' idea
%The idea is to divide the population
%into species such that similar
%topologies are in the same species.  This task appears
%to be a topology matching problem.  However, it
%turns out that historical markings offer a more efficient
%solution.
%%(figure \ref{fg:matchup}).  

%Using historical markings, the system can divide
%CEC: First line changed
Historical markings make it possible for the system to divide
the population into species based on topological similarity.
We can measure the distance $\delta$ 
between two network encodings as
a linear combination of the number of excess ($E$) and disjoint
($D$) genes, as well as the average weight differences of matching
genes ($\overline{W}$): 
%\vspace{-0.05in}
\begin{equation} \label{eqn:speciation}
\delta=\frac{c_1E}{N}+\frac{c_2D}{N}+c_3\cdot\overline{W}.
\end{equation}
%\vspace{-0.05in}
The coefficients $c_1$, $c_2$, and $c_3$
adjust the importance of the 
three factors, and the factor $N$, the
number of genes in the larger genome, 
normalizes for genome size ($N$ can be set to 1 if both genomes are
small).
%, i.e., consist of fewer than 20 genes).    
%The distance
%measure $\delta$ allows us to speciate using a compatibility
%threshold $\delta_t$.  
Genomes are 
tested one at a time; if a genome's distance to a randomly chosen
member of the species is less than $\delta_t$, 
a compatibility threshold, 
it is placed into this species.
%partitioned into
%species such that for every genome $g$ in a species,
%where $\delta$ is the distance between $g$ and a randomly chosen
%species representative $g_r$, $\delta<\delta_t$.  
Each genome
is placed into the first species from the \emph{previous generation}
where this condition is satisfied, 
so that no genome is in more than one species.  If a genome
is not compatible with any existing species, a new species is created.
The problem of choosing the best value for $\delta_t$ can be avoided
by making $\delta_t$ \emph{dynamic}; that is, given a target number of
species, the system can raise $\delta_t$ if there are too many
species, and lower $\delta_t$ if there are too few.
%\footnote{See Appendix \ref{sec:params} for 
%the speciation parameters used in the experiments.}
%NEAT EDIT
%An ordered list of species
%is maintained.  In each generation, genomes are sequentially
%placed into species.  Each existing species is represented by
%a random genome inside the species from the \emph{previous
%  generation}.
%A given genome $g$ in the current generation
%is placed in the first species in which $g$ is compatible with
%the representative genome of that species.  This way,
%species do not overlap.\footnote{It is also possible to
%determine the compatibility of a genome $g$ with a species
%$s$ by using the average compatibility of $g$ with every genome
%in a species $s$, but in practice only comparing to the first
%genome in $s$ is sufficient, and takes constant time.}
%If $g$ is not compatible with any existing species, a new species
%is created with $g$ as its representative.
%% such that organisms with $C<C_t$ are
%%partitioned into the same species.  Measuring $C$ for
%%a pair of genomes
%%is linear in the number of
%%connections even though $C$ precisely expresses compatibility
%%between multidimensional topologies.  This efficiency is
%%possible because of the historical markings.

%such that organisms with $\delta<\delta_t$ are
%partitioned into the same species.  Measuring $C$ for
%a pair of genomes
%is linear in the number of 
%connections even though $C$ precisely expresses compatibility
%between multidimensional topologies.  This efficiency is
%possible because of the historical markings.

%Holland \cite{holland:adaptation}, 
As the reproduction
mechanism for NEAT, we use 
\emph{explicit fitness sharing} \cite{goldberg:icga87}, 
where
organisms in the same species 
must share the fitness of their niche.
%preventing any one
%species from taking over the population \cite{stanley:ec02}.  
Thus, a species cannot
afford to become too big even if many of its organisms perform
well. Therefore, any one species is unlikely to take
over the entire population, which is crucial for
speciated evolution to maintain topological diversity.
The adjusted fitness $f'_i$
for organism $i$ is calculated according to its distance
$\delta$ from every other organism $j$ in the population:
\begin{equation} \label{eqn:spec-general}
f'_i=\frac{f_i}{\sum_{j=1}^{n}{\mathrm{sh}(\delta(i,j))}}.
\end{equation}

%Risto read
%In NEAT, as first proposed by \emcite{spears:hec95}, 
The sharing function $\mathrm{sh}$ is set to $0$ when distance 
$\delta(i,j)$ is above the threshold $\delta_t$; otherwise, 
$\mathrm{sh}(\delta(i,j))$ is set to 1 \cite{spears:hec95}. 
Thus, ${\sum_{j=1}^{n}{\mathrm{sh}(\delta(i,j))}}$ reduces to 
the number of organisms in the same species as organism $i$.  
This reduction is natural since species are already clustered by 
compatibility using the threshold $\delta_t$. Every species is 
assigned a potentially different number of offspring
in proportion to the sum of adjusted
fitnesses $f'_i$ of its member organisms.
Species reproduce by first eliminating 
the lowest performing
members from the population.  The entire population is then replaced
by the offspring of the remaining organisms in each 
species.

%NIPS EDIT
%Thus, a species cannot
%afford to become too big even if many of its organisms perform
%well. Therefore, any one species is unlikely to take
%over the entire population, which is crucial for
%speciated evolution to work.
%NIPS EDIT- another
%The adjusted fitness $f'_i$
%for organism $i$ is calculated according to its distance
%$\delta$ with every other organism $j$ in the population:
%\vspace{-0.05in}
%\begin{equation} \label{eqn:spec-general}
%f'_i=\frac{f_i}{\sum_{j=1}^{n}{\mathrm{sh}(\delta(i,j))}}.
%\end{equation}
%%\vspace{-0.05in}
%The sharing function $\mathrm{sh}$ is set to $0$ when distance $\delta(i,j)$ is
%above the threshold $\delta_t$;  
%otherwise, 
%%Spears \cite{spears:hec95},
%$\mathrm{sh}(\delta(i,j))$ is set to 1 \cite{spears:hec95}.  
%NIPS EDIT
%Thus, ${\sum_{j=1}^{n}{\mathrm{sh}(\delta(i,j))}}$ simply counts 
%the number
%of organisms 
%in the same species as organism $i$.  This reduction is natural
%since species are already clustered by compatibility using 
%the 
%threshold $\delta_t$.  
%Offspring are assigned to a species en masse, adding up the
%expected offspring of every individual in the species.  
%Every species is assigned a 
%potentially different number of offspring
%in proportion to the sum of after-sharing
%%fitnesses $f'_i$ of its member organisms.
%fitnesses of its member organisms.
%Species 
%reproduce by first eliminating 
%the lowest performing
%members from the population.  The entire population is then replaced
%by the offspring of the remaining organisms in each species.
%GECCO2002 EDIT
%\footnote{In rare cases when the fitness of the entire population
%does not improve for more than 20 generations,
%only the top two species are allowed to reproduce, refocusing
%the search into the most promising spaces.}

%NIPS EDIT
The net effect of speciating the population is that structural
innovation is protected.  The final goal
of the system, then, is to perform the search for a
solution as efficiently as possible.  This goal
is achieved through complexification from a simple
starting structure, as detailed in the next section.

\subsection{Minimizing Dimensionality through Complexification} 
%\subsection{MINIMIZING DIMENSIONALITY THROUGH COMPLEXIFICATION}
% Changed: Removed: through Incremental Growth from Minimal Structure}

Unlike other systems that evolve network topologies and
weights
\cite{angeline:ieeenn93,gruau:gp96,yao:ieee99,zhang:cplxsys93},
NEAT begins with a uniform population of simple networks with no hidden
nodes, 
%Added 03
differing only in their initial random weights.
Speciation protects new innovations, allowing topological
diversity to be gradually introduced over evolution.
Thus, because NEAT protects innovation using speciation,
it can start in this manner, minimally,
%%added CEC line:
%Added 03- changed 
and grow new structure over generations. 
%only as necessary.

New structure is introduced incrementally
as structural mutations occur, and only those structures
survive that are found to be useful through fitness evaluations.
This way, NEAT searches
through a minimal number of weight dimensions,
significantly reducing the number of generations
necessary to find a solution, and ensuring that 
networks become no more complex than necessary.
This gradual production of increasingly
complex structures constitutes \emph{complexification}.
%Added 03- changed
In other words, NEAT searches for the optimal
topology by incrementally complexifying existing structure.

%Risto read
In previous work, 
%\emcite{stanley:ec02,stanley:cec02}
%experimentally ablated
each of the three main components of NEAT
(i.e.\  historical
markings, speciation, and starting from minimal 
structure) were experimentally ablated in order to demonstrate how they
contribute to performance \cite{stanley:ec02,stanley:cec02nopress}.
The ablation study demonstrated that all three components are
interdependent and necessary to make NEAT work.   
In this paper, we further show how
%We argued in Section \ref{sec:background} that 
complexification
establishes the arms race in competitive coevolution.
The next section describes the experimental domain in which this
result will be demonstrated. 

%NIPS EDIT
%The system can use the protection of topological innovation through 
%speciation to improve its efficiency by starting with a population
%of minimal topologies.
%TWEANNs typically start with an initial population of
%%removed dasgupta:cogann92
%random topologies \cite{angeline:ieeenn93,gruau:gp96,yao:ieee99,zhang:cplxsys93}.  This way
%topological diversity is introduced
%to the population from the outset.  However, 
%it is not clear that such diversity is necessary or useful.
%A population of random topologies has 
%a great 
%deal of structure that has not withstood a single fitness
%evaluation.  Therefore, there is no way to know if any of
%such structure is \emph{necessary}.  
%It is costly though because
%the more connections a network contains, the higher the number of
%dimensions that need to be searched to optimize
%the network.
%Therefore, with random topologies the algorithm may
%waste a lot of effort by optimizing unnecessarily
%complex structures.
%
%In contrast,
%NEAT biases the search
%towards minimal-dimensional spaces by starting out
%with a \emph{uniform} population of 
%networks with zero hidden nodes (i.e.\ all
%inputs connect directly to outputs).  New structure is introduced
%incrementally as structural mutations occur,  
%and only those structures survive that are
%found to be useful through fitness evaluations.
%In other words, the structural elaborations that
%occur in NEAT are always justified.
%Since the population starts minimally,
%the dimensionality of the search space is minimized, and
%NEAT is always searching through fewer dimensions
%than other TWEANNs and fixed-topology NE systems.  Minimizing
%dimensionality gives NEAT a performance advantage compared
%to other approaches, as will be discussed next.  

%The reason that other TWEANNs can't afford to start minimally is that
%they do not protect innovation through speciation.  Thus, an initial
%uniform population will not be able to sustain diversity because
%innovations will be lost to lowered fitnesses as soon as they appear.
%Therefore these systems \emph{need} to start randomly in order to
%get diversity into the population.  NEAT can afford to start minimally
%because innovation in NEAT is protected.

\section{The Robot Duel Domain} \label{sec:duel}
%\section{THE ROBOT DUEL DOMAIN}

Our hypothesis is that the complexification 
process outlined above allows discovering more
sophisticated strategies, i.e.\ strategies that are more effective,
flexible, and general, and include more components and variations than
do strategies obtained through search in a fixed space.  To
demonstrate this effect, we need a domain
%Added 03 - note ``wide range'' does not imply infinite 
where it is possible to develop a wide range increasingly sophisticated strategies,
and where sophistication can be readily measured. A coevolution domain
is particularly appropriate because a sustained arms race should lead
to increasing sophistication.

In choosing the domain, it is difficult to strike a balance between
being able to evolve complex strategies and being able to analyze and
understand them. Pursuit and evasion tasks
%To demonstrate the effect of complexification, 
%a domain is needed where it is possible to develop
%increasingly sophisticated strategies and where the
%sophistication, i.e. the capability to defeat other strategies,
%can be readily measured.  
%Moreover, the domain must support coevolution, so that
%an arms race can potentially produce increasingly sophisticated
%strategies.
%A balance between the potential complexity of evolved strategies and
%their analyzability is difficult to strike.
%Pursuit and evasion tasks 
have been utilized for this purpose in the
past \cite{gomez:ab97,miller:sussextr94-311,reggia:alifej01,jim:alife00,sims:alife4}, 
and can serve as a
benchmark domain for complexifying coevolution as well.  
While past experiments
evolved either a predator or a prey,
an interesting coevolution task can be established if
the agents are instead equal and engaged in a duel.
To win, an agent must develop a strategy that outwits
that of its opponent, utilizing structure in the
environment.
% we evolve neural
%networks that can switch between the roles of both
%predator and prey, as well as forage for food.
%The evolution of 
%neural networks capable of both predator and prey behavior
%is a natural successor to these earlier experiments.
%The added complexity of evolving agents capable of 
%multiple roles is well suited to competitive coevolution.

%In the competition, two
%agents attempt to collect enough food to assume the role
%of predator and attack the opponent.
%In the robot duel domain, two simulated robots try to overpower
%each other (figure \ref{fg:board}).
%Added 03-2
In this paper we introduce such a duel domain,
in which two simulated 
robots try to overpower each other (Figure \ref{fg:board}).
The two robots
begin on opposite sides of a rectangular room facing away from each other.
As the robots move, they lose energy in proportion to the 
amount of force they apply to their wheels.  Although the robots
never run out of energy (they are given enough to survive the
entire competition), the robot with higher energy 
wins when it collides with its competitor.  
%Thus, a robot
%takes a risk by allowing its energy to fall below that of
%its competitor.  
In addition, each robot has a sensor indicating the
difference in energy between itself and the other robot.
To keep their energies high, the robots
can consume food items, arranged in a symmetrical
pattern in the room.  

%Added 03 - slight changes to caption, new figure
\begin{figure}
  \centering
  \pspic[\psline]{250pt}{!}{duel_redraw}
%\pspic[\psline]{!}{!}{ij-matchup-fig}      
  \titledcaption[\psline]{fg:board}
  {The Robot Duel Domain}
  {The robots begin on opposite
sides of the board facing away from each other as shown by the
arrows pointing away from their centers.  The concentric circles
around each robot represent the separate rings of opponent sensors
and food sensors available to each robot.  Each ring contains five
sensors. 
%which appear larger or smaller depending on their
%activations.
%From this 
%initial position, neither robot has a positional advantage.  
The robots lose energy when they move around, and gain energy
by consuming food (shown as small sandwiches).
The food is always placed in the depicted horizontally symmetrical pattern around
the middle of the board.  
The objective is to attain a higher level of energy than the opponent,
and then collide with it.
Because of the complex interaction between foraging, pursuit, and
evasion behaviors,
the domain allows for a broad range of strategies of
varying sophistication.  Animated demos 
of such evolved strategies are available at  
{\textbf{www.cs.utexas.edu/users/nn/pages/research/neatdemo.html}}.
%Done: switch to an NN address
%{\textbf{www.cs.utexas.edu/users/kstanley/demos.html}}.
%{\tiny \texttt{http://www.cs.utexas.edu/users/nn/pages/research/neatdemo.html}}.
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

The robot duel task supports a broad
range of sophisticated strategies that are easy to observe
and interpret.
The competitors must
become proficient at foraging, prey capture, and escaping predators.  
In addition, they must be able to quickly switch
from one behavior to another.  
The task is well-suited
to competitive coevolution because naive strategies 
such as forage-then-attack
can be complexified into more sophisticated
strategies such as 
luring the opponent to waste its energy before attacking.
%Role switching 
%introduces a high level of complexity into the strategies,
%providing a significant challenge to artificial neural networks.  
%%We chose this domain because, in addition to its potential
%%for sophistication, strategies are easy to observe and
%%describe without expert knowledge.  

\begin{figure}
  \centering
  \pspic[\psline]{350pt}{!}{DUELNET3}
  \vspace{-3.9in}
%\pspic[\psline]{!}{!}{ij-matchup-fig}      
  \titledcaption[\psline]{fg:sensors}
  {Robot Neural Networks} 
  {
Five food sensors and five robot sensors detect the presence of objects
around the robot.  A single wall sensor indicates proximity to walls,
and the energy difference sensor tells the robot how its energy level
differs from that of its opponent.  This difference is important
  because the robot with lower energy loses if the robots collide.
The three motor outputs are mapped to forces that control the left and 
the right wheel. 
%{\tiny \texttt{http://www.cs.utexas.edu/users/nn/pages/research/neatdemo.html}}.
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

%Because they use realistic simulations of physical robots,
%the experiments
%demonstrate the efficacy of combining robot control
%and coevolution.
The simulated robots
are similar to Kheperas 
\nocite{mondada:robotics93} (Mondada et al.\ 1993; Figure \ref{fg:sensors}).  
Each has two wheels controlled by
separate motors.  Five rangefinder sensors can sense food and another
five can sense the other robot.
Finally, each robot has an energy-difference sensor,
and a single wall sensor.  

The robots are controlled with
neural networks evolved with NEAT.
The networks receive all of the robot sensors
as inputs, as well as a constant bias that NEAT can use
to change the activation thresholds of neurons.  They produce
three motor outputs:  Two to encode rotation either
right or left, and a third to indicate forward
motion power.  These three values are then translated into
forces to be applied to the left and right wheels of the robot.

The state $s_t$ of the world at time $t$ is defined by the
positions of the robots and food, the energy levels of
the robots, and the internal states (i.e.\ neural activation)
of the robots' neural networks, including sensors, outputs,
and hidden nodes.  The subsequent state $s_{t+1}$ is 
determined by 
the outputs of the robots' neural network controllers, computed
from the inputs (i.e.\ sensor values) in $s_t$ in one
step of propagation through the network.  
%the robots' neural network outputs, which are computed from
%a single activation of the networks' inputs (i.e.\ sensors) in $s_t$.
The robots change their position in $s_{t+1}$ according to their
neural network outputs as follows.  The change in direction
of motion is proportional to the difference between the left and right motor
outputs. 
%multiplied by $0.24$ radians.  
The robot drives forward
a distance proportional to the forward output  
%$1.33f$, where $f$ is the forward output unit,
on a continuous board of size 600 by 600.  
%TODO: Move to appendix, make appendix B:
%The proportionality coefficients were determined through experimentation to
%calibrate reasonable motion with neural outputs between zero
%and one. 
The robot first makes
half its turn, then moves forward, then completes the
second half of its turn, so that the turning and forward
motions are effectively combined.  If the robot encounters food, it
receives an energy boost, and the food disappears from the
world.  The loss
of energy due to movement is computed as the sum of the turn
angle and the forward motion, so that even turning in place takes
energy.  If the robots are within a distance of 20,
a collision occurs and the robot with a higher energy wins
(see Appendix B for the exact parameter values used).

Since the observed state $o_t$
taken by the sensors does not include the internal state of the
opponent robot, the robot duel is a partially-observable
Markov decision process (POMDP).  Since the next observed state $o_{t+1}$
depends on the decision of the opponent, it is necessary for
robots to learn to predict what the opponent is likely to do,
based on their past
behavior, and also based on what is reasonable behavior in
general.  For example, it is reasonable to assume that if the opponent
robot is quickly approaching and has higher energy, it is probably
trying to collide.  Because an important
and complex portion of $s$ is not observable, memory, and hence
recurrent connections, are crucial for success.

%GECCO 2002 EDIT 
%The 3 outputs comprise an abstract interface
%to the low-level 2-motor apparatus.   

%NOTE: Not really important
%(CITEA Pierce) has
%shown that such abstract interfaces can be easily derived from 
%the motor apparatus of a robot through PCA of the effects
%of motor signals.  The abstract interface provides a 
%natural interface to the robot that is translated into
%low-level (two motor) control signals.

This complex robot-control domain allows competitive coevolution
to evolve increasingly sophisticated and complex
strategies, and can be used to understand
complexification, as will be described next.

\section{Experiments}
%\section{EXPERIMENTS}

In order to demonstrate how complexification 
enhances performance, we ran thirty-three 500-generation runs of coevolution  
in the robot duel domain.
%Four trials evolved with full NEAT,
%and three trials with complexification turned off,
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 methodology is described below.
%, allowing
%it to both optimize and complexify the networks as
%evolution progressed.  In addition, we ran
%three experiments with
%complexification turned off, in order to see
%how networks evolved with NEAT compared to those
%evolved with fixed topologies.  Running each experiment multiple times
%establishes the consistency of the results.
%%the effect of a fixed-size genome on the strategies
%%discovered in this domain.  
The competitive coevolution setup is described first, followed
by an overview of the dominance tournament method for  
monitoring progress.

\subsection{Competitive Coevolution Setup}
%\subsection{COMPETITIVE COEVOLUTION SETUP}

%``continual to the extent the domain allows it''
%   ``in other domains there is reason to believe it would continue''

%Added 03- changed
%The evolution in the robot duel domain is
%\emph{open-ended} in that it never reaches a final solution.
The robot duel domain supports highly sophisticated
strategies.   
Thus, the question in such a domain is whether \emph{continual
coevolution} will take place, i.e.\ whether increasingly
sophisticated strategies will appear
over the course of evolution. 
%Add ? :
%Although there may be a superior strategy in the robot duel
%domain after which improvement is not possible, 
%in other domains there is no reason in principle that
%innovation could not continue.     
The experiment has to be
set up carefully for this process to emerge, and to be able to
identify it when it does.
%Every member of the population
%should not have to compete against every other member of
%the population to achieve this goal because many of
%the strategies in the population may be similar or poor.
%In addition, playing every network against every other
%networks requires too many evaluations to be efficient.

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.  
%Thus, in each evolution trial, 2 populations,  
%each containing 256 genomes, were evolved
%simultaneously.  
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
\emph{host} population, and the population from which 
opponents are chosen is called the \emph{parasite} population
\cite{rosin:ec97}.  
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 
%compatibility
%Added 03 - reworded
distance
must exceed the threshold $\delta_t$ (section \ref{subsec:spec}).  
%must be outside the threshold $\delta_t$ (section \ref{subsec:spec}).  
Another eight opponents were chosen randomly from  
a Hall of Fame 
%Added 03 - reworded
composed of all generation champions \cite{rosin:ec97}. 
%after each
%generation, the current champion is added to the Hall of Fame.
The Hall of Fame ensures that existing abilities
need to be maintained to obtain a high fitness.  
%Added 03
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.
%Appendix \ref{sec:params} specifies the
%rest of the experimental parameter values.

It should be noted that complexification does not depend
on the particular coevolution methodology.  For example
Pareto coevolution \cite{ficici:ecal01,noble:gecco01}
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.

%However,
%as our experimental results will show, complexification is 
%the most important ingredient in establishing continual
%coevolution.

%Although there are slight differences, 
%they are not important towards experimental evaluation because
%we do not mean to make comparisons with Rosin and Belew.
%Rather, we are interested in the contribution of complexification
%to coevolution.  As long as the methodology is consistent 
%throughout the 7 experiments, conclusions can be drawn about
%how complexification interacts with coevolving populations. 

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

\subsection{Monitoring Progress in Competitive Coevolution}
%\subsection{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 \emph{dominance tournament}
method for monitoring progress in competitive coevolution 
\cite{stanley:geccows02} 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 playing a single pair of games (where each network gets 
%to play 1 game on each side of the board)
%is not representative
%of the overall quality of a strategy
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$ \emph{is superior} to network
$b$ if $a$ wins more games than $b$ out of the 288
total games.

%\begin{figure*}
%  \centering
%    \vspace{0.1in} %% Correct for bogus bounding box in eps file
%    \centering
%%    \pspic[\pscolororbw]{\textwidth}{!}{rf-lissom-architecture-bw}
%%\vspace{-0.8in}  
%\pspic[\psline]{250pt}{!}{master_fail3}
%%\vspace{-6.0in}
%%\pspic[\psline]{!}{!}{ij-matchup-fig}      
%  \titledcaption[\psline]{fg:master_fail}
%  {Master tournament ambiguity}
%  {
%Champions of generations one through six are depicted.  An arrow
%pointing from champion $x$ to champion $y$ denotes that $x$ is 
%superior to $y$ in a direct 288-way comparison.  
%%Added 03
%Arrows denoting comparisons involving champions 5 and 6 are darkened
%to emphasize the source of ambiguity.
%The master tournament reports that
%champion 5 defeats four other champions, while champion 6 only defeats
%three others.  These results imply that 5 is superior to 6.
%However, when 5 and 6 are compared directly against each other, 6
%actually wins.
%%6 is in fact superior to 5, illustrated by the thick line 
%%from 6 to 5.   
%This way, master tournament results can be misleading.  
%A method that captures the order of dominance among different
%  strategies avoids such a confusion.
%    \vspace{-\baselineskip}% Make figure a little tighter
%    }
%\end{figure*}

Given this definition of superiority, progress can be tracked.
%The goal is to determine whether 
%the arms race is progressing or stagnating.
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,
\emcite{floreano:ec97} used a measure called
\emph{master tournament}, in which the champion of each generation
is compared to all other generation champions.
%The master tournament is an extension of \emph{CIAO}
%\cite{cliff:ecal95} 
%(\emph{current individual vs.\ ancestral opponents}),
%in which every champion plays against all preceding 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$
\emph{even if} $B$ defeats $A$ in a direct comparison.
%TODO: Have Risto read, also mention figure was more confusing than it
%                       was worth in the response
%(figure \ref{fg:master_fail}).
%%%instead of only counting the 
%%%number of previous strategies that later strategies
%%%can defeat,
%instead of just finding out whether
%later strategies can beat more opponents
%than earlier strategies, 
In order to decisively track strategic innovation, we need to identify 
\emph{dominant strategies}, i.e.\ those 
that defeat
\emph{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 \emph{dominance tournament}
method of tracking progress in competitive coevolution 
meets this goal \cite{stanley:geccows02}.
Let a \emph{generation champion}
be the winner of a 288 game comparison between the 
host and parasite champions of a single generation.
%two population
%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:
%\footnote{Our definition of
%dominance is similar though not identical to the definition of a 
%\emph{transitive chain} (Rosin 1997, p.19)\nocite{rosin:phd}.}

\begin{itemize}
\item The first dominant strategy $d_1$ is the generation champion of the first generation;
\item 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).
\end{itemize}

\hspace{-0.1in}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. 
%Assume
%that $d_4$ occurred in the 50th generation of a run.  Then if the
%generation champion $c$ of generation 70 is superior to $d_4$, that
%alone is not enough to establish $c$ as $d_5$.  If it turns out that
%$d_2$ is superior to $c$, then $c$'s dominance is circular: it defeats
%recent dominant strategies but loses to older ones.  
%Those
%networks entered into the dominance hierarchy have defeated all
%previous dominant strategies.  

The entire process of deriving a 
dominance hierarchy from a population is a 
\emph{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 \cite{stanley:geccows02}. 
%or CIAO
%data monitoring techniques, which require every strategy to be 
%compared to at least every previous strategy.  Dominance tournaments
%only require comparisons to every previous \emph{dominant} strategy, and
%there are usually far fewer dominant strategies than total 
%strategies in the population.
%%which require $n^2$ and $\frac{n^2}{2}$ comparisons respectively, where $n$ is the
%%number of generations in the run.  The dominance
%%tournament takes less than 
%%$mn$ comparisons, where $m$ is the number of dominants
%%in the run, which is usually far less than $n$.

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?

\section{Results}
%\section{RESULTS}

%NOTE: Moved from 4.1 (Setup)
%Added - changed 23 to 33
Each of the 33 evolution runs 
took between 5 and 10 days on a 1GHz Pentium III processor, depending on
the progress of evolution and sizes of the networks
involved.  
The NEAT algorithm itself used less than 1\% of this computation: 
Most of the time was spent in evaluating networks in the robot duel
task.
%The evaluation of networks in the robot duel
%accounted for most of the running time,
%while the proportional 
%time utilized by the NEAT genetic algorithm was negligible. 
Evolution of fully-connected topologies 
took about 90\% longer than structure-growing NEAT because larger
networks take longer to evaluate.  

%We define \emph{complexity} as the
%number of nodes and number of connections in a network.  
%The more nodes and connections available to a network, the 
%more complex behavior it can potentially implement.
%Given this definition, the results were analyzed to answer three questions:
In order to analyze the results,
we define \emph{complexity} as the number of nodes and connections in
a network: The more nodes and connections there are in the network,
the more complex behavior it can potentially implement. The results
were analyzed to answer three questions:
(1) As evolution progresses does it also continually complexify?
(2) Does such complexification lead to more sophisticated strategies?
(3) Does complexification allow better strategies to be discovered than does
    evolving fixed-topology networks?
Each question is answered in turn below.

\subsection{Evolution of Complexity}
%\subsection{EVOLUTION OF COMPLEXITY}

NEAT was run thirteen times, each time from a different seed,
to verify that the results were consistent.
%We answer three questions 
%based on the results.  (1) What level of dominance was achieved?
%(2) How did complexity rise with dominance?
%(3) What causes complexity to rise with dominance?
The highest levels of dominance
achieved were 17, 14, 17, 16, 16, 18, 19, 15, 17, 12, 12, 11, and 13,
averaging at 15.15 (sd = 2.54).

\begin{figure*}
  \centering
  \begin{minipage}{\oneplotwidth}
    \vspace{0.1in} %% Correct for bogus bounding box in eps file
    \centering
%    \pspic[\pscolororbw]{\textwidth}{!}{rf-lissom-architecture-bw}
%  \pspic[\psline]{230pt}{!}{fcon}
%  \pspic[\psline]{230pt}{!}{fnode}
  \pspic[\psline]{215pt}{!}{con_bounds}
  \pspic[\psline]{215pt}{!}{nodes_bounds}
  \end{minipage}
%\pspic[\psline]{!}{!}{ij-matchup-fig}      
  \titledcaption[\psline]{fg:complexification}
  {Complexification of connections and nodes over generations}
  {
    The hashed lines depict the average number of connections
    and the average number of hidden nodes in the highest dominant
    network in each generation.  Averages are taken over
    13 complexifying runs.    A hash mark appears every generation in which
    a new dominant strategy emerged in at least one of the 13 runs.
    The graphs show that as dominance increases,
    so does complexity.  The differences
    between the average final and first
    dominant strategies are statistically significant for both 
    connections and nodes ($p<0.001$).
    For comparison the dashed lines depict the sizes of
  the average smallest and largest networks 
  in the entire population
%in each generation
%  in terms of both nodes and connections 
over five 
%random-fitness runs.
runs where the fitness is assigned randomly.  
These bounds show that the increase in complexity
is not inevitable; both very simple and very complex
species exist in the population throughout the run.
When the dominant networks complexify, they do so
because it is beneficial.
%  Assigning fitness randomly (i.e.\ choosing winners at random) 
%  allows determining the contribution of adding structure
%  to increasing complexity in the population.
% Note
%  that these random-fitness networks
%  are \emph{not} dominant networks; they are only graphed to establish
%  the range of complexity that NEAT generates on average.
%The
%  random-fitness bounds
%  demonstrate that complexification of the dominant strategies was
%  \emph{not} inevitable from adding structure.   
%When structure is neither an advantage nor disadvantage (i.e.\ in a
%  random-fitness run), NEAT maintains a broad range of complexities
%  in the population, including very low complexity solutions, up to 
%  the very end of the run.  Thus, for the complexity of dominant
%  solutions to have increased, there had to be an \emph{advantage} 
%  in increasing complexity.
%%
%because speciation
%  protects
%  different kinds of solutions as long as they perform well, the
%  population
%  continued to
%  include very low complexity networks until the 500th generation
%  even though structure had been added over the entire run.
%  Nevertheless, the complexity of dominant strategies tends to
%  increase, showing that complexity is indeed contributing to
%  strategic quality.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure*}

%Figure \ref{fg:complexification} shows how average network
%complexity rose with dominance.  
At each generation
where the dominance level increased in at least one of the thirteen runs,
we averaged the number of connections and number of nodes
in the current dominant strategy 
across all runs (Figure \ref{fg:complexification}).  
Thus, the graphs represent a total of 197  dominance 
transitions spread over 500 generations. 
%and show how
%with each dominance transition, complexity tended to go up.
The rise in complexity is dramatic, with the 
average number of connections tripling and the average number of hidden nodes
rising from 0 to almost six.
In a smooth trend over the first 200 generations, the 
number of connections in the dominant strategy
grows by 50\%.  During this early period, dominance transitions
occur frequently (fewer
prior strategies need to be beaten to achieve
dominance).
Over the next 300 generations, dominance 
transitions become more sparse, although they continue to occur.

%Risto read
%Added 03- changed staircase to ``stepped''
Between the 200th and 500th generations a stepped
pattern emerges:  The complexity first rises dramatically, then 
settles, then abruptly increases again (This pattern is even more marked  
%Added 03
%A similar pattern of rising complexity, settling, and then
%rising again occurred in most of the complexifying runs. 
in individual complexifying runs;
the averaging done in Figure \ref{fg:complexification} smooths
it out somewhat).  The cause for this pattern is speciation.
%The reason for this pattern 
%is speciation.  
%Speciation contributes to this pattern.
While one species is adding a 
large amount of structure, other species are optimizing the weights of 
less complex networks.  
Initially, added complexity leads
to better performance, but subsequent optimization takes
longer in the new higher-dimensional space.  Meanwhile,    
species with smaller topologies have a chance to temporarily catch up 
through optimizing their weights.
%While it is 
%initially faster to grow structure until something works,
%such ad hoc constructions are eventually supplanted by 
%older species that have been steadily optimizing for a long
%period of time. 
Ultimately, however, more complex structures eventually win,
since higher complexity is necessary for continued innovation.
%Thus, spikes in complexity occur when 
%structural elaboration leads to a better strategy, and
%complexity slowly settles when older structures optimize their
%weights and temporarily overtake more recent structural innovations.
%Eventually, even more elaborate structures will emerge and again 
%outperform the older structures. 

Thus, there are
two underlying forces of progress: The building of new
structures, and the continual optimization of prior
structures in the background.  The product of these
two trends is a gradual stepped progression towards 
increasing complexity.

%Added 03 - major revision
%\begin{figure*}
%  \centering
%  \begin{minipage}{\oneplotwidth}
%    \vspace{0.1in} %% Correct for bogus bounding box in eps file
%  \pspic[\psline]{230pt}{!}{con_bounds}
%  \pspic[\psline]{230pt}{!}{nodes_bounds}
%  \end{minipage}
%\titledcaption[\psline]{fg:bounds}
%  {Minimum and Maximum Complexities of Networks Generated by Random
%  Fitness Evolution}
%  {
%The figure shows that despite adding structure continually over
%  generations, NEAT preserves a broad range of network complexities
%  throughout the run.   
%The graphs depict the sizes of 
%  both the average smallest and largest networks in each generation 
%  in terms of both nodes and connections over 5 random-fitness runs.
%  Note 
%  that these networks
%  are \emph{not} dominant networks; they are only graphed to establish
%  the range of complexity that NEAT generates on average.  
%  The complexities of the highest dominant strategies (from
%  figure \ref{fg:complexification}) are also included for comparison.
%  The 
%  results
%  demonstrate that complexification of the dominant strategies was
%  \emph{not} inevitable from adding structure; because speciation protects
%  different kinds of solutions as long as they perform well, the
%  population 
%  continued to
%  include very low complexity networks until the 500th generation
%  even though structure had been added over the entire run.
%  Nevertheless, the complexity of dominant strategies tends to
%  increase, showing that complexity is indeed contributing to
%  strategic quality.
%    \vspace{-\baselineskip}% Make figure a little tighter
%  }
%\end{figure*}

%Added 03 - major revision
An important question is: Because NEAT searches by
adding structure only, not by removing it, does
the complexity always increase whether it helps 
in finding good solutions or not?  To demonstrate
that NEAT indeed prefers simple solutions and complexifies
only when it is useful, we ran five complexifying evolution
runs with
%Importantly, the dominant strategies did not have to complexify;
%even though NEAT adds new structure to networks over
%generations, because of speciation many species remain
%simple even as some species become more complex.
%This tendency to keep both simple and complex networks 
%in the population throughout the run is also shown
%in figure \ref{fg:complexification}.  
%% In order to demonstrate NEAT's ability to keep
%%  both simple and complex networks in the population, 
%We ran 5 runs
%  of complexifying evolution with 
fitness assigned randomly (i.e.\ the
  winner of each game was chosen at random).  
As expected, NEAT kept a wide range of networks in its
population, from very simple to highly complex (Figure \ref{fg:complexification}).
%The random fitness
%  function allowed us to isolate the effect of continually adding
%  structure from network performance.  That is, assigning random fitness
%  helps
%  answer the question of whether adding structure inevitably leads
%  to the complexification of dominant strategies, because it shows
%  whether the complexity of networks in the population increases
%  solely due to the constant addition of new structure.
%Interestingly, NEAT kept very simple
%networks in the population as long as they performed similarly
%to the complexifying networks.  
That is, the dominant networks
did not \emph{have to} become more complex; they only did
so because it was beneficial. 
%because NEAT would keep
%around simpler networks if they were doing as well.         
%Figure \ref{fg:complexification} shows that the dominant networks 
%do not increase in complexity as fast as chance would predict if 
%structural mutations were solely responsible for their topologies.
Not only is the minimum complexity in the random-fitness population 
much lower than
that of the dominant strategies, but the maximum complexity is
significantly greater.   
Thus, 
evolution complexifies sparingly, only when the
complex species holds its own in comparison with
the simpler ones.
%because speciation keeps species of varying complexities
%separate, 
%the growth of dominant networks 
%was \emph{not} an inevitable consequence of adding structure.

%TODO: Resurrect point?  Ask Risto?
%      he said he doesnt see anything new here..but it means something
%Furthermore, the results 
%show more than
%just that 
%the champions of each generation tend to become complex:
%%The results show a much more interesting trend: 
%The dominant strategies,
%i.e.\ the networks that have a strictly superior strategy to
%every previous dominant strategy, tend to be more complex \emph{the higher
%the dominance level}.  
%Thus, the results 
%verify that continual progress in evolution is paired
%with increasing complexity.
%%suggest that increasing
%%strategic sophistication utilizes complexification.

%adding new
%structure to genomes allows elaboration of strategies.

\subsection{Sophistication through Complexification}
%\subsection{SOPHISTICATION THROUGH COMPLEXIFICATION}

%In theory, increasing structure leads to
%more sophisticated strategies.  
To see how complexification
contributes to evolution, let us 
observe how a sample
dominant strategy develops over time.  While many complex
networks evolved in the experiments, we follow
the species 
that produced 
the winning network $d_{17}$ in the third run because its progress
is rather typical and easy to understand.
Let us use $S_k$ for the best network
%Added 03- ``species''
in species $S$ at generation $k$, and $h_l$ for the $l$th
hidden node to arise from a structural mutation over the course
of evolution.  
%Figure \ref{fg:progress} shows three key generations in
%the evolution of that species.  
%Let us use $S$ to denote the species that ultimately produced $d_{17}$.
We will track both strategic and structural innovations
in order to see how they correlate.
%that occurred over the history of $S$ in order to see how structural
%changes correlate with new strategies.  
Let us begin with
$S_{100}$ (Figure \ref{fg:progress}a), when $S$ had a mature 
zero-hidden-node strategy:

      \begin{figure}
  \centering
%  \pspic[\psline]{330pt}{!}{progress_annot_white2_gray}
\pspic[\psline]{430pt}{!}{prog_bw_annot}
  \titledcaption[\psline]{fg:progress}
  {Complexification of a Winning Species}
  {
    The best networks in the same species are depicted
    at landmark generations.  Nodes are depicted as squares beside their
    node numbers, and line thickness represents the strength
    of connections.
    Over time, the networks
    became more complex and gained skills.   (a) The champion from
  generation 10 had no hidden nodes.  (b) The addition of $h_{22}$ 
  and its respective connections gave new abilities.
  (c) The appearance of $h_{172}$ refined existing behaviors.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

\begin{itemize}
\item $S_{100}$'s main strategy was to follow the opponent, putting
it in a position where it might by chance collide with its opponent 
when its energy is up.
However, $S_{100}$ followed the opponent even when the opponent
had more energy, leaving 
$S_{100}$ vulnerable to attack.  
%$S_{100}$ also had trouble picking up nearby food.  
$S_{100}$ did not clearly switch
roles between foraging and chasing the enemy, causing it
to miss opportunities to gather food.

\item $S_{200}$. During the next 100 generations,
$S$ evolved a \emph{resting} strategy, which it used when it had
significantly lower energy than its opponent.  
In such a situation, the robot stopped moving, while the other
robot wasted energy running around. 
By the
time the opponent got close, its energy was often low enough
to be attacked.  
The resting strategy is an example of improvement that can
take place without complexification: It involved increasing
the inhibition from the energy difference sensor, thereby 
slightly modifying intensity of an existing behavior.

%The evolution of the resting strategy involved only
%the optimization of weights without the addition of structure.
%Because the resting strategy involves a
%simple inhibitory signal from the energy difference sensor,
%it was possible to evolve this strategy without complexification.
%However, some strategic elaborations do require the addition
%of structure, as the next strategy shows.

%\item $S_{100}$ (figure \ref{fg:progress}, left) 
%still had zero hidden nodes, although its
%following tended to be more accurate.  Otherwise, its
%strategies were identical to $S_{50}$.  

%\item In $S_{200}$, a single hidden node, $h_{21}$, added complexity to
%$S$.  The node $h_{21}$ first appeared in the 151st generation, and by 
%generation
%200 it was well connected.  The $h_{21}$ radically altered $S$'s
%core strategies.  Instead of using the resting strategy, $S_{200}$
%would now \emph{run away} from the enemy when it had less energy.  
%Whenever $S_{200}$ was running away, it would completely ignore
%food and eventually crash into a wall.  Interestingly,
%$S_{100}$ is superior to $S_{200}$, indicating that the resting
%strategy was probably better than the run away strategy.

%\item In $S_{210}$, a new hidden node, $h_{22}$ appeared through an
%interspecies mating ($h_{22}$ had been developing connections
%in another species for several generations already, so it
%arrived with many connections).   $h_{22}$ modulated $h_{21}$, which
%fed into $h_{22}$.  The situations where the robot would run
%away were significantly reduced to only very close emergencies where
%it was about to die.  Instead of running, $h_{22}$ caused $S_{210}$
%to attack, even when down, and then run away at the last instant
%if it had low energy, leading a significantly better strategy than
%$S_{200}$.

\item In $S_{267}$ (Figure \ref{fg:progress}b),
a new hidden node, $h_{22}$, appeared.  
This node arrived through an
interspecies mating, and 
had been optimized for several generations already. 
Node $h_{22}$ gave the robot the ability to 
change its behavior at once into an all-out attack.
Because of this new skill,
$S_{267}$ no longer needed to follow the enemy closely at all times,
allowing it to collect more food.
By implementing this new strategy 
through a new node, it was possible not to interfere with the 
already existing resting strategy, so that $S$ now switched
roles between resting when at a disadvantage to 
attacking when high on energy.  
%However, $S_{267}$ was very 
%conservative about attacking, sometimes still pursuing food even
%when it had sufficient energy to attack.  
Thus, the new structure resulted in strategic elaboration.

%\item In $S_{281}$, a crucial link between $h_{22}$ and the left turn
%output led to much more accurate, less haphazard attacks.  Clearly, 
%having $h_{22}$ directly modulate control was helpful.  However,
%$S_{281}$ was not very aggressive, sometimes missing opportunities
%to attack in favor of nearby food.

\item 
In $S_{315}$ (Figure \ref{fg:progress}c), another new hidden node, $h_{172}$,
split a link between an input sensor and $h_{22}$.  
Replacing a direct connection with a sigmoid function
%Adding a sigmoid
%where a direct connection used to be 
greatly improved 
$S_{315}$'s ability to attack at appropriate times, leading to very accurate
role switching between attacking and foraging.  
$S_{315}$ 
would try to follow the opponent from afar focusing on resting and 
foraging, and only zoom in
for attack when victory was certain. 
This final structural addition shows how new structure can
improve the accuracy and timing of existing behaviors.
\end{itemize}

The analysis above shows that
in some cases, weight optimization alone can produce 
improved strategies.  However, when those strategies need
to be extended, 
adding new structure allows the new behaviors to
coexist with old strategies.
Also, in some cases it is necessary to add complexity to
make the timing or execution of the behavior more accurate.
These results show how complexification can 
be utilized to produce
increasing sophistication.

\begin{figure}
  \centering
  \pspic[\psline]{130pt}{!}{duelshot}
  \titledcaption[\psline]{fg:duelshot}
  {Sophisticated Endgame}
  {
Robot $S_{313}$ dashes for the last piece of food while $S_{210}$ is still
collecting the second-to-last piece.  Although it appeared that
$S_{313}$ would lose because 
%it sat still while 
$S_{210}$ got the second-to-last piece,
(gray arrow), 
 it turns out that $S_{210}$ ends with a disadvantage. 
It has no chance to get to the last piece of food before
$S_{313}$, and $S_{313}$ has been saving energy while $S_{210}$ wasted
energy traveling long distances.  
This way, sophisticated strategies evolve through complexification,
combining multiple objectives, and utilizing weaknesses in the
opponent's strategy.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

In order to illustrate the level of sophistication 
achieved in this process, we conclude this section
by describing the competition between two
sophisticated strategies, $S_{210}$ and $S_{313}$, from another run of
evolution. 
%($S_{313}$ dominates $S_{210}$).  
At the beginning of the competition, $S_{210}$ and $S_{313}$ collected most of
the available food 
until their energy levels were about equal.
Two pieces of food remained on the board in locations
distant from both $S_{210}$ and $S_{313}$  (Figure \ref{fg:duelshot}).  
Because of the danger of colliding
with similar energy levels, the obvious strategy is to
rush for the last two pieces of food.  In fact, $S_{210}$ did exactly
that, consuming
the second-to-last piece, and then heading towards the
last one.  In contrast,
$S_{313}$ forfeited the race for the 
second-to-last piece, opting to sit still,
even though its energy temporarily dropped 
below $S_{210}$'s. 
%After $S_{210}$ consumed the second-to-last piece, it headed
%towards the last piece, which was now far away.  
%Even though
However,
$S_{313}$ 
%had less energy, it 
was closer to the last piece and got there first.
It received a boost of energy while $S_{210}$
wasted its energy running the long distance from 
the second-to-last piece.
Thus, $S_{313}$'s strategy ensured that it had
more energy when they finally met.  
Robot $S_{313}$'s behavior was surprisingly deceptive,
showing that high strategic sophistication had evolved.
%sophisticated level of strategic reasoning had evolved.
%Added 03
Similar waiting behavior was observed against several
other opponents, and also evolved in several other runs,
suggesting that it was a robust result.  

This analysis of individual evolved behaviors shows that
complexification indeed elaborates on existing strategies,
and allows highly sophisticated behaviors to develop that
balance multiple goals and utilize weaknesses in the opponent.
The last question is whether complexification indeed is necessary
to achieve these behaviors.

\subsection{Complexification vs. Fixed-topology Evolution and Simplification}
%\subsection{COMPLEXIFICATION VS. FIXED-TOPOLOGY EVOLUTION}

%New Explanation
Complexifying coevolution 
was compared to two alternatives:
standard coevolution in a fixed search space,
and to simplifying coevolution
%Added 03
from a complex starting point.     
Note that it is not possible to compare methods using the standard
crossvalidation
techniques because no external performance measure exists in this domain.
However, the
evolved neural networks can be compared \emph{directly}
by playing a duel. Thus, for example, a run of fixed-topology coevolution can
be compared to a run of complexifying coevolution by playing
the highest dominant strategy from the fixed-topology run against
the entire dominance ranking of the complexifying run.  The
highest level strategy in the ranking that the fixed-topology strategy
can defeat, normalized by the number of dominance levels,
 is a measure of its quality against the complexifying 
coevolution.  
For example, if a strategy can defeat up to and including the 13th 
dominant strategy out of 15, then its performance against that run 
is $\frac{13}{15}=86.7\%$.  
By playing every fixed-topology champion,
every simplifying coevolution champion, and every complexifying
coevolution champion
 against the dominance ranking 
from every
complexifying run and averaging, 
we can measure the 
relative performance of each of these methods.
%In addition, we established a baseline for
%comparison by also playing the champions of the \emph{complexifying}
%runs against the entire dominance ranking of every other
%complexifying run.  The average levels reached by
%complexifying,  fixed-topology, and simplifying coevolution can then be compared.

%Accordingly, the performance of a particular run is the 
%average highest dominance level of the strategies it can defeat
%among all
%complexifying runs, 
%normalized
%by the total number of dominance levels for that
%run.  
%The performance against all
%complexifying runs can then be averaged to obtain the
%overall performance of that run.   

In this section, we will first establish 
the baseline performance by playing complexifying
coevolution runs against themselves
and demonstrating that a comparison with dominance
levels is a meaningful measure of performance.  
We will then compare complexification with
fixed-topology coevolution 
of networks of different architectures, including
fully-connected small networks, fully-connected large networks,
and networks with an optimal structure as determined by
complexifying coevolution.
Third, we will compare the performance of complexification with
that of simplifying coevolution. 

\subsubsection{Complexifying Coevolution}

\begin{figure}
  \centering
%  \pspic[\psline]{330pt}{!}{progress_annot_white2_gray}
\pspic[\psline]{300pt}{!}{superdom}
  \titledcaption[\psline]{fg:superdom}
  {The Best Complexifying Network}
  {

The highest dominant network from the sixth complexifying coevolution
run was able to beat $99.6\%$ of the dominance hierarchy of the
other 12 runs. 
The network has 11 hidden units and 202 connections
  (plotted as in figure \ref{fg:progress}), making significant use
  of structure.  While it still contains the basic direct connections, the
  strategy they represent 
  has been elaborated by adding several new nodes and  
  connections.   For example, lateral and recurrent connections 
allow taking past events into account, resulting in
more refined decisions.
While such structures can be found reliably through complexification,
it turns out difficult to discover them directly in the high
dimensional space through fixed-topology evolution or
through simplification. 
%  We evolved fixed-topology 10-hidden-unit networks
%    of similar complexity, but comparable
%    strategies could not be found.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}


%On average, complexifying coevolution found 15.15 levels
%of dominance (sd = 2.54).  
The highest dominant
strategy from each of the 13 complexifying runs  
played the entire dominance ranking from every
other run.  
Their average performance scores were $87.9\%$, $83.8\%$,
$91.9\%$, $79.4\%$, $91.9\%$, $99.6\%$, $99.4\%$, $99.5\%$, $81.8\%$,
$96.2\%$, $90.6\%$, $96.9\%$, and $89.3\%$,
with an overall average of $91.4\%$ (sd=12.8\%).
Above all, this result shows that
complexifying runs produce consistently good strategies:
On average, the highest dominant strategies 
qualify for the top $10\%$ of the other complexifying runs.
The best runs were the
sixth, seventh, and eighth, which were able to defeat almost the 
entire dominance 
ranking of every other run.  
The highest dominant network from the best run
($99.6\%$) is shown in Figure \ref{fg:superdom}. 

\begin{figure}
\centering
%Added -03 - about the meaning of dominance levels 
 \pspic[\psline]{330pt}{!}{domsig}
  \titledcaption[\psline]{fg:domsig}
  {Interpreting Differences in Dominance Levels}
  {
The graph shows 
how many games in a 288-game comparison a more dominant
network can be expected to win, 
averaged over all runs at all dominance levels of complexifying coevolution.
For example, 
a network one level higher wins 50 more games out of 288.
A larger difference in dominance levels translates to
a larger difference in performance approximately linearly,
suggesting that dominance levels can be used as a measure
of performance when an absolute measure is not available.
 \vspace{-\baselineskip}% Make figure a little tighter
 }
\end{figure}

In order to understand what it means for a network to be one 
or more dominance levels above another, Figure \ref{fg:domsig} 
shows how many more games the more dominant network
can be expected to win on average over all its
288-game comparisons than the less dominant network.
%The following sections compare different non-complexifying 
%runs to the dominance levels of complexifying coevolution.
%In order to make this comparison more meaningful, figure \ref{fg:domsig}
%shows what differences in dominance level mean in terms of
%games won by the dominant network.  In other words, we want
%to know what it means for a network to be one or more dominance levels
%above another.  Since comparisons between networks include 288
%separate games, some of which can be ties (i.e.\ when neither network
%collides with the other), the figure shows the \emph{difference}
%between networks of different levels in terms of games won out of 288.
%The statistics were
%computed by averaging comparison results over all differences in
%all the runs of complexifying coevolution.  That is, for all 
%differences of one dominance level, we averaged all the score results
%from every dominance tournament.  Averages were similarly computed for
%differences of two dominance levels, etc., up to a difference of 18
%levels, which occurred in only one of the runs.     
Even at the lowest difference (i.e.\ that of one
dominance level),
the more dominant network can be expected to win about 50
more games on average, 
showing that each difference in dominance level is important.   
The difference grows approximately linearly: A network
5 dominance levels higher will win 100 more games, while a 
network 10 levels higher will win 150 and 15 levels higher
will win 200.  These results suggest that dominance
level comparisons indeed constitute a meaningful way to
measure relative performance. 

\subsubsection{Fixed-Topology Coevolution of Large Networks}

In fixed-topology coevolution,
the network architecture must be chosen by
the experimenter. 
One sensible approach is to approximate the complexity of the 
best complexifying network.
(Figure \ref{fg:superdom}).  
This network included 11 hidden units and 202
connections, with both recurrent connections and direct
connections from input to output.
As an idealization of this structure, we used  
10-hidden-unit fully recurrent networks with direct connections
from inputs to outputs, with a total of   
263 connections.  A network of this type should be able
to approximate the 
functionality of the most effective complexifying strategy.
%Added 03  
Fixed-topology coevolution runs exactly as complexifying coevolution
in NEAT, except that no structural mutations can occur.
In particular,
the population is still speciated based on weight differences
(i.e.\ $\overline{W}$ from equation \ref{eqn:speciation}), using
the usual speciation procedure.

%TODO: hyphens in figure look like they have a space after them 
\begin{figure}
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_10n}
%   \vspace{-3.0in}
  \titledcaption[\psline]{fg:node10}  
  {Comparing Typical Runs of Complexifying Coevolution and
  Fixed-Topology Coevolution with Ten Hidden Units}
  {
    Dominance levels are charted on the $y$-axis and generations 
    on the $x$-axis.  A line appears at every generation where 
    a new dominant strategy 
    arose in each run.  The height of the line represents the level
    of dominance.  The arrow shows that the highest dominant strategy
    found in 10-hidden-unit fixed-topology evolution only performs as
    well as the 8th dominant strategy in the complexifying run, which was found
    in the 19th generation.  (Average = 24, sd = 8.8)  
    In other words, only a few generations of complexifying
  coevolution are as effective as several hundred of fixed-topology evolution.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

Three runs of fixed-topology coevolution were performed with these
networks, and their highest dominant strategies were
compared to the entire dominance ranking of every complexifying
run.  Their average performances were
$29.1\%$, $34.4\%$, and $57.8\%$, for an overall average 
of $40.4\%$.  Compared to the
$91.4\%$ performance
of complexifying coevolution, it is clear that fixed-topology
coevolution produced consistently inferior solutions.
As a matter of fact, no fixed-topology 
run could defeat any of the highest dominant
strategies from the 13 complexifying coevolution runs.
%Because each level of
%dominance in a ranking is harder to achieve than the last,
%the first $40\%$ of a ranking takes significantly less search to
%discover than the next $40\%$.  

This difference in performance can be illustrated by
computing the \emph{average generation} 
%that the standard coevolution can defeat. 
of complexifying coevolution with the same performance
as fixed-topology coevolution.
This generation turns out to be 24 (sd = 8.8).
In other words, 500 generations of fixed-topology coevolution
reach on average the same level of dominance as only 24
generations of complexifying coevolution!
In effect, the progress of the entire fixed-topology coevolution
run is compressed into the first few generations of complexifying
coevolution (Figure \ref{fg:node10}).

\subsubsection{Fixed-Topology Coevolution of Small Networks}

\begin{figure}
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_5n}
%  \vspace{-3.0in}
  \titledcaption[\psline]{fg:node5}
  {Comparing Typical Runs of Complexifying Coevolution and
  Fixed-Topology Coevolution with Five Hidden Units}
  {
    As in figure \ref{fg:node10}, 
    dominance levels are charted on the $y$-axis and generations 
    on the $x$-axis, a line appears at every generation where 
    a new dominant strategy 
    arose in each run, and the height of the line represents the level
    of dominance.  The arrow shows that the highest dominant strategy
    found in the 5-hidden-unit fixed-topology evolution only performs as
    well as the 12th dominant strategy 
    in the complexifying run, which was found
    in the 140th generation (Average 159, sd = 72.0).
    Thus, even in the best configuration, fixed-topology evolution
    takes about twice as long to achieve the same level of performance.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

One of the arguments for using complexifying coevolution is that
starting the search directly in the space of the final solution may
be intractable.  This argument may explain why the 
attempt to evolve fixed-topology 
solutions at a high level of complexity failed.
Thus, in the next experiment we 
aimed at reducing the search space by evolving
fully-connected,
fully-recurrent networks with a small number of hidden nodes
as well as direct connections from inputs to outputs.
After considerable experimentation, we found out that 
five hidden nodes (144 connections) was appropriate,
allowing fixed-topology evolution to find the best
solutions it could.
Five hidden nodes is also
about the same number of
hidden nodes as
the highest dominant strategies had on average
in the complexifying runs.

A total of seven runs were performed with the 5-hidden-node networks,
with average performances of $70.7\%$,
$85.5\%$, $66.1\%$, $87.3\%$, $80.8\%$, $88.8\%$, and $83.1\%$.
The overall average was $80.3\%$ (sd=18.4\%), which is
better but still significantly below the $91.4\%$ performance of
complexifying coevolution ($p < 0.001$).  

%The results with 5-hidden-unit fixed-topology 
%coevolution are significantly better
%than with 10 hidden units, confirming the hypothesis that search
%is more difficult in higher-dimensional space.  However, the solutions
%found this way were still inferior to the complexified solutions.
In particular,
the two most effective complexifying runs were still  
never defeated by any of the fixed-topology runs.  Also, because each
dominance level is more difficult to achieve than the last, 
on average the fixed-topology evolution only reached the performance
of the 159th complexifying generation (sd=72.0).
Thus, even in the best case, 
fixed-topology coevolution on average only finds
the level of sophistication that complexifying coevolution 
finds halfway through a run (Figure \ref{fg:node5}). 

\subsubsection{Fixed-Topology Coevolution of Best Complexifying Network}

One problem with evolving fully-connected architectures is
that they may not have an appropriate topology for this domain.  
Of course, it is very difficult to guess an appropriate topology
\emph{a priori}.  However, it is still interesting to ask whether
fixed-topology coevolution could succeed in the task assuming
that the right topology was known?   
To answer this question, we evolved networks as in the other
fixed-topology experiments, except this time 
using the topology of
the best complexifying network  (Figure \ref{fg:superdom}).
%This network utilized 11 hidden nodes and 202 connections, making
%it comparable in size to the 10-hidden-unit fixed topology network
%of 263 connections.  
This topology may constrain
the search space in such a way that finding a sophisticated solution
is more likely than with a fully-connected architecture.  If so,
it is possible that seeding the population with a successful topology gives
it an advantage even over complexifying coevolution, which must build
the topology from a minimal starting point. 

Five runs were performed, obtaining
average performance score $86.2\%$,
$83.3\%$, $88.1\%$, $74.2\%$, and $80.3\%$, and an overall average
of $82.4\%$ (sd=$15.1\%$).  The $91.4\%$ performance of complexifying
coevolution is significantly better than even this version of fixed-topology
coevolution ($p<0.001$).     However, interestingly, the $40.4\%$ average 
performance of 10-hidden-unit fixed topology coevolution is
significantly \emph{below} best-topology evolution, even though both
methods search in spaces of similar sizes.  In fact, best-topology
evolution performs at about the same level as 5-hidden-unit 
fixed-topology evolution ($80.3\%$), even though 5-hidden-unit
evolution optimizes half the number of hidden nodes.  
Thus, the results
confirm the hypothesis that using a successful evolved topology   
does help constrain the search.  However, in comparison to
complexifying coevolution, the
advantage gained from starting this way is still not enough to
make up for the penalty of starting search directly
in a high-dimensional space.   
As Figure \ref{fg:best} shows, best-topology evolution
on average only finds a strategy that performs as well
as those found by the 193rd generation of complexifying coevolution. 

\begin{figure}
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_best}
%  \vspace{-3.0in}
  \titledcaption[\psline]{fg:best}
  {Comparing Typical Runs of Complexifying Coevolution and 
  Fixed-Topology Coevolution of the Best Complexifying Network}
  {
    Dominance levels are charted as in figure \ref{fg:node10}. 
%    dominance levels are charted on the y-axis and generations 
%    on the x-axis, a line appears every generation where 
%    a new dominant strategy 
%    arose in each run, and the height of the line represents the level
%    of dominance.  
    The arrow shows that the highest dominant strategy
    found by evolving the fixed topology of the best complexifying network
    only performs as
    well as the dominant strategy that would be found
    in the 193rd generation of complexifying coevolution  
    (Average 193, sd = 85).
    Thus, even with an appropriate topology given, fixed-topology evolution
    takes almost twice as long to achieve the same level of performance.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

The results of the fixed-topology coevolution experiments
can be summarized as follows:
If this method is used to
search directly in
the high-dimensional space of the most effective solutions,
it reaches only 40\% of
the performance of complexifying coevolution.
It does better if it is allowed to optimize less complex
networks; however, the most sophisticated solutions may not exist in
that space.
Even given a topology appropriate for the task, it does not reach the
same level as complexifying coevolution.
Thus, fixed-topology coevolution does not appear to be competitive
with complexifying coevolution with \emph{any} choice of topology.

The conclusion is that complexification is superior not only
because it allows discovering the appropriate high-dimensional
topology automatically, but also because it makes the optimization
of that topology more efficient.  This point will be discussed
further in Section \ref{sec:discussion}.

\subsubsection{Simplifying Coevolution}

\begin{figure}
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_red2}
%  \vspace{-3.0in}
  \titledcaption[\psline]{fg:simp}
  {Comparing Typical Runs of Complexifying Coevolution and Simplifying Coevolution}
  {
    Dominance levels are charted as in figure \ref{fg:node10}.
    In addition, the line plot shows the complexity of each dominance level
    in terms of number of connections in the networks
    with scale indicated in the $y$-axis at right.  In this
    typical simplifying run,
    the number of connections reduced from 339 to 227 connections. 
     The arrow shows that the highest dominant strategy
    found in simplifying coevolution
    only performs as
    well as the 9th or 10th dominant strategy of complexifying
    coevolution, which is normally found
    after 56 generations  (sd = 31).
    In other words, 
    even though simplifying coevolution finds more dominance levels,
    the search for appropriate structure is less effective than
    that of complexifying coevolution.
%    over 450 generations of simplifying
%    coevolution only produces strategies comparable
%    to those found after about 400 \emph{fewer} generations of
%    complexifying coevolution.
    %until a level 17 dominant strategy appeared in generation 315.
    \vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}

A possible remedy to having to search in high-dimensional spaces
is to allow evolution to search for smaller structures by
removing structure incrementally.  This \emph{simplifying coevolution}
is the opposite of complexifying coevolution.  The idea is that
a mediocre complex solution can be refined by removing unnecessary
dimensions from the search space, thereby accelerating the search.

Although simplifying coevolution is an alternative method
to complexifying coevolution for finding topologies, it still
requires a complex starting topology to be specified.  
This topology was chosen with two goals in mind: (1)
Simplifying coevolution should start with sufficient complexity
to at least potentially find solutions of equal or more complexity
than the best solutions from complexifying coevolution, 
%without
%excluding the possibility of finding even simpler solutions, 
and (2) with a rate of structural removal equivalent to the rate of structural
addition in complexifying NEAT, it should be possible to discover
solutions significantly simpler than the best complexifying solutions.  
%(Appendix \ref{sec:params} specifies
%structures mutation rates in NEAT).   
Thus, we chose to start search with a 12-hidden-unit, 339 connection
fully-connected fully-recurrent network.
Since 162 connections were added to the best complexifying
network during evolution, a corresponding simplifying
coevolution could discover solutions with 
177 connections, or 25 less than the best complexifying network.  

Thus, simplify coevolution was run just as complexifying coevolution,
except that the initial topology contained 339 connections instead
of 39, and structural mutations removed connections instead of 
adding nodes and connections.  If 
all connections of a node were removed, the node itself
was removed.  
%The rate of connection removing mutations was equivalent
%to the rate of connection adding mutations in complexifying
%coevolution.  
Historical markings and speciation worked as in
complexifying NEAT, except that all 
markings were assigned in the beginning of evolution.
(because structure was only removed
and never added).  A diversity of species of varying complexity 
developed as before.      

The five runs of simplifying coevolution performed at $64.8\%$,
$60.9\%$, $56.6\%$, $36.4\%$, and $67.9\%$, with an overall
average of $57.3\%$ (sd=19.8\%).  Again, such performance is 
significantly below
the $91.4\%$ performance of complexifying coevolution ($p<0.001$).
Interestingly, even though it started with 76 more connections
than fixed-topology coevolution with ten hidden units, simplifying 
coevolution still performed significantly
better ($p<0.001$), suggesting that evolving structure through reducing
complexity is better than evolving large fixed structures.  
    
Like Figures \ref{fg:node10}--\ref{fg:best},
Figure \ref{fg:simp} compares typical runs of
complexifying and simplifying coevolution.
On average, 500 generations of simplification
finds solutions equivalent to 56 generations
of complexification.
Simplifying coevolution also
tends to find more dominance levels than any other method tested.
It generated an average of $23.2$ dominance levels per run, once even
finding $30$ in one run, whereas e.g.\ complexifying coevolution
on average finds $15.2$ levels.  In other words,
the difference between dominance levels is much smaller
in simplifying coevolution than complexifying coevolution.
Unlike in other methods, dominant strategies tend 
to appear in spurts of a few at a time,
and usually after complexity has been decreasing for several
generations, as also shown in Figure \ref{fg:simp}.
Over a number of generations,
evolution removes several connections until
a smaller, more easily optimized space is discovered.  Then,
a quick succession of minute improvements creates several
new levels of dominance, after which the space is further
refined, and so on.  While 
such a process makes sense, the inferior results 
of simplifying coevolution suggest that
simplifying search is an ineffective way of discovering
useful structures compared to complexification.

%\subsubsection{Comparing Fixed-Topology vs.\ Complexifying Coevolution}
\subsubsection{Comparison Summary}

\begin{centering}
\begin{table}
%\caption{PERFORMANCE COMPARISON}
\label{tbl:coevcomp}
%  \small
  \tabcolsep 4pt
%  \renewcommand{\arraystretch}{0.7}
%  \centering
%\caption{Comparing the Dominant Stratgies in the Fixed-topology
%  (i.e. Standard) Coevolution with those of
%  Complexifying Coevolution.} 
\begin{tabular}{|l|r|r|r|r|}
\hline
\textbf{Coevolution Type} & \textbf{Ave. Highest} & \textbf{Ave. Highest} & 
           \textbf{Average} &\textbf{Equivalent}  \\
                & \textbf{Dom. Level} & \textbf{Generation}
                 & \textbf{Performance} & \textbf{Generation}\\ 
    &    &  \textbf{} & \textbf{} & \textbf{(out of 500)} \\
\hline
\hline
Complexifying & 15.2 & 353.6 & 91.4\% & 343\\ 
\hline
Fixed-Topology & 12.0 & 172 & 40.4\% & 24 \\
10 Hidden Node &  & & & \\
\hline
Fixed-Topology & 13.0 & 291.4 & 80.3\% & 159\\
5 Hidden Node & & & & \\
\hline
Fixed-Topology & 14.0 & 301.8 & 82.4\% & 193\\
Best Network & & & & \\
\hline
Simplifying & 23.2 & 444.2 & 57.3\% & 56 \\
\hline
\end{tabular}
\\Table 1: \textbf{Summary of the performance comparison.}  
The second 
column shows how many levels of dominance were achieved in each type 
of coevolution on average.
The third specifies the average generation 
of the highest dominant strategy,
indicating how long innovation generally continues.
The fourth column gives 
the average level in the complexifying coevolution
dominance hierarchy that the champion
could defeat, and the fifth column shows
its average generation.   
%Equivalent generation was calculated by averaging the generations in each
%complexifying run where the level of dominance surpassed the
%average performance. 
%(The equivalent
%%  generation is very high for $91.4\%$ effectiveness because in many
%%of the complexifying runs this level was only surpassed by the highest
%%dominant strategy, which occurs in the highest possible generation.)
%%%%%%%%%%%%%
%The differences in dominance level ($p < 0.05$), performance ($p <
%0.001$) , and equivalent
%generation ($p < 0.001$) are all significant.
%%%%%%%%%%%
The differences in performance  ($p <0.001$)  and equivalent
generation ($p < 0.001$) between
complexifying coevolution and every other method are 
significant.
%%%Is this overkill (below)?
%The difference in highest generation between 10-hidden-unit 
%fixed-topology coevolution and complexifying coevolution is
%significant ($p < 0.001$).  Although complexifying coevolution
%did continue to innovate for more 
%generations than 5-hidden-node fixed-topology 
%coevolution on average, this difference was not significant.
The main result is that the level of sophistication
reached by complexifying coevolution is significantly higher
than that reached by fixed-topology or simplifying coevolution. 
\end{table}
\end{centering}

Table 1 shows how the coevolution methods  
differ on number of
dominance levels, generation of the highest
dominance level, overall performance, and equivalent 
generation.  The conclusion is that complexifying coevolution
innovates longer and finds a higher level of sophistication
than the other methods. 
%Added 03 -removed bold claim
%and absolutely.  

\section{Discussion and Future Work} \label{sec:discussion}
%\section{DISCUSSION AND FUTURE WORK}

What makes complexification such a powerful search method?
Whereas in fixed-topology coevolution, as well as in
simplifying coevolution, the good structures must be 
optimized in the high-dimensional space of the
solutions themselves, complexifying coevolution
only searches high-dimensional structures that are
elaborations of known good lower-dimensional structures.
Before adding a new dimension,
the values of the existing genes have already been
optimized over preceding generations.  Thus, after
a new gene is added, the genome is \emph{already}
in a promising part of the new, higher-dimensional space.
Thus, the search in the higher-dimensional space is 
not starting blindly as it would if evolution began searching 
in that space.  It is for this reason that complexification
can find high-dimensional solutions that 
fixed-topology coevolution and simplifying coevolution
cannot.
%Added 03
%Even if an offspring with a new gene initially performs poorly,
%it may still be useful since most of its dimensions are 
%already partially in the new higher-dimensional space.  

%Complexification encourages continual \emph{elaboration},
%whereas evolution of fixed-structures only allows
%elaboration up to a point, after which only
%\emph{alteration} is possible.
Complexification 
is particularly well suited for coevolution problems.
%encourages continual \emph{elaboration},
%whereas evolution of fixed-structures proceeds primarily by
%\emph{alteration}.
When a fixed genome is used to represent a strategy,
that strategy can be optimized, but it is
not possible to add functionality without
sacrificing some of the knowledge that is already present.
In contrast, if new genetic material can be added, sophisticated
elaborations can be layered above existing structure,
establishing an evolutionary arms race.  This process
was evident in the robot duel domain, where
successive dominant strategies often built new
functionality on top of existing behavior by
adding new nodes and connections.
%Indeed, dominant strategies are usually more complex than
%their predecessors, showing that evolution capitalizes on
%the capacity to complexify.

%Complexification can find solutions that would be difficult
%to obtain through evolving fixed structure:
%No fixed-sized or simplifying network was able to defeat the best
%strategies from complexifying coevolution.
%In fixed evolution, the complexity must be guessed
%just right.  Too little structure will make it
%impossible to solve the problem and too much will
%make the search space too large to search efficiently.
%%For this reason, the two fixed-topology trials with ten hidden nodes
%%produced lower equivalent dominance levels
%%than the five hidden node trial.
%%However, even the five hidden node trial could only
%%defeat dominant strategies up to the 65th generation
%%of complexifying coevolution.
%%Unless the minimum complexity
%%necessary to express a sufficient strategy is known, it is possible
%%that an arbitrarily chosen fixed-structure will be insufficient. 
%%In addition, if the form of the solution strategy is not known
%%\emph{a priori}, then an appropriate complexity cannot
%%be estimated before evolution begins.  
%Moreover, \emph{even if} complexity is guessed right,
%searching in the the high-dimensional space of the final
%solution may be intractable because search 
%begins in a random part of the space.  
%%Added 03
%Furthermore, even if evolution can simplify solutions from
%a complex starting point, the expense of starting search
%in an intractable search space is still too high to overcome.  
%A complexifying system
%saves the user from such concerns.
%because it has \emph{no maximum}
%complexity, and requires no prior information on the complexity 
%of the desired result.

%Added 03 - removed section because of new experiment on simplification
%In principle, if the complexification process is efficient enough, it
%will generate just enough structure to solve the task. However, if
%complexification is too greedy or inaccurate, it may be useful to
%counterbalance it with a process of simplification, in which genes are
%occasionally disabled or deleted from the genome. Such a process could
%be useful in principle to keep the evolved structures minimal.
%However, removing structure is potentially more disruptive than adding
%it, since entire modules can be accidentally cut off with even a small
%deletion.  Moreover, removing a gene may initially improve fitness,
%even though the gene may be necessary to construct the final solution.
%In such a case, evolution may become stuck for several generations
%waiting for the gene to become reinstated.  As a result, in
%preliminary experiments we did not find minimization to improve the
%performance of complexifying system. Whether these two processes can
%implemented so that they leverage each other is an interesting
%direction of future work.

%It is possible to implement a complimentary process in which
%genes are also occasionally disabled or deleted, thereby
%reducing the complexity of the genome.
%However, removing structure is potentially 
%more disruptive than adding it, since
%it can cut off entire modules.  Moreover,  
%removing a gene may initially
%improves fitness, even though it would be needed in the
%solution. 
%As a result, many generations can pass in which evolution is stuck waiting for
%the gene to be reinstated.  In any case, gene deletion is
%not necessary for complexification to succeed, as the results
%demonstrate.  Still, deleting or disabling random genes could
%counterbalance unnecessary complexity, and finding
%the right way to implement such a system is future work.
 
%(Genes would not
%be \emph{deleted} since that would remove the historical 
%information that is used to compare and speciate genomes.)


%Explain why complexity increases in CAs dont count
The advantages of complexification do not
imply that fixed-sized genomes cannot sometimes
evolve increasingly complex \emph{phenotypic behavior}.
Depending on the mapping between the genotype
and the phenotype, it may be possible for a fixed, finite set
of genes to represent solutions (phenotypes) with varying behavioral 
complexity.
For example, such behaviors have been observed in Cellular Automata
(CA), a computational structure consisting of
%For example, cellular automata (CA) neighborhood functions of
%a fixed size can represent behaviors ranging from simple
%and periodic to complex and unpredictable \cite{mitchell:evca96}.
a lattice of cells that change their
state as a function of their own current state and the
state of other cells in their neighborhood.
%Thus, a neighborhood function takes as arguments $n$ neighboring cell
%states, where $n$ is the size of the neighborhood.  
This neighborhood
function can be represented in a genome of size
$2^{n+1}$ (assuming $n$ neighboring cells with binary state) and
evolved to obtain desired target behavior.  
For example, \emcite{mitchell:evca96} were
able to evolve neighborhood functions 
to determine whether black or white cells
were in the majority in the CA lattice.
%, which is called \emph{density classification}.
%Their neighborhood included three cells to the left and 
%three cells to the right in a one-dimensional CA. 
The evolved CAs displayed complex global behavior patterns that
converged on a single classification, depending on which
cell type was in the majority.    Over the course of evolution, 
the behavioral complexity
of the CA rose even as the genome remained the same size.

In the CA example, the correct neighborhood size was chosen a priori.
This choice is difficult to make, and crucial for success.
%evolving complex behavior only
%demonstrates that the desired behavior was within the space
%of the particular neighborhood, which was chosen \emph{a priori}
%as the correct size.  Rather than contradicting the notion
%that complexification is important for evolving sophisticated behaviors, this 
%example emphasizes the importance of the choice of genome
%size and the risk of making incorrect \emph{a priori} decisions.
%For example, 
If the desired behavior had
not existed within the chosen size, even if the behavior 
would become gradually more complex, the system would never
solve the task.
%did
%increase in complexity over some generations, it could never 
%reach the desired level.  
Interestingly, such a dead-end could
be avoided if the neighborhood (i.e.\ the genome)
could be expanded during evolution.  It is possible that CAs
could be more effectively evolved by 
complexifying (i.e.\ expanding) the genomes,
and speciating to protect innovation, as in NEAT. 

Moreover, not only can
the chosen neighborhood be too small to
represent the
solution, but it can also be unnecessarily large.  
Searching in a space of more dimensions than necessary can
impede progress, as discussed above.  
If the desired function
%a density classification neighborhood
%function 
existed in a smaller neighborhood 
%of two cells to
%the right and two to the left, 
it could have been found with
significantly fewer evaluations.  Indeed, it is even possible that
the most efficient neighborhood is not symmetric, or contains
cells that are not directly adjacent to the cell being processed.
Moreover, even the most efficient neighborhood may be too large
a space in which to begin searching.  Starting search in a small space
and incrementing into a promising part of higher-dimensional space
is more likely to find a solution. 
For these reasons, complexification can be an advantage, \emph{even
  if} behavioral complexity can increase to some extent within a
fixed space.

The CA example raises the intriguing possibility that
\emph{any} structured phenotype can be evolved through
complexification from a minimal starting point, historical
markings, and the protection of innovation through speciation.
In addition to neural networks and CA, 
electrical circuits \cite{miller:jgpem00_1,miller:jgpem00_2},
genetic programs \cite{koza:book92}, 
robot body morphologies \cite{lipson:nature00},
Bayesian networks \cite{mengshoel:phd94}, finite automata \cite{brave:gp96},
and building and vehicle architectures \cite{oreilly:alife00} 
are all structures of varying complexity that can
benefit from complexification.
By starting search in a minimal space and adding new
%Added 03- changed ``as necessary'' to ``incrementally''
dimensions incrementally, highly complex phenotypes
can be discovered that would be difficult to find if search
began in the intractable space of the final solution,
or if it was prematurely restricted to too small a space.

%Added 03
The search for optimal structures is a common problem
in Artificial Intelligence (AI).     
For example, Bayesian methods have been applied to learning model structure 
\cite{attias:nips00,ueda:nn02}.    In these approaches, the posterior
probabilities of different 
structures are computed, allowing overly 
complex or simplistic models to
be eliminated.   Note that these approaches are not aimed at generating
increasingly complex functional structures, but rather at providing
a model that explains existing data.
In other cases, solutions involve growing gradually larger
structures, but the goal of the growth is to form gradually
better \emph{approximations}. For example, methods like Incremental
Grid Growing \cite{blackmore:ml95}, and Growing Neural Gas
\cite{fritzke:anips95} add neurons to a network until it approximates the
topology of the input space reasonably well.  On the other hand,
complexifying systems do not have to be non-deterministic (like NEAT),
nor do they need to be based on evolutionary algorithms. For example,
\emcite{harvey:phd93} introduced a deterministic algorithm where the
chromosome lengths of the entire population increase all at the same
time in order to expand the search space; \emcite{fahlman:cascade} developed a
supervised (non-evolutionary) neural network training method called
cascade correlation, where new hidden neurons are added to the network
in a predetermined manner in order to complexify the function it
computes.
The conclusion is that complexification is an important general
principle in AI.  

In the future, complexification may help with the general problem
of finding the appropriate level of abstraction for difficult
problems.  Complexification can start out with a simple, high-level
description of the solution, composed of
general-purpose elements.  If such an abstraction is insufficient,
it can be elaborated by breaking down each high-level element into lower
level and more specific components.  Such a process can continue
indefinitely, leading to increasingly complex substructures, and
increasingly 
low-level solutions to subproblems.  
Although in NEAT the solutions 
%While NEAT does not follow exactly this
%process, since all of its solutions 
are composed of only connections and
nodes, it does provide an early example of how such a process could be
implemented.
%, thus motivating our conclusion that complexification may eventually
%have great impact on the search for the right level of abstraction.

One of the primary and most elusive goals of AI is
to create systems that \emph{scale up}.  In a sense, complexification
\emph{is} the process of scaling up.  It is the general principle
of taking a simple idea and elaborating it for broader application.
Much of AI is concerned with search, whether over 
complex multi-dimensional landscapes, or through highly-branching
trees of possibilities.  However, intelligence is as much about deciding
\emph{what space} to search as it is about searching once the proper
space has already been identified.  
%For many problems, the hard 
%question is not how to search, but rather, what should
%we be searching in?  
Currently, only humans are able to decide the proper level
of abstraction for solving many problems, 
%Added 03-2
whether it be a
simple high-level combination of general-purpose parts, 
or an extremely complex assembly of low-level components. 
%This question arises prominently in the
%debate over the proper level of abstraction for attacking particular
%problems.  
A program that can decide what level of abstraction is
most appropriate for a given domain would be a highly compelling
demonstration of Artificial Intelligence.  
This is, we believe, where complexification methods
can have their largest impact in the future. 

%For example, the search for an optimal policy
%in reinforcement learning can proceed if a gradient is established
%over the value function, and much research has gone
%into how this gradient can be established and used
%to improve control policies \cite{sutton:rlearn98}.  However, 
%humans have always chosen the \emph{representation} of the policy, whether
%it be a neural network, a state table, or something else.  
%Yet it is this representation that defines 
%whether the problem is tractable in the first place!
%On one hand, if the policy is encoded in a million-neuron
%neural network, a solution may never be found.  On the other,
%if the neural network instead contains only a single neuron, a
%sufficiently sophisticated policy may not even exist in the space
%of possible solutions.  In other words, AI is just as much about finding 
%the right representation as it is about finding the solution within
%the space of that representation.  Complexification is 
%unlike almost any other approach in that it finds \emph{both}
%the right level of representation \emph{and} the solution
%simultaneously.  Just as climbing a hill leads to a more optimal
%solution, so does increasing complexity lead to a more expressive
%representation.  It is the combination of both of these principles
%that allows the wholly autonomous synthesis of solutions.
%NEAT is a principled approach to complexification, embodying 
%the intuitive idea that novel representations need to be protected
%from premature elimination 
%in order to give them a chance to realize their full potential.

\section{Conclusion}
%\section{CONCLUSION}

The experiments presented in this paper show that
complexification of genomes
leads to continual coevolution 
of increasingly sophisticated strategies.
Three trends were found in the experiments:  (1) As evolution progresses,
complexity of solutions increases,
(2) evolution uses complexification to elaborate on 
existing strategies, and
(3) complexifying
coevolution is significantly more successful in
finding highly sophisticated strategies
than non-complexifying coevolution. 
These results suggest that complexification is a crucial
component of a successful search for complex solutions.  
%By both complexifying and optimizing, a system can discover
%both the appropriate representation for the solution
%as well as the location of the solution itself.


\acks{This research was supported in part by the National Science
%Foundation under grant NNN-NNNNNNN.  
Foundation under grant IIS-0083776 and by the Texas Higher Education
Coordinating Board under grant ARP-003658-476-2001.
Special thanks to an anonymous reviewer for 
constructive suggestions for non-complexifying comparisons.}
%%%

\appendix

\section*{Appendix A. NEAT System Parameters} \label{sec:params}

Each population had 256 NEAT networks, for a total of 512.  
The coefficients for measuring compatibility were $c_1=1.0$, 
$c_2=1.0$, and $c_3=2.0$.  The initial compatibility distance was
$\delta_t=3.0$.  However, because population dynamics can be unpredictable
over hundreds of generations, we assigned a target of 10
species.  If the number of species grew above 10, $\delta_t$ was
increased by $0.3$ to reduce the number of species.  Conversely,
if the number of species fell below 10, $\delta_t$ was
decreased by $0.3$ to increase the number of species.
The normalization factor $N$ used to compute compatibility was fixed at one.  %TODO
In order
to prevent stagnation, the lowest
performing species over 30 generations old was not allowed to
reproduce.  The champion of each species with more than five networks was 
copied into the next generation unchanged.  
There was an 80\% chance of a genome having its
connection weights mutated, in which case each 
weight had a 90\% chance of being uniformly perturbed and a 10\%
chance of being assigned a new random value.
(The system is tolerant to
frequent mutations because of the protection speciation provides.)
There was a 75\% chance that an inherited
  gene was disabled if it was disabled in either parent.
In 40\% of crossovers, the offspring inherited the \emph{average}
of the connection weights of matching genes from both parents, instead of the
connection weight of only one parent randomly.
In each generation, 25\% of offspring resulted from mutation without
crossover.  The interspecies mating rate was 0.05.  
The probability of adding a new node was 0.01 and the probability
of a new link mutation was 0.1.  
We used a modified sigmoidal transfer function, 
$\varphi(x)=\frac{1}{1+e^{-4.9x}}$, at all nodes.
These parameter values were found experimentally, and
they follow a logical pattern: Links need to be
added significantly more often than nodes, and an average weight
difference of 0.5 is about as significant as one disjoint or excess
gene.  Performance is robust to
moderate variations in these values.  
%The dynamic compatibility
%distance measure caused speciation to remain stable.
NEAT software is available in the software section at
{\textbf{http://nn.cs.utexas.edu}.
%at 
%{\textbf{http://steam.csres.utexas.edu/nn/soft-view.php?RECORD\_KEY(Software)=SoftID\&SoftID(Software)=4}}
%TODO: Is this software link reasonable?

%Risto read
\section*{Appendix B. Robot Duel Domain Coefficients of Motion} \label{sec:params2}
The turn angle $\theta$ is determined as $\theta=0.24|l-r|$, where $l$
is the output of the left
turn neuron, and $r$ is the output of the right turn neuron.
The robot moves forward a distance of $1.33f$ on the 600 by 600
board, where $f$ is the forward motion output.   
These coefficients were calibrated through experimentation to
achieve accurate and smooth motion with neural outputs between zero
and one. 

%%\setlength{\bibhang}{0.125in}  % To match CogSci97 specs
%\bibliography{nnstrings,mybib,nn}

%\bibliographystyle{nnapalike}
\bibliographystyle{nntrueapa}
%\bibliographystyle{theapa}
%%\setlength{\bibhang}{0.125in}  % To match CogSci97 specs
\bibliography{nnstrings,mybib,nn,alife,newentries}

\end{document}







