Things are going well so far. Almost two weeks into the new year and the new version of ANGELINA (which is version three, not two as I said before) is coming along well. It can read basic game descriptions in YAML and then turn that into a playable game, with multiple levels, real objectives, and so on. It’s not hugely pretty but the code itself is quite flexible – sufficiently so that I’m going to try and release part of it openly as soon as I can, in case anyone wants to take a peek or, god forbid, try and use it themselves.
Once the engine is finished, we come onto the thornier matter of actually evolving games. I want to take my time here to avoid a repeat of the Metroidvania project I did at the end of last year. I rushed ahead, didn’t analyse at each step, and ended up with a messier project as a result. So we’re going to take this slowly, first building up a system that can analyse definition and unit operation files (that is, the rough outline of the game rules, but with no level-specific info), possibly evolve new ones, and offer new information it infers from reading these design files. I’ll keep you posted on that latter point in particular, as it involves an interesting AI challenge that I’m not sure how I’m going to solve yet.
Consider these rules from Space Invaders (the YAML for which you can find here):
Aliens shoot bombs.
Bombs travel downwards.
Bombs kill the player.
These specify one of the things about Space Invaders that makes it a game – there are opponents that generate threat (in the form of bombs). It hides a bit of level design information as well, though, namely:
Aliens start above the player.
We know that anyway, because we’ve played Space Invaders before, but ANGELINA doesn’t know that, and without that information it’ll spend a long time trying designs where the aliens spawn underneath the player, or next to it, rather than above it. Knowing that piece of information can save ANGELINA time and help improve the quality of the games it designs. But how do we get at it? How do we go from the three rules I wrote above, to the fact about the player/alien locations?
Here’s a great paper from last year’s International Conference on Computational Creativity by Adam Smith and Michael Mateas (that last name might ring a bell since Mateas was one of the two chaps behind the superb drama-game-research piece Façade from way back in 2005. Incidentally, Mateas’ name is also attached to Prom Week, another great-looking AI piece that’s an IGF finalist this year). One of the interesting ideas in the paper, which is really explored more fully in other publications by these authors, is the notion that game design is a lot about juggling logical concepts around, and can be thought of as a scientific or inductive process, almost.
What do we mean by this? There are two main implications of that statement. Smith and Mateas in particular are talking about how game designers can learn from playtesting and prototypes, but what we’re interested in is this other idea – that games have an order to them, and that we can define this rigidly for an AI such as ANGELINA to manipulate. With our Space Invaders example, we are trying to derive the fact that the player ship spawns underneath the aliens. This involves thinking about things like logic, location, change over time. Facts like aliens shoot bombs give us information about the initial state of objects in the world (so we know where bombs are when they come into the game). Facts like bombs travel downwards give us transformational information about how an object changes between states. Using initial state information and rules that decide how you change between one state and the next, you can map out all potential paths of an object through the game world (here it’s pretty trivial – the bomb only moves one way).
Using facts like this might allow the application of various AI reasoning tools to deduce things about our game designs. My supervisor, Simon Colton, worked on a system called HR for a large portion of his early research career (and indeed HR still affects much of what we do today in the group). HR is an automated discovery tool, designed to look at systems of knowledge and information and draw interesting and novel conclusions about them. It was originally applied to number theory, starting out rediscovering existing ideas like Goldbach’s Conjecture simply from being given an understanding of integers and arithmetic operations. HR is built not just to draw conclusions from systems, but to understand which of these theorems, conclusions or conjectures are interesting or useful to people. That isn’t so far off what we want to do with ANGELINA and the game descriptions.
So, lots to do. Starting next week I’m going to try evolving small game designs using me as the fitness function (something I’ve not tried before). I’ll let you know how it goes. No news on the EvoGAMES paper yet, but I’ll notify people through Twitter when it comes.