logic-programminganswer-set-programmingclingo# Optimizing difficulty with a level generator using Clingo

I’m making a puzzle level generator (sokoban) using Clingo and got stuck trying to create levels with a specific move limit. The idea is to use the move limit to control difficulty of a level. This is how I’ve created the generator:

- Specify rules for a valid looking level (all walkable tiles are connected, correct ampunt of pushable barrels and target platforms, etc.)
- Specify rules for moving around and pushing barrels.
- Specify winning conditions.

My first iteration was to simply require that a level is solvable in N moves by requiring that winning conditions are met in `0..N`

moves. This resulted in valid levels but there was no control over the difficulty.

My second iteration was to minimize the moves required for a winning condition to be met. This resulted in levels that are completed in a single move.

My third iteration was to state that a level could not be completed in less than M moves. This resulted in the logic doing unnecessary moves just to reach the minimum, there was still no meaningful control over difficulty.

My fourth iteration was to prevent the same game state from reoccurring to avoid unnecessary ”filler” moves, but this still resulted in the logic solving the levels in very unoptimally just to reach the minimum requirement.

Now I don’t really know what to do. I think what I want to do is maximize the minimum required amount of moves (up to a limit), but I’m not sure if that makes any sense. Preferrably I’d like to be able to state that the minimum amount of moves for completing this level should be `M`

.

How should this problem be approached?

Solution

So to put it in other terms: you are searching for a puzzle that can be solved in `N`

moves but solving it in `N-1`

would return unsatisfiable. Those two parts state complimentary problems ("Find at least one" vs. "Find none/all") and are difficult to put in one program and the combination raises the problem complexity (see polynomial hierarchy). Here three suggestions to solve it via enumeration:

Enumeration and difference: For

`N`

and`N-1`

enumerate all answers. A puzzle is solvable in exactly`N`

steps, when it appears for`N`

but not for`N-1`

. This requires some sort of post processing, like a script or neat text editing.Enumeration and unsatisfiable: In a script enumerate all answer sets one by one for the current

`N`

. For the current puzzle, try to solve it for`N-1`

: if it returns`0`

answers, you have your puzzle. This requires data-handling of some form, I would suggest using python.Enumeration avoiding doubles: In a script, for

`N-1`

generate all answer sets. Transform each answer set into a constraint and add it to the program. Example: the tiles`m(1..4,l). m(1..4,r)`

define your puzzle in general, your current answer set is`m(1,l). m(2,l). m(3,r).`

, add the following constraint to avoid generating this puzzle again. Afterwards solve the updated program for`N`

.`:- m(1,l), m(2,l), m(3,r), not m(1,r), not m(2,r), not m(3,l), not m(4,l), not m(4,r).`

As you might see all three methods would solve your problem but require additional effort outside of clingo.

- Event-Driven Programming Paradigm in Logic Programing
- What are the main technical differences between Prolog and miniKanren, with respect to logic programming?
- Prolog: Failure driven loops
- Purity of Prolog predicates that use impure primitives
- Inductive proofs in theorem provers (Z3, Vampire, with TPTP syntax)
- Why does introducing numbero in minikanren cause the failure of valid unifications?
- Optimizing difficulty with a level generator using Clingo
- Does the term "Functor" in Prolog have any relation to the term taken from Category Theory?
- PyDatalog: list of values in answer
- Route Inspection of Directed Graph in ASP
- Negative optimization result in Answer Set Programming
- Spanning Trees in Answer Set Programming
- Answer Set Programming - filtering from a large number of models
- Non-termination when query variable is on a specific position
- Can you do Logic Programming in Scala?
- What is the most elegant way to find 16-bit numbers which satisfy some conditions?
- Does Prolog need GC when the occurs check is globally enabled?
- Are there elements of 'logic programming' in Java?
- Converting `appendo` relation from smt2 to python
- How to replace constants terms from python API in clingo / gringo?
- Clarify search algorithms in different minikanren implementation
- Does MiniKanren have the "not" operator?
- Shorthand for multiple choice predicates in clingo
- Clingo program expected to be satisfiable
- Riddle puzzle in clingo
- Haskell's type system and logic programming - how to port Prolog programs to type level
- Look for algorithm/research area that determines facts that would make a Prolog query true given a Prolog program
- Why does "disj" from miniKanren work in Scheme but not in Racket?
- "Generating Numbers" Puzzle
- Executing prolog code on an iPhone