11.1 Introduction

In some games, it is possible to enhance the efficiency of evaluation by converting the ordinary view relations in a game description into base relations.

As a simple example of this, consider the fragment of GDL shown below. There are two base relations f and g. There are definitions for three view relations - h, j, and k.

Let's assume that we need to compute k while processing a state, e.g. to determine whether it is terminal, to get a goal for a player, to compute legal moves, or to compute the next state after a move. And let us suppose that there are n object constants. Then, using our standard evaluation algorithm, we would evaluate j n² times. For each of these, we would compute h n² times. And, for each of these, we would look at n facts about f. Hence, we have an overall cost of n⁵.

The good news is that we can improve matters by reformulating this game slightly. Consider the variation shown below. Here we have made j a base relation and we have dropped k altogether. It is easy to see that this h is the same in all states of this game.

As before, to compute h, we would evaluate j n² times. However, since j is stored, we would evaluate it at most n times, for an overall runtime of n³.

Note that indexing can mitigate the cost of the original formulation in this case, but it is still possible to find cases where materialization helps. Caching is also a possibility, but that entails complexity and overhead that is unnecessary with the materialized version.

Intuitively, materializing is quite simple, but it is a little tedious. In order to make it easier to understand, let's break the process down into components.

11.2 Dematerialization

In some game descriptions, there are base relations that are useless in that they are not needed for computing any of the key properties of game states. The existence of such useless relations is sometimes due to sloppy game description; sometimes it is the result of materializing view relations and thereby making some base relations useless.

The existence of useless base relations is often not that expensive. However, maintaining such relations is still wasteful. It costs times to compute the relations in updates; and, in the absence of indexing, the presence of the resulting facts in a state description can increase the cost of processing other relations.

The good news here is that it is relatively easy to detect and eliminate most useless relations.

Revision.

Method