Information Technology Reference
In-Depth Information
to capture its advanced pawns. This behavior, however, results in a smaller maximal
number of moves until the game ends and forces to advance the few remaining pawns
quickly. Thus, the problem in this game is not the distance estimate but the fact that the
heuristic is not suitable for the game.
Finally, in some of the games no changes were found since both distance estimates
performed equally well. However, rather specific heuristics and analysis methods of
flux basic could be replaced by our new general approach. For example, the original
Fluxplayer contains a special method to detect when a fluent is unreachable, while this
information is automatically included in our distance estimate.
7
Related Work
Distance features are part of classical agent programming for games like chess and
checkers in order to measure, e.g., the distance of a pawn to the promotion rank. A more
general detection mechanism was first employed in Metagamer [8] where the features
“promote-distance” and “arrival-distance” represented a value indirectly proportional to
the distance of a piece to its arrival or promotion square. However, due to the restriction
on symmetric chess-like games, the features are still too specific for an application in
GGP.
Currently, a number of GGP agent systems apply distance features in different forms.
UTexas [6] identifies order relations syntactically and tries to find 2d-boards with co-
ordinates ordered by these relations. Properties of the content of these cells, such as
minimal/maximal x- and y-coordinates or pair-wise Manhattan distances are then as-
sumed as candidate features and may be used in the evaluation function. Fluxplayer [9]
generalizes the detection mechanism using semantic properties of order relations and
extends board recognition to arbitrarily defined
n
-dimensional boards.
Another approach is pursued by Cluneplayer [2] who tries to impose a symbol dis-
tance interpretation on expressions found in the game description. Symbol distances,
however, are again calculated using Manhattan distances on ordered arguments of board-
like fluents, eventually resulting in a similar distance estimate as UTexas and Flux-
player.
Although not explained in detail, Ogre [4] also employs two features that measure
the distance from the initial position and the distance to a target position. Again, Ogre
relies on syntactic detection of order relations and seems to employ a board centered
metrics, ignoring the piece type.
All of these approaches rely on the identification of certain fixed structures in the
game (such as game boards) but can not be used for fluents that do not belong to such a
structure. Furthermore, they make assumptions about the distances on these structures
(usually Manhattan distance) that are not necessarily connected to the game dynamics,
e.g., how different pieces move on a board.
In domain independent planning, distance heuristics are used successfully, e.g., in
HSP [1] and FF [3]. The heuristics
h
(
s
)
used in these systems is an approximation of
the plan length of a solution in a relaxed problem, where negative effects of actions are
ignored. This heuristics is known as delete list relaxation. While on first glance this may
seems very similar to our approach, several differences exist:
