Labs 4 – ASP

Procedural Content Generation for Computer Games

Vojtěch Černý

cerny@gamedev.cuni.cz

Prerequisites

• Windows / Mac / Linux
• Python 3

Installing clingo

• We’re going to use Potassco’s clingo client

​

• Download clingo from Anaconda/Miniconda or pip
• For conda, run conda install -c potassco clingo

How does clingo work?

ASP program

(AnsProlog)

Ground program

​

(propositional

logic rules)

Answer set(s)

Grounding

gringo

Solving

clasp

clingo = gringo + clasp

Grounding

• Transforming into predicate logic

edge(0,1). edge(1,2). edge(2,0).

color(r; g; b).

:- edge(X, Y), colored(X, C), colored(Y, C).

:- colored(1, r), colored(0, r).

:- colored(1, g), colored(0, g).

:- colored(1, b), colored(0, b).

:- colored(2, r), colored(1, r).

:- colored(2, g), colored(1, g).

:- colored(2, b), colored(1, b).

:- colored(0, r), colored(2, r).

:- colored(0, g), colored(2, g).

:- colored(0, b), colored(2, b).

Solving

• Solving in ASP (by clasp) is done by search
• Specifically, conflict-driven learning (enhancement of DPLL, a method used by most modern SAT solvers)
• Selecting in choice rules, disjunctive formula’s, …
• Heuristic-guided (several heuristics available) or partially random

First clingo run

Start with the answer-set-programming repo

• You can run clingo programs from command-line (but you don‘t need to, we have a useful Python wrapper)
• You can run it like this:

​

clingo 0_sprinklers.lp

​

• The second argument is number of solutions (default 1), running:

​

clingo 0_sprinklers.lp 0

​

gets you all solutions possible (0 = all)

Python runner

• There’s a prepared clingo runner from Python - simple_clingo.py

​

• Check out simple_example.py for example usage
• Try running other programs from it, like 0_sprinklers.lp
• Additional programs (worth checking out):
• sudoku_solver.py
• sudoku_generator.py
• maze_generator.py
• murder_mystery_text.py

Preparation tasks

Start with the answer-set-programming repo

Read through the numbered examples (best in order) and make sure you understand them.

Try doing these „simple“ tasks:

1. (playground) Modify 1_graph_coloring.lp. Try adding more colors, alter the graph, see what happens when no solution is possible.
2. (easy) Modify 2_hamiltonian_cycle.lp so it only looks for Hamiltonian path
3. (medium) Write a program that finds a vertex cover of size N in a graph
4. (hard) Optimize 5_maze.lp – use only reachable(X, Y) instead of distance_from_start(X, Y, D)

​

The Task

Make a murder mystery text-based game!

​

Start with the ASP + Python example

• examples/3_murder_mystery.lp
• murder_mystery_text.py

​

This version is playable, but quite bland (try playing it yourself).

• Modify it to be more exciting!
• Aim for GameJAM quality

​

Extensions (mainly for inspiration)

• Allow the murderer to lie
• Allow asking who-saw-who
• Add motive into the mix
• You may have to add some relationships, experiences, so that it makes sense
• Add evidence and tampering with it
• Maybe somebody hid the murder weapon somewhere

​

• Ideally, come up with (at least some of) your own!
• Give it a theme so that it stands out!
• Try to make the game fun!

Task details

• You must make notable changes in both the ASP and in Python

​

• Make sure (in ASP), that it is always logically possible to deduce the murderer

Criteria

• At least 2 new features in ASP
• Always place comment “% FEATURE: <short description of your feature>”
• At least 10 lines of AnsProlog (ASP code)

​

• You may modify existing code, just not drastically (keep the structure)

​

• The whole mystery should be generated by ASP:
• Python should be used just for the interaction
• If something can be done in ASP and in Python, you should do it in ASP
• However, you may add rules dynamically from Python at the start (and it counts towards the 10 needed)

​

​

​

​

Points

• Non-trivial added concepts –1pt each (total capped at 2pts)
• If you feel your concepts might be too simple, add more than 2

​

• Description on how you ensured a single possible logical deduction – 1pt

Submission details

• Send your solutions to cerny@gamedev.cuni.cz
• Prefix the subject with “NAIL123-HW4”
• Submit:
• Python file murder_mystery_text.py, ASP file 3_murder_mystery.lp
• with comments!
• 3 playthroughs of your game, as .txt files
• describe your additions
• describe what you have tried, what worked or didn’t, the problems you faced
• how much time you spent with the project (will not be part of evaluation)
• Deadline is 3.5.
• If you need more time, talk/write to me before the deadline

​

Questions / Problems

• You can always e-mail me at cerny@gamedev.cuni.cz
• I’m also frequently online at Discord https://discord.gg/4nfAzG

Q & A

Vojtěch Černý

cerny@gamedev.cuni.cz

Meta-programming in ASP (optional topic)

• Motivation: how do you generate a Sudoku with a unique solution?

​

• Can you use ASP to express such uniqueness?

​

• Yes, by exploiting the minimality aspect of answer sets.

How to guarantee unique solution

• The approach:
• Generate a counter-example candidate
• If counter-example candidate isn’t valid, generate atom “bot”
• If bot is generated, fill the whole counter-example space
• Add a constraint that bot must be generated

​

• Why it works?

If a counter-example exists, generating it will be a smaller (in inclusion) than if bot is derived and the whole counter-example space is filled.

And in that case, solutions with bot won’t be answer sets.

How to guarantee minimal assignment

• Secondly, how do you generate a Sudoku without giving too many hints?

​

• Approach: In minimal sudoku, each clue has a possible replacement, such that it is still solvable (otherwise it isn’t minimal, the clue can be deduced).
• In ASP, we can construct all alternative solution when each (one) clue is reassigned.

​

• predicate alt_solution(ClueX, ClueY, X, Y, N).

Contains solution (X, Y, N) for each ClueX, ClueY, where the clue at ClueX, ClueY is changed. Has to be derived for each ClueX, ClueY.

​

​