|
|
Post by Steve Draper on Nov 7, 2014 13:58:12 GMT -8
Does anyone know of a tool for testing the semantic equivalence (at least statistically) of two GDL descriptions?
|
|
|
|
Post by Sam Schreiber on Nov 7, 2014 17:17:29 GMT -8
I've built a few of these, but I don't think there's anything authoritative (or guaranteed to be correct). Out of curiosity, what do you want to do with it?
|
|
|
|
Post by Steve Draper on Nov 8, 2014 7:16:45 GMT -8
I've built a few of these, but I don't think there's anything authoritative (or guaranteed to be correct). Out of curiosity, what do you want to do with it? I've been talking with Jakub (co-author of Dumalion) about some work he has been doing recently, which involves an alternate representation of a more limited domain of games (simplified board games). We've been doing a little testing of his player against Sancho in some test games (which have GDL constructed in such a way as to be interprettable by his player). In particular a variant of chess cropped up that pre-dated Alex's recasting of the GDL to run much more efficiently, which started a conversation about automatic re-casting of logically equivalent GDL. Jakub's work learns game semantics from observing games (random or otherwise), which means any GDL representation (that stays within the domain of applicability at last) can act as input, resulting in a state machine representation which is not GDL-based at all. It struck me that it should then be possible to translate THAT representation back into a 'canonical' GDL representation (based on some templates for known semantic constructs in the domain of applicability, which always involves boards and pieces that move about them). I was thinking that suitable templating of how the abstraction patterns in Jakub's representation are mapped to the canonical GDL, could lead to propnet-friendly output GDL (using ideas like the ones Alex outlined in his blog on rewriting chess). The result would be something capable of taking arbitrary input GDL (within the domain of applicability) and canonicalizing it to produce GDL that runs efficiently. We also discussed how this can lead to game-identity detection even across representation changes, and (given similarity metrics in Jakub's representation domain, which will lend itself to them much better than raw GDL since it has an in-built understanding of some broad semantics) similarity measures between GDL games (which then could suggest use of heuristics based on what is known about similar games). This was all off-the-cuff chat though - so we're only talking about ideas here at this stage. I was hand optimizing some GDL for peripheral reasons (that stemmed from the interaction with Jakub) and wanted some way to check that what I ended up with was still a representation of the same game (at least to good probability) - hence the original question. |
|
|
|
Post by Sam Schreiber on Nov 10, 2014 22:05:28 GMT -8
Oh, cool! That sounds really interesting.
So, one approach that could be useful is doing "structural comparisons" of random simulations through the game tree: basically, create a state machine with GDL_1 and another with GDL_2. Make sure they have the same number of roles. Start with the initial state in each, and make sure they have the same legal moves for each role; then pick random legal moves for each role, go to the next state, and repeat. If you arrive in a terminal state, make sure it's terminal in both, and make sure the goals are the same.
This will ignore any changes to the "implementation details" of the game, and verify that the "publicly visible" parts of the games are the same.
Of course it's simulation-based, so it's not a *proof* that the games are the same, but if lots of simulations are turning out the same way, that strongly suggests that the games are the same. (Of course, it could also mean that they differ in some extremely obscure detail, like castling-through-check in Chess, so it's not perfect...)
|
|
