Information Technology Reference
In-Depth Information
-
The underlying languages, GDL for general game playing and PDDL for planning,
are different. A translation of GDL to PDDL is expensive in many games [5]. Thus,
directly applying planning systems is not often not feasible.
-
The delete list relaxation considers all (positive) preconditions of a fluent, while we
only use one precondition. This enables us to precompute the distance between the
fluents of a game.
-
While goal conditions of most planning problems are simple conjunctions, goals
in the general games can be very complex (e.g., checkmate in chess). Additionally,
the plan length is usually not a good heuristics, given that only the own actions and
not those of the opponents can be controlled. Thus, distance estimates in GGP are
usually not used as the only heuristics but only as a feature in a more complex eval-
uation function. As a consequence, computing distance features must be relatively
cheap.
-
Computing the plan length of the relaxed planning problem is NP-hard, and even
the approximations used in HSP or FF that are not NP-hard require to search the
state space of the relaxed problem. On the other hand, computing distance estimates
with our solution is relatively cheap. The distances
Δ
G
(
f,g
)
between all fluents
f
and
g
in the fluent graph can be precomputed once for a game. Then, computing
the distance
Δ
(
s, f
)
(see Definition 3) is linear in the size of the state
s
, i.e., linear
in the number of fluents in the state.
8
Future Work
One problem of the approach is its computational cost for constructing the fluent graph,
that may prevent an application of our distance features for narrow time constraints.
One way to reduce the time needed for construction is a reduction of the size of
φ
via
a more selective expansion of predicates (line 5) in Algorithm 1. Developing heuristics
for this step is one of the goals for future research.
In addition, we are working on a way to construct fluent graphs from non-ground
representations of the preconditions of a fluent to skip the grounding step. For example,
the partial fluent graph in Figure 1(a) is identical to the fluent graphs for the other 8
cells of the Tic-Tac-Toe board. The fluent graphs for all 9 cells are obtained from the
same rules for
next
(cell(X,Y,_)
, just with different instances of the variables
X
and
Y
. By not instantiating
X
and
Y
, the generated DNF is exponentially smaller while still
containing the same information.
The quality of the distance estimates depends mainly on the selection of precondi-
tions. At the moment, the heuristics we use for this selection are intuitive but have no
thorough theoretic or empiric foundation. In future, we want to investigate how these
heuristics can be improved.
Furthermore, we intend to enhance the approach to use fluent graphs for generaliza-
tions of other types of features, such as, piece mobility and strategic positions.
9
Summary
We have presented a general method of deriving distance estimates in General Game
Playing. To obtain such a distance estimate, we introduced fluent graphs, proposed an
