Re: [game-lang] review of GDL

[Marc Lanctot <lanctot@xxxxxxxxxxx>]

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

Agreed.

> >  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
> expressivity...
>
> 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,
> though.

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.

**http://en.wikipedia.org/wiki/Situation_calculus

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.

Marc

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