Shuffle algorithm?

[Programmer]

Hi Edward,

It is very interesting when you look at a question like this and see it in two different ways, like we are doing, and both ways seem to make sense while apparently contradicting each other. Aren't paradoxes fun!

When you look at the maths involved in shuffling, you can see that in, let's say, six shuffles you can arrive at every possible deck. Assume the maths is good. The maths assumes that it can be any dealer, on any occasion, with any deck. Physics intervenes because when you talk about a specific dealer, on a specific day and even a specific tick, with a given deck, you will never be able to be able to get that number of outcomes.

If you give the Orphalese Tarot the same benefit of the doubt, that it might be running on any machine, at any time, anywhere in the world, then obviously it can reach any possible deck too - on the first shuffle. But of course it is the second shuffle that you are worried about!

How about I build the following feature into the next beta? There is a button on the utilities part of the Options form which says "New Random Deck". This gives you a new deck, based on stored data from mouse movements. Because it is a new deck it is actually very easy to capture that data and have it handy at any given time - you only need 78 numbers.

The "MouseMove" event fires very frequently. I am not sure off the top of my head how many pixels the mouse has to move in order to fire the event, I suspect that it's as little as one. Obviously how often Windows looks to see whether the mouse has moved is a question of processor speed, but I know from having used this event that if you stored the decimal value of the last two digits of, say, the X co-ordinate, and appended them to an array, you would have a new array of 78 digits in a couple of seconds.

Any number higher than the number of cards in the current deck would simply not get stored. New numbers could just be pushed in at the top and old ones go out the bottom. Actually there is a "stack" class in .NET which would be very nice for this, the code would be a no-brainer.

After creating a new deck the button would be temporarily disabled until the user has generated a little bit more "entropy". They could be shown a helpful graphic of a battery recharging or something. All with no shuffling involved - what we might call a workaround.

What are you thoughts about this?

Cheers
Richard

[Edward Faith]

Hi Richard,

If you give the Orphalese Tarot the same benefit of the doubt, that it might be running on any machine, at any time, anywhere in the world, then obviously it can reach any possible deck too - on the first shuffle.

If we're talking about a copy of Orphalese that has already been used a lot and that hasn't had its deck re-sorted in a good while, then I agree, because multiple shuffles have a powerful compounding effect on their ability to randomize (but your next deck will still be mathematically related to your last deck - to put it roughly, the next deck could be anything for the simple reason that the last deck could have been anything). But if we're talking about a just-downloaded copy of Orphalese, or a copy in which the user is about to shuffle a sorted deck, then we have to keep in mind that, unlike people, the copies of Orphalese are all identical twins - in fact, they're so identical that they make human identical twins look like completely unrelated people. Every copy of Orphalese with a sorted deck, will, universally, for everyone, be limited to the same minuscule fraction of possible shuffles, a fraction which with some work you or I could identify ahead of time, purely based the algorithm and the number of ticks possible in a modern computer in the first X minutes of program use. While X can vary, it is at any moment still bounded by however old Orphalese is.

How about I build the following feature into the next beta? There is a button on the utilities part of the Options form which says "New Random Deck". This gives you a new deck, based on stored data from mouse movements. Because it is a new deck it is actually very easy to capture that data and have it handy at any given time - you only need 78 numbers.

I think that would be fantastic.

A technical issue: you need to make sure that in your list of numbers there are no repeats, because you can't have two cards in the same location in the deck. The direct way, of course, is to compare each new number that comes in with all the previous numbers. As you get close to gathering all 78 numbers it becomes more and more rare to find a new number that is not a repeat. There are less computationally intensive ways to achieve the same effect but they are not as easy to program.

Edward

[Programmer]

Hi Edward,

I take your point about different copies of the program being like identical twins. I also found this blog http://www.codinghorror.com/blog/archives/000728.html which goes into a bit more depth of about how the .NET classes actually produce the numbers they do. The strongest one is obviously that one in the Cryptography namespace which self seeds using a number derived from:

The current process ID
The current thread ID
The tick count since boot time
The current time
Various high precision CPU performance counters
An MD4 hash of the user's environment (username, computer name, search path, etc)

In the sense of having every copy of the program behave in a unique way this would obviously be better than the class the program uses at the moment. It produces its own seed value internally so you can't actually give it one of your own, but I thought I could use this to generate the seed for the other random class. e.g. the user types in "what shall I do today?" and then the program uses this, plus the cryptography RNG output, to create a new seed (first letter is added, second letter is multiplied or whatever), which could then be given to the other Random class to create the deck. Of course, the problem still remains that the total number of possible first decks is limited by the upper value of a 32 bit signed integer. For a regular "non seeded" shuffle I could just use the cryptography version of the class directly. I suspect this uses long (64 bit) integers internally.

The writer also gives a link to this book http://www.amazon.com/exec/obidos/ASIN/ ... ghorror-20 which looks at the actual algorithms that these classes use internally. I know it would be beyond me but I thought you or anyone else who is following this thread might be interested.

I have been thinking a bit more about the practicalities of the "new deck" button too. As you point out, as you get closer to a full deck you end up discarding more numbers (I want to stick to using whole numbers to avoid any rounding issues and keep it a simple minded as possible), so it might take a little longer than I said to generate a full deck. The obvious answer will be to let the user store up two or three decks as they go. That way when they are using one deck they can be charging up the next one and so on.

Cheers
Richard

[Edward Faith]

Hi Richard,

That page that you found is a goldmine. It opens up the whole thing. I have the book which it refers to so I'll look it up. The plots of even the weaker randomizer in action are pretty impressive (though not unexpected - it's just reassuring to see it in action graphically).

Thanks! I'm looking forward to any changes you make. No rush - as things stand I have a good feel now for how to use the software "as is".

Edward

[Programmer]

Hi Edward,

I just posted various new threads about the new Version 8.4 beta release, one of which was about the changes to the shuffle algorithm and the new mouse capture based RNG. I am sure you will be interested in how I have implemented this and might like to suggest some improvements, so here goes:

1) The normal shuffle just uses the Cryptography RNGCryptoServiceProvider class instead of the System.Random class. This is straightforward because it self-seeds.

The shuffle is based on choosing two cards and swapping them. The RNGCryptoServiceProvider returns a number from 0 to 255, so the shuffles does 1000 swaps where each position is NewRandomNumber % 78.

2) The seeded shuffle now looks like this:

int iVal = 0;
int iSeed = (int)DateTime.Now.Ticks;

char[] charArray = sWhatTheUserTypes.ToCharArray();

for (int i = 0; i < charArray.Length; i++)
{
iVal = (int)charArray;
iSeed += iVal;
iSeed *= NewRandomNumber;
}

Shuffle(iSeed);

...The Shuffle function is as before, based on System.Random. It is only the seed generation method that has changed. I can't really do a lot about that, because I need a function that takes a seed in order to maintain the functionality of the program.

The eventual seed is always going to be a number between - 2,147,483,648 and + 2,147,483,648. Obviously that doesn't cover every possible deck so the user might want to do two or three or more shuffles if they want to get closer to that assurance. As we have already said, the number of possible outcomes increases geometrically the more times you shuffle.

3) The mouse capture takes the X co-ordinate and divides it by the Y co-ordinate. Then it takes the 13th and 14th significant figures, which is the limit of what the decimal datatype goes to, and stores that in the array. The array goes up to 99 in order to handle slightly larger decks. I still have to take care of the eventuality where the deck is 100+ cards, such as tell the user that the function is not available.

Double db = Math.Abs((float)MouseX / (float)MouseY);
String s = db.ToString("0.00000000000000", CultureInfo.InvariantCulture);
int iX = Convert.ToInt32(s.Substring(s.Length - 2));

This might be a bit simplistic. I haven't been able to find any source code for doing this, so please feel free to suggest any improvements.