D&D, Knowledge bases, and Prolog (oh, my!)

Posted by Jamis on September 29, 2006 @ 11:58 AM

I only get to tinker on my D&D DSL (as mentioned in 1d6 more reasons to love Ruby) a very little bit each week—maybe an hour or two, if I’m lucky. This means the project is moving ahead with excruciating slowness, but it also gives me plenty of time to think about the roadblocks I face.

My current obstacle is how best to represent dependencies. For instance, certain feats are only available to characters who have met specific prerequisites. Likewise, prestige classes have various lists of requirements, as do certain magic items. Additionally, the list of goal conditions that the user requests of the utility (“I want a mid-level male elven wizard who can cast Fireball”) is essentially a list of dependencies, too.

I did manage to implement a simple tree for representing some kinds of dependencies. It can take the prerequisites for the Archmage prestige class and apply them to a character, telling me not only whether the character is eligible for the class, but if not what the character still requires in order to become eligible. It’s pretty slick, though hardly something to brag about at this point.

The last couple of weeks have seen me pondering over how to represent another kind of dependency; that is, the parameterized dependency, and especially a chain of parameterized dependencies, where each link in the chain has the same parameter. Consider the case of the Greater Weapon Specialization feat. You have to select a weapon that you already have the Weapon Specialization and Greater Weapon Focus feats for. Weapon Specialization and Greater Weapon Focus both require the Weapon Focus feat, and Weapon Focus requires (among other things), Weapon Proficiency in the weapon of choice. The chain from Greater Weapon Specialization to weapon proficiency requires that each link reference the same weapon; weapon proficiency with a dagger won’t make you eligible for Weapon Focus with a longsword.

It’s one thing to evaluate this chain when the parameter is known. If I want to know if a character is eligible for Greater Weapon Specialization (Longsword), then I know that they have to have the requisite feats with the longsword as well. However, sometimes I need to ask “what feats is the character eligible for right now?” In that case, I can see that the character has weapon proficiency with a particular set of weapons, which implies that the character may be eligible for Weapon Focus in any of those weapons as well. Even trickier is the case of a prestige class that simply says “must have the Greater Weapon Specialization feat”, but doesn’t require a specific weapon. In that case, when I ask whether or not the character is eligibile for the prestige class, I basically have to use a variable for the feat’s parameter and then bind it, at the end, to the set of all weapons that the character might be able to use to eventually meet that requirement.

Ah, my head spins!

However, as I was pondering all of this, I kept getting a little ping from my university memories. Something I studied (and promptly forgot) 10 years ago was trying to tell me it was now relevant…

Enter automated theorem proving. As I begin researching and remembering the hours I spent on my homework and programming assignments, the concepts of Resolution and Unification came flooding home. I actually really enjoyed that class (which is probably why I remembered anything at all about it), even though I was sure I would never ever be doing anything with that knowledge.

For about 10 years, I was right. It was useless data stored in my brain.

But suddenly, it was relevant. How? Well, what my NPC generator needs to be is a knowledge base of all the facts and relationships between the various data in the system. Generating a character is (essentially) a query against the knowledge base—”has this character met this goal?” The knowledge base then needs to come back and either say “yes” (in which case the goal is met), or “no” (in which case the response includes the actions that need to be taken to help the character achieve the goal). Revelation!

With that in mind, I finally decided it was time to learn Prolog. It’s been one of those languages on my “huh, maybe I ought to look at that someday” list, but now it actually has relevance to something I want to accomplish. Mostly, I only want to use Prolog to test my ideas, and to prototype the NPC generator. I still love Ruby and think I could make a killer DSL for this in Ruby, but we’ll see what happens.

So far, all I’ve managed to do in Prolog is hard code a bunch of assertions that define a genealogy database, along with some rules that I can use to ask things like “who are the grandparents of this person”. It’s fun, and I’m looking forward to delving further in. I’m especially excited to see how far I can apply this to my original problem domain: random generation of gaming characters with some (potentially arbitrary) set of constraints.

Posted in Essays and Rants

Comments

Have something to add? Click here to leave a comment.

29 Sep 2006

1. Christian Romney said...

Hi Jamis, Just out of curiosity, what are your thoughts on Ruby's TSort stdlib. My understanding was that it was good at this sort of automated dependency resolution. Of course, this stuff is out of scope so I'm not qualified to make that assessment. I'd be interested in your thoughts on this.

2. Jamis said...

Christian, I haven't actually looked at any of Ruby's solutions. I kinda wanted to get my feet wet with Prolog first. Once I get a handle on how this may relate to my problem domain, I'm definitely going to investigate what Ruby has to offer, though. I'll most likely be following up with another blog article eventually.

