Daniel Ashlock
Representations for Evolutionary Computation in Games

Abstract: Representation is a central issue in evolutionary computation. The no free lunch theorem demonstrates that there is no intrinsic advantage in a particular algorithm when considered against complete spaces of problems. The corollary is that algorithms should be fitted to the problems they are solving. Choice of representation is the primary point in the design of an evolutionary algorithm where the designer can incorporate domain knowledge and, in effect, choose the adaptive landscape he is searching. This tutorial will introduces representations for level design, agents for playing mathematical games, and for the design of non-player characters. Time permitting, other examples of representation will be included.
The tutorial will present a survey of representations in the context of specific applications.
  • Normally, performance is the issue in choosing a representation, but for designing level maps, representation can have a large impact on the look and feel of the resulting levels. Direct and generative representations are presented as well as techniques for decomposing level design and incorporating required content.
  • Mathematical games are using in modeling human behavior. The representation chosen for the game playing agents can have a huge impact on the outcome of experiments. A variety of representations are presented including one that incorporates an abstraction of emotion and the impact on behavior is documented.
  • A representation is given for controlling the challenge rating of a non-player character. The NPC's chromosome is in the form of a wish list of capabilities which are then expressed in the presence of a budget. The budget can be used to shape or constrain the agents capabilities. Changing the price list for different capabilities can then shape the NPCs.
  • Once a representation is designed, limits can be placed on the way it is instantiated. This practice is called controlling the shape of the representation. Examples are given of the impact of shape control of representations. Shape is a simple tool for constraining the expressive power of a representation.
This tutorial assumes familiarity with evolutionary computation and games. In addition to the specific examples of application of representation to game problems, general comments on the design of effective representations will be given.
Daniel Ashlock is a Professor of Mathematics holding the Chair in Bioinformatics of the Department of Mathe-matics and Statistics at the University of Guelph in Guelph, Ontario, Canada. He is a senior member of the IEEE serving on the technical committees on games and bioinformatics. He has 240 peer-reviewed scientific publications. Dr. Ashlock serves as an associate editor for the Transactions on Evolutionary Computation, the Transactions on Computational Intelligence and Artificial Intelligence in Games, The Transaction on Computational Biology and Bioinformatics, and Biosystems. Dr. Ashlock's research interests include bioinformatics, representation in evolutionary computation, games, optimization, automatic content generation, combinatorics, and group theory.