A.1 Syntax

Logic Programs are built up from four disjoint classes of symbols, viz. object constants, function constants, relation constants, and variables. In what follows, we write such symbols as strings of letters, digits, and a few non-alphanumeric characters (e.g. "_"). Constants must begin with a lower case letter or digit. Examples include a, b, 123, comp225, and barack_obama. Variables must begin with an upper case letter. Examples include X, Y, Z, Age14, and so forth.

A term is either an object constant, a variable, or a functional term, i.e. an expression consisting of a function constant and n simpler terms. In what follows, we write functional terms in traditional mathematical notation - the function constant followed by its arguments enclosed in parentheses and separated by commas. For example, if f is a function constant, if a is an object constant, and if Y is a variable, then f(a,Y) is a term. Functional terms can be nested within other functional terms. For example, if f(a,Y) is a functional term, then so is f(f(a,Y),Y).

An atom is an expression formed from a relation constant and n terms. As with functional terms, we write atoms in traditional mathematical notation - the relation constant followed by its arguments enclosed in parentheses and separated by commas. For example, if r is a relation constant, if f is a function constant, if a is an object constant, and if Y is a variable, then r(a,Y) is a term and so is r(a,f(a,Y)). Although functional terms can be used within functional and within atoms, the reverse is not true - atoms cannot be nested inside of other atoms or inside of functional terms.

A literal is either an atom or a negation of an atom. A simple atom is called a positive literal, The negation of an atom is called a negative literal. In what follows, we write negative literals using the negation sign ~. For example, if p(a,b) is an atom, then ~p(a,b) denotes the negation of this atom.

A rule is an expression consisting of a distinguished atom, called the head, and a conjunction of zero or more literals, called the body. The literals in the body are called subgoals. In what follows, we write rules as in the example shown below. Here, q(X,Y) is the head; p(X,Y) & ~r(Y) is the body; and p(X,Y) and ~r(Y) are subgoals.

   q(X,Y) :- p(X,Y) & ~r(Y)

A logic program is a finite set of atoms and rules of this form. For the purposes of GDL, we add some additional constraints on logic programs. In particular, we require each program to be safe, bounded, and stratified, as defined in the following paragraphs.

A rule in a logic program is safe if and only if every variable that appears in the head or in any negative subgoal also appears in at least one positive subgoal. A logic program as a whole is safe if and only if every rule in the program is safe.

The first rule below is safe. All of the variables that appear in the head appear in positive subgoals, and all of the variables that appear in the negative subgoal also appear in positive subgoals.

r(X,Z) :- p(X,Y) & q(Y,Z) & ~r(X,Y)

By contrast, the rules shown below are not safe. The head of the first rule contains a variable that does not appear in any positive subgoal. The second rule has a variable in a negative subgoal that does not appear in any positive subgoal.

r(X,Z) :- p(X,Y) & q(Y,X)

r(X,Y) :- p(X,Y) & ~q(Y,Z)

Safety is important in defining the semantics of rules. It ensures that there are no unbound variables in deriving conclusions of rules and no unbound variables in determining whether or not negations are true. This will become clearer after we look at semantics below.

In order to define boundedness and stratification, we need the notion of a dependency graph. The dependency graph for a logic program is a directed graph in which there is a node for each relation in the program and in which there is an arc from a node p to a node q if and only the program contains a rule in which p occurs in the body and q occurs in the head. If p appears in a positive subgoal of the rule, we say that the arc is positive; if it occurs in a negative subgoal, the arc is negative. If p appears both positively and negatively in a rule defining q, then there are two arcs - one positive and one negative.

We say that q depends on p if and only if there is a path in the dependency graph from p to q. A cycle is a path from a node to itself. A path / cycle is positive if and only if every arc in the path / cycle is positive; the path / cycle is negative if and only if it includes a negative arc.

A relation in a logic program is recursive if and only if it depends on itself, i.e. it is part of a cycle. The relation r in the following logic program fragment is recursive because it depends on itself.

r(X,Y) :- p(X,Y)

r(X,Z) :- p(X,Y) & r(Y,Z)

Unrestricted recursion can lead to difficulties, such as ambiguities or infinite answer sets. Boundedness and stratification eliminate these difficulties.

Let us say that a subgoal in a rule is a recursion subgoal if and only if it contains the head relation of the rule or a relation that depends on the head relation (in other words, it is part of a cycle). A logic program is bounded if and only if every variable in every recursion subgoal of every rule also appears in a subgoal that is not a recursion subgoal. These non-recursion subgoals ensure that the number of possible values for the variables in every recursion subgoal are bounded.

For example, the following recursive logic program fragment is bounded. Let us assume that there are also some facts defining the p relation and the q relation and that they do not depend on r. The second last subgoal of the second rule is a recursion subgoal. The program is bounded because every variable is contained in a non-recursion subgoal. If we were to drop the q subgoal from the second rule, we would have a safe recursive program, but it would not be bounded because the variable Z would not be constrained by any non-recursion subgoal.

r(X,Y) :- p(X,Y)

r(X,Z) :- p(X,Y) & q(Z) & r(Y,Z)

A logic program is stratified if and only if every cycle in the program's dependency graph is positive, i.e. there are no negative cycles. Note that it is okay to define a relation in terms of the negations of other relations; we are just not permitted to define any relation, either directly or indirectly, in terms of its own negation.

For example, the following logic program is not stratified because the relation r is defined in terms of its own negation.

r(X,Y) :- p(X,Y)

r(X,Z) :- p(X,Y) & q(Z) & ~r(Y,Z)

As mentioned above, in GDL, we focus exclusively on programs that are safe, bounded, and stratified. While it is possible to extend the language to programs that are not safe or not bounded or not stratified, such extensions are not widely used in General Game Playing.

A.2 Semantics

A logic program is, in effect, a compact representation of a set of ground atoms, which is called a model of the program. More precisely, a model of a logic program is the set of all ground atoms that are entailed by the program. In what follows, we begin by defining the notion of entailment for programs without negations. We then extend our definition to programs with negated subgoals.

To define entailment for programs without negation, we start with a dataset consisting of the ground atoms that are listed explicitly in the program. We then systematically iterate through program's rules and the dataset in search of an instance of a rule in which all of the subgoals are contained in the dataset, adding the head of each such rule instance to our dataset. This process continues until no new ground atoms can be found. It can be shown that this process terminates for every logic program that is safe and bounded.

As an example, consider the following logic program. We have a few facts about about the parent relation; we have two rules defining the person relation, and we have a rule defining grandparent.

  parent(art,bob)
  parent(art,bud)
  parent(bob,cal)
  parent(bob,coe)
  parent(coe,dan)

  person(X) :- parent(X,Y)
  person(Y) :- parent(X,Y)

  grandparent(X,Z) :- parent(X,Y) & parent(Y,Z)

We start the computation by initializing our dataset to the five ground atoms in the program.

  parent(art,bob)
  parent(art,bud)
  parent(bob,cal)
  parent(bob,coe)
  parent(coe,dan)

Looking at the rules defining the person relation and matching its subgoals to the data in our initial dataset, we see that we can add the following additional facts.

  person(art)
  parent(bob)
  parent(bud)
  parent(cal)
  parent(coe)
  parent(dan)

Using the grandparent rule and matching its subgoals to the data in our dataset in all possible ways, we see that we can also add the following facts.

  grandparent(art,cal)
  grandparent(art,coe)
  grandparent(bob,dan)

At this point, it is not possible to find any additional conclusions, and so the process terminates.

Our definition also deals with recursive rules. Suppose, for example, we were to add the following recursive rules to our program. One person is an ancestor of another if that person is a parent or is the parent of a person who is an ancestor.

  ancestor(X,Y) :- parent(X,Y)
  ancestor(X,Z) :- parent(X,Y) & person(Z) & ancestor(Y,Z)

Looking at the ancestor rule and matching its subgoals to the data in our dataset in all possible ways, we get the following data.

  ancestor(art,bob)
  ancestor(art,bud)
  ancestor(bob,cal)
  ancestor(bob,coe)
  ancestor(cal,dan)

With these additions, we can then derive the following additional data.

  ancestor(art,cal)
  ancestor(art,coe)
  ancestor(bob,dan)

However, we are not done. Using the ancestor rule again, we can derive the following additional datum.

  ancestor(art,dan)

At this point, none of the rules when applied to this collection of data produces any results that are not already in the set, and so the process terminates. The resulting collection of facts is the model.

The presence of negated subgoals in a program complicates matters. Fortunately, our definition of entailment can be extended in a natural way to eliminate these problems.

We start by associating a level with each relation. Every relation that does not appear as the head of a rule with negative subgoals is assigned level 0. We assign level n+1 to every relation that appears as the head of a rule with at least one negated subgoal, where n is the maximum level of any relation that appears negatively in the body. This is well-defined so long as the program does not contain any negative cycles, i.e. the program is stratified. Note that the level of a relation can also be defined as the maximum number of negative arcs in any path to the corresponding node in the dependency graph. The definitions are equivalent.

As an example, consider the following program. We say that a person satisfies the isparent relation if and only if the person has a child. We say that a person is childless if and only if the person does not satisfy the isparent relation. Here, isparent is is at level 0, and childless is at level 1.

  isparent(X) :- parent(X,Y)
  childless(X) :- person(X) & ~isparent(X)

Using the notion of levels, we can extend our definition of entailment to programs with negative subgoals. We start by applying the definition we have just seen to obtain a model of all relations at level 0 of the stratification hierarchy. We then repeat the process for relations at higher levels. In so doing, we assume any negative subgoal is true at level n+1 if and only if the negated subgoal is not true in the model at level n. The process continues until we reach the top level of the hierarchy. As before, it can be shown that this process terminates for any logic program that is safe, bounded, and stratified. Moreover, the model defined in this way is unique.

To illustrate this, consider how we can use the rules above to compute the childless relation. Let's assume we have already computed all of the facts previously computed. Using the definition or isparent, we can add the following facts.

  isparent(art)
  isparent(bob)
  isparent(coe)

At this point, we have computed all relations at level 0, so can now compute childless, which is at level 1. This effectively produces the complement of the isparent relation.

  childless(bud)
  childless(cal)
  childless(dan)

If there were other relations at level 1, we could compute them in similar fashion and then move on to higher levels. In this case, there are no other relations at level 1 or any higher level, so we we are done.

A.3 Open Logic Programs

Logic programs as just defined are closed in that they fix the meaning of all relations in the program. In open logic programs, some of the relations (the inputs) are undefined, and other relations (the outputs) are defined in terms of these. The same program can be used with different input relations, yielding different output relations in each case.

Formally, an open program is a logic program together with a partition of the relation constants into two types - base relations (also called input relations) and view relations (also called output relations). View relations can appear anywhere in the program, but base relations can appear only in the subgoals of rules, not in their heads.

The input base for an open logic program is the set of all atoms that can be formed from the base relations of the program and the entities in the program's domain. An input model is an arbitrary subset of its input base.

The output base for an open logic program is the set of all atoms that can be formed from the view relations of the program and the entities in the program's domain. An output model is an arbitrary subset of its output base.

Given an open logic program P and an input model D, we define the overall model corresponding to D to be the model of P ∪ D. The output model corresponding to D is the intersection of the overall model with the program's output base; in other words, it consists of those sentences in the overall model that mention the output relations.

Finally, we define the meaning of an open logic program to be a function that maps each input model for the program into the corresponding output model.