Questions and Answer Sets

This post might get a little bogged-down in logic programming, but stick with it. I thoroughly enjoyed revisiting two articles last week by Adam Smith and Michael Mateas of the Expressive Intelligence Studio at UC Santa Cruz. They’re both very readable – Variations Forever is an account of building a sort of self-designing arcade videogame, and the slightly more intimidatingly-titled Answer Set Programming for Procedural Content Generation is a superb article in an AI-for-games journal. I was turned back to these projects after some paper feedback pointed me towards Tanagra, another UCSC project (but a topic for another day). Both articles come highly recommended! Here’s what I took away from them.

ASP, Briefly

Answer Set Programming (ASP) is a kind of constraint logic programming. Logic programming isn’t something that everyone comes across, even if they study Computer Science, and in general requires a very different way of thinking about code and data organisation. I realise I am not selling this terribly well. In all honest, this sort of thing makes more sense when you see it, so let’s take a quick look at some ASP-style code (canonical example courtesy of Adam Smith):

wet :- raining.
wet :- sprinkler_on.
dry :- not wet.
:- not wet.

A lot of logic programming is about stating knowledge. The ‘:-‘ syntax is like an implication, so the first two lines say it is wet if it is raining and it is wet if the sprinkler is on. The third line is a special bit of syntax that says it is dry if you cannot prove that it is wet. If you’ve done Boolean logic before, beware – this isn’t the same as being able to prove it’s not wet. For instance, you think highly of me if I don’t write blog posts in my underwear. You can’t prove for sure that I’m not writing this in my pants right now, but all you need to retain your respect for me is to not be able to prove that I am writing this in my underpants. Subtle, but different.

The last line is even more special – it has nothing on the left-hand side of the ‘:-‘. It’s what we call an integrity constraint and, to cut a logic-based story short, says that it is wet. (It actually says that it is not the case that wet is unprovable, but translated to English it’s about that).

Answer set solvers find all the situations that satisfy an answer set program. In the above example, there are three possible situations – it is raining, the sprinkler is on, or it is raining and the sprinkler is on. We know that one of these must be the case, because we used integrity constraints to specify that it is definitely wet, so those solutions all make sense. As you can see, ASP can be used to state things that are definitely true about the world, and then draw conclusions about what other things are logically consistent. For instance, the above toy program might help us decide why we are currently soaking wet. We know that we get wet if it’s raining, or if the sprinkler is on, so any of these might be true. I realise this doesn’t strike you as the most amazing application of computer science, but it gets better.

Procedural Content Generation using ASP

Smith and Mateas propose ASP as a useful tool for procedural content generation for a number of reasons, but the ones which stand out to me having toyed with it for a while are the incredible flexibility of the programs, and the complexity that can arise out of low-level statements about how a system works.

When I say flexible, I’m talking about ASP’s declarative nature. It’s easy to add extra knowledge or constraints to an existing system without breaking everything. We can point out that it’s unlikely you’d water your garden in the rain by adding one line:

:- raining, sprinkler_on.

And bam! Any answer sets featuring both of those things disappear. We can add more complexity to the world by expressing things in terms of other things:

has_affair(X,Y) :- married(X,Z), relationship(X,Y), Y != Z.
has_motive(X,Y) :- married(X,Z), has_affair(Z,Y).

Which, in some hypothetical social engineering program, describes what an affair is, and adds that someone has a motive to kill their spouse’s lover. That’s just knowledge about the world that doesn’t (in most cases) affect the rest of the ASP program we’ve written. Then, by adding a constraint about what is already true:

:- not has_motive(alice, eve).

(Remember, this means that it is true that has_motive(alice, eve))

We let the ASP solver work out that maybe Eve is having an affair with Alice’s husband Bob. As we add more conditions under which someone has a motive to kill someone, the list of solutions expands, reshaping things we haven’t specified (is Alice herself having an affair and Eve found out about it?) and finding new solutions.

But what I like most about this approach is how readable it almost is. There are a few counterintuitive concepts, but this feels like a system that the mod community for many games would instantly click with and be able to shape to their own desires. I’m keen to try this in my spare-time game design projects, as well as integrating a bit of this into ANGELINA’s game design sensibilities.

For more info on ASP as a procedural content generation tool, check out the two articles I linked at the top of the article. More on this stuff soon!

As for the ‘Questions’ part of the post title – I’ve started a Formspring for ANGELINA. If you’ve got any questions about the project that you don’t want to ask in a post comment/email, feel free to toss them up there.