[alicebot-archcomm] [discuss] <shuffle>

[Conan Callen]

A couple questions:

Q. Does a real conversation last long enough to actually hit these
theoretical limits? What is the priority on something like this in a single
conversation, or what do bot masters see actually happening in the field?
Q. If the indexes are to be stored until the next time the client returns?


A variation on your algorithm:  Its farily simple to code and probably not
too bad in the worst case. I just typed it off the top of my head and
probably buggy, but I hope it demonstrates the general idea.


Step 1:
Create a copy of the index array
Shuffle the copy.
    Now you have the orginal array in the orginal order (A), and a shuffled
copy (A2).

Step 2:
SwapIndex = 0;

    // Starting from the end of A2 ( moving backward ) and the beginning of
A1 ( moving forward )
    //    Check to see the first X items of A2 ( n = 0 to X ) occurs in the
last X items of A1.
     // if (A2[n] occurs within the last X items of A1 ( A1[length of A1 -
X] ) )

ProximityFactor is passed in and is similar to the Proximity Repitition (or
even the same?)

int A2len = Length of A2;
int X = 0;
while (X < ProximityFactor)
{
    while (1)
    {
        if (A2[X] == ( A1[A2len - X] ) )
        {
                swap A2[n] with A2[length of A2 - SwapIndex]
                SwapIndex++
                Perform the same check on the new value of A2[n] (step 4)
        }
        else
            break;
    }
}







----- Original Message -----
From: "Christopher Fahey [askrom]" <askROM@graphpaper.com>
To: <alicebot-archcomm@list.alicebot.org>
Sent: Thursday, May 16, 2002 2:35 PM
Subject: RE: [alicebot-archcomm] [discuss] <shuffle>


> > 2. When the deck is shuffled, it is possible that the last
> > card will be the first card after the shuffle.
>
>
> I came up with a theoretical algorithm for this once back when I was
> designing computer games.
>
> There's another potential problem beyond avoiding the two-in-a-row
> repeating problem. Simply adding a rule saying "the first card after the
> shuffle cannot be the same as the last card before the shuffle" doesn't
> prevent the *second* card in the second shuffle from being a repeat of
> the last card in the first shuffle.
>
> In other words, you could have 26 options (lets say A-Z) and using a
> simple shuffle, you could end up with this sequence in the first
> shuffle:
>   a,e,r,u ... ,t,d,o,g
>
> Then, even with the "no two in a row" fix, you could end up with this in
> the second shuffle:
>   p,g,o,d ...
>
> So the user would see this sequence:
>   t,d,o,g,p,g,o,d
>
> The user sees the g, the o, and the d repeat themselve in pretty close
> proximity to each other. I call this "proximity repetition". And the
> "shuffle" and "no two in a row" rules arent enough to prevent proximity
> repetition.
>
> My algorithm allowed the randomness to be set using some more complex
> attributes. To put it into AIML terms, it would look like this:
>
>    <random type="shuffle" buffer="25%">
>
> The "buffer" attribute fills a little buffer of "forbidden" options.
> This buffer is not just the last one selected, it's several items long.
> It tells the randomness to disallow any repeats if the item was selected
> within the last 25% of the deck. So in a set of 26 options, only the
> first 19 (approximately 75% of 26) that were delivered to the user would
> be available for selection. This is in addition to the standard
> shuffling behavior - the first 26 hits would be the standard "show it &
> take out of the deck" shuffle method. The next 7 hits would be from the
> first 19 hits. The next 19 hits would be from whatever is leftover from
> the 26. Then the cycle repeats.
>
> This is super complex, but it allows the bot to more successfully avoid
> seeming to repeat itself.
>
> I wonder if there is some constant for the "buffer" attribute that would
> maximally ensure the least occurrence of proximity repetition. There
> could also be a more curved probability way of doing this - that the
> first items selected in the first round would be more likely to be
> picked the second time, while the last ones would be less likely, with a
> curve of probabilities between them. That would be fancy!
>
> -Cf
>
> [christopher eli fahey]
> art: http://www.graphpaper.com
> sci: http://www.askrom.com
> biz: http://www.behaviordesign.com
>
>
> _______________________________________________
> alicebot-archcomm mailing list
> alicebot-archcomm@list.alicebot.org
> http://list.alicebot.org/mailman/listinfo/alicebot-archcomm
>