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
}