\batchmode
\documentclass[jair,11pt]{article}
\RequirePackage{ifthen}


\usepackage{jair}


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


\citestyle{nntrueapa}


\usepackage{html}               
\usepackage{heqn}               


\HTMLset{MAX_SPLIT_DEPTH}{4}


\HTMLset{FIGURE_SCALE_FACTOR}{2.0}


\usepackage{amssymb,amsmath}


\input{nnmacros}


\jairheading{21}{2004}{63-100}{8/03}{2/04}
\ShortHeadings{Competitive Coevolution through Evolutionary Complexification}
{Stanley \& Miikkulainen}
\firstpageno{63}




\usepackage[dvips]{color}


\pagecolor[gray]{.7}

\usepackage[]{inputenc}



\makeatletter
\AtBeginDocument{\makeatletter
\input /v/filer1a/v0q030/kstanley/proposaldir/gecco2002/jairhtml.aux
\makeatother
}

\makeatletter
\count@=\the\catcode`\_ \catcode`\_=8 
\newenvironment{tex2html_wrap}{}{}%
\catcode`\<=12\catcode`\_=\count@
\newcommand{\providedcommand}[1]{\expandafter\providecommand\csname #1\endcsname}%
\newcommand{\renewedcommand}[1]{\expandafter\providecommand\csname #1\endcsname{}%
  \expandafter\renewcommand\csname #1\endcsname}%
\newcommand{\newedenvironment}[1]{\newenvironment{#1}{}{}\renewenvironment{#1}}%
\let\newedcommand\renewedcommand
\let\renewedenvironment\newedenvironment
\makeatother
\let\mathon=$
\let\mathoff=$
\ifx\AtBeginDocument\undefined \newcommand{\AtBeginDocument}[1]{}\fi
\newbox\sizebox
\setlength{\hoffset}{0pt}\setlength{\voffset}{0pt}
\addtolength{\textheight}{\footskip}\setlength{\footskip}{0pt}
\addtolength{\textheight}{\topmargin}\setlength{\topmargin}{0pt}
\addtolength{\textheight}{\headheight}\setlength{\headheight}{0pt}
\addtolength{\textheight}{\headsep}\setlength{\headsep}{0pt}
\setlength{\textwidth}{349pt}
\newwrite\lthtmlwrite
\makeatletter
\let\realnormalsize=\normalsize
\global\topskip=2sp
\def\preveqno{}\let\real@float=\@float \let\realend@float=\end@float
\def\@float{\let\@savefreelist\@freelist\real@float}
\def\liih@math{\ifmmode$\else\bad@math\fi}
\def\end@float{\realend@float\global\let\@freelist\@savefreelist}
\let\real@dbflt=\@dbflt \let\end@dblfloat=\end@float
\let\@largefloatcheck=\relax
\let\if@boxedmulticols=\iftrue
\def\@dbflt{\let\@savefreelist\@freelist\real@dbflt}
\def\adjustnormalsize{\def\normalsize{\mathsurround=0pt \realnormalsize
 \parindent=0pt\abovedisplayskip=0pt\belowdisplayskip=0pt}%
 \def\phantompar{\csname par\endcsname}\normalsize}%
\def\lthtmltypeout#1{{\let\protect\string \immediate\write\lthtmlwrite{#1}}}%
\newcommand\lthtmlhboxmathA{\adjustnormalsize\setbox\sizebox=\hbox\bgroup\kern.05em }%
\newcommand\lthtmlhboxmathB{\adjustnormalsize\setbox\sizebox=\hbox to\hsize\bgroup\hfill }%
\newcommand\lthtmlvboxmathA{\adjustnormalsize\setbox\sizebox=\vbox\bgroup %
 \let\ifinner=\iffalse \let\)\liih@math }%
\newcommand\lthtmlboxmathZ{\@next\next\@currlist{}{\def\next{\voidb@x}}%
 \expandafter\box\next\egroup}%
\newcommand\lthtmlmathtype[1]{\gdef\lthtmlmathenv{#1}}%
\newcommand\lthtmllogmath{\lthtmltypeout{l2hSize %
:\lthtmlmathenv:\the\ht\sizebox::\the\dp\sizebox::\the\wd\sizebox.\preveqno}}%
\newcommand\lthtmlfigureA[1]{\let\@savefreelist\@freelist
       \lthtmlmathtype{#1}\lthtmlvboxmathA}%
\newcommand\lthtmlpictureA{\bgroup\catcode`\_=8 \lthtmlpictureB}%
\newcommand\lthtmlpictureB[1]{\lthtmlmathtype{#1}\egroup
       \let\@savefreelist\@freelist \lthtmlhboxmathB}%
\newcommand\lthtmlpictureZ[1]{\hfill\lthtmlfigureZ}%
\newcommand\lthtmlfigureZ{\lthtmlboxmathZ\lthtmllogmath\copy\sizebox
       \global\let\@freelist\@savefreelist}%
\newcommand\lthtmldisplayA{\bgroup\catcode`\_=8 \lthtmldisplayAi}%
\newcommand\lthtmldisplayAi[1]{\lthtmlmathtype{#1}\egroup\lthtmlvboxmathA}%
\newcommand\lthtmldisplayB[1]{\edef\preveqno{(\theequation)}%
  \lthtmldisplayA{#1}\let\@eqnnum\relax}%
\newcommand\lthtmldisplayZ{\lthtmlboxmathZ\lthtmllogmath\lthtmlsetmath}%
\newcommand\lthtmlinlinemathA{\bgroup\catcode`\_=8 \lthtmlinlinemathB}
\newcommand\lthtmlinlinemathB[1]{\lthtmlmathtype{#1}\egroup\lthtmlhboxmathA
  \vrule height1.5ex width0pt }%
\newcommand\lthtmlinlineA{\bgroup\catcode`\_=8 \lthtmlinlineB}%
\newcommand\lthtmlinlineB[1]{\lthtmlmathtype{#1}\egroup\lthtmlhboxmathA}%
\newcommand\lthtmlinlineZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetinline}
\newcommand\lthtmlinlinemathZ{\egroup\expandafter\ifdim\dp\sizebox>0pt %
  \expandafter\centerinlinemath\fi\lthtmllogmath\lthtmlsetmath}
\newcommand\lthtmlindisplaymathZ{\egroup %
  \centerinlinemath\lthtmllogmath\lthtmlsetmath}
\def\lthtmlsetinline{\hbox{\vrule width.1em \vtop{\vbox{%
  \kern.1em\copy\sizebox}\ifdim\dp\sizebox>0pt\kern.1em\else\kern.3pt\fi
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\lthtmlsetmath{\hbox{\vrule width.1em\kern-.05em\vtop{\vbox{%
  \kern.1em\kern0.8 pt\hbox{\hglue.17em\copy\sizebox\hglue0.8 pt}}\kern.3pt%
  \ifdim\dp\sizebox>0pt\kern.1em\fi \kern0.8 pt%
  \ifdim\hsize>\wd\sizebox \hrule depth1pt\fi}}}
\def\centerinlinemath{%
  \dimen1=\ifdim\ht\sizebox<\dp\sizebox \dp\sizebox\else\ht\sizebox\fi
  \advance\dimen1by.5pt \vrule width0pt height\dimen1 depth\dimen1 
 \dp\sizebox=\dimen1\ht\sizebox=\dimen1\relax}

\def\lthtmlcheckvsize{\ifdim\ht\sizebox<\vsize 
  \ifdim\wd\sizebox<\hsize\expandafter\hfill\fi \expandafter\vfill
  \else\expandafter\vss\fi}%
\providecommand{\selectlanguage}[1]{}%
\makeatletter \tracingstats = 1 


\begin{document}
\pagestyle{empty}\thispagestyle{empty}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength hsize=\the\hsize}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength vsize=\the\vsize}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength hoffset=\the\hoffset}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength voffset=\the\voffset}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength topmargin=\the\topmargin}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength topskip=\the\topskip}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength headheight=\the\headheight}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength headsep=\the\headsep}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength parskip=\the\parskip}\lthtmltypeout{}%
\lthtmltypeout{latex2htmlLength oddsidemargin=\the\oddsidemargin}\lthtmltypeout{}%
\makeatletter
\if@twoside\lthtmltypeout{latex2htmlLength evensidemargin=\the\evensidemargin}%
\else\lthtmltypeout{latex2htmlLength evensidemargin=\the\oddsidemargin}\fi%
\lthtmltypeout{}%
\makeatother
\setcounter{page}{1}
\onecolumn

% !!! IMAGES START HERE !!!

\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure39}%
\begin{figure}  \centering
\pspic[\psline]{400pt}{!}{alter_elab2}        
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure88}%
\begin{figure}  \centering
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure100}%
\begin{figure}  \centering
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsection}
\refstepcounter{equation}
\refstepcounter{equation}
\stepcounter{subsection}
\stepcounter{section}
{\newpage\clearpage
\lthtmlfigureA{figure166}%
\begin{figure}  \centering
  \pspic[\psline]{250pt}{!}{duel_redraw}
\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. 
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}}.
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure175}%
\begin{figure}  \centering
  \pspic[\psline]{350pt}{!}{DUELNET3}
  \vspace{-3.9in}
\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. 
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage\clearpage
\lthtmlfigureA{figure241}%
\begin{figure}  \centering
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure270}%
\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 
$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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsection}
\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure305}%
\begin{figure}
% latex2html id marker 305
  \centering
\pspic[\psline]{300pt}{!}{superdom}
  \titledcaption[\psline]{fg:superdom}
  {The Best Complexifying Network}
  {
\par
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. 
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

{\newpage\clearpage
\lthtmlfigureA{figure315}%
\begin{figure}\centering
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure328}%
\begin{figure}  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_10n}
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure339}%
\begin{figure}
% latex2html id marker 339
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_5n}
\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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure354}%
\begin{figure}
% latex2html id marker 354
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_best}
\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}. 
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}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
{\newpage\clearpage
\lthtmlfigureA{figure366}%
\begin{figure}
% latex2html id marker 366
  \centering
  \pspic[\psline]{330pt}{!}{complex_vs_red2}
\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.
\vspace{-\baselineskip}% Make figure a little tighter
    }
\end{figure}%
\lthtmlfigureZ
\lthtmlcheckvsize\clearpage}

\stepcounter{subsubsection}
\stepcounter{section}
\stepcounter{section}
\appendix

\end{document}
