Information Technology Reference
In-Depth Information
Admissible Distance Heuristics for General Games
Daniel Michulke
1
and Stephan Schiffel
2
1
Dresden University of Technology, Dresden, Germany
2
Reykjavık University, Reykjavık, Iceland
dmichulke@gmail.com, stephans@ru.is
Abstract.
A general game player is a program that is able to play arbitrary games
well given only their rules. One of the main problems of general game playing
is the automatic construction of a good evaluation function for these games. Dis-
tance features are an important aspect of such an evaluation function, measuring,
e.g., the distance of a pawn towards the promotion rank in chess or the distance
between Pac-Man and the ghosts.
However, current distance features for General Game Playing are often based
on too specific detection patterns to be generally applicable, and they often apply
a uniform Manhattan distance regardless of the move patterns of the objects in-
volved. In addition, the existing distance features do not provide proven bounds
on the actual distances.
In this paper, we present a method to automatically construct distance heuris-
tics directly from the rules of an arbitrary game. The presented method is not
limited to specific game structures, such as Cartesian boards, but applicable to all
structures in a game. Constructing the distance heuristics from the game rules en-
sures that the construction does not depend on the size of the state space, but only
on the size of the game description which is exponentially smaller in general.
Furthermore, we prove that the constructed distance heuristics are admissible,
i.e., provide proven lower bounds on the actual distances.
We demonstrate the effectiveness of our approach by integrating the distance
heuristics in an evaluation function of a general game player and comparing the
performance with a state-of-the-art player.
Keywords:
General game playing, Feature construction, Heuristic search.
1
Introduction
While in classical game playing, human experts encode their knowledge into features
and parameters of evaluation functions (e.g., weights), the goal of General Game Play-
ing is to develop programs that are able to autonomously derive a good evaluation func-
tion for a game given only the rules of the game. Because the games are unknown
beforehand, the main problem lies in the detection and construction of useful features
and heuristics for guiding search in the match.
One class of such features are distance features used in a variety of GGP agents
(e.g., [6,9,2,4]). The way of detecting and constructing features in current game playing
systems, however, suffers from a number of disadvantages:
