Fw: [alicebot-archcomm] [discuss] <shuffle>

[Conan Callen]

A small optimization on this algorithm would be that it would only be
required to keep last X elements of the orginal index array. For instance,
if you didnt want an element to repeat itself for at least 3 elements or the
length of the list (what ever is shorter). Then you only need to test
against the last 3 items in the pervious permutation.

If you need to cache the these indexes, you only need to cache the last 3
indexes of just those random templates index arrays that were actually put
into production. It may require a different algorithm to reconstruct the
indexes when the user returns in the future. Although the actual strings
refered to by the saved indexs may been changed (added, deleted or update)
by the bot master. Caching involves many problems to solve.

Conan


> 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
> >
>