26
Mar
13

How to build a constraint propagator in a weekend

This is a tutorial that Leif Foged and I did for the AI summit at GDC on how to build your own finite-domain constraint solver using AC-3.  It’s won’t solve the really hard problems that high-end SAT solvers can solve, but it’s very fast for problems with a lot of solutions; fast enough to run in a game engine:

      http://www.cs.northwestern.edu/~ian/GDCConstraintsHowTo.pdf

Comments welcome.  I intend to keep revising it, since it isn’t archivally published.

 

About these ads

10 Responses to “How to build a constraint propagator in a weekend”


  1. 1 Tom
    August 20, 2013 at 5:21 pm

    Hey, nice topic. I’m reading the paper but I’m not sure if there is a mistake or I’m not reading it right. You have the following:

    newset = v.values & set

    in the function

    Narrow(v, set)

    now, set = v \in v_i.values where v_i.values = v.values which means that the value of newset is set no matter what the values of the sets, v.values and set. Did you mean XOR? Or do I not understand what’s going on.

    Thanks.

  2. August 20, 2013 at 8:12 pm

    Good point. However, set won’t always be a subset of v’s current values. For example, if you have a propagate method that’s ensuring two variables x and y have different values and it notices that x has been narrowed to a single value, then it will narrow y to ~x.values (i.e. everything except x’s single value).

    One could write it differently so that Narrow just updates v to be the set argument, but then in cases like the above, you need to remember always to manually intersect the new mask with the old values. Since doing the intersection is cheap, it makes more sense to do it automatically inside Narrow.

    • 3 Tom
      August 20, 2013 at 9:47 pm

      Ah, I see, yeah, I caught the reuse of the function later on. Should have kept reading.

      I’m also not sure why every constraint contains a list of all variables? Is it not better to remove variables that have already been placed from the list or does this not make a difference in performance?

      Does such a method work where the list of variables is infinite such as finding solutions to equations?

      • August 20, 2013 at 10:00 pm

        It’s just the variables that are involved in the constraint. So if you have a constraint like x = y+z, it would just be the variables x, y, and z. The constraint needs it so it knows what other variables to propagate to when one of the variables is narrowed.

        Equations don’t generally have infinite numbers of variables, but the variables might have infinite numbers of possible values (again, x = y + z is an example). And no, this technique doesn’t work then. The tutorial is mostly just talking about “finite domain” solvers, and “finite domain” here means the set of possible values for the variables (their domains) is finite. And realistically, it also means the sets are small enough to be represented as a bitmask in a machine word.

        The tutorial also talks briefly toward the end about how you can handle limited cases of floating-point variables by representing the current possible values for the variable using an interval (upper- and lower-bounds) rather than a bitmask. Our path function system uses that, although only in a very limited way. I’m working now on a system that has a much more general implementation of floating-point variables, although as with all this stuff, things get slow fast if you make the constraint solver work too hard. I ought to have a paper on it in time for the FDG conference.

  3. 5 Tom
    August 21, 2013 at 10:28 am

    Thanks, I think I understand now. Good luck with your submission.

  4. March 31, 2014 at 1:12 am

    I read the draft when it was first published and am finally getting around to implementing a solver in order to better understand it. I noticed that, Narrow, in the examples before the undo stack assigns the variable’s values attribute with newset. Yet in the “realish world” examples where you describe the Variable class I noticed that this line is missing and was wondering if that was intentional.

    Nice work, btw. Really digging your work.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: