GGDL

GGDL is an extension of GDL. If unfamiliar with that topic, the Stanford book on General Game Playing is an excellent resource.

The following is an example of valid GGDL for a simple game, Tic-Tac-Toe:

role x, o  // Two roles.  As in GDL, simultaneous play is assumed.
// Aternative turns can always be implemented on top of simultaneous.

// The init keyword indicates conditions to hold at the start of play.
// The `:=` indicates initialization and assignment of variables, where
// `=` should only be used to update existing values.
init control := x

// Partitioning arguments of a function constant is equivalent to
// expanding the arguments for separate statements.
data index ( 1 | 2 | 3 )
// index(1)
// index(2)
// index(3)
// can also be written index(1 .. 3) for contiguous ranges
// These are also equivalent to the more verbose `base index(1) :- .`
// style found in some GDL game descriptions.

// Initialization can also be defined in terms of base relations.
init cell(?row, ?col) := b
  :- index(?row) and index(?col)
// ...produces the nine cell locations with initial value `b`.

// Legal moves and their consequence are defined within the same rule,
// but they can be presented separately as well (and will generate the
// separate `legal` and `does` relations when formatted as GDL-II).

// A player's only move is NO-OP when it is not their turn, and becuase
// it is a two-player game, the control always hands over to this player.
?p -> noop
  :- role(?p) and ?p # control
  ==> control = ?p
// A game with more players could use a next(?p, ?q) relation to
// support proper turn sequence.

// The player in control may only mark blank cells.
?p -> mark(?i, ?j)
  :- control(?p) and (cell(?i, ?j) == b)
  ==> cell(?i, ?j) = ?p

// Consequences of persistence do not depend on a player's move,
// but relations can depend on any player move still recorded in
// the knowledge base, or in their distinctions (as shown below).

// The `P <:- Q` operator is shorthand for `_ ==> P :- Q`, an
// effect without player action.  Typically this is for upkeep
// needed when transitioning the turn.
// The `#` bin-op here indicates the two terms are distinct in the
// GDL sense, akin to syntactically distinct or distinct after all
// α-conversions of the current parameters.
cell(?i, ?j) = ?p
  <:- cell(?i, ?j) == ?p and ?p # b
cell(?i, ?j) = b
  <:- ?p -> mark(?m, ?n) and (?m # ?i or ?n # ?j)

// There are two terminating conditions -- success or a draw.
terminal :- role(?p) and line(?p)
terminal :- not open

open :- exists ( cell(?m, ?n) == b )

// Goals are used to evaluate the outcome of a game.  They are also
// useful to agents for planning a successful strategy.

goal ?p = 100 :- line(?p)
goal ?p =  50 :- draw
goal ?p =   0 :- line(?o) and ?p # ?o

// Relations can be composed from other relations for building more
// complex game rules from simpler structures and patterns.

// A row is any sequence with the same row index and marker.
row(?k, ?p) :-
  cell(?k, 1) == ?p and cell(?k, 2) == ?p and cell(?k, 3) == ?p

// A column is any sequence with the same column index and marker.
column(?k, ?p) :-
  cell(1, ?k) == ?p and cell(2, ?k) == ?p and cell(3, ?k) == ?p

// Diagonals have two possible forms, we can use multiple rule
// definitions to implicitly define it as one or the other.
diagonal(?p) :- cell(1, 1) == ?p and cell(2, 2) == ?p and cell(3, 3) == ?p
diagonal(?p) :- cell(1, 3) == ?p and cell(2, 2) == ?p and cell(3, 1) == ?p

// A line is either a row, a column or a diagonal.
line(?p) :- index(?m) and row(?m, ?p)
line(?p) :- index(?n) and column(?n, ?p)
line(?p) :- diagonal(?p)

// The game is a draw if neither player has made a line.
draw :- not line(x) and not line(o)

Background

Philosophy

GGDL is based on GDL which in turn is based on Datalog, a logic programming language.

There are two variants of GDL in the wild, the prefix-formatted one that is constructed from s-expressions, and the infix-formatted one that looks more like a subset of KIF with prolog/datalog inference operator :- for defining relations that imply. The prefix-formatted version is found in rulesheets defined for Stanford's collection of games, the infix notation is more human-readable and what is typically found in academic journals and other offshoots that derived from GDL.

While making GGDL a superset of GDL, I also noticed that the player responses and server updates are a further restricted subset of GDL. Indeed, the possible strings (after normalization) that a player could legally submit as an action are countably finite, and typically a trivially small quantity. It occurred to me, since you would not want to allow the full strength of the interpreter system, that you would either need a sufficiently constrained parser or an interpreter with enough context to know not to evaluate certain otherwise well-formed sentences, nor include them in any unification passes. Indeed, with enough knowledge of the game definition, a compiler could produce a parser that would only accept legal moves from the player, and that it would be much smaller than even a ground-statement parser since all symbolic and relational names would be known beforehand, and that there would be no need to warily evaluate its contents after a successful parse.

So, when defining the syntax, it is important to call out which parts are core GDL, which parts are extensions of that language, and which parts influence the construction of a custom move-accepting parser. And, because GDL is powerful enough to define a broad set of game rules as it is, the language used when conveying the game rules can be interpreted with only GDL syntax and a small runtime library, provided here as a typescript implementation.

Syntax

role

true

init

Gameplay State Machine

START

PLAY

READY

DONE

STOP

TODO

Describe the language, its motivation and the problem(s) it is meant to address.

Describe the environment, the facility of play and how GGDL is the language that a gameplay model is built from.

Define the high-level language choices (declarative, stratified, restricted recursion, action definition, board and equipment, etc.) and link to specific pages on each of these topics.

Also be sure to mention:

• grammar, syntax page
• logic programming page
• game FSM (start, actions, update, forfeit, stop, results)
• API repo
• GM repo
• ...