Togelius

Help us test new strategy game ideas

2011-07-14T15:03:00.003+02:00

We have two new playtests/surveys going on, this time about strategy games. Those of us working on AI in the Center for Computer Games Research are interested in creating adaptive mechanisms for games, and automating the generation of various forms of game content. For strategy games, we are working on automatic map generation, automatic rule generation and AI techniques for competently playing strategy games with little domain information.

What we want from you is some help with evaluating the results of our recent endeavours.

The first survey is about automatically generated rulesets and general AI. If you take this survey, you will play a tutorial scenario and then two different (very short) scenarios in a strategy game you have never seen before. You will then be asked which one you prefer, which opponent AI was best, and a couple of other relevant questions. It will take you about 10 minutes. Click here to participate in the playtest survey.

You can also read the paper describing some of the previous research leading up to the system used in the current playtest. However, you are only allowed to read the paper after you've taken the survey. No cheating!

The second survey is about automatically generated maps for the classic real-time strategy game StarCraft. If you take this survey, you will be asked to look at ten different StarCraft maps and judge their relative qualities. It helps if you have played StarCraft, but it's not necessary. This survey will take you about 5 minutes to complete. Click here to take part in the StarCraft survey.

When you're finished, you could reward yourself with reading a paper on how the maps were created (though the current version of the system has evolved a bit). But only after you've taken the survey, or you'll bias the results...

Seriously though: thanks a lot for helping us with this!

On the Game AI versus traditional AI debate

2011-07-13T01:00:00.003+02:00

Luke Dicken wrote a very nice blog post the other day on the differences between how AI is viewed in academia (and among students) and in the game industry. He focuses on the real-time requirements of game AI, and how little processing power most games make available for AI. He also talks about how NPC behaviour in games needs to be entertaining, not just high-performing, and reminds the reader that in striking contrast to e.g. AI for robots, game AI is allowed to cheat if it makes the game better.

Kevin dill wrote a response post where he points out that "traditional AI" is simply trying to solve very different problems than those faced by AI in games. Far from being simplistic and primitive, the techniques devised specifically within game AI are well suited to their specific purpose: reliably providing interesting NPC behaviour, while being understandable and moddable by designers. Perhaps academic AI research should take a hint or two from industrial game AI, rather than the opposite.

I am not fundamentally disagreeing with anything Luke or Kevin say. I think they both make several good points. However, I'd like to point out that I have a rather different and, I think, broader perspective on what game AI is. Both posts make implicit assumptions on what games are and what AI is, which I think are limiting.

The main game examples used by Luke and Kevin are Red Dead Redemption, Dragon Age, Battlefield Bad Company 2 and Left 4 Dead. While these are impressive games, they are all representatives of a pretty small subspace of gaming: AAA first-person story-driven games with a real-time component and graphics that require them to run on a home console or computer. They are also all targeted at a classic "hardcore gamer" audience. These are the sort of games that we typically talk about when discussing games, and these are the sort of games that everybody wants to work on. But not the games that most people play. It's like if in the automotive industry, everybody would want to work on the next Porsche, while most people drive a Toyota.

Bejeweled, FarmVille and Diner Dash don't have a first-person perspective, don't have complex graphics and don't have a story in the same sense as the games above. Yet as far as I know, they have more players than those games. Importantly, they don't have NPCs that need to be controlled by AI, but still they present a number of interesting AI problems. Even traditional hardcore strategy games like Civilization, StarCraft or Total War present hard AI problems which are only insufficiently solved by the techniques used in the game industry.

The other limiting assumption is that AI is used for controlling NPC behaviour. In fact, this is only one of many applications for the bountiful toolbox of techniques found in artificial intelligence. AI techniques can also be used to generate game content (levels, maps, rules, puzzles etc), model players, adapt various aspects of the game (such as the difficulty or the reward schedule), match players in online games, control artificial economy, debug game mechanics or implementations, and so on.

Between all the myriad types of games out there and the multitude of interesting AI problems within them, I feel there's more than enough to work on even for an academic like me. Real-time pathfinding and planning for FPS and RTS games is all great, and I look forward to playing the results, but I'm happy to see someone else doing that specific work.

If you're interested in the "other" game AI work I'm involved, you might want to read our recent survey papers on generating game content and on adapting games based on player models.

New Infinite TD playtest

2011-07-09T18:55:00.002+02:00

Elvis has now done significant additional development on his Infinite Tower Defense game. Please help us by playing the game and answering

Infinite Tower Defence: please help us playtest the prototype

2011-05-01T14:51:00.002+02:00

My student Elvis Alistar has developed a first version of his "Infinite Tower Defence" game, which aims to continuously creating personalized challenges in response to your playing style. The game is an application of experience-driven procedural content generation to tower defence games, a very popular yet relatively complex and cerebral genre of casual strategy games.

We are currently looking for playtesters. Please head over to http://itu.dk/people/elal/ and play a few rounds of the game, and then answer our questionnaire about it. Those who provide best feedback will be included in the credits for the game!

Second CfP for CIG 2011. Yes, the deadline has been extended!

2011-03-03T11:52:00.000+01:00

Second call for papers -- deadline extended!
Call for tutorial proposals

2011 IEEE Conference on Computational Intelligence and Games

COEX, Seoul
South Korea, August 31-September 3, 2011

http://sclab.yonsei.ac.kr/~cig

Games have proven to be an ideal domain for the study of computational intelligence as not only are they fun to play and interesting to observe, but they provide competitive and dynamic environments that model many real-world problems. Additionally, methods from computational intelligence promise to have a big impact on game technology and development, assisting designers and developers and enabling new types of computer games.

The 2011 IEEE Conference on Computational Intelligence and Games brings together leading researchers and practitioners from academia and industry to discuss recent advances and explore future directions in this quickly moving field.

Topics of interest include, but are not limited to, the following:

* Learning in games
* Coevolution in games
* Neural-based approaches for games
* Fuzzy-based approaches for games
* Player/Opponent modeling in games
* CI/AI-based game design
* Multi-agent and multi-strategy learning
* Applications of game theory
* CI for Player Affective Modeling
* Intelligent Interactive Narrative
* Imperfect information and non-deterministic games
* Player satisfaction and experience in games
* Theoretical or empirical analysis of CI techniques for games
* Comparative studies and game-based benchmarking
* Computational and artificial intelligence in:
o Video games
o Board and card games
o Economic or mathematical games
o Serious games
o Augmented and mixed-reality games
o Games for mobile platforms

The conference will consist of a single track of oral presentations, tutorial and workshop/special sessions, and live competitions. The proceedings will be placed in IEEE Xplore, and made freely available on the conference website after the conference.

IMPORTANT DATES:
Tutorial and special session proposal deadline: March 15, 2011
Paper submission deadline: March 30, 2011 -- extended!
Decision notification: May 15, 2011
Camera-ready submission: June 15, 2011
Conference dates: August 31-September 3, 2011

General Chair : Sung-Bae Cho
Program Co-Chairs: Simon Lucas and Phllip Hingston
Competitions Chair: Julian Togelius
Publicity Chair: Clare Bates Congdon
Proceedings Chair: Mike Preuss
Tutorials and special sessions chair: Georgios Yannakakis
Local Chairs: Kyung-Joong Kim, Kyu-Baek Hwang, Eun-Youn Kim

CIG 2011

2011-01-25T11:06:00.003+01:00

The 2011 IEEE Conference on Computational Intelligence and Games will run in Seoul, Korea, August 31-September 3.

This conference builds on the massive success of last year's conference, and we hope even to surpass the quantity and quality of that conference. So if you're at all interested in CI and/or AI in games, you need to be there.

Submission deadline March 15.

Super Mario data collection - play a game and contribute to science!

2011-01-24T15:51:00.004+01:00

Don't ask what Super Mario can do for you. Ask what he can do for us. And what you can do for science.

We're running two separate data collection experiments using the Infinite Mario codebase. Both are connected with modelling player preferences and procedurally generating game levels.

If you have a few minutes to spare, please head over to this page and play a few short levels of Super Mario Bros and answer some simple questions. You will contribute to science and (hopefully) have fun at the same time.

2011 Workshop on Procedural Content Generation (PCGames)

2011-01-22T12:25:00.002+01:00

We're organizing the PCG workshop this year again (well, actually Gillian is doing most of the organizing), following the success of last year's workshop. Yes, it's co-located with FDG this year again. Which means it's in France at the end of June. Probably best to stay far away from it then, unless you're one of those people that like sunshine, good food, good wine and/or good scientific discussions then.

So, if you have any interest in procedural content generation, see you in France in June!

CfP: TCIAIG Special Issue on Procedural Content Generation

2010-06-09T14:07:00.000+02:00

Call for Papers: Special Issue on Procedural Content Generation
IEEE Transactions of Computational Intelligence and AI in Games
Special issue editors: Julian Togelius, Jim Whitehead and Rafael Bidarra

The cost of manually creating virtual worlds for computer games is spiraling upwards. Procedural content generation (PCG), by which a computer algorithm generates game levels, art assets, quests, background history, stories, characters, or weapons, offers hope for substantially reducing the authoring burden in game development. Moreover, PCG has the potential to facilitate artistic expression and to promote creative experimentation, enabling individuals to create appealing games that otherwise could only be developed by large teams.

Automated content generation can take player behaviour history and player preference models as its inputs, and thereby create games that adapt to individual players. Content generation algorithms can also create novel game elements, in the process revealing new game potentials and improving our theoretical understanding of game design.

This special issue welcomes high-quality, mature work on procedural content generation for games. We welcome submissions relating to all game genres, including commercial games focused on entertainment, experimental indie games, web-based and social networking games, tabletop games, and serious games for simulation and education. Topics include but are not limited to:

* Procedural game level, scenario and quest generation
* In-game procedural creation of game objects
* Procedural creation of urban and natural environments
* Automatic layout techniques and generation of interiors
* Procedurally-assisted generation of art assets
* Adaptive game balancing and dynamic content generation
* Automatic generation of game rules and game variants
* Deployment of procedural generation within game design
* Case studies of industrial application of procedural generation
* Systematic evaluation of procedural content generation
* Combining manual editing with procedural generation of content

Authors should follow normal T-CIAIG guidelines for their submissions, but clearly identify their papers for this special issue during the submission process. See http://www.ieee-cis.org/pubs/tciaig/ for author information. Extended versions of previously published conference/workshop papers are welcome providing the journal paper provides a significant extension of the conference paper, and is accompanied by a covering letter explaining the additional contribution.

Deadline for submissions: November 1, 2010
Notification of Acceptance: January 15, 2011
Final copy due: April 15, 2011
Publication: June 2011

CfP: 2010 IEEE Conference on Computational Intelligence and Games

2009-12-18T00:59:00.000+01:00

First call for papers
Call for tutorial and special session proposals
2010 IEEE Conference on Computational Intelligence and Games
IT University of Copenhagen, Denmark, August 18-21, 2010
http://game.itu.dk/cig2010/

Games have proven to be an ideal domain for the study of computational intelligence as not only are they fun to play and interesting to observe, but they provide competitive and dynamic environments that model many real-world problems. Additionally, methods from computational intelligence promise to have a big impact on game development, assisting designers and developers and enabling new types of computer games. The 2010 IEEE Conference on Computational Intelligence and Games brings together leading researchers and practitioners from academia and industry to discuss recent advances and explore future directions in this quickly moving field.

Topics of interest include, but are not limited to, the following:

* Learning in games
* Coevolution in games
* Neural-based approaches for games
* Fuzzy-based approaches for games
* Player/Opponent modeling in games
* CI/AI-based game design
* Multi-agent and multi-strategy learning
* Applications of game theory
* CI for Player Affective Modeling
* Intelligent Interactive Narrative
* Imperfect information and non-deterministic games
* Player satisfaction and experience in games
* Theoretical or empirical analysis of CI techniques for games
* Comparative studies and game-based benchmarking
* Computational and artificial intelligence in:
o Video games
o Board and card games
o Economic or mathematical games
o Serious games
o Augmented and mixed-reality games
o Games for mobile platforms

The conference will consist of a single track of oral presentations, tutorial and workshop/special sessions, and live competitions. The proceedings will be placed in IEEE Xplore, and made freely available on the conference website after the conference.

Paper submission deadline March 15
Tutorial and special session proposal deadline January 31

CfP: Workshop on Procedural Content Generation in Games (PC Games)

2009-12-02T13:04:00.000+01:00

Workshop on Procedural Content Generation in Games (PC Games)

Co-located with FDG 2010 – Monterey, California – June 18, 2010

http://pcgames.fdg2010.org/

Overview

As computer games increasingly take place inside large, complex worlds, the cost of manually creating these worlds is spiraling upwards. Procedural content generation, where a computer algorithm produces computationally generated levels, art assets, quests, background history, stories, characters, and weapons, offers hope for substantially reducing the authoring burden in games. Procedural content generation has multiple benefits beyond reducing authoring cost. With rich procedural generation, a single person becomes capable of creating games that now require teams to create, thus making individual artistic expression easier to achieve. Automated content generation can take player history as one of its inputs, and thereby create games that adapt to individual players. Sufficiently rich content generation algorithms can create novel game elements, thereby discovering new game potentials. Finally, the procedural generation algorithm itself acts as an executable model of one aspect of the game, thereby improving our theoretical understanding of game design.

Important Dates

* Paper submission: Feb. 24, 2010

* Notification to authors: April 5, 2010

* Workshop held: June 18, 2010 (day before the main conference)

Workshop Organization

PC Games is a full-day workshop, with a peer-reviewed workshop program. Following a traditional working conference model, each talk session will have 2-3 paper presentations, followed by extensive time for questions and answers, as well as general discussion.

Research Areas

The PC Games workshop solicits paper submissions as either full papers (8 pages) or short papers (4 pages). PC Games welcomes research results that are either fully or semi-automated, in the following (and related) list of research areas. Papers will be published as part of the workshop proceedings.

* Procedural game level generation, for all game genres
* Procedural scenario generation for both entertainment and serious games
* Procedural quest generation, for single and multiplayer (online) games
* Procedural (non-player) character generation
* Procedurally generated game objects (e.g. weapons, vehicles, …)
* Procedural art asset generation, for a wide range of art assets
* Procedural creation of buildings, villages, towns, and cities
* Automatic layout techniques and procedural generation of interiors
* Procedural creation of natural environments, including terrain, water, clouds, plants, trees, etc.
* Procedural generation of crowds in real time
* Procedural animation of both procedurally and manually created content
* User control in procedural generation and intuitive input mechanism for procedural systems
* Construction and use of mixed-mode systems with both manual editing and automatic generation of content
* Integrating frameworks for procedural methods
* Procedural creation of background history and background stories for game worlds
* Adaptive game balancing and content generation based on prior player history
* Techniques for games that evolve and/or discover new game variants
* Procedural generation of computer and/or tabletop games
* Automatic generation of game rules
* Procedural generation of content for web-based and social networking games
* Player and/or designer experience with procedural content generation
* Models of player experience with procedurally generated content
* Theoretical implications of procedural content generation
* Meaningful incorporation of procedural generation into game design
* Procedural generation during development (e.g. for prototyping, design, testing, tuning, etc.)
* Lessons from historical examples of procedural generation
* Case studies of industrial application of procedural generation

Submission Instructions

Submissions to the PC Games workshop must follow ACM SIG conference formatting guidelines (http://www.acm.org/sigs/publications/proceedings-templates). Papers must be submitted using the Easychair submission system (http://www.easychair.org/conferences/?conf=pcgames2010).

Program Committee

Ruth Aylett, Heriot-Watt University
Rafael Bidarra, TU Delft
Ian Bogost, Georgia Tech.
Cameron Browne, Imperial College London
Simon Colton, Imperial College London
Eric Galin, LIRIS - CNRS - Université Lumière Lyon 2
Magy Seif El-Nasr, Simon Fraser University
Erin Hastings, Alion Science and Technology
Pascal Mueller, Procedural, Inc.
Ian Parberry, Univ. of North Texas
Jimmy Secretan, DiSTI Corporation
Ken Stanley, Univ. of Central Florida
Julian Togelius, ITU Copenhagen
Jim Whitehead, Univ. of California, Santa Cruz
Georgios Yannakakis, ITU Copenhagen
R. Michael Young, North Carolina State Univ.

The PC Games workshop is co-located with the 2010 Foundations of Digital Games (FDG 2010, www.fdg2010.org), which is an official conference of the Society for the Advancement of the Science of Digital Games (SASDG).
FDG 2010 is supported by a generous sponsorship from Microsoft Research.

Publicity. I suppose it's good for something.

2009-10-08T14:36:00.004+02:00

There's a new story about my research in New Scientist. A bit short, but apart from that correct. And in contrast to the previous stories about the autonomous car driving and the Mario competition this one is actually about my "core" research.

So, as one commenter said on my Facebook post about this, I'm getting more than my fifteen minutes of fame. The question is - what's this good for? Is it helping me do better research? Arguably not. And it doesn't seem to be impressing the girls either. I should probably just get back to coding.

Nothing to see here, move on...

Moving to ITU

2009-05-25T15:21:00.002+02:00

I've just tendered my resignation at IDSIA.

The reason is that I've gotten a grant from the Danish Research Council for Technology and Production, allowing me to start working in the Center for Computer Games Research at the IT University of Copenhagen. I'll move on August 1st.

Writing this feels almost surreal, as I've been longing to move home for quite some time now. But this is not only about moving home. At least as important is that I'm moving from a world-class machine learning institute to a world-class games research group.

This closely mirrors the ongoing shift in the emphasis of my research efforts. I simply think that I have more good ideas within applications of computational intelligence methods to games and game design, than within the development of new computational intelligence methods themselves. Naturally, this has much to do with the former field being much younger and thus less exploited. More white spots on the map to fill in with bright colours.

So yes, I'm very happy right now.

How fun is Super Mario Bros?

2009-04-24T12:14:00.002+02:00

Do you want to participate in some research? Please?

It's simple. Go to this address, play two levels of Super Mario Bros, and answer some questions about them. (Actually, it's not the "real" Super Mario game, but a customized version with some differences - you'll see!)

It's all part of a project that I'm involved in together with Chris Pedersen and Georgios Yannakakis at ITU. We're trying to investigate certain factors that affect entertainment in platform games and how to automatically optimize levels in such games. You'll hear about the results soon enough...

So, please play a game and contribute to science!

Machine learning might be too easy, but so what?

2009-03-28T18:44:00.002+01:00

John Langford argues that machine learning is too easy. He doesn't specify exactly what he means by this, but it seems to be that it's possible to publish papers and make a career in one area of machine learning without even understanding the core ideas of other areas.

Apparently, he thinks this is a problem. But why?

I could agree that it would be a problem if we were talking about science here. But we aren't. I've long since stopped pretending that I do science. (Except for the remote possibility that something I do might have an impact on a real science, such as biology or psychology.) We are just not studying the natural world.

I don't think of it as engineering either, as an engineer is meant to construct that that actually work and make economic sense. Most of what I do is pretty far from being useful or even reliable. Instead I think of myself as an inventor, practicing blue-sky invention of algorithms and toy applications without direct economic pressure. (Role model: Gyro Gearloose.)

So in a field of invention where people are inventing things following different paradigms and variations on a common theme of learning/optimization, is it a problem that most of the inventors have only a very hazy idea of what the others are doing? Not necessarily, as we are not all working towards the same goal (at least in the near term) and don't need to agree on anything.

Of course, it's great when you can combine knowledge from different research fields and come up with a nice synthesis - this is an almost surefire way to "be creative", and it's necessary that someone does it every once in a while. But for the most part, I don't feel like digesting hundreds of pages of dormative formulas in order to understand e.g. statistical learning theory. I feel my time would be much better spent just getting on with my own inventions, and reading up on stuff that's directly relevant to it (or seemingly completely unrelated, in order to look for new applications).

Simply unacceptable

2009-03-28T18:30:00.002+01:00

Defamation of religion is now a violation of human rights. I'd love to be able to just laugh at this, but it's far too serious to to be a laughing matter. Actually, just reading this fills me with primitive and undignified anger.

For the record, I don't consider any religion worthy of any sort of respect or protection. On the contrary, I think an enlightened and modern society should work towards harm reduction and possibly eventual elimination of religion with peaceful and rights-respecting means, similarly to how most western countries counteract tobacco smoking and its harmful effects.

(Thanks to Shane.)

No privacy without piracy!

2009-02-16T12:16:00.002+01:00

This slogan just appeared to me. I don't think I've seen it anywhere else.

The idea is that any method I've ever heard of for eradicating piracy, and indeed any conceivable method for doing so, build on also eradicating (or at least severely curtailing) privacy.

So if people start spreading this meme around, maybe the two issues (privacy and piracy) would become more linked in the general debate and in people's minds.

No privacy without piracy! You can't have one without the other.

Do you agree?

"Machine learning"

2009-02-05T09:50:00.002+01:00

Yahoo! have* posted their list of key scientific challenges in machine learning. I don't work on and hardly know anything at all about any of these topics. In fact, I think I understand what the question is in only three out of five cases.

Funny. I've always seen myself as working on some sort of machine learning, using computational intelligence methods. But if this is machine learning, I'm certainly not working on machine learning - it's about as related to my work as meteorology or linguistics is. So I should probably not say that I work on machine learning any more than I say that I work on meteorology or linguistics.

I'm actually OK with this, as I can still claim that I'm a computational intelligence researcher. Good enough for me.

But still... who gets to set the agenda? Ten years ago, what I do was machine learning; at least if Tom Mitchell's book is anything to go by. Nowadays, the important "machine learning" conferences such as NIPS and ICML wouldn't even look at the sort of stuff I do, irrespective of its quality. This is mildly annoying, as these conferences somehow have more prestige than CEC, Gecco and PPSN (probably because of ridiculously low acceptance rates).

And, most importantly: how does this semantic drift affect who gets the grant money?

* My intuition is really to write "Yahoo! has posted" here, as Yahoo! is a corporate entity usually referred to as it rather than they. However, British English seems to want to have it otherwise.

Kurukshetra AI Game Dev Event

2009-01-07T11:07:00.003+01:00

Sanjeev Chandran recently told me about this Game AI event, part of an international science festival in Pune, Bangalore and Hyderabad (India). One of the competitions that forms part of the event concerns automatic content creation, and I was told it is inspired by my work. Cool!

Sanjeev chose the classic Lunar Lander game as the domain. In the automatic content creation competition, participants are expected to come up with ways of automatically designing the lunar surface as well as setting parameters such as gravity in order to make the game more fun for human players.

I think that with a game as simple as Lunar Lander, there is lots of scope for focusing the development effort on the AI/CI algorithms rather than petty technical questions. The rules for the competition are quite loose, as is the objective and scoring. This could be a problem, but could also mean that we see some really creative submissions.

In any case, it will be very interesting to see what comes out of this!

CIG 2009 CFP

2009-01-07T02:51:00.003+01:00

New year, new CIG. Below is the first CFP for the conference to go to if you're interested in computational intelligence and games. This time, I'm on the organizing committee as well.

*** IEEE Symposium on Computational Intelligence and Games (CIG-2009) ***
Milano, Italy - September 7-10, 2008
http://www.ieee-cig.org

Games are an ideal domain to study computational intelligence methods.
They provide cheap, competitive, dynamic, reproducible environments
suitable for testing new search algorithms, pattern based evaluation
methods or learning concepts. At the same time they are interesting to
observe, fun to play, and very attractive to students. This symposium,
sponsored by the IEEE Computational Intelligence Society aims to bring
together leading researchers and practitioners from both academia and
industry to discuss recent advances and explore future directions in
this field.

Topics of interest include, but are not limited to:
* Learning in games
* Coevolution in games
* Neural-based approaches for games
* Fuzzy-based approaches for games
* Console and video games
* Character Development and Narrative
* Opponent modeling in games
* CI/AI-based game design
* Multi-agent and multi-strategy learning
* Comparative studies
* Applications of game theory
* Board and card games
* Economic or mathematical games
* Imperfect information and non-deterministic games
* Evasion (predator/prey) games
* Realistic games for simulation or training purposes
* Player satisfaction in games
* Games for mobile or digital platforms
* Games involving control of physical objects
* Games involving physical simulation

CONFERENCE COMMITTEE
General Chair: Pier Luca Lanzi
Program Chair: Sung-Bae Cho
Proceedings Chair: Luigi Barone
Publicity Chair: Julian Togelius
Competition Chair: Simon Lucas
Sponsorship Chair: Georgios N. Yannakakis
Local Chairs: Nicola Gatti and Daniele Loiacono

IMPORTANT DATES (tentative schedule)
Tutorial proposals: 15 April 2009
Paper submission: 15 May 2009
Decision Notification: 15 June 2009
Camera-ready: 15/30 July 2009
Symposium: 7-11 September 2009

CONFERENCE VENUE
The symposium will be held at the Politecnico di Milano, the largest
technical university in Italy, ten minutes from downtown Milan, the
shopping area, and its famous galleries and museums.

For more information please visit:
http://www.ieee-cig.org

Automatic Game Design

2008-12-28T23:48:00.011+01:00

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...

CIG 2008 Conference Report

2008-12-26T11:37:00.002+01:00

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!

Submit a paper to the CEC special session in CIG, or to TCIAIG

2008-10-16T17:14:00.002+02:00

Another reminder: please consider submitting a paper to the CEC 2009 special session on Computational Intelligence and Games, which I am co-organizing together with Pier Luca Lanzi and Daniele Loiacono.

If you're looking to submit your paper to a journal rather than a conference, you might be interested in IEEE Transactions on Computational Intelligence and AI in Games, a new high quality journal that is starting next year (but already accepts submissions) and for which I am an associate editor. Quite a mouthful of a name, but it's bound to be the most important publication outlet for us researchers working in applying CI methods to games.

CIG 2008 Car racing competition

2008-10-16T17:01:00.002+02:00

Just a reminder: please consider submitting to the TORCS-based car racing competition, that I am again organizing together with Daniele Loiacono and Pier Luca Lanzi. The goal is to use your favorite learning algorithm (evolution, td-learning, policy gradients, PSO etc.) and function representation (neural nets, expression trees, rulesets etc.) to develop the best controller for a racing car. Your car needs to win over all the over submitted controllers in a number of races.

PPSN 2008, post 3

2008-09-18T11:29:00.002+02:00

With some hindsight - that is, one day's worth of hindsight - I must say that PPSN 2008 was one of the best conferences I've ever attended. On my very personal ranking, it's up there in the top with CIG 2007 in Hawaii. The organisation of PPSN was top-notch, with nothing going wrong, the food good, the opportunities for socialising/networking plentiful and the schedule adhered to (this is Germany, after all).

It's striking how high the quality of the papers are in PPSN. In Gecco and CEC you know and then find papers you think should not have been accepted in a scientific conference, but never so in PPSN. There is also a difference in "scientificness". Many papers at the two other major conferences present yet another variation on a well-known algorithm, or yet another application, with little in the way of analysis and comparison to the state of the art. At PPSN, the norm seems to be to isolate a particular phenomenon, parameter or operator of known algorithms and benchmarks and study it further, making sure that even papers that are not groundbreaking (which is by necessity most papers) add to the body of human knowledge.

Of course, there are new algorithms and applications at PPSN as well. In particular, a number of variants of the CMA-ES were presented. CMA-ES seems to have become the standard algorithm to benchmark continuous optimization algorithms against, which makes sense, as it reaches good result very quickly on many problems.

Speaking of benchmarks, there seems to be a consensus that there is a lack of good reinforcement learning benchmark. A poster by Marc Schoenauer even went so far as to list "Stop balancing the double pole!" among it's conclusion. Of course, I tried to convince everybody who brought up the topic that they should use simplerace instead. A much better benchmark in many ways.

Now I'm going to prepare the talk I'll give tomorrow (with Marie Gustafsson) on "AI from Science to Fiction" at the Fantastic Film Festival in Lund, and the talk I will give on Monday on "Computational Intelligence and Game Design" at ITU Copenhagen.

PPSN 2008, post 2

2008-09-17T01:26:00.002+02:00

We've now been to the conference dinner, in an old steel mill. Excellent food, and an excellent place to visit. I love lo-tech and especially huge, rusting metal structures.

Towards the end of the conference dinner, DJ JJ organized a singing competition between Spanish-speakers and a group of speakers of various other tongues(Swedish, English, Dutch, Hebrew etc.). Needless to say, we lost - we couldn't find any songs in English we all knew the lyrics to. After the dinner most of us went back to our respective hotels to recuperate. In my case, I'm recuperating from the excellent Dortmund nightlife. Clubbing until 4.30 on a packed dance floor, with the beers priced 50 cents each. On a Monday. Brilliant!

So you want to know about the scientific side of things? Well, PPSN is really a very good conference. It is hard to find a paper which is not good, though it is of course easy to find papers that don't interest me. I'm not interesting in everything. For example, a theoretical analysis of the behaviour of the 1+1 ES does not interest me very much, even if it is obvious that the research is sound and the paper good. Still, there are many papers here that I like.

PPSN 2008, post 1

2008-09-15T10:08:00.002+02:00

I am at PPSN in Dortmund. I am listening to the talk on "Semidefinite Programming and Lift-and-Project Methods in Combinatorial Optimization" by Levent Tunçel. I do not understand anything at all of this talk. I am not the only one in the audience.

While I applaud the PPSN tradition of inviting people who are not evolutionary computation researchers to give keynotes, I don't think people outside our field understand how very little mathematics many (most?) people in this field know.

But the tutorials yesterday and the workshops on Saturday were really nice.

What should we call non-evolutionary reinforcement learning?

2008-07-26T21:18:00.004+02:00

I work in evolutionary reinforcement learning. That is, I develop reinforcement learning problems, and evolutionary algorithms that solve such problems.

The problem is that many people in reinforcement learning (RL) would say that I'm not working on RL at all. These people work on things like temporal difference learning, policy gradients, or (more likely) some newfangled algorithms I have never heard of, but which are most certainly not evolutionary. Most of the people working on non-evolutionary RL probably don't know much (maybe nothing!) about evolutionary RL either. So disconnected are our communities. It's a shame.

In their discipline-defining (4880 citations on Google Scholar) book "Reinforcement Learning", Sutton and Barto start with defining RL as the study of algorithms that solve RL problems, and mention in passing that they can be solved by evolutionary algorithms as well. The book then mentions nothing more about evolution, and goes on to essentially discuss TD-learning and variations thereof for a few hundred pages.

In practice, the evolutionary and non-evolutionary RL folks publish in different conferences and journals, and don't cite (nor read?) each other much. We write our papers in very different styles (the non-evolutionary RL people having much more maths in them, evolutionary RL researchers often relying on qualitative argument coupled with experimental results), and I for one often simply don't understand non-evolutionary RL papers.

Again, it's a shame. And it would be great if we could find some way of bridging this divide, as we work on the same class of problems.

But to do this, we need to find a way of addressing the issue, which was really the purpose of this blog post. Simply put, what do we call the two classes of algorithms and the research communities studying them? This is an issue I run into now and then, most recently when writing a grant proposal, and now again when preparing lecture slides for a course I'll be teaching this autumn.

The non-evolutionary RL people would not want a negative definition, based on what their algorithms aren't rather than what they are. They would rather go for RL, plain and simple, but this has the problem that non-evolutionary RL is excluded from that field, in spite of being part of the definition. In the proposal we wrote we ended up talking about "classical" versus evolutionary RL, but this has the problem that evolutionary algorithms predated td-learning by several decades. We could also use the term "single-agent RL", but then again, a simple hill-climber is arguably a (degenerate) evolutionary algorithm, and very much single-agent. Besides, there is multi-agent non-evolutionary RL. Sigh.

So I really don't know.

CIG 2008 special session on coevolution in games

2008-07-02T15:05:00.002+02:00

Coevolution in Games: A Special Session at IEEE Symposium on Computational Intelligence and Games
Perth, Australia
15-18 December, 2008

Special Session Chairs: Julian Togelius, Alan Blair and Philip
Hingston
Contact: julian@togelius.com

Submission deadline: 15 August 2008

http://www.csse.uwa.edu.au/cig08/specialSessions.html

Description:

In coevolution, the fitness of a solution is determined not (only) by a fixed fitness function, but also by the other solution(s) being evaluated. Thus, coevolution has the potential to overcome several problems with static fitness functions, paving the way for more open-ended evolution. However, several phenomena common to coevolutionary algorithms are at present poorly understood, including cycling and loss of gradient. Further understanding of such phenomena would facilitate more widespread use of coevolutionary algorithms.

This special session seeks to bring together research that uses coevolutionary algorithms to learn to play games, uses games to investigate coevolution, or uses coevolution as a basis for game design. Due to their adversarial nature, often involving interaction of multiple agents, games are uniquely suited to be combined with
coevolution. We invite both theoretical and applied work in the intersection of coevolution and games, including but not limited to the following topics:

Competitive coevolution
Cooperative coevolution
Multiple populations in coevolution
Coevolution with diverse representations
Theory of coevolution
Preventing cycling and loss of gradient
Coevolution-based game design
Self-play and coevolutionary-like reinforcement learning
Relative versus absolute fitness metrics

About the organisers:

Julian Togelius is a researcher at the Dalle Molle Institute for Artificial Intelligence (IDSIA) in Lugano, Switzerland. His research interests include evolving game-playing agents, modelling player behaviour, and evolving interesting game content, mainly using evolutionary and coevolutionary techniques. He also co-organizes the well-attended Simulated Car Racing Competitions for the IEEE CIG and CEC conferences. See his home page for more information.

Philip Hingston is an associate professor of computer science at Edith Cowan University in Perth. His research interests are in the theory and application of artificial intelligence and computational intelligence. He has a particular interest in evolutionary computation as a tool for design, and in computer games. He is chair of the IEEE CIS Task Force on co-evolution. More information can be found on his home page.

Alan Blair is Chair of the IEEE CIS Task Force on Co-evolution and Games. His research interests include robot navigation, image and language processing as well as co-evolutionary learning for Backgammon, Tron, IPD, simulated hockey and language games. Homepage.

Busy days in Hong Kong in June

2008-03-14T10:16:00.003+01:00

If you're going to WCCI2008 in Hong Kong in June, you might run into me. Chances are, however, that I'll just keep on running, as I've got a busier schedule than I've ever had in a conference. So just don't take it personally, OK?

To begin with I'm giving a tutorial together with Simon Lucas and Tom Runarsson on "Learning to play games". Preliminarily, Tom will talk about evolution versus other types of reinforcement learning, Simon will talk about different sorts of function approximators, including his n-tuple classifier, and I will discuss different ways in which such techniques can be used in games, with examples. Not only car racing, is the plan...

Then, I will participate in a panel discussion about Computational Intelligence and Games, together with some of the people that are defining this young field.

Staying on the topic of games, I will then present the results of the car racing competition, together with Daniele Loiacono and Pier Luca Lanzi. By the way, have you considered participating? We now have proper software packages available, so it's easy to get started with developing controllers using your favourite brand of learning algorithms.

Yes, I do have some papers as well. However, these are not (primarily) about games this time...

The first paper, a collaboration with my good friends Alberto Moraglio and Renzo De Nardi, is called Geometric PSO + GP = Particle Swarm Programming. The idea is to combine Alberto's geometric particle swarm optimization algorithm with genetic programming. The good thing with GPSO is that it can be used in any search space where a distance between two solutions can be defined, and a weighted recombination operator for these solutions can be devised; in contrast, standard PSO only works in continuous spaces. We have previously successfully used GPSO to solve Sudoku problems, to show this really works. In our new paper, we invent a few weighted recombination operators for expression trees, and test the PSP (GPSO + GP) algorithm on two standard GP benchmarks. The results are decent, but not as good as we would have wanted them; we think this is down to the recombination operators still needing some more work. Nevertheless, we think this is the first time PSO has been applied directly to GP.

The other paper, my first collaboration with Faustino Gomez and Juergen Schmidhuber (my new colleagues at IDSIA) is called Learning what to ignore: Memetic climbing in topology and weight space. It's about "memetic neuroevolution", an idea I've had for a while, and which someone else really should have thought about. The key algorithm here (the "memetic climber") is incredibly simple: evolve topology of weights of a neural network at different time scales. Topology mutations are almost always very destructive, so after each topology mutation, do local search (hill-climbing) in the space of neural network weights do find the potential of the new topology. If the fitness at the end of the local search is not at least as high as it was before the topology mutation, the topology mutation is discarded. This algorithm turns out to work really well, especially for problems where an agent has to handle high-dimensional input arrays. In such problems, which is really the ones i'm most interested in, most neuroevolution algorithms get stuck in local optima if you don't manually specify a good topology for the neural net. So I have big plans for this little algorithm in the future.

Mentioned at the GDC

2008-02-22T15:12:00.003+01:00

A paper by me, Renzo and Simon was recently mentioned as "one of the top ten research finding in games studies" at the Game Developers Conference. This is really cool, as GDC is the most important conference for the games industry, attended by all the important developers and industry heads and tons of journalists.

The presentation can be found here:
http://www.avantgame.com/top10.htm

A short description and some discussion on Raph Koster's site:
http://www.raphkoster.com/2008/02/20/gdc2008-game-studies-download-30/

And the paper:
http://julian.togelius.com/Togelius2007Towards

Quite surprising to see that I'm doing "games studies", I thought I was doing artificial intelligence...

Call for participation: IEEE WCCI 2008 Simulated Car Racing Competition

2008-02-21T20:59:00.004+01:00

*** SIMULATED CAR RACING COMPETITION @ IEEE WCCI 2008 ***
*** DEVELOPING CONTROLLERS FOR A REALISTIC CAR RACING SIMULATOR ***

Homepage: http://cig.dei.polimi.it/?page_id=5

Deadline: May 25th, 2008
Organizers: Daniele Loiacono, Julian Togelius and Pier Luca Lanzi.
Email: carracing@gmail.com

The car racing competition, organized in association with the 2008 IEEE World Congress on Computational Intelligence WCCI 2008, is now open for submissions. Competition rules and further details can be found on the competition web site:

http://cig.dei.polimi.it/?page_id=5

while recent news can be found at

http://cig.dei.polimi.it/?cat=4

*** GOAL & SCOPE***

The goal of the competition is to develop racing car controllers that can compete on a set of tracks against the timer or other controllers.

There are no limitations on the type of controller, handcoded controllers are also welcome, although the focus of the competition, given the venue, will be on controllers using computational intelligence techniques (e.g. genetic programming, neuroevolution, td-learning, policy gradient search, fuzzy logic, etc.).

*** ORGANIZATION ***

The competition is organized as the successful car racing competitions held in association with CEC2007 and CIG2007, but it is based on "The Open Racing Car Simulator" (TORCS), a realistic car racing simulator, and structured as a client-server architecture.

A racing server will manage the race, while controllers will run as different processes. Communication between the racing server and the controllers is done through TCP/IP. The race is therefore in *real time* and the controller's reaction time is likely to be an important factor in the design.

We will score every submitted controller on the distance raced in a fixed amount of time when driving on its own on a set of tracks. At the end of the competition, the best few controllers will race against each other on a different set of tracks, validating that the controllers perform well in the presence of other cars and that their performance generalizes to other tracks than those they were trained for. The winner of the final competitive races will get to present their controller at WCCI2008 <http://www.wcci2008.org>, and will have their registration fee reimbursed.

*** SOFTWARE ***

The competition software can be downloaded from:

http://cig.dei.polimi.it/?page_id=5

where detailed installation instructions, a description of the sensors model, and examples of controllers are available; more example trainers and interfaces in different programming languages will be added soon.

On industrial-academic collaboration in game AI

2007-12-13T00:47:00.001+01:00

Today was the kick-off event day for the UK Artificial Intelligence and Games Research Network. I wasn't there, but my ex-supervisor is one of the organizers, so I heard about it beforehand.

This is the first blog post I've seen about the kick-off; the author seems to have left the event with a pretty pessimistic view of the prospects for industrial/academic collaboration. His main complaints is that academics don't understand games, and the specific needs of game developers. Well, then tell us! I would love to hear about specific problems in game development where evolution or some other form of machine learning or computational intelligence could matter.

Alex J. Champandard, in a comment on the same blog post, develops the point further. He asks:

So why do you need government funding for [applied games research]? It's a bit like admitting failure :-)

On the other hand, if [academics are] doing research for the sake of research, why do they need input from industry?

These questions can be asked for just about any research project in the interface between academia and industry. And yet companies happily keep funding PhD students postdocs, and even professors in a huge number of research fields, from medicinal chemistry to embedded systems design to bioinformatics. In some cases these collaborations/funding arrangements definitely seem strange, but apparently it makes economic sense to the companies involved.

I once asked an oil company executive (at a party! Now, stop bothering me about what sort of parties I go to...) why his company funds a professor of geology. His answer was roughly that it was good to have expert knowledge accessible somewhere close to you, so you know who to ask whenever you need to. Plus, a professor's salary wasn't really that much money in the grand scheme.

Now, game companies and oil companies are obviously very different sorts of creatures. I think the main opportunity for game companies would be to outsource some of their more speculative research - things that might that not be implementable any time in the near future, either because the computational power is not there yet, or because the technique in question would need to be perfected for a couple of years before deployment. Having a PhD student do this would be much more cost-efficient than assigning a regular employee to do it (especially with government funding, but probably also without), and frees up the employee for actual game development. In addition, the company's own developers might very well be too stuck in the way things currently work to try radically new ideas (of course, academics might also be stuck in old ways of thinking, but there are many academics around and if you offer some funding you can typically select which academic you want to work for you).

This argument assumes that game companies do any sort of research into technologies that lie more than one release cycle away. I'm not stupid enough to claim that no game companies do this - e.g. Nintendo obviously does - but I venture to guess there are many that don't.

As for the other part of Alex's question, "if we do research for the sake of research, why do we need input from industry?", the answer is more obvious. Because even if we do research because we love the subject itself and really want to find out e.g. how to best generalize from sparse reinforcements, we also want to work on something that matters! And fancy new algorithms look best together with relevant problems. It's that simple.

New webpage at IDSIA

2007-11-27T14:32:00.000+01:00

I've now set up a parallel home page at my new workplace, IDSIA. It's currently mostly a quick overview of the various things I'm involved in academically, but I plan to set up pages with a bit more detail about the projects in that domain as well (for those who don't feel like going straight for the papers).

My primary home page will still contain my publication list, CV and such formal stuff.

A task force and an interview

2007-10-19T12:36:00.000+02:00

More games-related news today. The IEEE Computational Intelligence Society has just spawned a Task Force on Computational Intelligence in Video Games, chaired by Ken Stanley (of NERO and NEAT fame) and which I am an inaugural member of. From the mission statement:

"We are aiming to become a repository of information on CI in video games, a networking resource for those in the field, and the spearhead for initiatives in the area. We will also attempt to bridge academia and industry by including members from both. Thus ideally we can become a focal point for discussion and action that will facilitate further progress in the field."

This is a very good initiative in my opinion, and being backed by a such a powerful organisation as the IEEE is certainly not bad. As the web site is only just up, the member list is far from complete yet. The task force is looking for information on interesting research groups and projects, so if you want your project featured, contact them!

Over at Alex J. Champandard's blog, "Game AI for Developers", we find an interview with none other than yours truly. Personally, I think it's an interesting read, of course... Thanks for the opportunity, Alex!

One of the things I suggest in the interview is that game developers initiate contacts with academic researchers interested in CI in games. The above mentioned task force could come in very handy for such purposes, as soon as the member list is expanded to include everyone who should be there!

Confessions of an academic crack smoker

2007-10-10T17:31:00.000+02:00

Look, I got some attention again. This time from Christer Ericson at Sony Santa Monica, "the God of War team". His blog post is a scathing critique of most of what I've been doing for the last three years, without going into any detail whatsoever, and devoid of constructive suggestions.

I'll try to be less rude.

Christer's argumentation consists in showing one of my early videos with two cars on a track, and pointing out that the AI is not very impressive, as the cars behave erratically and crash into walls. He also makes fun of question I posted to Slashdot, where I was genuinely wondering about what people perceive as being the flaws of current game AI. From this, he implies that my contribution to game AI is null and that I could as well stop what I am doing.

Now, if someone from industry came and argued that what I'm doing is completely useless for game developers, I would take this seriously. Even if he was right, it seems that at least some of what I do is appreciated by the CI community, which is at least equally important to me, so I could accept developer' thinking my ideas were all stupid. However, I would only take such criticism seriously from someone who had actually read my papers and knew what I was doing, and bothered to come up with some suggestions on how to improve my work. None of this is true for Christer's rant.

It's true that the cars in the video don't seem to be driving very well. That was never the objective. Instead, the video is from a series of experiments where I manipulated the fitness function in order to produce interesting driving behaviour. Evolution of controllers that drove a particular track better than any tested human was already reported in our very first car racing paper. It's also true that the cars never learned to recover from some wall crashes. I had wanted this to emerge from the overall progress-based fitness function, which it didn't, and I might get back to work on this later; however, it would be straightforward to either add crash recovery as a specific learning objective, or add a hard-coded function for this. After all, normal game AI is 100%hard-coded.

In short, it would help if Christer either judged my experiments based on their actual objectives, or told me in what way I needed to change my objectives.

It would also help if he looked at some of the work that I myself consider more useful for game development, at least conceptually. (I'm not an expert in graphics, physics, or for that sake real-time collision detection, and don't profess to be one.) Especially the experiments on player modelling and track evolution, but also generalization and specialization for quickly creating drivers for any track, and co-evolution of diverse sets of opponents.

If he read these, and came back and still thought it all stank, I would be very happy to listen to his ideas on how to make my research more relevant for hard-working game developers like him. In the meantime, I'll continue my vacation.

And by the way, I don't smoke.

CEC 2007 Conference Report

2007-10-08T16:31:00.000+02:00

So, the 2007 IEEE Congress on Evolutionary Computation is now over. Actually, it's been over for the last ten days. Sorry for taking such time to update my blog, I'm out backpacking at the moment to celebrate finishing my PhD, and I try not to spend all my vacation in front of a computer (even though it's hard fighting that Internet addiction)!

Overall, CEC was an excellent event this year as well. A generous supply of on average really good keynote and invited speakers, so many parallel sessions that there was always something interesting going on, and a superb organization. The only things I would have done differently is spreading the conference out on five or six instead of four days, and not charging money for the tutorials (in fact, many of the tutorials are the same as are included in the general registration for Gecco or PPSN). But those are really minor issues. (A major issue that CEC shares with Gecco and some other conferences is the too low entry barriers / too high acceptance rates, but that's stuff for another blog post.)

Simon's keynote on Evolutionary Computation and Games went down really well, it seems. Apparently, more and more EC researchers are warming up to the idea of using games as testbeds for their algorithms. Simon plugged the car racing competition as well, and there were lots of people talking to me about it in appreciative terms both before and after I presented the results. It seems we have quite a momentum for these kinds of activities at the moment.

Hugo de Garis' invited talk was interesting in a very different way. Actually, it was quite sad. de Garis is known for his huge ambitions and provocative statements, (evolving "artificial brains" as complex as those of kittens, or was it even humans this time around?) so I was looking forward to bold new theories on how such grand aims should be achieved. What followed was some very conventional neuroevolution stuff, and a complete failure to appreciate the real challenge in putting all his evolved neural modules together. Most importantly, he has absolutely no empirical results to show. Predictably, the audience gave him a hard time during the question round.

Other interesting talks included those of Jong-Hwan Kim, the father of RoboCup, on evolvable artificial creatures for ubiquitous robotics, and of Marc Schoenauer on how modern bio-inspired (and population-based) continuous optimisation algorithms such as CMA-ES and PSO now often outperform the orthodox optimisation algorithms used by the applied maths people, on their own benchmark problems. Quite cool.

By the way, did I point out that the organization was superb? Anyway, it deserves saying again. The Stamford convention centre is not only lavishly, but also tastefully, decorated and conference delegates were continuously tended to by an army of servants making sure that we always had something to eat and drink and knew where the venue for the next talk was. The food was simply fantastic, the night safari at the end of the conference was a very nice event, and the conference banquet had nine (!) courses. I can't imagine how our conference fees can have paid for all this - some of the sponsors must have contributed serious money. Rooms were generally easy to find, and most importantly, there was plenty of places where you could just bump into old and new people and have those all-important corridor chats. In all, a very rewarding experience.

Thesis online

2007-09-23T12:33:00.000+02:00

My thesis corrections have now been approved, and the final version is online at http://julian.togelius.com/thesis.pdf

Now I'm off to Singapore to attend CEC, present two papers and the competition results, and have a bit of vacation!

Just passed my viva!

2007-09-14T21:26:00.000+02:00

Only minor corrections, will take me a few days to sort out, and them I'm a PhD! External examiner was professor Peter Cowling, University of Bradford (who has a research group on computational intelligence and games), and internal examiner was John Gan.

Yes, it feels fantastic... now we're going out to party! See you!

"Advanced Intelligent Paradigms in Computer Games"

2007-08-07T16:14:00.000+02:00

Just found this new book from Springer in my mailbox today - it contains a chapter by me, Simon and Renzo on "Computational Intelligence in Racing Games". I'll make it available online soon enough, but almost all of its contents can be found in some of our earlier papers.

The issue of finding those papers...

2007-08-03T20:10:00.000+02:00

I read lots of academic papers in my field - though certainly not as many as I "should" - but how do I go about finding them? It sometimes strikes me that I don't really have a good strategy for keeping up to date, or for finding good references when I get a new idea.

I go to conferences, like others do. But obviously I don't go to every conference, and I don't see every presentation on a conference, and I'm not mentally present during every presentation I see. Anything else would be impossible. Worse, conference proceedings are usually only available as hard-to-search CDs or books, instead of for free on the conference website, which would be the sensible option.

There are a few repositories meant to contain papers, or links to papers, in particular research fields, and also to provide good means of finding the papers you want. Sadly, many of them are half-baked.

CoRR (arXiv) have never reached anywhere near the same popularity in Computer Science as it has in physics, probably partly due to weird requirements of submitting the latex source of every paper, something that rarely works in practice. Cogprints have likewise failed to take off, even though the technical platform seems decent enough. Citeseer used to be good around 2002-2003, but seems to have been neglected by its administrators lately (I've had serious problems correcting missing or faulty metadata for my own papers). Bill Langdon's GP Bibliography is excellent, though for a limited domain.

In the best of all world, every paper should be easy to find through Google Scholar. A main obstacle to this is that so many researchers fail to make their papers available on their personal websites. Even in computer science! This is puzzling, and shameful.

I think it is every serious researcher's obligation to make his complete scientific output publicly available on his own home page, unless he/she has a very good excuse. Otherwise one would suspect that he/she has something to hide.

So if you are reading this, and still haven't made all your publications freely downloadable from your website, go and do it. Now. For the sake of science, and your own reputation as an honest scientist. Unless you have a very, very good reason why you shouldn't. And you probably haven't.

(Yes, I do feel quite strongly about this...)

How better AI can make racing games more fun

2007-08-01T13:49:00.000+02:00

In some previous posts on this blog (e.g. this one, this one and this one) I've been discussing evolving neural networks to drive racing cars around a track. We did this research (published in several papers, e.g. this one and this one) for several reasons, the main motivation being to explore how games can be used as environments in which (artificial) evolution can create complex (artificial) intelligence. The related topics of which evolutionary algorithms and controller architectures (neural networks, expression trees etc.) learn best and fastest have also been investigated.

While the interest in this kind of research from the point of view of artificial/computational intelligence and machine learning is fairly obvious, one might wonder whether it might also have applications in computer games. This is less obvious. For example, most racing games would not benefit from having faster, better driving opponents; who would want to play a racing game where you always finish last? Apparently, minor "cheats" (such as allowing the computer-controlled drivers more complete information than is given to the human player) is enough for game designers to be able to manually create opponents that drive well enough.

Racing games are not alone in this respect: in most game genres (with the notable exception of strategy games like Civilization), game designers have no problems at all coming up with sufficiently (appropriately?) challenging opponents, without resorting to blatant cheats (again, remember that Civilization and its likes are exceptions to this rule). Instead, the challenge for designers is coming up with interesting enough opponents and environments, and doing it fast enough. In fact, this consumes huge amounts of money, and is a major expense post in the development of a new game.

So, the challenge we set ourselves was to use the technology we'd already developed to come up with something that could make racing games (and in the future other games) more fun and interesting.

What we came up with was this: modelling the driving style of a human player, and use our model of the driving style together with an evolutionary algorithm to create new racing tracks that are fun to drive for the modelled player. This combination of player modelling and online content generation has, as far as we know, never been attempted before.

The technical details of (different versions of) our proof-of-concept implementation of this was presented at an SAB Workshop last year, and at the IEEE CIG Symposium in April (read the paper online). A discussion of the experiments will also be included in a chapter in a forthcoming book from Springer. But the basic procedure of the most recent version of our software is as follows:

Let the human player drive on a test track, designed to contain different types of challenge (straights, narrow curves, alternating smooth bends). Record the driving speed and lateral displacement (distance from the center of the track) on a large number of points around the track.
Take a neural network-based controller, which has previous been evolved to be a competent driver on a large variety tracks, and put it back into the evolutionary algorithm. This time, however, the fitness function is not how well the controller drives the track, but how similar the its driving style is to the human's. Specifically, the more similar the speed and lateral displacement of the neural network-controlled car is to the recorded values of the human driver on the same track, the higher fitness it gets.
Next, a track is evolved. For this we need an evolvable representation of the track. We've experimented with a couple of different solutions here, but what currently seems to work best is representing the track as a b-spline, i.e. a sequence of Bezier curves.
We also need a fitness function for the track. Here, it should be remembered that we are not looking for a track that is as hard or as easy to drive as possible (that would be easy!), but rather the most fun track for the modelled player. To be able to measure how fun a track is, we looked at the theories of Thomas Malone and Raph Koster. The outcome of the rather long discussion in the paper, is that we try to maximize the difference between average and maximum speed, the maximum speed itself, and the variance in progress between different trials. But you really have to read the discussion in the paper to see the point of this, or possibly another blog post I'll write later.
Finally, we evolve the track, using this fitness function and track representation, by driving the controller modelled on the human player on each track and selecting for those tracks in which the controller has maximum speed, maximum difference between average and maximum speed, and maximum progress variance.

Below is a few evolved tracks:

This procedure works well enough in our proof-of-concept implementation, but how well it actually works in a full racing game remains to be tested. The most obvious candidate for testing this would be a racing game that comes with a track editor, such as TrackMania. On the horizon, we could have racing games with endless tracks, that just keeps coming up with the right types of track features as you drive, i.e. the ones which are neither to easy nor too hard, and thus keeps you challenged in the right way.

And of course we have been thinking a bit on how this general idea might be extended to other types of games, we just haven't had any time to do experiments yet...

The IEEE CEC 2007 car racing competition

2007-07-18T15:31:00.000+02:00

Finally, we've got the CEC version of the car racing competition up and running. Feel free to participate! Indeed, please participate! We're very eager to have as many participants as possible, using as different approaches as possible to how to develop their controllers. It's OK if you don't win - at least, it's OK for me...

I quote from the mail I just sent out to the CIG mailing last:

The competition is an incrementally evolved version of the competition
run for the Computational Intelligence and Games Symposium in April.
If you participated in that competition, you will be able to adapt
your submission to the new format with minimum effort. Even if you
have never heard of the competition before, the software is designed
to be as easy as possible to get started with.

Some main changes when compared to the CIG version of the conference are:

* A prize of 500 US Dollars is awarded to the winner. This is subject
to the winner being a registered attendant at CEC, and to at least 5
of the competitors registering for CEC.

* The software package and API have been extended to better
accommodate value function based control, and the software comes
complete with examples of temporal difference learners and genetic
programming controllers as well as various types of neural networks
and evolutionary algorithms.

* The submission format has changed in order to make sure that any
competitor (as well as the organizers) can easily download and run any
other competitor's submission.

Apart from that, various bug fixes have been made, and the competition
score method has changed slightly.

Me, Myself, I, etc.

2007-07-18T01:11:00.000+02:00

It's now three weeks since I handed in my PhD thesis. I'm still trying to find out how to wind down; I don't think I've ever been as exhausted as right after handing it in.

The title of the thesis is "Optimization, Imitation and Innovation: Computational Intelligence and Games". It contains the experimental sections of most of the papers I've published so far (I had to omit the Sudoku ones to keep the thesis focused, and also to keep the length down - it is already quite a massive heap of paper). It also contains a number of background chapters situating my research in the context of evolutionary robotics and of game AI, and trying to define some sort of taxonomy of apporaches to computational intelligence and games.

I will of course make it available for download from my home page, but not until I've finished my corrections, which will be issued when I've had my viva, which I really hope will take place in early September. Oh yes, and I need to pass the viva as well. Fingers crossed. In the meantime, if you're interested in a copy of the uncorrected version, just mail me.

Assuming I pass my viva, I will then start my new job as a posdoctoral researcher at IDSIA in Lugano, Switzerland, in November. There, I will be working with Juergen Schmidhuber, who is quite famous for his work on reinforcement learning and recurrent neural networks. The place is full of other intelligent people doing great research as well, such as Faustino Gomez doing very interesting work on neuroevolution. That I'm excited about this goes without saying.

GECCO 2007 conference report

2007-07-17T13:32:00.000+02:00

A little late, but I figured I should write something about GECCO, even though so many others have.

I was first author on one paper, which I also presented, and second author on two other papers and a poster, so the conference was quite busy for me. Literally. There was a lot of walking through long corridors, and running back through the same corridors after figuring out a wrong turn had been taken somewhere. Let this be my one comment on the organisation of this year's GECCO: UCL is not a good conference venue. Sure, it's in London, and London is one of the world's capitals and very easily accessible through cheap flights and all that, but UCL is the sort of ancient labyrinth where you would expect to bump into a minotaur at any time. Or at least some trolls, or Jeremy Bentham. There was not a single room where all of the conference attendees could fit at once, severely limiting the potential for these all-important random encounters with other researchers, and some of the talk venues seemed to be ten minutes on foot from each other - if you could find them.

I can safely say that the recent SSCI in Hawaii and CEC in Vancouver were better in at least these respects.

But on to the important question: were the papers any good? Better or worse than CEC?

I don't know if I can, and want to, answer that question. As it is physically impossible to see more than perhaps a fifth of the papers, and I didn't even see that many, it's a bit preposterous to have a firm opinion on that. Also, it is a well-known but seldom-talked-loudly-about fact that there is a certain unhealthy animosity between CEC and GECCO, and I don't want to isolate myself from any of these communities. I suppose it's fair to say that the quality is at least comparable but with the conferences having slightly different focus, with somewhat more of e.g. GP and EDA on GECCO, and somewhat more of the stuff I'm most interested in (e.g. games, robotics, neural nets) on CEC.

Then again, one could make the argument that both of these conferences have their entry barriers set a bit too low. That's why I like the GECCO's approach to not treat poster presentations as full papers, in order to enforce more of a separation between contributions of different quality, but I would rather see that the oral acceptance rate was lowered a bit, so that some of the less original studies that were now presented as full papers were accepted as posters instead. Just my 2p.

Oddly enough, I don't know which papers won the best paper awards. They were presented in a session so early in the morning that no-one could reasonably be expected to attend, and the actual awards (as opposed to the nominations) are not to be found on the GECCO homepage. No-one seems to have blogged about it, either. My own picks for two of the tracks would be the paper on HyperNEAT by David D'Ambrosio and Ken Stanley, and the paper on learning noise by Michael Schmidt and Hod Lipson; the first because it is a really cool new idea which might initiate a new paradigm in developmental systems (in addition to the cell chemistry and graph rewriting paradigms), and the second as the general idea might prove to be very useful for modelling the dynamics of physical robotic systems, something I've become rather intereseted in myself recently. As for the other tracks, I didn't see all the best paper nominees, so I don't really have an informed opinion.

Does anyone of you actually know which papers won the awards?

The problem with the iPlayer

2007-06-27T18:42:00.000+02:00

So the BBC is going ahead with making much of their content available online - through a system crippled by Microsoft's DRM. The reason they give is that "the right's holders - the people that make the programmes, from Ricky Gervais to the independent producers that account for up to a third of our programming - simply wouldn't have given us the rights to their programmes unless we could demonstrate very robust digital rights management."

Alright. But what about the programs that the BBC produce themselves? Shouldn't they by default be exempt from DRM? As for the independent producers, the BBC by merit of its size should be in such a bargaining position that they could force them to accept DRM-free distribution. But apparently the corporation hasn't got enough spine for that. Sad.

DRM is fundamentally at odds with the spirit of public service. Who is going to stand up against DRM if not the public service media corporations? And what's the point in public service at all if it bows to commercial media's ideas about DRM?

Where is Julian?

2007-06-06T21:47:00.000+02:00

Is he nowhere to be seen? That is only because he is writing up his thesis. He's been hiding in Ekerö, Sweden for quite a while now, where everything is quiet, idyllic and there is nothing to disturb his thesis writing. See for yourselves how idyllic it is:

But now he's back in England! Rumours have it that he's trying to get the thesis ready for submission in two weeks time. Lots of work, then. Probably not much time for blog posting until that's done.

09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0

2007-05-02T02:02:00.000+02:00

So there you have it.

Grand and Molyneux on game AI

2007-04-19T20:26:00.000+02:00

The Guardian has an article containing short interviews with Peter Molyneux and Steve Grand, two people who have managed to put out commercial games (in one case arguably commercially successful as well) containing "real" AI. Interesting read. They're both essentially pushing the idea that as games get even prettier, the stupidity of current game "AI" will shine through more and more, and so the need for "real" AI will increase, not increase.

I say maybe. While Molyneux's games are a great source of inspiration it's possible that it and its likes will always constitute a niche market, and your average FPS, RTS or movie tie-in adventure will never benefit from a neural network or evolutionary algorithm. But I do hope that I'm wrong here.

Whichever the case, we can still use commercial games for academic research just the same, in order to help us understand natural and computational intelligence. And I think we should. Much more than today.

Back from Hawaii, back to reality...

2007-04-17T16:17:00.000+02:00

Finally, my first "normal" day since coming back. That is, I plan to spend most of my day in the lab... reviewing some papers for CEC, answering some mails, and starting to write my thesis.

Yes, that's right. The plan is to start writing my PhD thesis. Today. So maybe it's not that normal a day after all. Further, according to the plan, I will hand in my thesis in June and have a viva in September. It's not impossible, I believe.

The IEEE Symposium Series on Computational Intelligence was a good event from a scientific perspective, and an excellent one from a networking perspective. I spent plenty of time drinking cocktails with Games and ALife people, discussing research ideas and completely unrelated stuff.

After the conference we spent a few more days in Hawaii, and me and Hugo went on to do some touristing in San Francisco. Fantastic city, indeed.

CIG Car Racing Competition results

2007-04-15T20:50:00.000+02:00

The winner of the CIG Car Racing Competition is Peter Burrow - congratulations, Pete! He used a modular controller based on two incrementally evolved neural networks, and the nearest competitor, Thomas Haferlach, also used a modular controller based on two neural networks, although CTRNNs rather than the more straightforward networks Pete used.

Aravind Gowrisankar and Matthew Simmerson submitted controllers based on NEAT (NeuroEvolution of Augmenting Topologies) and I submitted a simple hard-coded controller, an simple evolved neural network, as well as (together with Hugo Marques) a controller based on an evolved neural network for controlling the car together with a copy of the whole simulation environment for predicting which car will reach the current way point first. None of these approaches scored as well as the modular controllers of Pete and Tom, but with some more work they might well do.

As for where that work would be submitted, we are planning to run another car racing competition for CEC 2007. That would give contestants several more months (until September) to work on their controllers. We haven't currently decided on the exact details of that competition, but plan to finalise it before the end of April. So if you have any ideas on in what direction to take the competition (changing the interfaces? dynamics model? task? etc) please speak up now!

In Hawaii

2007-03-31T22:22:00.000+02:00

So now I'm in Hawaii, "preparing" for the IEEE Symposium Series which will start tomorrow. Preparing on the beach, that is.

There has been a lot of interest in the CIG Car Racing Competition after the recent media coverage. Unfortunately, the deadline is passed (the results will be presented on Thursday) but given the interest I will definitely look into some way of rerunning the competition, either by attaching it to another conference or making it into some form of permanent league.

Another "Ask Slashdot" of mine recently got on the frontpage - it's about the Most Impressive Game AI. Check it out. Unfortunately I don't know if I can contribute much to the discussion as there's no Internet on the beach. Or, at least, I'm not bringing a laptop to the beach.

Slashdot and New Scientist

2007-03-24T19:54:00.000+01:00

Thread on Slashdot on the car racing research:

Slashdot thread

Contains some interesting discussion, and was soon picked up by New Scientist:

New Scientist article

Hmm... interesting that I am linking to a post that links back to this blog. Self-referential promotion.

Mini-Grand Challenge, sort of...

2007-03-22T18:05:00.000+01:00

So now it's official: we (a team led by Simon) will build a demonstrator model car with onboard computer control, and organize the first model car competitions at WCCI 2008. The IDEA is that a smaller car faces the same problems of navigation, control, computer vision etc. as a full-size car does, but is enormously cheaper to build. So it's like a miniature version of the DARPA Grand Challenge, that anyone can participate in. Of course, this makes it possible to try some riskier approaches, that you would never dare try with a full-size car, such as various machine learning techniques. We hope we will see lots of innovative entrants to the competition.

Most impressive game AI?

2007-03-22T18:04:00.000+01:00

I have the feeling that when developers make the effort to put really sophisticated AI into a game, gamers frequently just don't notice (see e.g. Forza). Conversely, games that are lauded for their fantastic AI are sometimes based on very simple algorithms (e.g. Halo 1). For someone who wants to apply AI to games, it is very interesting to know what AI is really appreciated. So, what is the most impressive game AI you have come across? Have you ever encountered a situation where it really felt like the computer-controlled opponents were really thinking, that there were "someone in there"?

Evolution versus td-learning revisited

2007-02-23T16:54:00.000+01:00

One of the papers we are presenting at this year's Computational Intelligence and Games symposium is about comparing td-learning and neuroevolution for learning car racing skills.

The paper (go read it!) contains lots of material, and I won't try to summarize the rather dense methods and results sections here. But let me reflect a bit on some of the major conclusions:

First of all, td-learning can be blazing fast when it works like it should. Of course td-learning could potentially be faster than evolution as it learns from feedback during the lifetime of an individual, but we didn't expect it to be quite as fast as it sometimes was. A few times we saw a car controller starting from tabula rasa and going to driving decently between waypoints in a few hundred time steps, maybe 20 seconds of simulated time!

But to balance the picture, td-learning can be a bitch. Really. Performance is completely unpredictable, the very same parameter configuration gives completely different learning results in successive runs, and the same configuration can learn very well sometimes and not at all at other times. Often, already learned good behaviour is unlearned after a few more epochs. Etc, etc. It is simply much easier to learn something sensible with evolution than td-learning. And in the end, the best evolved controllers are consistently better than the best td-learned controllers.

Which brings us on to the question of whether these effects are inherent to the algorithms, or whether they are an artifact of Simon and me being much more familiar with evolution than td-learning. Interesting question. I don't know. We did, however, bring in Thomas Runarsson to help us with the experiments and he's done quite a bit of td-learning in the past.

Another interesting thing that came out of our experiments is how good it is to have a forward model available. Evolving state value functions consistently outperformed direct control. I think the use of forward models might very well be the next big thing in evolutionary robotics. We have a couple of exciting ideas for how to do this, now we just need time to get working on that...

Anyway, that's all for today. Slightly more unstructured than the usual. But so am I.

Car Racing Competition updated

2007-02-15T20:21:00.000+01:00

The car racing competition is now updated, with minor changes to the code, submission instructions, and a hall of fame:

http://julian.togelius.com/cig2007competition/

Please consider participating. It's easy to get started, and really fun! (Hah, like I was ever going to tell you it's hard and boring, even if it was... Really, I've tried hard to make it as easy as possible to enter.)

If you decide to give it a go, I would appreciate a mail stating this intention, so I can put your mail address on a list of people to notify in the unlikely event of changes to the rules, code, etc.

Sensorless but not senseless

2007-02-06T19:40:00.000+01:00

Imagine you were driving a car in a long, dark, tunnel, and suddenly your headlights started flickering, going off and on irregularly, with intervals of a second or so. What would you do? It seems the only way you could keep from crashing would be to accurately remember the bends of the tunnel. For example, if the lights went out just before a left turn, you would have to predict in how long time the turn starts and start turning appropriately.

Now imagine you were driving a radio-controlled car, but due to some low-grade engineering, there was an unfortunate delay between when you issue a command (such as turning left) and the command has an effect (angling the wheels). How would you handle this? It seems you would have to predict the effects of your turning, so that you started and stopped turning slightly before you seemed to need to.

These two situations are the inspiration for a paper we (Hugo, me and Magdalena) are presenting at the 2007 IEEE-ALife Symposium in Hawaii. Essentially, we wanted to see whether we could force our controllers to learn to predict. Of course, we used my good old car racing simulator for the experiments. To remind you, this is what one of our evolved controllers looks like when all six sensors are turned on and current: (The strange lines represent the sensors)

Now, let's turn of the sensors intermittently and see what happens: (No lines = no sensors)

Not very pretty. Can we improve on this? We tried, by recording the car driving around a few tracks and trying to teach neural networks to predict the future (what sensor input comes next, given current input and action taken). First, we used backpropagation for this. Combining such a predictor with the same evolved controller as before looks like this:

Better than before, but not much.

So we tried another thing. Instead of training the predictor networks to predict, we evolved them for being able to help the controller to drive. It might at first not seem like much of a difference, but in fact it is crucial. Look for yourselves:

CLearly much better. And the difference turns out to be not only quantitative, but also qualitative. But before we go into the analysis, let's look at the other task: the delay task. Below is the same good old evolved controller as in the above examples, but with all sensor inputs delayed by three time steps:

Looks like the driver is drunk, doesn't it?

Let's see if we can do something about this. First, we try to predict the current sensory state from the outdated perceptions, using a predictor trained with backpropagation. We then get something like this:

Pretty terrible. The driver went from drunk to stoned.

The next step was to instead evolve a predictor for maximum performance, as we did with the intermittent task above. Again, the result is strikingly different:

So, what's the take-home message from this? That evolution works better than backpropagation for learning predictors? Not so simple. Because when we analyse the various evolved and trained predictors, it turns out that the evolved predictors don't actually do any prediction! In other words, the mean squared error of the predicted next state and the real next state is quite low for the trained predictors, but horribly high for the evolved ones!

So, again, what does this mean? For one thing, the type of neural networks and the data we are using (only one prior state and action) is not enough to predict the next state as accurately as we would have needed. Therefore the predictors we got with supervised learning were not up to the task. Evolution, on the other hand, quickly figures out that accurate prediction is impossible and decides to go for something else. The evolved predictors instead act as extensions of the controller, changing its behaviour so that it copes with the missing or delayed data better. These changes might include slower driving, higher propensity for turning one way rather than the other, or making sure that when bumping into walls, the back end of the car goes first, rather than the front of the car.

At least, this is what we think happens. Let's say that the topic merits further study... please read the paper if you're interested.

I'm not so sure if any of the above made much sense to you, dear reader. Is my habit of trying to summarise the main points of whole papers a good one? Or does it all just become compressed to the point of unintelligibility? Tell me!

Physical car control

2006-12-06T03:07:00.000+01:00

We recently got a new Vicon motion capture system installed in our robot arena here at Essex. It's an amazing piece of equipment. Able to track hundreds of infrared reflectors at a 100 hz or more with millimetre precision, you can even use it to track the spinning blades of a micro-helicopter!

The video below is from our first experiments with tracking a real radio-controlled toy car with the Vicon system, and controlling it from a desktop computer via a hacked transmitter connected to the parallel port (as in earlier experiments using webcams).

Although the car above was controlled by a hard-coded algorithm (about 15 lines of code!) we think we can do significantly better through a learned, and possibly learning, controller. So right now we are working on an approach to automatically inferring models of the car dynamics, evolving controllers for these models, and using the controllers thus learned in simulation to control the real car. We (as usual I'm working with Simon, but right now also with Renzo, Richard and Hugo) have a couple of exciting ideas about this, which I might blog about as soon as we've convinced ourselves that they actually work. Stay tuned!

Simulated car racing competition

2006-10-25T23:21:00.000+02:00

I am running the simulated car racing competition for CIG 2007. The problem is a bit different from the versions of the car racing problem we've been exploring so far in that there are no walls, and the next two waypoints are visible to the controller. But there are similarities as well - in fact, quite a bit of the simulation code is reused from my earlier experiments...

Please consider taking part in the competition - the final rules are not online yet (will be really soon, promise), but the code is there for you to start playing around with. It will be really interesting to see what sort of controller the winner will be - hand-coded? Evolved neural network? Fuzzy logic? Genetic programming? Learned through temporal difference learning? Something completely different? (Probably it will be some sort of hybrid of man and machine efforts. Hybrids always win in the end.)

So, off you go. Have a look at the competition, and start designing your controllers.

Yes, I mean you.

That's more like me

2006-10-10T04:25:00.000+02:00

Richard needed a face to use on a cube for his humanoid robot to play with (don't ask) so he put me up against the wall and took a shot. I think it captures the inside of me pretty well, maybe better than it captures the outside of me.

SAB 2006 Workshop on Adaptive Approaches for Optimizing...

2006-10-06T13:31:00.000+02:00

...Player Satisfaction in Computer and Physical Games is the rather long title of a workshop I visited in Rome last week. It was organized by Georgios Yannakakis and John Hallam, who wish this to be the first of a series of workshops dealing with how various computational intelligence techniques can be used to make games more entertaining - a most laudable initiative, and a good start to the series. The workshop featured seven academic papers and one invited talk from Hakon Steinö, and of course lots of good discussion over pizza and white russian.

Our paper there had a long title too: Making racing fun through player modeling and track evolution. I must say that I think this is a quite good paper, definitely one of the better I've (co-)written. It deals with how to identify and reproduce a human player's driving behaviour in a racing game, and use thus behavioural model to automatically create tracks that are "fun" for the player.

Of course, how to measure "fun" in a game is a question which is far from settled. But an interesting question, and potentially industrially relevant. The issue of automatically creating content (e.g. racing tracks) for games seems to be quite hot as well - fertile ground for research indeed.

PPSN 2006 Conference report

2006-09-14T00:02:00.000+02:00

So, the conference is over now, and I look forward to a few days of doing nothing at all. (Well, maybe visit a museum or two, or go hiking on a glacier, but I mean nothing involving evolutionary computation.) The last afternoon was spent in the Blue Lagoon, an outdoor thermal bath, making this one of the precious few scientific conferences where you get to see the other participants in only swimwear. A shame, though, that the population in question has so little "diversity".

So, how was the conference itself? Good. Very well organized, and fabulous for networking, because of the small size, poster-only presentations, and generally good atmosphere. It really made you feel part of the community, much more so than for example CEC does. So much part of the community that I'm really reluctant to write anything negative about the conference. (Maybe I should get an anonymous blog as well?)

The one thing I could complain about was that the conference was rather focused on theory and basic empirical research, and I might be a bit more of an applications guy. That's more of a problem with me than with the conference, however. And there were plenty of papers I did enjoy. I tend to enjoy theory when I understand it. My good friend Alberto won the best student paper award, which I think was well-deserved. His theory is one of those I do understand.

We also had some very good keynotes, especially the one from Edward Tsang on computational finance. And it was possibly to pick up some of the trends in the community. Basically everybody seems to be involved in Multiobjective Optimization, which I find potentially useful, and quite a few people are doing Evolution Strategies with Covariance Matrix Adaptation, which I find completely incomprehensible.

But I must say that quite a few people took an interest in my own paper as well, in spite of it being so different from most other papers there. Or maybe because of that.

New papers online

2006-09-13T01:40:00.000+02:00

Two new papers on the evolutionary car racing project are now available on my home page. One will be presented on a small workshop in Rome in a few weeks time, the other was presented at PPSN yesterday. Yes, that means I am in Iceland right now. What it's like over here? Cold and expensive. But not without its charm. I'll be back soon with a conference report of some sort.

Learning to fly

2006-08-01T23:41:00.000+02:00

The Gridswarms project, on which my friend Renzo is working, is about creating swarms of miniature helicopters that fly around and share their computing resources in order to perform tasks in a coordinated manner, inspired by the way they do it on the Discovery Channel. (That is, inspired by cooperation among insects. Nothing else.)

Yes, it sounds pretty science fiction, and yes, it's been covered several times by the media, e.g. Wired. And I'm pretty sure they will succeed as well.

I'm not officially part of that project, but as I tend to hang out with Renzo all the time, we cooperate quite a bit on our research as well. Only on things we both understand, of course; I hardly know anything about hardware design, Kalman filters and such stuff. One problem I could help him with, though, is the automatic design of the basic helicopter controller.

You see, the plan is to have the helicopters perform all sorts of interesting flocking and swarming behaviour, perhaps coordinated target tracking, or distributed surveillance. But these advanced behaviours need to be built on top of a reliable flight controller layer, whose task it is to keep the machine flying in the face of various disturbances, and implement the orders (e.g. "go to point x, y, z, but quickly!") of the swarming layers.

Designing such a controller by hand is in no way easy. It is even harder than actually flying the helicopter, which I can tell you is not easy at all. So we turned to evolutionary algorithms and neural networks to do the job for us.

Now, what an evolutionary algorithm does is essentially systematical trial-and-error on a massive scale. Doing massive trial and error on real helicopters (albeit miniature) would be a bit... expensive. Not to mention slow. So we needed to do the evolution in simulation, and because the real helicopters are still under developments we had to contend with a third-party (very detailed) helicopter simulation for the time being.

Without further ado, this is what it looks like. Remember that we have provided absolutely no knowledge of how to fly the helicopter to the neural network, it has learnt it all by itself, through evolution!

As you might or might not see from the movie, the task is to fly a trajectory defined by a number of waypoints (yellow). (As should be evident from the movie, the helicopter is shown from behind in the right panel and from above in the left panel.) Our evolved neural networks perform this task much better than a hand-coded PID controller, and is reliable even under various disturbances, such as changing wind conditions. And as far as we know, we are the first people in the world to successfully evolve helicopter control.

Getting there wasn't all that easy, though. To begin with, the computational complexity is absolutely massive - we used a cluster of 34 Linux computers, and even then a typical evolutionary run (a hundred generations or so) took several hours. What we also discovered was that no matter how much computer power you have, the right behaviour won't evolve if the structure of the neural network is wrong. It took us a lot of time to find out, but a standard fully connected MLP net won't cut it. Instead you have modularize either according to the dimensions of control or according to...

...but hey, I'm losing you. I can't get too far into technical details on a blog, can I? Go read the paper we presented at CEC two weeks ago instead. It is available online, click here!

Anyway, there is more work to do on the project, and I'll get back to this topic!

WCCI 2006 conference report

2006-07-30T19:49:00.000+02:00

As of yesterday, I'm back from Canada. Vancouver is fantastic, and I certainly wouldn't mind moving there. The conference (WCCI/CEC) was not bad either, though a bit too big - how are you supposed to find the information you are interested in among a total of almost 1600 papers, including 400-500 on evolutionary stuff?

There was some excellent stuff presented, including the keynotes by Sebastian Thrun and Risto Miikkulainen, and some individual papers, such as a simple but ingenious co-evolutionary algorithm by Thomas Miconi.

As usual, there was also a lot of "noise" - it is astonishing how many papers are presented that, while not being technically incorrect, makes insignificant progress on insignificant topics, and just makes you wonder why. Why did anyone care to write these papers, and then travel far away to present them to not very interested audiences? Because the authors didn't have any better research ideas, and desperately needed to lengthen their publication lists in order to get their PhDs / obtain funding / get tenure etc.? Probably.

As Philip Ball notes in his book Critical Mass, more than half of all scientific papers don't get cited at all, except by their authors. Makes you think. (And no, I haven't had that many citations either - yet...)

Anyway, back to the conference. It all started out with a quite amusing keynote by Robert Hecht-Nielsen, who presented an "Architecture of cognition", ~~speaking~~ preaching with no shortage of confidence and enthusiasm. What he actually presented was an example application based on a form of Hebbian learning, which could generate complete sentences based on afew trigger words and large amounts of previously scanned text. From a linguistic standpoint his invention indeed seems rather radical, as it produces correct English grammar without any explicit rules of grammar at all. But the suggestion that it has any kind of "real" intelligence is quite stupid, as the sentences produced were most often simply not true, and there is no mechanism by which it can learn from mistakes or suppress false information. Intelligence requires some sort of interaction with the environment, and I'm more prepared to say that a thermostat is intelligent than that Hecht-Nielsens program is. As someone on the conference said, what he presented was a bullshit engine. A good one apparently, and potentially useful, but still only a bullshit engine. A little bit like Eliza.

My own talk received fairly good feedback, and I had some stimulating discussions, including some industry people. I'm looking forward to PPSN, though, where the format of the presentations is more focused on interaction.

Another evolutionary car racing video

2006-07-12T20:01:00.000+02:00

Here is an evolved car controller navigating a rather difficult track. I usually do worse than the controller does when I try to drive that track myself, frequently colliding with walls and having to back up and try again. Note that it seems impossible to evolve a controller for this track from scratch, instead I had to start from a controller that was previously evolved to drive several easier tracks. Evolution had to progress in an incremental fashion.

For more on this, read my previous post on evolutionary car racing.

Reinforcement learning - what is it, really? And why won't it work?

2006-07-12T02:35:00.000+02:00

At the moment I'm working on several car racing-related projects simultaneously, but the one that's receiving the most attention is trying to compare evolution with reinforcement learning, to see if I can achieve the same results with those methods.

Well, I suppose I should say that I try to compare evolution with other forms of reinforcement learning. After all, evolutionary algorithms are just one set of ways of solving reinforcement learning problems.

It turns out not to be very easy at all to get anything working. I've tried learning values of state-action pairs from a good driver; this might not really be reinforcement learning but rather some sort of supervised learning, and anyway it doesn't work. I'm now working on simultaneous learning of forward models and sensor-state value estimators, which frankly seems unnecessarily complicated.

Of course, it must be possible to apply reinforcement learning to car driving, and I'm sure people have done it. But I am pretty sure it has not been done with the limited information I'm giving the controller. Anything is easy when you cheat, and part of my research program is not to cheat.

Anyway, I'm off to CEC in a few days. I'm bringing the Sutton and Barto book to read on the flight, hopefully I'll get an insight or two.

Sticky stuff

2006-06-27T19:52:00.000+02:00

Those stickers had been disgracing mine and Renzo's already ugly computers for much too long. Finally we decided to put them where they belong.

Hmm... what more can you do with these stickers?

Why do I keep reading Digg when Slashdot is better?

2006-06-27T19:42:00.000+02:00

They say Digg is bigger than Slashdot than these days. Bigger, better, newer, 2.0 and what not.

Indeed, I find myself scanning the Digg front page more often than Slashdot's ditto. Far too often, actually. Obsessively often? Well well, I actually get proper work done now and then.

Still, it's simply not true that the quality of the "news" on Digg's frontpage is higher than the news on Slashdot. On the contrary, Digg suffers from a disgusting amount of mob mentality. Half of what's on the front page is not news at all, merely short text snippets propagating rumours that everybody's already heard or views that most people already agree with. Which is why they get digged to the front page: people like to hear/read what they already believe in.

And this is not really a problem with Digg, it's a problem with people. (And like all problems we can't really do anything about, it's not even worth thinking of it as a problem, just as a fact.)

Slashdot, on the other hand, has sometimes-competent editors that sometimes put an effort into selecting and editing stories. While I might learn something I didn't already know from either Digg or Slashdot, I'm far more likely to learn something new about something I didn't already know anything about from Slashdot. Crucial difference.

So, back to the question: Why do I keep reading Digg when Slashdot is better? Because the Digg is updated more often, and the items are shorter. It's that simple. I think.

List of researchers/centres active in Computational Intelligence and Games

2006-06-20T19:12:00.000+02:00

I thought a list of researchers and research centres working in the field of Computational Intelligence and Games (CIG) would be a useful resource to people like myself. For a definition of CIG, see the eponymous conference series; in short, it's about applying techniques such as evolutionary computation, reinforcement learning and neural networks to computer games, like strategy games, shooters, platformers, driving games and board games.

The format of the list would be the institution (university, company etc.), followed by a list of relevant researchers (those who spend a significant amount of their time on CIG research), and possibly a few words about what the topics of research are. The list is meant to be continuously updated: I am fully aware it is far from complete at the moment, so please help me expand it by posting additions and corrections to the list in the comments below! This post will then be updated as additions come in.

Brandeis University: Jordan Pollack. Co-evolution, theory, backgammon.

Natural Selection, inc.: David Fogel. Evolution, board games.

University of Essex: Simon Lucas, Julian Togelius. Neuroevolution, board games, Pac-man, car racing.

University of Iceland: Thomas P. Runarsson. Evolution, reinforcement learning, board games.

University of Nevada, Reno: Sushil J. Louis. Evolution, strategy games.

University of Paisley: Benoit Chaperot, Colin Fyfe. Motocross racing.

University of Pretoria: Andries P. Engelbrecht. Particle swarm optimization, board games.

University of Southern Denmark: Henrik Hautop Lund, Georgios N. Yannakakis. Player modeling, Pac-man.

University of Texas, Austin: Bobby Bryant, Risto Miikkulainen. Neuroevolution, strategy games.

AI: All fun and games

2006-06-20T19:10:00.000+02:00

Who believes in artificial intelligence (AI) nowadays? Not many, it seems.

For some fifty years, computer scientists have been saying that they know the principles for creating intelligent machines, and that a working piece of AI hardware of software is just around the corner. Or maybe around the next corner. People nowadays seem not so much to take those claims with a pinch of salt as they seem to just ignore it.

AI research is all good, the reasoning goes, but all we are likely to get is better chess players, traffic control systems, brain scanners, search engines, rice cookers, or what have you. Human-made technology that autonomously learns and adapts to truly new situations, acting seemingly goal-directed and generally sensible will never appear, because we just don’t know how intelligence such as our own works. Some say that if we were so simple that we could understand ourselves, we would be so stupid that we couldn’t.

Of course, I don’t agree with this.

If I didn’t believe that we will some day create real artificial intelligence, if what I do all day was just plain engineering, I wouldn’t be doing it. (I would probably do something that involved significantly more glamour, girls and sunshine.) But the critics do have a point: we don’t understand how intelligence works right now. Maybe we will understand one day, maybe we won’t.

And this of course makes building an AI using standard engineering techniques, like how we would build a car, a house or an operating system, all but impossible.

Instead, I (and some others with me) think that we can create AI without knowing how it works. The idea is to let the AI build itself, and the method is trial-and-error, or as it is know in biology: Darwinian evolution.

To put it simply, we start with a “population” of randomly generated candidate AI’s, (most often these are software programs in the form of simple brain simulations, or “neural networks”) and we evaluate how good they are at some task. Because they are all randomly generated, they are usually not very good at the task, but some are a little less bad than others, and we keep those. We then delete the worst of the lot, and replace them with slightly changed (“mutated”) copies of the least bad. And then we do that again, and again, and again…

This is so simple that seems it shouldn’t work. But it does. It works in nature – we are intelligent, aren’t we? – and it works in computer simulation. A small community of researchers have been working along these lines for a decade or so; some representative research can be found in the book Evolutionary robotics by Stefano Nolfi and Dario Floreano.

The astute reader will already have noticed a problem with this: this research has been going on for a decade or so, but where is the AI we were promised? Where is HAL, R2D2, Skynet? Not even the car from Knight Rider seems to be ready for the market anytime soon. Indeed, we have a problem. The evolutionary approach works perfectly well for simple problems, but fail to “scale up” to more complex tasks.

I believe this is because the tasks people try to evolve solutions for are not right. What researchers usually do is to teach a robot to do a specific action, like pick up red balls and avoid blue. Ultimately, very little is gained from this, as there is no obvious way to proceed. Once you have learned to pick up red balls, how is that going to help you to brew a good cup of coffee, or take over the world?

It's like a rat learning to push a lever in a skinner box for some food reward. Once it has learnt to push this lever, there is no way to build on this "knowledge" to learn anything interesting.

The right task needs to be simple to get started with, yet more or less limitless in its ultimate complexity, and with a good learning curve so you can make continuous progress. Like life, or like a well-designed computer game.

Indeed, some games (mostly puzzles and board games) are marketed as taking "a minute to learn, but a lifetime to master". That's exactly what we're looking for. But this doesn't only apply to board games. The basic principles behind a carefully designed FPS like counter-strike are grasped in almost no time at all, but many people play it every day for several years and keep getting better at it!

At the moment we are working with a simple car racing game. Racing games are in a way ideal, as more or less anyone can pick up the controller and race a lap, but to become a racing champion requires a lifetime of practice, and quite a bit of intelligence. For example, you need to be able to plan your path, keep track of your opponents and anticipate their actions. I am making steady progress on having my AI’s teach themselves how to do this - ssee the videos.

But will automatic development of car racing AI really be a stepping stone toward general intelligence? I think so, but you are welcome to disagree with me - I'd love to hear why it wouldn't. And in any case, it will at least make for better racing games.

What makes racing fun?

2006-05-15T18:26:00.000+02:00

Me and Renzo are working on a paper on how to automatically create fun racing tracks. And not only that, but racing tracks that are fun just for you - which means that we must first model how you drive with a neural network, and then use this model of your driving to create the tracks.

Grand plans, but will it work? Well, we'll see soon. In the meantime, here's a question for all of you: what exactly is it that makes a racing game fun? And what is it that makes a particular track/circuit in racing game fun?

Of course, in the end we want some quantitative measure we can put into our code, but the quantitative part is really up to us. What we're looking for right now is suggestions, ideas. Any sort. What makes racing fun? Please leave your comment below!

Slashdotted! (Well, sort of...)

2006-05-10T16:43:00.000+02:00

I posted a question to Ask Slashdot a few days ago, which recently got up on the front page and has at the time being had 190 replies:

What Would You Like to See from Game AI?

(Incidentally, it seems to have generated quite a bit of traffic to this blog as well...)

So what can I say about the answers? Well, there seems to be a lot of variance in what people want, or think they want. The two most common requests are AI that learns (from the player, or from past behaviour) or just "lives its own life", and AI whose reasoning is understandable/transparent/believable. While I certainly agree with the learning and adaptation bit - that is very much what I am working on - I am not so sure about the other request. Architectures that learn are generally not very good at explaining why they do what they do, but usually very good at coming up with behaviour you didn't expect when you designed them.

Do people really want to understand why agents in games do what they do? And to what extent? Surely it becomes boring when you can predict every move of your opponent, but I suppose a game where the opponents act seemingly randomly is not so fun either. Maybe there's a tradeoff. But then again, isn't there a difference between seemingly random behaviour, and seemingly random but obviously effective and therefore somehow goal-directed behaviour? The sort of difference that makes people go to great lengths to understand the behaviour?

Of particular note is the poster who complained about racing games that adapt their difficulty level to the human player, and thus ends up winning in the last lap however well you drive. But that's not AI. That's just adapting a difficulty setting. A game that not just adapted to your skill, but instead adapted to counter your particular driving style, would be much more interesting. And you would learn more from it.

Evolutionary car racing videos

2006-04-27T21:00:00.000+02:00

I've put up a few videos of our evolved car racing controllers. The fascinating thing is that no human has told the cars you will see below how to drive, or indeed how to maneuver aggressively so that competitors crash into walls. Instead, me and Simon used evolution strategies (similar to genetic algorithms) to evolve neural networks (sort of simple simulated brains) that control the cars. It's plain simple survival of the fittest - we start with random networks, and see who can drive the car furthest in a set time. To start with, all of the networks are pretty bad, but some are less bad than the others, so we allow them to "reproduce" (being copied) with small changes, and repeat the process... Just like in nature, this seemingly random process produces seemingly intelligent behaviour.

To start with, this is a single car driving one of the standard tracks:

The inputs to the neural networks are sort of simulated rangefinder sensors (e.g. ir or sonar) as shown below, the network is a three-layer MLP (probably the most common type of neural network), and the outputs are motor and steering commands:

The paper detailing the original experiments, where we compared neural networks and rangefinder sensors with other architectures, is here. A follow-up paper, where we evolved cars to be able to drive several different tracks, is here. This was done by evolving the network to drive the car on one track, and then step by step letting the network teach itself new tracks. There are many tricks to making this work properly, such as starting with fixed sensor positions but later letting the evolutionary process handle the positioning of the sensors.

Most recently, we submitted a paper (not available online yet) to the conference PPSN about co-evolving several cars to drive against each other. Have a look at the following:

We did notice a few interesting things concerning the interaction of the cars in the course of the experiments. One was that what went into the fitness function - in other words, what we rewarded the neural networks for doing - had a drastic effect on the cars' behaviour. If we used a fitness function where the neural network was rewarded for its car being in front of the other car, regardless of how far along the track it was, we often saw some pretty aggressive driving with cars actively crashing into each other and trying to force each other off the track. If, on the other hand, we rewarded the networks just for getting far along the tracks, the cars usually avoided collisions. Check out the following examples of vicious neural network-drivers:

The last example shows that we still have some way to go: sometimes the outcome of the race is that both cars find themselves stuck against some wall. So far, the cars haven't found out how to back away from a wall and resume the correct course. We're working on more complex neural networks and sensors to overcome this.

Of course, I hope that these technologies will some day be incorporated into actual racing games (which shouldn't be impossible, looking at the sorry state of most game AI) and physical vehicles. But along the way, I think there is a lot to be learned about how the evolution and learning of behaviour works, and I think that games are the ideal environment for doing that research in. More on that in a later post.

This is me

2006-04-23T03:22:00.000+02:00

Last summer, I volunteered to be a subject in some BCI (Brain-Computer Interface) research. Hinrik, an MSc student I also used to go out and get drunk with (and try to avoid fighting with squaddies, but that's another story) was doing a project on robot control via EEG. He fitted lots of electrodes on my head, and I had to think of moving (without moving) while watching a robot move. This is what I looked like:

Nice, eh?

BCI is definitely an interesting field, and the BCI group here at Essex seems to contest of thoroughly nice (and competent!) people. I wouldn't mind being more involved in such research...
...but no, I have enough to do as it is. And I'm quite happy with what I do.

Evolutionary sudoku solving

2006-04-22T23:21:00.000+02:00

Alberto, me, and Simon recently got our paper on evolutionary sudoku solving accepted at CEC 2006. We thought we were the first researchers in the world to apply evolutionary algorithms to Sudoku, but according to one of the reviewers, we actually came second, as another paper on EC and Sudoku was accepted to Euro-GP a month or so earlier.

Anyway, our experiments worked really well. A quick introduction, for those who don't think in terms of evolutionary algorithms: We start with the empty sudoku grid, empty except for the fixed positions that define the puzzle. The algorithm, in its very simplest version, then fills in the empty positions with random numbers between one and nine. At each generation, a random change (mutation) was made to each grid, by changing one of the non-fixed numbers to another random number between one and nine. At the end of each generation, the fitness of each grid was evaluated by counting the number of unique elements in each row, grid and square. The grids with highest fitness were kept for next generation, and those with lower fitness were replaced with mutated clones of those with higher fitness, just like in nature. After a number of generations, such an algorithm actually solves most, if not all, Sudoku problems!

Not that our evolutionary algorithms solved sudoku grids faster than existing methods that take into account the structure of the problem - it is doubtful whether evolution will ever do that, at least for standard-size grids. But our main aim was to verify some predictions from Alberto's theory using Sudoku as a testbed.

Alberto's theory is about geometric crossover. In my description I omitted crossover - when a new individuals (in this case a new Sudoku grid) is created by mixing two parents (in this case two other Sudoku grids). Actually, many evolutionary algorithms don't use crossover, because it is so tricky to get it right - it can easily end up doing more harm than good. But when it's used right it can actually improve the efficiency of an evolutionary algorithm dramatically. The highly mathematical theory of Alberto is about exactly what sort of crossover is appropriate for what problem representation. Greatly simplified, it says that the offspring should be somewhere between its parents in the multidimensional space of representations. And it turned out that the crossover operators designed according to this theory indeed were very effective.

But enough about this - go read the paper to get to know more! The source code is available if you want to do your own experiments.