Genetically Programming Patterns

Open Computer Science Games Engineering eXtended Artifical Intelligence Bachelor Master Project Thesis Games Research Lab

Background

There are different ways to simulate real-world phenomena. Consider, for instance, the ghosts in the video game pac-man. They see pac-man when moving along the same path segment and then start chasing him. These non-player characters are modelled as so-called agents equipped with sensors, actuators and controllers that connect the received information to the resulting actions. Agent-based modelling is a very wide-spread approach to modelling and simulating various real-world phenomena—from the interaction of biological cells over the simulation of crowd movement, or population-wide happiness. All the empirically unearthed aspects of real-world agents can be reflected by their digital counterparts. However, since the interactions of agents are so open-ended, their degrees of interaction so great, the ensuing simulations are quickly computationally rather costly.

Task

Based on the background explained above, in order to arrive at viable computational loads, the degrees of freedom have to be systematically reduced - but only in such a way that relevant simulated results would not be impeded. To this end, we need to learn the patterns that occur. We can do this by observing, recording, and comparing series of simulation states. But we can also attempt this by guessing a pattern and seeing whether it’s applicable anywhere. In case it is, even if only partially, we could modify this guessed pattern a little to fit even better. Guessing a set of patterns and evolving it as a group can be done by means of Genetic Programming (GP). This is the task of this project/thesis work. You need to setup a simulation in which patterns at various spatio-temporal scales occur, apply and evaluate GP to evolve a program that captures the patterns that unfold in the simulation.

In ordert to ensure a smooth and easy foundation for your experiments, I suggest you:

• rely on a cellular automaton (find an existing implementation or do it yourself),
• configure it to yield patterns of various levels of complexity (recipies can be the rules of Conways’ Game of Life and other patterns can be looked up in Wolfram’s book, see below).

For the GP training, I would recommend using GPQUICK (see link and references below). Wrt to the evaluation, it’s most exciting to learn what kind of GP-evolved model can match which patterns and how well. So these would be my primary questions. Secondarily, I would be interested in the evolutionary process and its impact on the evolved specimen, including, e.g., the consideration of local optima, continued improvement, and bloat.

Literature

• Langdon, W. B., & Banzhaf, W. (2019, July). Continuous long-term evolution of genetic programming. In Artificial Life Conference Proceedings (pp. 388-395). One Rogers Street, Cambridge, MA 02142-1209, USA journals-info@ mit. edu: MIT Press.
• https://dl.acm.org/doi/10.1145/3319619.3326770 (the supplementary material contains the code base of GPQUICK)
• Wolfram, S. (2002). A new kind of science (Vol. 5, p. 130). Champaign, IL: Wolfram media.
• http://www.scholarpedia.org/article/Game_of_Life

Contact Persons at the University Würzburg