[game-lang] review of GDL

[Joel Uckelman <uckelman@xxxxxxxxx>]

I've now had a chance to grok the GDL introductory article and the language
specification:

  [1] http://games.stanford.edu/competition/misc/aaai.pdf
  [2] http://games.stanford.edu/language/spec/gdl_spec_2008_03.pdf
 
Comments:

1. I can see already that this is going to be quite long...

2. GDL is designed for "finite, discrete, deterministic, multi-player
games of complete information" [2, p.1]. We unambiguously hit "game"
and "multi-player". We clearly don't satisfy "complete information"
and "deterministic", since we want games with hidden information (such
as hands of cards, hidden rolls, piece stacks which can't be examined
by opposing players) and we want games with stochastic events (such as
die rolls and card shuffling).

The remaining two properties, "finite" and "discrete", I'm not so sure
about. The way finiteness shows up in GDL is that the rules and also the
game state models must be finite. GDL can't (explicitly) model games with
infinitely many players, as the only way to (explicitly) do that would 
would be to have infinitely many "(player bob)" literals in the ruleset.
This isn't a problem for us, since there are no real games with infinitely
many players. (However, there might be some games which can accomodate an
unbounded finite number of players, and there are many, many games which
can accomodate a range of players...)

There are games (e.g., naval and space comabat games, tile-laying games)
where the playing surface is infinite in all directions. (Basically, you're
playing in $\mathbb{Z}^2$, or a hex-tesselated version of it.) However, in
all such games only a finite part of it is ever in use at any one time, so
this won't cause models of games with infinite playing surfaces to be
infinite themselves---so long as locations in the plane can be defined
inductively. E.g.,

  loc(0,0).
  loc(x,y) -> loc(x,y-1) & adj(x,y,x,y-1).
  loc(x,y) -> loc(x,y+1) & adj(x,y,x,y+1).
  loc(x,y) -> loc(x-1,y) & adj(x,y,x+1,y).
  loc(x,y) -> loc(x+1,y) & adj(x,y,x-1,y).

However, GDL doesn't support arithmetic expressions, so you end up needing
something like

  loc(00).
  loc(c) -> \exists u,d,l,r
    loc(l) & adj(l,c) &
    loc(r) & adj(r,c) &
    loc(u) & adj(u,c) &
    loc(d) & adj(d,c) &
    !adj(u,d) & !adj(l,r) & !adj(l,u) & !adj(l,d) & !adj(r,u) & !adj(r,d).

  adj(x,y) -> adj(y,x).

And this, so far as I can tell, isn't sufficient to guarantee that 1,0 and
0,1 have exactly two distinct neighbors in common. (There's a related
problem in axoimatizing modal logics of grids, which I've published a paper
on:

  [3] Modal and temporal logics for abstract spaceâ??time structures. Studies
  in History and Philosophy of Modern Physics 38(3):673â??681, 2007.)

I haven't convinced myself yet that there's NOT a way to do this, but if
there is I think it will be rather nasty.

I'm also wondering about whether there are any games where at some point a
player will have infinitely many possible moves. I can think of one real
example where this is the case according to the rules, though it's not 
essential to the way the game works: In Empires in Arms, when you bid for
countries at the beginning, you're technically permitted to bid any
natural number of VP you want. Of course, the most VP you can make per
quarter is 15, so the absolute maximum number of scorable VP in 44
quarters of game play is 660. At the end of the game, on-map home-nation
manpower is also converted into VP as is saved manpower for the Prussian
player. I think it would be mathematically impossible to win if the sum
of your bid and base VP-needed-to-win was more than around 750---hence
player prudence prevents unbounded bidding, but you could just as well
make a rule preventing bidding above 750 and it wouldn't change the game
at all. What I'd like to know is whether there are games where it is an
essential feature that some player has infintely many moves at some point.

Discreteness: I think we agreed that density of space isn't a necessary
feature of miniatures games (let alone continuity), the only games we
could come up with where this might make a difference, so we might be
ok on this point.

3. Turn-taking: [1] defines the game model so that every player moves
simultaneously at every choice point, but then provides for turn-taking
by letting players other than the turn-taker have a no-op as their only
legal move. (See [1, p.7] for an example.) We're in a domain where
overwhelming majority of moves are not simultaneous, so the user will
have to write statements explicitly declaring that to be so for almost
all moves. It would be more user-friendly if the assumption was that
moves are sequential but could be delcared simultaneous for the rare
cases when they are. 

4. Language features and warts:

* true(\phi) indicates that \phi is true in the current state, while
\phi indicates that \phi is true in all states. This is a confusing
use of "true" as a predicate name. Using now(\phi) would be more
perspicuous for asserting that \phi is true now.

* The current state is treated implicitly, which is why GDL can be
so much more succinct than a representation which explicitly contains
all of the possible game states.

* Specifying goal values strikes me as strange. [1, p.8] has the value
of winning at tic-tac-toe as 100, tying as 50, and losing as 0. I can 
see why you might make this assumption for doing AI, but it isn't
properly part of the game rules that a win has twice the value of draw.
This might be the case for some games, but only because it's in their
rules. GDL seems to have no way of providing for outcomes which are
merely ordinal, insted of cardinal.

* It would be nice to permit heads which are conjunctions of atoms, as
this would prevent the need for repeating common bodies. (E.g., see
the rules in the middle of [1, p.8].)

* There are two semantic conditions which sets of GDL rules must respect
[2, Definitions 8 & 15]. As a logician, I can read these and understand
them, but the properties they express---stratification and recursion
restriction---are complex enough that if you gave me 10 GDL rules, I 
wouldn't immediately be able to tell you whether the set satisfied them.
This makes me think that it will be very easy to write malformed rules
in GDL. Additionally, there's [2, Definition 20], which contains two more
restrictions for which it is not so simple to verify that they're met.

* I don't follow at all the reasoning behind removing the '=' predicate
from Datalog. [2, p.6].

* I'm not at all a fan of KIF, the syntax they're using for writing GDL
rules in [2]. The outer parentheses are syntactic junk, the inner
parentheses around function arguments are missing, having space-separated
argument lists instead of comma-separated ones is hard to read, putting
'?' as a sigil makes it look like a test, they're using Polish notation
for '<=' rather than infix, which just makes things harder for humans to
read.

-- 
J.

_______________________________________________
game-lang mailing list
game-lang@xxxxxxxxx
http://lists.ellipsis.cx/mailman/listinfo/game-lang