GDL isomorphism (SgianDubh feature)

Welcome to the forum!

I believe it's talking about defeating the particular obfuscation done on Tiltyard, which is a much simpler task. In particular, it doesn't even reorder the rules (as this could have random negative impacts on rules engines, such as GGP-Base's default ProverStateMachine).

As you say, if someone were to rewrite a game with a substantially different set of relations, it would be impractical to prove the equivalence of the games.

And then there is the question about the philosophy of GDL. I suspect that it's in the realm of GGP (broadly speaking) to consider what can be learned about games over time by a program, so long as that knowledge doesn't originate from a person. For example, Prof. Genesereth was considering an addition to the GDL standard to let the game server expose a new game to the gamers before playing several rounds of the game in a tournament, in an attempt to give the gamer time to develop deeper strategies.

Maciej asked "And also isn't it against the GGP idea not to have any knowledge at the beginning?"

I asked a similar question in the discussion forum of the recent GGP MOOC on Coursera. The answer there was inconclusive. Setting aside the pragmatics of whether it is feasible to enforce this with obfuscation technology, I am going to propose that ideally a GGP player should play as if each game was being encountered for the first time. This is consistent with the machine learning principal that the training set used to learn the algorithm parameters needs to be distinct from the testing set used to validate that the learning algorithm is effective.

The naive reason for not recognizing the game is to prevent players from selecting an algorithm specifically designed for the game.

The counterargument in favor of recognizing the game is to enable machine learning techniques for use in tuning the GGP algorithm (e.g. weighting different heuristics). The analogy is that humans learn to play well through repetition. However, that is what the metagaming phase is intended to allow, where the GGP player can play thousands of (random) games. Recognizing the game from prior sessions and applying that experience is basically an arbitrary extension of the time allowed for metagaming to play more systematic games. To the extent that the machine learning algorithms can benefit from the additional time (as opposed to manual tweaking ), this seems more of an argument for increasing the metagaming time than an argument against the ideal of playing each GGP session as if the game were presented for the first time.

I will concede that there are some practical challenges in running competitions and game masters like Tiltyard if we are to allow metagaming to run for hours or days, but that would be the level playing field. Otherwise we start getting into an arms race optimizing the players for all known games.

Machine learning that is not specific to recognizing a specific game presents an even greater challenge to the ideal that the GGP player should play as if it had never encountered the game previously. Machine learning in this sense would recognize features of the game from the GDL, another representation like the PropNet, or even playing games and would use these features to select "optimal" parameters for the GGP algorithm(s). (This is a generalization of measuring the correlation of heuristics with score and weighting the heuristics accordingly.) Experience playing many different games many times (possibly against different opponents) is used to compute the optimal parameters for different combinations of features. While the GGP field is probably some years away from this level of player, it does present the classic machine learning problem of over fitting to the training set. In this case, the games used to learn the feature weights associated with different parameters are the training set. The problem is that the training set may not be fully representative of the universe of data (games) and so the tuned parameters may not work so well in general as on the training set. The way to test for this is to use data (games) that were not in the training set, so competition would need to use different games (testing set) than were used to train the players.

In a nutshell, if the goal is to win a competition then anything within the rules is valid, but if the goal is to find the best algorithm then we need to be careful to distinguish between training games (data) and testing games (data) and the competitions need to take this into account.

The straightforward, albeit painful, solution to confounding the effects of the offline database with the algorithm changes is to reset the offline database after each algorithm change. The painful part is when the offline database represents hundreds or thousands of past games, which makes it tempting to make a risk assessment of whether the change is significant enough to make the database reset worthwhile in terms of the design knowledge gained.

The other interesting point here is that the training depends not only on the games used, which are static or changes slowly even when using a facility like Tiltyard, but also on the players, which is subject to greater change depending on who else is testing players. Training is difficult to control unless you have access to many strong players and the resources to host the players and a game master of your own.

This relates to the general challenge in machine learning that the correct answers need to be known for the training and testing sets used with the algorithm before applying it to the larger universe of data where the answer is not known (consider speech recognition). At first blush, we seem to have it easy in GGP because we always get to terminal scores, which seem like an answer. In fact, this is an approximation because it depends on the "strength" of the opponent, and is reflected in the statistics collected by Tiltyard to assess how much weight to assign to the game outcomes in rating the players. The only games with known answers are those, like tic tac toe or connect four, that have been completely solved to show that game is always a draw, a win for a specific player, or more generally, the specific score for each player in a perfectly played game.

This puts us into an advanced area of machine learning where algorithms "learn" on data sets where the correct answers are not known. These algorithms may use a small "bootstrap" training set with known answers, followed by a larger training set with unknown answers to refine the parameters. A separate testing set is then used for evaluating the algorithm, but the evaluation is based on statistical measurements of quality. Recommendation algorithms fall in this area.