Information Technology Reference
In-Depth Information
-
Distance features require a prior recognition of board-like game elements. Current
approaches formulate hypotheses about which element of the game rules describes
a board and then either check these hypotheses in internal simulations of the game
(e.g., [6,9,4]) or try to prove them [10]. Both approaches are expensive and can
only detect boards if their description follows a certain syntactic pattern.
-
Distance features are limited to Cartesian board-like structures, that is, n-dimen-
sional structures with totally ordered coordinates. Distances over general graphs
are not considered.
-
Distances are calculated using a predefined metric on the boards. Consequently,
distance values obtained do not depend on the type of piece involved. For exam-
ple, using a predefined metric the distance of a rook, king and pawn from
a
2
to
c
2
would appear equal while a human would identify the distance as
1
,
2
and
∞
(unreachable), respectively.
In this paper we will present a more general approach for the construction of distance
features for general games. The underlying idea is to analyze the rules of game in order
to find dependencies between the fluents of the game, i.e., between the atomic prop-
erties of the game states. Based on these dependencies, we define a distance function
that computes an admissible estimate for the number of steps required to make a cer-
tain fluent true. This distance function can be used as a feature in search heuristics of
GGP agents. In contrast to previous approaches, our approach does not depend on syn-
tactic patterns and involves no internal simulation or detection of any predefined game
elements. Moreover, it is not limited to board-like structures but can be used for every
fluent of a game.
The remainder of this paper is structured as follows: In the next section we give
an introduction to the Game Description Language (GDL), which is used to describe
general games. In Section 3 we introduce the theoretical basis for this work, so called
fluent graphs, and show how to use them to derive distances from states to fluents. We
proceed in Section 4 by showing how fluent graphs can be constructed from a game
description and demonstrate their application in Section 5. We conduct experiments
in Section 6 to show the benefit and generality of our approach and discuss related
approaches in Section 7. Finally, we give an outlook on future work in Section 8 and
summarize in Section 9.
2
Preliminaries
The language used for describing the rules of general games is the Game Description
Language [7] (GDL). GDL is an extension of Datalog with functions, equality, some
syntactical restrictions to preserve finiteness, and some predefined keywords.
The following is a partial encoding of a Tic-Tac-Toe game in GDL. In this paper we
use Prolog syntax where words starting with upper-case letters stand for variables and
the remaining words are constants.
