"Advanced Intelligent Paradigms in Computer Games"

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

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

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

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.

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

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

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?

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

So there you have it.

Grand and Molyneux on game AI

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.