General intelligence for games

A game playing agent for Chess can play a chess game, but a general agent can play any game (or at least learn it). The idea of General Game Playing (or GGP) is to create a software agent that plays an arbitrary game. The description of the game is given during runtime. Because the rules of the game is not known a priori, the knowledge the programmer might derive from the game rules cannot be coded into the agent. The programmer's impossible mission is to build general intelligence into the agent.

The GGP competition defined by the AAAI limits itself to games that can be described by a state machine. The game has a set of states S, a set of players, P (P has size n), a set of actions A. L = S x A identifies the actions allowed in a given state. The mapping to determine the next state, M uses the current state and the action of each player:

The game starts at the state s (in S) and ends when it reaches one of the end states, t. At this point an outcome for each player is assigned from a mapping G: S x P -> [1,100]

The number of elements in any of the sets must be finite. However, this does not mean that the games have to be simple. Chess has 10^30 elements in S, but it can still be described using this simple scheme. However, to a game with this many states, a simple enumeration of states is not possible.

This is where the Game Definition Language (GDL) comes in. GDL uses a variant of first order logic. It is essentially a subset of PROLOG, and in fact PROLOG can be used to implement a game engine of sorts.

For GGP there are some constraints placed on the described game:

1. The game must be playable. This means there must be a legal move for every player at every state.
2. The games with one player must be strongly winnable. There must be some sequence of moves that maximises G.
3. The games with more than one player must be weakly winnable. This means there must be a path that considers joint moves from any state such that each player's goal is maximal (in G)

In a single player game, it might be possible to search the game space for a goal state, but in a multi player game, the moves of the other players cannot be determined. Typically, an exhaustive search likely to be out of the question. The problem with heuristic searches is that a heuristic cannot be defined for a general game without knowing the rules. In addition, games dot not have names -- in order to recognise a previously played game, the agent must first assess whether this is in fact the same game. Is is also not possible to learn the strategy of another opponent because the opponents' identity is not shared.

In order to implement the challenge a mediator called Gamemaster is available as a web service. Using a specifically designed protocol the Gamemaster controls the game and gives each player a chance to move. If he does not respond in time, a random move is chosen for that player. At the end of the game, each player receives his reward (calculated from G).

Anyone up for a small competition?