Introduction to General Game Playing

So far, we’ve talked about designing agents for specific single player and two-player zero-sum games, using heuristics to guide the search, and saw how we can model and tackle uncertainty in move generation. It’s finally time to discuss General Game Playing (GGP).

GGP is a project of the Stanford Logic group. They designed a platform for general game playing and hold annual GGP competitions at the AAAI conference. GGP is the design of intelligent computer systems that can play arbitrary games, based solely on their formal game description passed to them at runtime i.e., a general game player does not know in advance which game it’s supposed to play; it has to be able to play a variety of games: single-player games (like 8-puzzle), two-player zero-sum games (like checkers), cooperative games (like Prisoners’ dilemma), multiple player games (like Chinese checkers) etc., and it’ll only be told which game it’s supposed to play at runtime.

I know it sounds almost unreal so let’s uncover some of the mystery and dig deeper into how it all works. The system has been broken into several components:

Game Description Language (GDL)
Games are defined in a formal language known as GDL, which is a logic programming language similar to Prolog. By parsing the game description, a player can find out how many players there are, which is the start state, which are the terminal states and the rewards for each player in those states, which actions are available to each player in any given state and how states evolve in response to their actions. A practical general game player will transform the GDL into a representation that can answer these questions efficiently; there are several options: using an interpreter based on state machine or propositional net, or translating to another language like Prolog and then using its interpreter or compiler.
Game Management
The system is composed of a game manager, which maintains a collection of game descriptions, match records and temporary state of matches in progress, and several game players. Communication between game manager and players takes place over HTTP connections. A typical match takes place as follows:

  1. Players register themselves with the game manager.
  2. The game manager receives a request to schedule a match.
  3. The game manager sends a start message to each player; the message contains the game description, the role this player is playing, and the start and play clocks (the time it has before the match starts and the time to make each move afterwards, respectively).
  4. The players respond with a ready message. Match begins after all players have responded or after the start clock has expired.
  5. The game manager sends a play message to each player; the message contains the actions taken by each player in the previous move.
  6. Each player responds with their choice of the actions. If a player doesn’t respond before the play clock expires, the game manager chooses a random legal action for that player.
  7. The game manager checks legality of the actions and updates its state. If the game is over, it sends a stop message to each player, otherwise it goes back to step 5.
Game Player
A game player is implemented as a web service and it communicates with the game manager over HTTP. It has to be able to parse the game description and make legal moves within the allowed time.

All of this is a lot to take in but you don’t have to implement most of this stuff. It’s already implemented as part of the platform. You only have to care about implementing your own player, and even there, most of the infrastructure is pre-implemented and several sample players are provided so that it’s easy for anyone to get started:

While starting out, you can assume that you have access to a game representation (state machine-based interpreter in the above package) and you just have to implement start() and play() methods. In the start() method, you can do any preprocessing you want, within the start clock. Typically, this time is used to analyze the game, build a suitable game representation, and find heuristics from game structure. In the play() method, you have to choose the next move, within the play clock. You are free to implement any strategy you want, and it can be as simple as just choosing a random legal move, to as complex as reasoning about the game from its structure and the players from their choice of the previous moves, coupled with some tree search algorithm.

With this short description of GGP out of the way, we can now start building general game players from the next post.


One thought on “Introduction to General Game Playing

  1. Pingback: A simple heuristic-based General Game Player | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s