Admissible Distance Heuristics for General Games - Agents and Artificial Intelligence - page 191

The value Δ max ( f ) represents the longest finite distance Δ G ( g,f ) from any fluent g to
f in G .
Thus the normalized distance δ ( s, f ) will be infinite if and only if Δ ( s, f )=

∞

, i.e.,
there is no path from any fluent in s to f in the fluent graph. In all other cases it holds
that 0 1 .

Note, that the construction of the fluent graph and computing the shortest paths be-
tween all fluents, i.e., the distance function Δ G , need only be done once for a game.
Thus, while construction of the fluent graph is more expensive for complex games, the
cost of computing the distance feature δ ( s, f ) (or Δ ( s, f ) ) only depends (linearly) on
the size of the state s .

≤ δ ( s, f ) ≤

5.1 Using Distance Features in an Evaluation Function
To demonstrate the application of the distance measure presented, we use a simplified
version of the evaluation function of Fluxplayer [9] implemented in Prolog. It takes the
ground DNF of the goal rules as first argument, the current state as second argument
and returns the fuzzy evaluation of the DNF on that state as a result.

1 eval((D1; ...; Dn), S, R) :- !,
2 eval(D1, S, R1), ..., eval(Dn, S, Rn),
3 R is sum(R1, ..., Rn) - product(R1, ..., Rn).
4 eval((C1, ..., Cn), S, R) :- !,
5 eval(C1, S, R1), ..., eval(Cn, S, Rn),
6 R is product(R1, ..., Rn).
7 eval( not (P), S, R) :- !, eval(P, S, Rp), R is 1 - Rp.
8 eval( true (F), S, 0.9) :- occurs(F, S),!.
9 eval( true (F), S, 0.1).

Disjunctions are transformed to probabilistic sums, conjunctions to products, and true
statements are evaluated to values in the interval [0 , 1] , basically resembling a recursive
fuzzy logic evaluation using the product t-norm and the corresponding probabilistic
sum t-conorm. The state value increases with each conjunct and disjunct fulfilled.
We compare the evaluation to a second function that employs our relative distance
measure, encoded as predicate delta . We obtain the distance-based evaluation function
by substituting line 9 of the previous program by the following:

1 eval( true (F), S, R) :- delta(S, F, Dist), Dist =< 1, !,
2 R is 0.8 * (1-Dist) + 0.1.
3 eval( true (F), S, 0).

Here, we evaluate a fluent that does not occur in the current state to a value in [0 . 1 , 0 . 9]
and, in case the relative distance is infinite, to 0 since this means that the fluent cannot
hold anymore.

5.2 Tic-Tac-Toe
Although on first sight Tic-Tac-Toe contains no relevant distance information, we can
still take advantage of our distance function. Consider the two states as shown in Fig-
ure 2. In state s 1 the first row consists of two cells marked with an x and a blank cell.