The last half year I've been doing working on a Master's Thesis, mostly preliminary research work, but it never occurred to me to use this as an excuse to start using my blog more actively again. I've now decided to start holding a sort of work log here, as a place to collect my thoughts about the progress of the thesis, maybe get some feedback or discussion and maybe even teach someone something. This might also help structure my work in the same way the "review" structures the GTD process.

This first blog post is not going to be a work log for my project, but rather an introduction to the project (as it is currently formulated, which may change) that I am working on and the tech that is used. I intend to create my work log posts on Wednesdays, to coincide with my GTD review, so the first work log post is going to be next Wednesday.

Introduction

The tentative title of my thesis is "Evolving entertaining game adversaries using ADATE" which probably tells you very little. In more descriptive terms the aim of the thesis to use artificial evolution to create the artificial intelligence for a game's opponents, with the aim of creating a more entertaining game. This will be accomplished using a system for doing such artificial evolution named ADATE created by one of my supervisors, Dr. J. Roland Olsson.

The hypothesis I'm working from is that variation in game adversaries would create a more entertaining game than if all the adversaries behaved in a similar way, and that using artificial evolution makes it easy to create diverse AI for opponents that fulfill the criteria set for them, in this case entertainment value.

The game

At this point you might wonder which game I will be using. Sadly this part is perhaps not as fancy as others, I won't be making new opponent behaviors for a game like Skyrim or anything of that complexity. The game I will be using will be a very simple "predator-prey" game akin to Pacman or other games where the aim is basically to avoid a small amount of enemies that are chasing you and fulfill a goal.

I don't have any more specific details about the game I will be using, but this is the focus of my current work, and will most likely be the topic of next week's work log, where I will cover how to integrate the game into ADATE, and other such fancy things.

Artificial evolution and ADATE

Of course, most people will not know what this mysterious ADATE system is or what artificial evolution is all about, so I'm going to take some time to describe. I'm going to treat artificial evolution in the context of the ADATE system, which might gloss over certain parts of the more general description, but these are easily looked up if one is more interested.

First off, ADATE's name is actually a decently good description of what it actually does. The name stands for Automatic Design of Algorithms Through Evolution, which is exactly what it does. More specifically, it uses artificial evolution to automatically create program code in the language SML (more specifically, a subset of this named ADATE-ML), based on some input data and a function which is used to rate the performance of the evolved algorithms.

General description of artificial evolution

Artificial evolution is a technique that takes what we know about the process of biological evolution and applies it to programming. In this process, the "species" are pieces of program code, data or any other artificial thing, often termed individuals, and "genes" are usually small pieces of each individual that are considered to be the smallest division, in program code this could be a single instruction, in a picture this could be a pixel, etc.

This population of individuals are run through a "cycle of life" where the individuals are reproduced to create new individuals which are slightly different from their parent(s), through genetic recombination, mutation or other techniques which are inspired by biological reproduction. The new individuals are then ranked according to what is called a fitness function, which is a function that takes the individual and anything else it needs (such as input to the system), and gives it a rating.

After enough reproduction, the population is trimmed to a certain size by removing the worst performing individuals, and the process starts over, and is run over and over until the system is stopped, either because good enough individuals have been created, a time limit has been exceeded, or any other reason, really.

How ADATE works

ADATE takes this process and specializes it. As mentioned before, the individuals are pieces of SML code, and the genes are individual instructions of this code. In ADATE new individuals are created only through a form of mutation, there is no genetic recombination. The mutation process works as such: the parent individual has one or more alterations applied to it, picked from a predefined set of possible alterations. (things such as changing one variable/value to another random one, adding a new function call, adding an if-else, and so on)

ADATE starts this process from a specification which defines a set of input values, a fitness function that rates the performance of individuals over the input values, a function that serves as the starting point for creating the individuals (often just an empty function for maximum randomness), and various pieces of support code that the individuals and fitness function might need.

Other than all of this, ADATE's cycle of is very similar, it uses some more specialized ways of managing its population, and decides when to stop creating new individuals based on the time expired and how "complex" the individuals were, but these are all minor details which aren't worth going into here.