Re: Is Prolog a good language for generating semi-random, constrained solutions?

You might want to look at stochastic logic programs.
http://www.doc.ic.ac.uk/~shm/Papers/slp.pdf‎

A simple SLP is
  0.5: coin(head).
  0.5: coin(tail).

You can then sample the slp like this
?- between(1, 5, _), slp_sample(coin(X)).
X=head;
X=head;
X=tail;
X=head;
X=tail;
no

You would write a more complex stochastic logic program for it to be useful, but it strikes me as quite an elegant approach.

I don't know if there are any implementations of an SLP prover floating around.  Perhaps someone else could comment on that.  Although I do recall it being implemented as a meta-interpreter in Ashwin Srinivasan's Aleph.  

Cheers,
Parker


> Date: Fri, 14 Mar 2014 01:30:46 -0700
> From: [email protected]
> To: [email protected]
> Subject: [SWIPL] Is Prolog a good language for generating semi-random,	constrained solutions?
> 
> I've been working on something in the last week for which I assumed Prolog
> would be a good tool, but I'm slightly on the fence about its suitability
> now.
> 
> Essentially I am trying to use Prolog to generate a single, semi-random
> sequence of entries that needs to meet some loose criteria only. For the
> sake of simplicity, let's assume I want to create a list of atoms. For each
> atom considered as a candidate to be added to the end of a list under
> construction, there are some constraints on which ones are legal. Let's say
> (arbitrarily) that
> 1. I can add an a,b or c as a new entry at any time.
> 2. I can add a new entry d if a and b are already in the list (at least one
> of each).
> 3. I can add an e if there is already at least one c.
> 4. If there is both an entry c and an entry e in the list then I can no
> longer add d.
> These sorts of things (waves hand). Details are not important.
> 
> Using these kinds of addition rules, I want to ask the system to generate
> me a (semi-) random sequence of a given length whose only requirements are
> that each entry added must obey all given rules at the time of its addition
> to the sequence. I don't require an enumeration of all legal sequences; I
> just want one each time I execute the program. So
> [a,b,a,b,a,b,c]
> ...is legal (assuming I asked for a list of length 7), as is
> [a,b,c,d,e,a,b]
> ....but
> [a,b,c,d,e,b,d]
> ...is not (the final d violates rule 4).
> 
> I might then add some further constraints: I'd like the system to create
> such a sequence, but with some additional macro-level requirements:
> 
> * There must be 2 bs in the first five entries. (This would rule out the
> second list above, but the first would be accepted.)
> * There cannot be any ds between entries five and seven inclusive.
> etc.
> 
> I have built such a program, but it feels a little inelegant and slightly
> arbitrary, and although Prolog helps make the writing of the
> rules/constraints easy, I feel a bit uncertain that my program is
> particularly idiomatic. I can't enumerate all solution lists and then pick
> one at random, because the state space is too large. Also, I can't see how
> it's easy to build a list with a mixture of bound and unbound members and
> use that to help guide the search efficiently, because I don't always know
> precisely which members should be bound, and the possible combinations of
> such semi-bound lists can themselves be very large in number.
> 
> What I'm doing right now is creating the list a few entries at a time (e.g.
> five at a time). For each added member, I consider the list of all new
> entry candidates that would be legal using the universal rules, and pick
> one of these at random to add to the end of the list. When five have been
> added, I apply my extra constraint checks to see if these all pass. If they
> do, I move on to adding the next batch of five. If not, I try again. (Why
> five? That's the arbitrary part. Perhaps I'd be better off applying those
> constraints for every single entry added. But the macro constraints don't
> always apply to individual entries, but rather to the list as a whole, or
> subsequences of it.)
> 
> This current approach does work, certainly for small-ish sequences (20-30)
> and a set of perhaps a dozen general rules and some mild macro-level list
> constraints. But I'm not sure that this is the best or most efficient way
> to approach the problem. It is really a hybrid imperative-declarative
> design (the control of the batched search in chunks of five is controlled
> by a C algorithm that calls into Prolog to execute the search itself). I
> would prefer a more idiomatic Prolog approach, but perhaps the language
> simply isn't especially well-suited to this task? (It is first and foremost
> designed to provide a total enumeration of solution state space.)
> 
> I would welcome any thoughts/suggestions.
> 
> KJ
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
 		 	   		  
-------------- next part --------------
HTML attachment scrubbed and removed
_______________________________________________
SWI-Prolog mailing list
[email protected]
https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog