AbstractThis paper describes a system for the evolution andco-evolution of virtual creatures that compete inphysically simulated three-dimensional worlds. Pairsof individuals enter one-on-one contests in whichthey contend to gain control of a common resource.The winners receive higher relative fitness scoresallowing them to survive and reproduce. Realisticdynamics simulation including gravity, collisions,and friction, restricts the actions to physically plausi-ble behaviors.The morphology of these creatures and the neuralsystems for controlling their muscle forces are bothgenetically determined, and the morphology andbehavior can adapt to each other as they evolvesimultaneously. The genotypes are structured asdirected graphs of nodes and connections, and theycan efficiently but flexibly describe instructions forthe development of creatures’ bodies and control sys-tems with repeating or recursive components. Whensimulated evolutions are performed with populationsof competing creatures, interesting and diverse strate-gies and counter-strategies emerge.1 IntroductionInteractions between evolving organisms are generallybelieved to have a strong influence on their resulting com-plexity and diversity. In natural evolutionary systems themeasure of fitness is not constant: the reproducibility of anorganism depends on many environmental factors includingother evolving organisms, and is continuously in flux. Com-petition between organisms is thought to play a significantrole in preventing static fitness landscapes and sustainingevolutionary change.These effects are a distinguishing difference betweennatural evolution and optimization. Evolution proceeds withno explicit goal, but optimization, including the genetic algo-rithm, usually aims to search for individuals with the highestpossible fitness values where the fitness measure has beenpredefined, remains constant, and depends only on the indi-vidual being tested.The work presented here takes the former approach. Thefitness of an individual is highly dependent on the specificbehaviors of other individuals currently in the population.The hope is that virtual creatures with higher complexity andmore interesting behavior will evolve than when applyingthe selection pressures of optimization alone.Many simulations of co-evolving populations have beenperformed which involve competing individuals [1,2]. Asexamples, Lindgren has studied the evolutionary dynamicsof competing game strategy rules [14], Hillis has demon-strated that co-evolving parasites can enhance evolutionaryoptimization [9], and Reynolds evolves vehicles for compe-tition in the game of tag [19]. The work presented hereinvolves similar evolutionary dynamics to help achieveinteresting results when phenotypes have three-dimensionalbodies and compete in physically simulated worlds.In several cases, optimization has been used to automat-ically generate dynamic control systems for given two-dimensional articulated structures: de Garis has evolvedweight values for neural networks [6], Ngo and Marks haveapplied genetic algorithms to generate stimulus-responsepairs [16], and van de Panne and Fiume have optimized sen-sor-actuator networks [17]. Each of these methods hasresulted in successful locomotion of two-dimensional stickfigures.The work presented here is related to these projects, butdiffers in several respects. Previously, control systems weregenerated for fixed structures that were user-designed, buthere entire creatures are evolved: the evolution determinesthe creature morphologies as well as their control systems.The physical structure of a creature can adapt to its controlsystem, and vice versa, as they evolve together. Also, herethe creatures’ bodies are three-dimensional and fully physi-cally based. In addition, a developmental process is used togenerate the creatures and their control systems, and allowssimilar components including their local neural circuitry tobe defined once and then replicated, instead of requiringeach to be separately specified. This approach is related to L-systems, graftal grammars, and object instancing techniques[8,11,13,15,23]. Finally, the previous work on articulatedstructures relies only on optimization, and competitionsbetween individuals were not considered.Evolving 3D Morphology and Behavior by CompetitionKarl SimsThinking Machines Corporation(No longer there)Published in: Artificial Life IV Proceedings, ed. by R. Brooks & P. Maes, MIT Press, 1994, pp28-39.A different version of the system described here has alsobeen used to generate virtual creatures by optimizing for spe-cific defined behaviors such as swimming, walking, and fol-lowing [22].Genotypes used in simulated evolutions and geneticalgorithms have traditionally consisted of strings of binarydigits [7,10]. Variable length genotypes such as hierarchicalLisp expressions or other computer programs can be usefulin expanding the set of possible results beyond a predefinedgenetic space of fixed dimensions. Genetic languages suchas these allow new parameters and new dimensions to beadded to the genetic space as an evolution proceeds, andtherefore define rather a hyperspace of possible results. Thisapproach has been used to genetically program solutions to avariety of problems [3,12], as well as to explore procedurallygenerated images and dynamical systems [20,21].In the spirit of unbounded genetic languages, directedgraphs are presented here as an appropriate basis for a gram-mar that can be used to describe both the morphology andneural systems of virtual creatures. The level of complexityis variable for both genotype and phenotype. New featuresand functions can be added to creatures or existing onesremoved, as they evolve.The next section of this paper describes the environmentof the simulated contest and how the competitors are scored.Section 3 discusses different simplified competition patternsfor approximating competitive environments. Sections 4 and5 present the genetic language that is used to represent crea-tures with arbitrary structure and behavior, and section 6summarizes the physical simulation techniques used. Section7 discusses the evolutionary simulations including the meth-ods used for mutating and mating directed graph genotypes,and finally sections 8 and 9 provide results, discussion, andsuggestions for future work.2 The ContestFigure 1 shows the arena in which two virtual creatures willcompete to gain control of a single cube. The cube is placedin the center of the