Answer Set Programming

An idea was to use Answer Set Programming to solve single player games. A normal approach uses a grounder, solver and a time parameter. But this approach has the disadvantage of grounding the whole problem before it can be solved. The grounding is an bottleneck which is one of the hardest problem with this idea. Because of that we used the technology of iterative grounding and solving.

1. Build Domains

First of all we have to determine Domains for all variables which are used in a recursive predicate. We use a dependency graph to calculate this Domains.

Rules (predicate h with arity n_h):
h/n_h :- b₁/n₁ , ... , b_j/n_j.
h/n_h :- c₁/0, ... c_i/0.

Graph:
h/n_h=> b₁/n₁ ; ... ; b_j/n_j ; c₁/0 ; ... c_i/0

To build a Domain we run through the graph (respect for cycles) and collect all constants.

2. Meta Predicates and Time Parameter

For iterative grounding each meta predicate of GDL needs a time parameter. Therefor we add this parameters and rename to predicates

init(p/n) -> holds(p/n,1)
true(p/n) -> holds(p/n,t)
next(p/n) -> holds(p/n,t+1)
legal(R,p/n) -> legal(R,p/n,t)
does(R,p/n) -> does(R,p/n,t)
terminal -> terminal(t)
goal(R,P) -> goal(R,P,t)

[R = Role, P = Points]

for all predicates with

h(X₁ , ... , X_n) :- [body], b(Y₁ , ... , Y_m , t) , [body].

add t to h -> h(X₁ , ... , X_n ,t) in every occurence. (loop with fixpoint)

3. Format for iclingo

Iclingo is a iterative grounding und solving tool, consisting of gringo and clasp. To use Iclingo the encoding has to have the following structure:

#base.
holds(p/n,1).
... % every predicate without time parameter.
#cumulative t.
... % every predicate with time parameter.
1{does(R,M,t):moveDomain(M):role(R)}1 :- not terminal(t).
:- does(R,M,t), not legal(R,M,t), role(R).
:- terminal(t), terminal(t-1).

#volatile t.
:- terminal(t), not goal(R,100,t), role(R).
:- not terminal(t).

#HIDE.
#SHOW does/3.

Results:

will follow

Literatur:

 Answer Set Programming for Single-Player Games in General Game Playing (Prof. Thielscher)

ASPBenchs list with games and recent problems