[alicebot-archcomm] [discuss] <shuffle>

[Christopher Fahey [askrom]]

> 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