Re: [Potassco-users] puzzle generation ~ disjunctive ASP

[Adam S. <am...@so...>]

Tremendous thanks, Roland!

For anyone else interested, here are some nice pictures of conforming
outputs for a few different parameter settings (all solved in a few
seconds):

http://tinyurl.com/7dlr7cp
http://tinyurl.com/74h4t3g
http://tinyurl.com/7tzsfkr
http://tinyurl.com/7d726zr
http://tinyurl.com/7usok9q

I want to clarify what you mean by "the disjunctive part of the
program". Does this mean that default negation is meaningless when
directly applied to any atom mentioned in a disjunction? Or does it
mean, in a saturation encoding, that "bot" should never depend even
indirectly on the negation of an atom in a disjunction? Relatedly,
what does this imply for choice rules with upper bounds, e.g. negation
as 0 { ... } 0 ? In the code snippet below, "not black(X)" is ok
because black represents one of the existentially quantified values in
the 2QBF interpretation, right?

This decaying-unconnectedness derivation is an interesting and
unexpected compliment to the spreading-connectedness derivation in the
original definition. Is it part of a more general idiom for expressing
recursive things without negation?

    % determine the unconnected positions
    steps(N+M) :- num_white(N), num_black(M).
    unconnected(X,1)    :- pos(X), not root(X).
    unconnected(X,1..N) :- pos(X), not black(X), nwhite(X), steps(N).
    unconnected(X,S+1)  :- unconnected(X,S), unconnected(Y,S) :
adj(X,Y), S < N, steps(N).
    bot :- black(X), unconnected(X,N), steps(N).

