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.

3 comments

  1. Adam M. Smith

    In noting “how readable it almost is”, you’ve made a first observation on the gap between logic and design — ASP is going for something that is close (and closer than most alternatives) to but not quite what you want in design automation. Its this gap that makes me think, however awesome ASP seems right now, the ultimate fate of ASP is for it to be buried deep inside of future artifact generators where nobody will be able to tell if it’s used or not. ASP offers a clean and declarative interface to automated abductive reasoning, and abduction has been called “the logic of design”. However, the abductive reasoning of AI is distinct from the abductive reasoning of design (which is used synonymously with “appositional reasoning”). Having to understand design-as-abduction before proceeding is, I hope, a removable bottleneck. I’m writing up something to explain this more (for which this post is healthy procrastination), so I’ll save the details for now.

    Philosophy aside, PCG-uses of ASP could probably benefit from a new surface syntax. The people who are likely to use this stuff for popular games might feel more at home with braces and indenting, a module system with imports and exports, and design-relevant keywords relating to form/function/requirement instead of assumption/derivation/contradiction. Transparent inclusion of something like SPOCK (http://www.kr.tuwien.ac.at/research/systems/debug/index.html), regression testing, and other software engineering goodies would help a bit also. Likewise, closer integration between SAT-style reasoning and the imperative details you can express with Clingo’s Lua scripting interface would remove some conceptual overhead as well.

    Assuming you could solve all of the computational details behind the scenes, what would you ideal generative space programming language look like?

  2. Pingback: The Saturday Paper: Dungeon Feng Shui | Games By Angelina

Leave a Reply