Marc Lanctot on Tue, 27 Jul 2010 11:51:17 -0700 (MST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: [game-lang] review of GDL

Thanks Joel for the review of GDL.

On 10-07-27 02:09 PM, Joel Uckelman wrote:
Thus spake Simon McGregor:

I'll try a different angle here from yours. Given that we presumably
want to model arithmetic in our language, are there compelling reasons
not to model the integers and the reals?

Regarding the reals: I'm struggling to think of any reason for needing more
than the rationals. Actually modeling the irrationals is going to be sort
of complicated, probably involving a lot of extra symbols


 From a purely pragmatic point of view, if we restricted ourselves to
finite models of arithmetic, then whenever we defined a game involving
numbers we'd presumably have to specify the cardinality of the model.
This strikes me as both tedious and inelegant.

 From a logician's point of view, here's the problem with modeling full
arithmetic: Once you have full arithmetic, you fall prey to incompleteness
and undecidability. These are in some ways worst-case notions. For example,
we might want a decidable language if we're expecting to receive input
from the devil, since the first thing he'll do is give us a set of game
rules which encode the Halting Problem or a Goedel Sentence or some other
such pathological object if we give him enough expressivity to do it.

Now, you might ask whether this actually matters for modeling *games*.
I don't know of any board games which involve determining whether an
aribtary program will halt or doing proof search, so the answer might
just be that it doesn't matter at all---we're not going to use enough
of the expressivity to get us into trouble, but at the same time we
don't want to go through the trouble of coming up with precise boundaries
within which safety is guaranteed, so we don't bother limiting the

I think a bigger problem comes up if you want to use existing tools for
doing model checking or theorem proving, as they might not support the
level of expressivity we're aiming at. Hard to tell at this point,

Yes. IIRC, this was similar to their argument at last year's general game-playing workshop. "It [arithmetic] makes resolution much harder" is what I kept hearing them say. That's precisely where I lost interest because I'm not interested in the purity of the logical properties of the language for uses that are irrelevant to our purpose.

I just want to be able to express a game comfortably (e.g. having arithmetic should not be a luxury.. it should be given), know what state I start out in, know which moves are available to me in a given state, know how my state changes when I take one of those moves, and know how I win or lose. Of course we want to add our high-level board gaming concepts on top of this.

I'm not an expert here, as I'm sure you can tell. So I can't comment on much about the logic. I agree with Joel's points and observations. I always expected a logical game description language to be more like the situation calculus** with built-in high-level abstract board game concepts and stochastic events.


I agree with most everything else. I don't have any particular opinions about syntax of the resulting aesthetic properties of the language unless it ends up being completely incomprehensible by humans.

The way I currently deal with imperfect information in my code is that I have a function that translates a game state to a description of a player's information set from that state (e.g. hides any information that should not be seen by that user). Any implementation of the games I have coded would just present this partial description. I think this is what they were going for with "sees" in GDL-II, a recent paper at AAAI that I linked and Joel relinked in one of his first messages.

At this point I don't see much gain in designing a superset of GDL rather than starting from scratch.


game-lang mailing list