JESS: random strategy

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

JESS: random strategy

Rajcsányi Vilmos
Hi!

I would like to write a conflict resolution strategy that orders (all)
activations into a completely random order.
I've written a simple class implementing the Strategy interface, looks
like this:

public final class RandomActivation implements Strategy, Serializable
{
     private static final long serialVersionUID = 1L;
     private static final String mName = "RandomActivation";
     private final Random mGenerator;

     public RandomActivation()
     {
         mGenerator = new Random();
     }

     public final int compare( final Activation pAct1, final Activation
pAct2 )
     {
         int result;

         final double r1 = mGenerator.nextDouble();
         final double r2 = mGenerator.nextDouble();

         if ( r1 < r2 )
         {
             result = 1;
         }
         else if ( r1 > r2 )
         {
             result = -1;
         }
         else
         {
             result = 0;
         }
         return result;
     }

     public final String getName()
     {
         return mName;
     }
}

(I don't know whether the random numbers are really necessary, as I've
read in a former message that returning 0 would
result an indeterministic order of the activations, anyway my problem
has nothing to do with this.)
I've noticed that this strategy doesn't behave as I have expected.
I watched how many times the compare method was invoked after a new
activation was placed to the agenda,
and I don't understand why there are such activations
that aren't compared to every other activations. Isn't this the way the
conflict resolution should work?
Compare every activations to every others?
For example there was such activation that was compared to only one
other activation... Why is that?
Or am I misunderstanding something? Please explain me how and how many times
the compare method should be invoked, and how can I reach a complete
random reordering of the agenda.
Thanks.


--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users [hidden email]'
in the BODY of a message to [hidden email], NOT to the list
(use your own address!) List problems? Notify [hidden email].
--------------------------------------------------------------------

Reply | Threaded
Open this post in threaded view
|

Re: JESS: random strategy

Friedman-Hill, Ernest
Lots of questions here, some explicit, some implicit. First I'll  
answer the one about why you saw an activation compared to only one  
other.

Imagine you have a sorted partial deck of cards -- say you have a 5,  
8, 10, Queen and King, in that order, top to bottom. The cards have  
the important property that they can be sorted into a definite order,  
and that order is stable. No matter how many times you check, the 8  
will always belong after the 5. Furthermore, it's a transitive  
relationship: if the 10 comes after the 8, and the 8 comes after the  
5, then the 10 comes after the 5. Remember that -- we'll come back to  
it later.

Now imagine you're picking up cards one at a time and inserting them  
into the correct place in the deck. If you pick up a 4, what would you  
do? You'd see the 5 on top, realize that it's larger than the 4, and  
lay the 4 on top. You've only compared the 4 to one other card.

If you picked up a Jack, however, you might cut the deck in half and  
compare the card with the middle cards, searching around a little bit  
until you found the right spot. The important point is that no matter  
what, the number of necessary comparisons is always vastly less than  
the number of cards.

Jess doesn't actually use a fully-sorted array for the agenda. It uses  
a "priority queue" (which you can Google to learn more about). A  
priority queue is a very clever data structure which (1) always knows  
which item is "first", (2) lets you insert new items quickly, and (3)  
lets you remove items quickly. So Jess always knows which activation  
is next to fire, but it doesn't need to have all the other ones sorted  
completely into firing order; they're only partially ordered. This  
keeps the number of comparisons to a minimum.

Now, to return to the point about the stable, transitive ordering:  
your compare() function doesn't behave that way, and that's bad  
because Jess assumes that it does. If we call that function with the  
same arguments again and again, we'll get different answers. That  
means it doesn't provide a random ordering, but rather *no* ordering.  
What you want is a function whose result for any two activations is  
unpredictable but stable and transitive. You could achieve this by  
creating a map of activation/Integer pairs. The first time compare()  
sees a given activation as an argument, it could generate a random  
number and store it in that map. Then the comparisons would just be  
comparing those random numbers from the map. By keeping the random  
numbers and reusing them for all comparisons, you'd achieve both  
necessary properties.

