Sunday, December 28, 2008

Automatic Game Design

One of the papers I presented at the recent CIG conference is called "An Experiment in Automatic Game Design". Designing games automatically, what's that all about? I thought I'd take a blog post to explain the main ideas in the paper (and it really is mostly a proof-of-concept paper).

What we're trying to do is search a space of game rules for rule sets that constitute fun games. This immediately raises two questions: how do you define and search a space of game rules, and how can you measure whether a game is fun?

We decided to create set of "meta-rules" or "axioms" that define a space of grid-based games, where one of the games that could be created would be a simple version of Pac-man. The game arena ("maze") is very simple (just a few walls) and is the same for all games. The player controls an agent (the purple blob in the figure below) and can move one block up, down, left or right every time step. Apart from the agent, there are a number of red, green and blue "things" in a game. They are deliberately called "things" and not opponents, food, mines, collaborators etc. because their exact relation to the player is decided by the rules of the game.

The rules of any particular game is defined by:

  • The number of red, green and blue things
  • A table of collision effects: what happens when a thing of one colour occupies the same space as a thing of another colour or with the agent - decrementing or incrementing the score, teleportation and/or death (usually different effects for the two parts in a collision)
  • Movement logics - how things of different colours move (random, clockwise, counter-clockwise)
  • The score the player has to reach in order to win the game
  • The time the player has to reach this score before losing the game

In this space, a Pacman-like could be defined using e.g. red things as pills (increments score and disappears when the agent moves over them) and green things as ghosts (kills the player when he touches them, moves randomly). But many other elements are possible, including things that eat other things, teleportation etc.

Here is a screenshot from a little example game:

It should be pretty straightforward to see how game rules can be represented to be evolved: just encode them as e.g. an array of integers, and define some sensible mutation and possibly recombination operators. (In this particular case, we use a simple generational EA without crossover.) For other rule spaces, some rules might be more like parameters, and could be represented as real numbers.

What's the much trickier question is the fitness function. How do you evaluate the fitness of a particular set of game rules? What we want is a fitness function for rulesets that somehow approximates how fun it would be for a human to play a game with that particular ruleset.

In our previous experiments on evolving racing tracks for car games, we used various measures of how a neural network-based controller drove on the track as the fitness function for tracks. In the case of evolving complete games, we can't really judge the behaviour of particular agent on the ruleset, as there is no agent that can play every game.

Our solution is to use learnability as a predictor of fun. A good game is one that is not winnable by a novice player, but which the player can learn to play better and better over time, and eventually win; it has a smooth learning curve. This can be seen as an interpretation of Raph Koster's "Theory of Fun for Fame Design", or of Juergen Schmidhuber's curiosity principle.

Somewhat more technically, our fitness function proceeds in two stages: first it tries to play the game using only random actions. If a random player can win a the game, the ruleset (=the game) is assigned a negative fitness. Otherwise, an evolutionary algorithm is used to try to learn a neural network that plays the game (using the score of the game as fitness function). The fitness of the game then becomes the best fitness found by the "inner" evolutionary algorithm after a certain number of generations.

The important and novel idea here is that a learning algorithm is used as a fitness measure inside another learning algorithm. We call this a dynamic fitness function, to discriminate it from the static fitness functions we used in our papers on track evolution and which did not assume that the agent was learning anything.

Using this setup we managed to evolve a couple of games - none of them very interesting in itself, but together a proof that the idea works. All the details and much more background is in the paper, which is available online.

There is a huge number of questions left to answer - are the generated games with high fitness really more fun for humans than those that have low fitness? Does the evolutionary algorithm learn to play games like a human? Does the approach scale up to more complex games, and different sorts of rule spaces? Well, that means there's lots of interesting research left to do...

Friday, December 26, 2008

CIG 2008 Conference Report

I'm still jetlagged from coming home from CIG 2008 in Perth four days ago (Perth-Singapore-London-Copenhagen is a 26 hours trip from first takeoff to last landing). But it was worth it. As usual, I find the CIG conferences enormously interesting and inspiring. Mostly because it's Computational Intelligence and Games is as much my "core" research area as it gets.

It's true that the acceptance rate it's a bit high, and there are quite a few papers which might not even be good science, in the sense of providing systematic experiments with statistically valid conclusions. In fact, someone who came from the broader CI or ML community and was not specifically interested in the application areas would probably complain about this. (However, it strikes me that most people can easily be made enthusiastic about games when you talk to them a bit... in striking contrast to some other common CI application areas such as scheduling or traffic flow optimization.)

We've beem discussing whether we should lower the acceptance rate, but I don't think we should. At least not yet. The main reason is that the research community is still quite small and we want it to grow. Another reason is that don't really believe in being too harsh. Reviewers can usually tell whether a paper is crap or not, but it's very hard to tell whether it's a seminal contribution. That's for posterity to judge, and to be approximated by the number of citations the paper has amassed after ten years or so. Conferences that only accept 25% or so of papers are, in my opinion, bound to make a rather arbitrary selection. Besides, we now have TCIAIG for publishing the cream of CIG research.

Enough about this, and back to the conference. There were keynotes representing both the ivory-tower variety of CIG research (Jonathan Schaeffer on solving Checkers), the industry perspective (Jason Hutchen, whose keynote I missed due to the conference banquet being the day before. Yes, free drinks) and the harmonious marriage of the two (Penny Sweetser on Emergence in Games).

One paper I particularly liked was Bobby Bryant and Matt Parker on learning to play Quake II using visual inputs only. I think their work is very relevant both for studying the evolutionary emergence of complex intelligence (seeing the FPS as a more advanced robot simulator) and for developing more lifelike NPC behaviour (e.g. aiming behaviour). The paper is not online yet, but here is a previous paper of theirs (NB their results are not very impressive yet, it's the idea I like.)

As for my own contributions, I gave a tutorial (with Georgios Yannakakis) on "Measuring and Optimizing Player Satisfaction". I also presented three papers, one on An Experiment in Automatic Game Design, one on Generating Diverse Opponents with Multiobjective Evolution and one detailing The WCCI 2008 Simulated Car Racing Competition. I hope to find time to write posts on this blog explaining the concepts behing the first two of these papers sometime soon, as I think they are really quite cool myself. I also presented the results of the CIG installment of the ongoing car racing competitions.

This post is already long enough, so I'll stop writing here. What can I say - if you are interested in games and AI/CI, you should have been there! And you should definitely come to the next CIG in Milan, Italy, September 2009. I'll be involved with the organization of that one, so I'll be writing more about it!