C H A P T E R  20
Advanced General Game Playing

20.1 Introduction

Although we have looked at a few variations on traditional GGP, the variations have been relatively minor. Over the years, researchers have proposed more extreme variants. In this chapter, we briefly describe some of the more popular proposals, viz. Temporal General Game Playing, Inductive General Game Playing, Really General Game Playing, and finally Enhanced General Game Playing.

20.2 Temporal General Game Playing

In traditional General Game Playing, players are given two clocks - one for initialization and one for game play; and they are both hard limits. Over the years, members of the community have proposed other sorts of timing restrictions.

One possibility is to replace the hard time limits on each step with a cumulative clock, with the idea that each player stops its clock as soon as it replies to the game manager's play request. This way, players can conserve their time for portions of a match requiring more attention. The downside of cumulative time is that players must decide for themselves how to allocate their time; and this can add to the difficulty of building effective systems.

A different approach is to connect playing time with reward. For example, a player might get a reward that depends not just on the game state but also on the amount of time spent computing its moves. Again, this is a complication, but it allows us to model some real-world applications that do not fit the fixed clock or cumulative time models.

Finally, some people have proposed making the world dynamic, so that the world state changes while the players are contemplating their moves, placing emphasis on economy of deliberation and careful timing of action.

20.3 Inductive General Game Playing

In traditional General Game Playing, the players are given game descriptions at runtime. Usually, these game descriptions are complete; and, even then, the task of playing such games is difficult. As we have seen, in some cases, the descriptions are incomplete; and this complicates the process of playing games. Inductive General Game is a variant of General Game Playing that is even more difficult.

In Inductive General Game Playing (IGGP), the players are given no rules at all. In the place of rules, they are provided with a corpus of records for game matches. Given only this corpus of data, they must figure out the rules of the game for themselves; and then, in traditional GGP fashion, they must use these rules to play the games effectively.

One thing that makes the job a little easier is that there is no noise, i.e. no errors in the match records. All matches are correctly played games. At the same time, the job is complicated by the fact that there are no negative examples, i.e. match records that do not correspond to correctly played games. Of course, both of these limitations can easily be rectified. It is simple to add in some false positives and no problem at all in supplying negative examples as well, with or without false negatives.

20.4 Really General Game Playing

Really General Game Playing (RGGP) extends this progression of difficulty one step further. In RGGP, players are given structural information about their games and a simple utility sensor but that is all. They know the roles, the percepts, and the actions of each player; but that is all. They are not even given samples of games.

In RGGP, players explore the world, reading their utility sensors. They must then develop theories of how the world works and use those theories to optimize the readings of their utility sensors.

20.5 Enhanced General Game Playing

Finally, some have proposed a variant of GGP with more information rather than less. This is often called Enhanced General Game Playing (EGGP).

The extra information in EGGP might included identity information about their opponents. With this information, players can do meaningful opponent modeling and re-use that analysis from one match to another.

The extra information in EGGP might also include tournament information, e.g. whether it is a cumulative score tournament, a single elimination ladder, a double elimination ladder, and so forth, so that it can strategize about how to proceed. For example, in a cumulative score tournament, a player should try to maximize its return on every game, whereas in an elimination ladder, all it needs to do is to beat its opponent.

In its most general form, EGGP is interesting because a player's decisions do not end when a match is over. It is playing a bigger game, which can involve the multiple matches of a tournament and even the results of multiple tournaments. For an EGGP player of this sort, its entire existence constitutes one big game.