Implementing a propnet rules engine

So I've been looking through the implementation of the flattener: github.com/ggp-org/ggp-base/blob/5089a5b998d453044741bbe41f9934be93b16640/src/main/java/org/ggp/base/util/propnet/factory/flattener/PropNetAnnotatedFlattener.java

I kind of understand how it works on a high level, but I don't understand it well enough to rewrite it on my own. I've been looking online for descriptions of the flattening algorithm but I can't find anything.

Could you explain the algorithm, or point me to a description of the algorithm online?

First, just to be clear, it's not necessary to write your own propnet construction code in order to write a propnet-based rules engine; you can use the output of the OptimizingPropNetFactory, which takes care of all the grounding and everything.

But let's say you just want to learn what's necessary to construct the propnet, or you're interested in writing this in some other language for whatever reason.

(The implementation I'm going to describe is roughly what the OPNF does, not necessarily what the PropNetAnnotatedFlattener does; someone else wrote the latter.)

So, you want to come up with a description of all the sentences that could be true in the game (while keeping them to a finite number). The OPNF does this by dividing sentences into “sentence forms”. The idea is that two sentences have the same sentence form if you can get from one to the other by replacing constant and variable terms with other constant and variable terms.

For example, these have the same sentence form:

(does xplayer (move a 1 b 2))
(does oplayer (move a 1 ?x2 ?y2))

These don't:

(does xplayer (move a 1 b 2))
(does xplayer noop)

And these don't (you can't swap out function names):

(does xplayer (move a 1 b 2))
(does oplayer (capture c 8 d 7))

If you call toString() on a sentence form, it looks like one of these, which might help your intuition:

(does _ (move _ _ _ _))
(legal _ _)
(true (cell _ _ (piece _ _)))
terminal

This can be beneficial because it flattens the structure of the sentence. A sentence can now be represented as a sentence form plus a tuple of constants and variables, where the length of the tuple is fixed based on the sentence form. Now if you want to represent the location of a variable within a sentence, and the sentence form is fixed, you can use a single integer to represent the variable's place within the tuple.

(does _ (move _ _ _ _)) has tuple length 5
(legal _ _) has tuple length 2
(true (cell _ _ (piece _ _))) has tuple length 4
terminal has tuple length 0

Most of the sentence forms that can exist in a game are already present in the set of sentences and rules. The tricky cases look like this:

(<= (legal ?player ?move)
    (legalMove ?player ?move))
(<= (legalMove ?player (move ?x1 ?y1 ?x2 ?y2))
    …)

In this case, you have to account for the fact that ?move in the first rule may be a “move” function. To account for this, after we add all the obvious sentence forms, we repeatedly look through the game's rules for cases where a variable might represent a function, and add new sentence forms representing the rule's head when appropriate. This process is repeated until nothing new needs to be added. (This almost always terminates, but see test_case_5a.kif for an edge case of GDL that can break this. I kind of hope the GDL spec can change at some point to prevent this kind of case.)

The class that does this work in GGP-Base is the SentenceFormsFinder. It's generally used by the SentenceFormModelFactory as part of creating a SentenceFormModel, which contains a set of all the sentence forms in a game, plus some other useful information (like which of those sentence forms are constant, according to the structure of the rules).

GGP-Base actually has a specific class to deal with this by modifying the GDL directly. The VariableConstrainer changes a set of game rules so that it's equivalent to the old version, but it's also safe to assume that variables will not have functions as their values. In the above case, it would add a rule like the following:

(<= (legal ?player (move ?a1 ?a2 ?a3 ?a4))
    (legalMove ?player (move ?a1 ?a2 ?a3 ?a4)))

Note that if you do allow variables to have functions as values, this is just redundant and still doesn't change the meaning of the rules.

Once you have all the possible sentence forms, it's a pretty similar process to find which ground values each sentence form can have in each index of its tuples. Again, after finding the obvious values, we go through all the rules and find places where a variable will move a new value from a positive conjunct in the body into the head. This process is repeated until nothing new is added.

In GGP-Base, the SentenceDomainModelFactory uses this to produce a SentenceDomainModel. This is an extension of the SentenceFormModel that also includes domain information: given a sentence form, it can provide a SentenceFormDomain that allows iteration through the possible sentences in that sentence form. You can also check the possible values for each index of the sentence form individually.

After you're done with finding the domain, it should be pretty straightforward in principle to take each rule, iterate through each possible assignment of variables, and create the appropriate set of logic gates. (Each instantiation of a rule is an “and” among its conjuncts, which is then the input to an “or” pointing to the head of the rule.) The catch is that doing this naively will often take too long or create too large a propnet, even for relatively simple games like Connect Four. You need to find ways to skip and fast-forward through impossible and irrelevant assignments. Some games even need to be rewritten to make this tractable. That's a bit beyond the scope of the question, but it's what much of the OPNF code is concerned with.