On Jun 5, 2011, at 7:03 AM, Rajcsányi Vilmos wrote:

> Hi!
>
> I would like to write a conflict resolution strategy that orders  
> (all) activations into a completely random order.
> I've written a simple class implementing the Strategy interface,  
> looks like this:
>
> public final class RandomActivation implements Strategy, Serializable
> {
>    private static final long serialVersionUID = 1L;
>    private static final String mName = "RandomActivation";
>    private final Random mGenerator;
>
>    public RandomActivation()
>    {
>        mGenerator = new Random();
>    }
>
>    public final int compare( final Activation pAct1, final  
> Activation pAct2 )
>    {
>        int result;
>
>        final double r1 = mGenerator.nextDouble();
>        final double r2 = mGenerator.nextDouble();
>
>        if ( r1 < r2 )
>        {
>            result = 1;
>        }
>        else if ( r1 > r2 )
>        {
>            result = -1;
>        }
>        else
>        {
>            result = 0;
>        }
>        return result;
>    }
>
>    public final String getName()
>    {
>        return mName;
>    }
> }
>
> (I don't know whether the random numbers are really necessary, as  
> I've read in a former message that returning 0 would
> result an indeterministic order of the activations, anyway my  
> problem has nothing to do with this.)
> I've noticed that this strategy doesn't behave as I have expected.
> I watched how many times the compare method was invoked after a new  
> activation was placed to the agenda,
> and I don't understand why there are such activations
> that aren't compared to every other activations. Isn't this the way  
> the conflict resolution should work?
> Compare every activations to every others?
> For example there was such activation that was compared to only one  
> other activation... Why is that?
> Or am I misunderstanding something? Please explain me how and how  
> many times
> the compare method should be invoked, and how can I reach a complete  
> random reordering of the agenda.
> Thanks.
>
>
> --------------------------------------------------------------------
> To unsubscribe, send the words 'unsubscribe jess-users  
> [hidden email]'
> in the BODY of a message to [hidden email], NOT to the list
> (use your own address!) List problems? Notify [hidden email]
> .
> --------------------------------------------------------------------

---------------------------------------------------------
Ernest Friedman-Hill
Informatics & Decision Sciences, Sandia National Laboratories
PO Box 969, MS 9012, Livermore, CA 94550
http://www.jessrules.com








--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users [hidden email]'
in the BODY of a message to [hidden email], NOT to the list
(use your own address!) List problems? Notify [hidden email].
--------------------------------------------------------------------

Reply | Threaded
Open this post in threaded view
|

Re: JESS: random strategy

Rajcsányi Vilmos
Thank you for the detailed answer! All clear now...

2011.06.05. 18:33 keltezéssel, Ernest Friedman-Hill írta:

> Lots of questions here, some explicit, some implicit. First I'll
> answer the one about why you saw an activation compared to only one
> other.
>
> Imagine you have a sorted partial deck of cards -- say you have a 5,
> 8, 10, Queen and King, in that order, top to bottom. The cards have
> the important property that they can be sorted into a definite order,
> and that order is stable. No matter how many times you check, the 8
> will always belong after the 5. Furthermore, it's a transitive
> relationship: if the 10 comes after the 8, and the 8 comes after the
> 5, then the 10 comes after the 5. Remember that -- we'll come back to
> it later.
>
> Now imagine you're picking up cards one at a time and inserting them
> into the correct place in the deck. If you pick up a 4, what would you
> do? You'd see the 5 on top, realize that it's larger than the 4, and
> lay the 4 on top. You've only compared the 4 to one other card.
>
> If you picked up a Jack, however, you might cut the deck in half and
> compare the card with the middle cards, searching around a little bit
> until you found the right spot. The important point is that no matter
> what, the number of necessary comparisons is always vastly less than
> the number of cards.
>
> Jess doesn't actually use a fully-sorted array for the agenda. It uses
> a "priority queue" (which you can Google to learn more about). A
> priority queue is a very clever data structure which (1) always knows
> which item is "first", (2) lets you insert new items quickly, and (3)
> lets you remove items quickly. So Jess always knows which activation
> is next to fire, but it doesn't need to have all the other ones sorted
> completely into firing order; they're only partially ordered. This
> keeps the number of comparisons to a minimum.
>
> Now, to return to the point about the stable, transitive ordering:
> your compare() function doesn't behave that way, and that's bad
> because Jess assumes that it does. If we call that function with the
> same arguments again and again, we'll get different answers. That
> means it doesn't provide a random ordering, but rather *no* ordering.
> What you want is a function whose result for any two activations is
> unpredictable but stable and transitive. You could achieve this by
> creating a map of activation/Integer pairs. The first time compare()
> sees a given activation as an argument, it could generate a random
> number and store it in that map. Then the comparisons would just be
> comparing those random numbers from the map. By keeping the random
> numbers and reusing them for all comparisons, you'd achieve both
> necessary properties.
>
> On Jun 5, 2011, at 7:03 AM, Rajcsányi Vilmos wrote:
>
>> Hi!
>>
>> I would like to write a conflict resolution strategy that orders
>> (all) activations into a completely random order.
>> I've written a simple class implementing the Strategy interface,
>> looks like this:
>>
>> public final class RandomActivation implements Strategy, Serializable
>> {
>>    private static final long serialVersionUID = 1L;
>>    private static final String mName = "RandomActivation";
>>    private final Random mGenerator;
>>
>>    public RandomActivation()
>>    {
>>        mGenerator = new Random();
>>    }
>>
>>    public final int compare( final Activation pAct1, final Activation
>> pAct2 )
>>    {
>>        int result;
>>
>>        final double r1 = mGenerator.nextDouble();
>>        final double r2 = mGenerator.nextDouble();
>>
>>        if ( r1 < r2 )
>>        {
>>            result = 1;
>>        }
>>        else if ( r1 > r2 )
>>        {
>>            result = -1;
>>        }
>>        else
>>        {
>>            result = 0;
>>        }
>>        return result;
>>    }
>>
>>    public final String getName()
>>    {
>>        return mName;
>>    }
>> }
>>
>> (I don't know whether the random numbers are really necessary, as
>> I've read in a former message that returning 0 would
>> result an indeterministic order of the activations, anyway my problem
>> has nothing to do with this.)
>> I've noticed that this strategy doesn't behave as I have expected.
>> I watched how many times the compare method was invoked after a new
>> activation was placed to the agenda,
>> and I don't understand why there are such activations
>> that aren't compared to every other activations. Isn't this the way
>> the conflict resolution should work?
>> Compare every activations to every others?
>> For example there was such activation that was compared to only one
>> other activation... Why is that?
>> Or am I misunderstanding something? Please explain me how and how
>> many times
>> the compare method should be invoked, and how can I reach a complete
>> random reordering of the agenda.
>> Thanks.
>>
>>
>> --------------------------------------------------------------------
>> To unsubscribe, send the words 'unsubscribe jess-users [hidden email]'
>> in the BODY of a message to [hidden email], NOT to the list
>> (use your own address!) List problems? Notify
>> [hidden email].
>> --------------------------------------------------------------------
>
> ---------------------------------------------------------
> Ernest Friedman-Hill
> Informatics & Decision Sciences, Sandia National Laboratories
> PO Box 969, MS 9012, Livermore, CA 94550
> http://www.jessrules.com
>
>
>
>
>
>
>
>
> --------------------------------------------------------------------
> To unsubscribe, send the words 'unsubscribe jess-users [hidden email]'
> in the BODY of a message to [hidden email], NOT to the list
> (use your own address!) List problems? Notify
> [hidden email].
> --------------------------------------------------------------------
>





--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users [hidden email]'
in the BODY of a message to [hidden email], NOT to the list
(use your own address!) List problems? Notify [hidden email].
--------------------------------------------------------------------