Re: [game-lang] review of GDL

[Joel Uckelman <uckelman@xxxxxxxxx>]

Thus spake Simon McGregor:
> 
> Well, one desideratum is that (in at least some cases) it should be
> possible to automatically generate a finite list of available moves
> from the rules. This is at least as difficult a task as model checking
> (as you've described it), so we need to think carefully about how to
> go about it.
>

The decision-problem version of checking finding all legal moves from a
given state (which would amount to deciding whether a given set of moves
are all legal in that state) is the same problem as single-move model
checking, which is potentially easier than model checking.

This might be a case where the function problem doesn't have the same
(functional) complexity as the decision problem, though. Also, if you
have some characterization of legal moves other than an explicit
representation (i.e., just a set of moves) that might also matter.

> On the other hand, I'm imagining that a sufficiently well-behaved
> logic will correspond to a set of computable constraints on the syntax
> of the rules. Consequently, the algorithms which handle that logic
> will both correctly enumerate the moves and also be provably correct
> (assuming the syntactic restrictions). Or is that a terribly naive
> view?

This seems possible, prima facie. It's hard to tell without having the
details laid out. (It might be hard to tell even then.)

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