gdl/

GDL parser in golang

This parser can read GDL in prefix-KIF notation, as is customarily used by the GGP servers of the AAAI and Stanford competitions. An example of its syntax, using the very simple game of Rock-Paper-Scissors a.k.a. じゃんけん (Janken):

;; Roles are a special expression that define a player character (either human
;; or AI) and are necessary parameters for other special forms such as `does`
;; and `legal`.  Here we have two players, and though they are simultaneously
;; moving (as in all GDL play) they are specified as separate sentences.
(role player1)
(role player2)

;; Anything after semicolons like this is a comment until the next newline.

;; Relations are sentences beginning with <=, the right-to-left infer op.
;; This game is finished when the outcome can be decided and a player wins;
;; i.e., when players have made different choices where one is superior.
(<= terminal (winner player1))
(<= terminal (winner player2))

;; Legal moves for both players are 'rock', 'paper', and 'scissors'.
;; Since this is a simple game, there is no condition on these relations
;; and each move is equally valid as long as play has not yet terminated.
(<= (legal ?p (rock)))
(<= (legal ?p (paper)))
(<= (legal ?p (scissors)))

;; Winning condition expressed as a `next` special relation.  It says that
;; when two distinct players make a move and there is a `super/2` relation
;; defined for the moves made, add a (winner <role>) relation to the KB.
(<= (next (winner ?p))
    (role ?p) (role ?pu)
    (distinct ?p ?pu)
    (does ?p (?x))
    (does ?pu (?y))
    (super ?x ?y))

;; Superiority of each choice is given as axioms.
(<= (super rock scissors))
(<= (super scissors paper))
(<= (super paper rock))

;; Goal values indicate the desirability of an outcome on a scale of 0-100.
(<= (goal ?p 100)
    (winner ?p))
(<= (goal ?p 0)
    (winner ?np) (distinct ?p ?np))

This is a simple game, in order to show a brief example, and so many of the relations are lacking a body. It is, however, a complete game and demonstrates the power of GDL's datalog-like expressiveness and the simplicity of

The game could be extended to count multiple bouts between the players, to count draws as zero values in best-of-N, to add other legal moves for the players (and the respective win/lose/draw relations as additional sup clauses), etc. The above is sufficient for the construction of an AI player and, because it is possible to mechanically determine a move's legality from unifying on these relations and the Knowledge Base, it is possible to define the game protocol for autonomous play based on the expressions and relations of the game. It is portable in that the client uses the same declarative logic to represent the game rules, so assuming the same correctness in interpreters, there would be no disagreement about what is a legal play, even the game state has a very consistent representation in the Knowledge Base inferred via these rules, though it places no strict requirements on their internal representations in any environment as long as all the relations can be decided.

File layout for this module

lexer/ for tokenization of an io.RuneReader into a channel of Token elements

ast/ for the AST representation and encoding a Token stream into well-formed GDL Sentences

parser/ for the machinery for converting lexer.Token sequences to ast.Node trees, sending complete Sentence (top-level relations) instances to an output channel. There is a prefix parser (the one typically used in GGP competitions) and an infix parser (for the syntax usually expressed in GGP literature), both mostly draw from the same tokens and all of the same ast.Node representations.

Properties of GDL

TODO summarize [Game Description Language paper]

Syntax of GDL

TODO synopsis, perhaps in the same style and ordering as the seminal GDL paper

Semantics of GDL

TODO

Sentences and Expressions in AST

TODO this is a WIP

Special constructs of GDL language

• role
• input (*)
• does
• <=
• legal
• next
• base (*)
• init
• terminal
• goal
• distinct
• true
• not
• and
• or

(*) The KIF files from the dresden repo inferred these (input ...) and (base ...) relations based on the semantics of legal & does for input, and on positive definite values in the other relations for what is in the domain or base.

Structure of output representation

{
    TODO

}