Joel Uckelman on Tue, 27 Jul 2010 07:06:33 -0700 (MST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
[game-lang] review of GDL |
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