On Fri, Dec 9, 2011 at 6:29 AM, Roland Kaminski
<kam...@cs...> wrote:
> Hi Adam,
>
> here is a possible encoding. The problem with disjunctive encodings is that
> you cannot use reachability in the disjunctive part of the program because
> there you cannot make use of negation as failure. I suppose that this has been
> your problem when trying to encode this.
>
> Regards, Roland
>
> On Friday 09 December 2011 08:41:30 Adam Smith wrote:
>> Hi Roland, all,
>>
>> Here's a gist with a some code: https://gist.github.com/1450537
>> - instance.lp (definition of numerical parameters from previous message)
>> - encoding.lp (definition of valid board states)
>> - visualization.lp (a nice diagram generator using the Lonsdaleite
>> tool I linked last month)
>> - USAGE (obvious command line and link to a visualization of an example
>> output)
>>
>> In the example visual output [ http://tinyurl.com/6pn5tcc ], you'll
>> see an example of the kind of situation that I can't figure out how to
>> avoid yet. It shows 8 black stones being linked by no more than 12
>> white stones, but there are clearly solutions that use fewer. I want
>> to enumerate exactly the configurations of black stones that can be
>> linked by 12 white's but are impossible to link with 11 or fewer.
>>
>> I'm trying to set up the 2QBF problem "∃ Black ∀ White st.
>> solves(White,Black) → enough(White)", hence the need for a disjunctive
>> solver.
>>
>> Thanks,
>>
>> Adam
>>
>> On Thu, Dec 8, 2011 at 1:42 PM, Roland Kaminski
>>
>> <kam...@cs...> wrote:
>> > Hi Adam,
>> >
>> > we are writing disjunctive Encodings from time to time. It would be nice
>> > if you could send us an encoding (as compact as possible) that finds a
>> > solution for your simplified problem. I mean a normal encoding without
>> > anything fancy here: clingo instance.lp encoding.lp -> solution
>> >
>> > >From there it should be straightforward to write something that
>> > >generates
>> >
>> > puzzles that have a certain shortest solution length. Although, I can
>> > make no promises that this will scale.
>> >
>> > Regards, Roland
>> >
>> > On Wednesday, December 07, 2011 06:33:17 PM Adam Smith wrote:
>> >> Hi folks,
>> >>
>> >> I'm struggling with a project that involves claspD, and I'd like to
>> >> pick your brains for help. Even if you aren't familiar with
>> >> disjunctive ASP, your input on model stuff might be helpful.
>> >>
>> >> For some context, I'm building a level generator for the educational
>> >> puzzle game Refraction (http://games.cs.washington.edu/refraction/).
>> >> We want to replace the fixed sequence of hand-designed levels in the
>> >> current game with a generated sequence (to be more relevant to a
>> >> player's spatial and mathematical problem solving abilities). I've
>> >> already got a very rich level generation setup for Refraction levels
>> >> based on Clingo, but it fundamentally addresses a weaker problem: it
>> >> proposes puzzles with an example solution that involves some target
>> >> concepts (like constructing 1/2+1/4=3/4), but this existence proof
>> >> gives us no assurance that there isn't an alternative solution to the
>> >> same puzzle that sidesteps the target concepts.
>> >>
>> >> Instead of getting you all tangled up in the rather complex mechanics
>> >> of Refractions, let me propose a vastly simpler game that (I'm
>> >> assuming) has the same underlying computational challenges.
>> >>
>> >> You are given a 9x9 grid -- imagine a Go board. Your puzzle design
>> >> challenge is to place 8 black stones around the board in such a manner
>> >> that it takes all 12 white stones I have to build a network of
>> >> adjacent pieces connecting all of the black stones. Here's a visual
>> >> example: http://imgur.com/LNA1l (dunno if it's not solvable in a
>> >> simpler way, I just typed in my best guess). The programming challenge
>> >> is to write a (preferably small and fast) answer set program that
>> >> enumerates all such arrangements of black stones (and preferably under
>> >> optional aesthetic constraints like forced symmetry/asymmetry of black
>> >> stones or the like). The numerical parameters (9x9 / 8 / 12) are
>> >> flexible, however the numbers I gave are representative of the scale
>> >> in which I'm interested.
>> >>
>> >> This puzzle design problem is imminently finite, small even! It's easy
>> >> to whip of a generator for boards containing 8 black stones and 12
>> >> white stones forming a network, but if you reach for #minimize when
>> >> you try to express the idea that there is no simpler solution then
>> >> you've missed the subtlety. Imagine a pathological puzzle-and-solution
>> >> pair where all 8 black stones are clumped at the top-left and the 12
>> >> white stones form line that snakes off into the open area (technically
>> >> it's a valid play for white). Minimizing the number of white stones in
>> >> play in this encoding would simply result in all of them disappearing,
>> >> leaving the self-networked clump of black stones behind as a trivial
>> >> solution.
>> >>
>> >> I saw that Martin Gebser made a Sudoku puzzle generator for use with
>> >> claspD that is very relevant here:
>> >> http://asparagus.cs.uni-potsdam.de/encoding/show/id/12739 Where this
>> >> generator enforces uniqueness of the constructed solution witness, I
>> >> only want to enforce minimal cardinality (which is a stand in for the
>> >> much more complicated things that I want in Refraction). Does anyone
>> >> on the list feel up for the programming challenge of adapting the
>> >> generator I linked into one that solves the stones/grid problem I
>> >> described above? I can't seem to wrap my head around the saturation
>> >> technique with enough generality to adapt it myself.
>> >>
>> >> (I can offer generous acknowledgement in publications and potential
>> >> co-authorship on a paper about mechanizing game content generation
>> >> with ASP if puzzle generation tickles your interests enough to stay
>> >> involved.)
>> >>
>> >> Adam
>> >>
>> >> ------------------------------------------------------------------------
>> >> ---- -- Cloud Services Checklist: Pricing and Packaging Optimization
>> >> This white paper is intended to serve as a reference, checklist and
>> >> point of discussion for anyone considering optimizing the pricing and
>> >> packaging model of a cloud services business. Read Now!
>> >> http://www.accelacomm.com/jaw/sfnl/114/51491232/
>> >> _______________________________________________
>> >> Potassco-users mailing list
>> >> Pot...@li...
>> >> https://lists.sourceforge.net/lists/listinfo/potassco-users
>> >
>> > -------------------------------------------------------------------------
>> > ----- Cloud Services Checklist: Pricing and Packaging Optimization
>> > This white paper is intended to serve as a reference, checklist and point
>> > of discussion for anyone considering optimizing the pricing and
>> > packaging model of a cloud services business. Read Now!
>> > http://www.accelacomm.com/jaw/sfnl/114/51491232/
>> > _______________________________________________
>> > Potassco-users mailing list
>> > Pot...@li...
>> > https://lists.sourceforge.net/lists/listinfo/potassco-users