3. Joe said...

You are a huge nerd. :-)

4. Gregg Irwin said...

There are a lot of ways to go with this kind of thing. I think using it as incentive to learn some Prolog is great though. Topo sort is something else to consider, certainly; and you could probably do it with a recursive DFS approach as well (sort of pseudo-make).

5. Jamis said...

Joe, haha! I choose to take that as a compliment! :) Greg, thanks for the recommendations. I'll keep those in mind.

6. Christian Romney said...

I'm really looking forward to the next article. Incidentally, Brian Harvey (of Simply Scheme fame) has a great Structure and Interpretation of Computer Programs lecture series available as streaming RealMedia video or mp3 audio. You can find it on the Berkeley website. Anyway, the last two lectures go into prolog a bit. I find Brian's didactic style to be easy to follow, so you might want to look into it.

7. Jeremy said...

I was reading through your article, and followed the wikipedia links, and must say that you caught my interest.

Over the past year I’ve been programming in Ruby on Rails. But prior to that I came from an environment where I programmed in RPG (ironically). In my previous job, we had a tool for determining if a group selected this insurance benefit what was the next set of benefits they could select.

Best luck, I’ve started exploring how I would translate that system to Ruby. Here is my attempt based in large part from what I took away from my previous job.

class PrerequisiteSet < ActiveRecord::Base
  has_many :restrictions
  has_many :prerequisites

  # If the restricted item has at least one of the prerequisites
  # then it meets this particular prerequisite set
  def has_prerequisite?(restricted)
    prerequisites.detect { |p|  p.has_prerequisite?(restricted) }
  end
end

class Prerequisite < ActiveRecord::Base
  belongs_to :prerequisite
  belongs_to :qualifying_prerequisite, :polymorphic => true

  def has_prerequisite?(restricted)
    restricted.has_qualifying_prerequisite?(qualifying_prerequisite)
  end
end

class QualifyingPrerequisite
  # is_abstract_class
  has_many :qualifying_prerequisites, :as => :qualifying_prerequisite
end

class RestrictedEntity
  # is_abstract_class
  has_many :restrictions, :as => :restricted

  # This isn't the end all solution, and only looks at shallow relations, but the magic has to start somewhere
  def has_qualifying_prerequisite?(prerequisite)
    self.reflect_on_assocations.detect { |assoc| prerequisite.class.to_s == assoc.class_name && assoc.find(prerequisite.id) }
  end

  # If a restricted entity meets all of its restrictions, then it can be "chosen" 
  def meets_all_retrictions?
    restrictions.detect do |r| 
      return false unless r.meets_restriction?
    end
    return true
  end
end

class Restriction
  belongs_to :restricted_entity, :polymorphic => true
  belongs_to :prerequisite_set

  # If the restricted entity has at least one element of the prerequisite set, then
  # this restriction has been met.
  def meets_restriction?
    prerequisite_set.has_prerequisite?(restricted)
  end
end
<pre>
09 Oct 2006

8. Nicolas Sanguinetti said...

Heh, as Joe said, you’re a huge Nerd, bu t I mean it as a compliment ;)

I know you haven’t checked any ruby solutions yet, but you might like to check out Luke Redpath’s ActiveSpec1. It’s an implementation of the Specification pattern, which borrows some concepts from logic-programming :)

Anyway, this DSL of yours is a great idea, can’t wait to see it!

http://www.lukeredpath.co.uk/2006/9/28/introduction-to-activespec
18 Oct 2006

9. Mark said...

When I read your article I realised I’d seen a discussion on Ruby and Prolog before. With a bit of searching I rediscovered these:

Parsing: http://www.kdedevelopers.org/node/2369 Implementation: http://www.randomhacks.net/articles/2005/10/11/amb-operator Discussion (in the comments): http://www.randomhacks.net/articles/2005/12/03/why-ruby-is-an-acceptable-lisp

Hope you find some of that useful.

10. Jamis said...

Mark, fantastic links! Thanks for digging those up and sharing them here. Wonderful food for thought.

23 Oct 2006

11. Niels said...

Hey Jamis,

maybe you also want to look into the following stuff (I started writing a traffic light controller tonight (yes, just for fun)):

Monads in Ruby (wip): http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html

Jim Weirich’s AMB library: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/183846

Other solutions to the “Constraint processing” Ruby quiz: http://www.rubyquiz.com/quiz70.html

A “rule engine” (probably not too useful): http://www.talios.com/a_ruby_rule_engine.htm

And I can also highly recommend the links posted by Mark.

Cheers, Niels