#114211 - keldon - Fri Jan 05, 2007 10:21 am
Reference
In short:
| Code: |
// how not to shuffle
for (i is 1 to n)
Swap i with random position between 1 and n |
| Code: |
// how to shuffle
for (k is 1 to n)
Swap kwith random position between k and n |
Notice that the first version selects a random number between 1 and n, the second between k and n. The former will produce uneven odds of some combinations, even with n as low as 3!
#114216 - sgeos - Fri Jan 05, 2007 12:01 pm
I always use this. It might be improveable.
| Code: |
void shuffle(type_t *pObject, int pSize)
{
type_t *a;
type_t *b;
int index;
int i;
for (i = 0; i < pSize; i++)
{
index = rng(0, pSize - 1);
a = &pObject[i];
b = &pObject[index];
swapObjects(a, b);
}
} |
EDIT: After working through the exercise, it is evident that this is the bad shuffle algorithm. index should be calculated as such:
| Code: |
| index = rng(i, pSize - 1); |
The loop only needs to work through (pSize - 1) because swapping that item with itself would be silly. That makes the good shuffle algorithm one iteration shorter.
| Code: |
| for (i = 0; i < pSize - 1; i++) |
Neat find!
-Brendan
#114246 - Miked0801 - Fri Jan 05, 2007 8:12 pm
I just realized that in all my years of game coding, I have never created a card game nor a shuffle program. I may have to do one now in my spare time for fun :)
#114265 - sgeos - Fri Jan 05, 2007 11:49 pm
Go for it!
I've never created a card game, but I use shuffle algorithms all the time. They are a good way to mix things up and make games more interesting.
-Brendan
#114271 - keldon - Sat Jan 06, 2007 12:56 am
Yes! Ever felt like you were being fed blocks from a finite list in tetris? I've always been convinced that there are many combinations that appear regularly on the gameboy from the beginning and it is so distinct that you can't help but recognize it.
Poker would be an interesting one; simple to make and you can have fun with making the AI, and trying to beat it.
EDIT: on second thoughts I suggest trying something less addictive ^-^
#114277 - sgeos - Sat Jan 06, 2007 4:47 am
Shuffle can be used for a lot of things. You could place power up spawn points on a map and then shuffle the power ups every time the player enters the map. I'd put more power ups in the list than points on the map. This way certain things just won't show up. Admittedly you could just spawn power ups from a probability. (The consequences of each should be obvious.)
This is similar, but you could create a list of enemy spawn data. Shuffle the list, pull the top X entries when the player enters the map, and then spawn them. X could be difficulty level specific. (You could change the difficulty as the player progresses if you don't want to bother with options.)
I guess I shuffle more often than I pull from probability lists, but I do both. Both work. My point is that shuffling isn't limited to cards.
-Brendan
#114292 - keldon - Sat Jan 06, 2007 10:11 am
I quite like the 'random generator bag' concept for a random selection. You would think that the sequences don't seem random, but put it into your tetris clone and see how much more random it feels.
#114294 - sgeos - Sat Jan 06, 2007 11:05 am
| keldon wrote: |
| I quite like the 'random generator bag' concept for a random selection. You would think that the sequences don't seem random, but put it into your tetris clone and see how much more random it feels. |
That's how I program. I know the results are random and they work quite well. With a normal "bag", you will note that the same shape will never show up more than twice in a row. You might consider a bag with two or three of each shape. Try a bag with two of each shape and one random shape (choose the random shape before shuffling). Try a bag with two of each shape, but only pull half of the shapes (this actually won't work as well, but you can try it). If you want to go crazy, allow the player to set the amount of each shape that goes into the bag.
-Brendan
#114325 - tepples - Sat Jan 06, 2007 6:22 pm
Shuffle theory is interesting. In fact, Lardarse and I are working on a language to express various shuffle behaviors.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#114523 - Miked0801 - Mon Jan 08, 2007 7:33 pm
Ok, that jogged a memory. I did create a baseball schedule creator routine (Crushed Baseball, all skews) that was a glorified shuffle routine.
Take X games for division opponents, Y games for league, Z games for inter-league. Shuffle and draw game types (with inter-league being in 2 groups.) Place in groups of 2-5 game series and go :)
#114527 - sirpoonga - Mon Jan 08, 2007 7:56 pm
Interesting read.
I think decks should run through the algorithm twice though. Once going forward through the array, and once going backwards.
One thing about the second algorithm. Assuming most programs that deck[0] is an ace there is a good chance the first card dealt is not that particular ace.
#114529 - keldon - Mon Jan 08, 2007 8:29 pm
There is still a 1/52 chance that the first card is an ace of spades, which is the probability you want.
#114545 - sirpoonga - Mon Jan 08, 2007 10:38 pm
| keldon wrote: |
| There is still a 1/52 chance that the first card is an ace of spades, which is the probability you want. |
That's true. However, the problem is not the chance of what that card is, but the chance of what it isn't and probability that the card changed positions. While you want that first card to be 1/52 chance of being a particular card, you want a 50% chance that it was switched so people are unsure of what that position in the deck is (or isn't in this case)
The key to the problem is we know how the cards started before the shuffling routine. Most programmers will initialize the deck as A-K for each suit because it is easy to take the array index and mod by 13 to get the card value, divide by 13 to get the suit. It's unknown in what order the suits are though.
Since we know that first card started as an ace and there is a high chance it switched you have a high chance the first person doesn't have an ace. It isn't that there is a 1/52 chance it is an ace, it's the 48/52 chance that it was swapped with something that wasn't an ace. Since you know what that top card started as it affects what happens after the shuffle.
How about we scale this down to 3 cards and work our way up to 52. This was explained on the tv show Numb3rs. The choose a door game. You have three doors, behind one is a prize, behind the other two is nothing. You choose a door. Then one of the other doors that doesn't have a prize is taken away. Do you keep your current door or switch to the other door? What's the odds on the second pick that you choose the right door? Most people will answer you have a 50% chance on the second choice, but that is incorrect.
Those are misleading questions, the question you need to answer is what are the odds you didn't pick the right door on your first turn? The odds you picked the wrong door 2/3. That means it is more likely one of the other doors is the right door. So when one is taken away there is a 2/3rds chance the other door is the right one.
I know someone that question that and I made a computer program that proved it for him. I made a program that randomly put a prize behind a door (three buttons). Told told him to switch every time. The computer would keep track of wins. After about 100 games he had 68 wins. I then modified the program to simulate the choices. After 10,000 iterations it was very close to 66%.
Now, let's change this situation to fit a shuffled deck. In my program I randomly choose a door to put the prize. What if instead of randomly picking a door I started out with the first door has the prize and we shuffle the doors. If the contestant didn't know the shuffling routine there wouldn't be a problem. But let's say the contestant searched the internet and found out someone leaked the shuffling routine. On your first choice, would you choose something other than the first door? You know the first door started with the prize and it most likely switched. There's still a 33% chance the first door is right. That's a pretty high chance for most people.
Let's scale it to 52. Let's say there is only 1 prize behind 52 doors, it started out at door 1 but was shuffled. Then you are asked what door to choose. Then one of the other doors that doesn't have the prize is taken away. You are asked if you want to switch. The process is repeated until one door is left. Why would you not choose that first door as your first choice? You see, the key is knowing the state before the shuffle.
Depending on the card game, that could be important. If you were playing blackjack you know there is a high chance the first card dealt isn't an ace. That's an important card in blackjack. Granted it is most likely to not be an ace with any shuffling routine. But based on the door example you know that if you know the starting condition you have an edge over people that don't.
So the solution it to shuffle more than once, forward and backward through the array. The even distribution still remains. If your algorithm for one shuffle evenly distributes it will do multiple shuffles evenly. So if you shuffle more than once it is more uncertain if that first card will not be that ace as there were chances it could have been put back into that position.
The reason you go forward and backwards is if you only shuffle once forward, the first position will only be switched once. If you shuffle twice forward, it will only be switched twice. Now think of the last position if you go forward. There's 52 chances that it switched, that's more than the 1 chance at the beginning. First iteration the last card has a 1/52 chance of switching. Next iteration it has is a 1/51, and so forth until you get to 1/2. So, after the first iteration most likely the last card wasn't switched. After the second iteration even though the odds of it being switch go up it is still most likely to not be switched. This trend happens until it get to the 1/2 chance. The it is a toss up.
That mean that the first card has most likely changed while the last card is pretty much a toss up. You want that for both ends of the array, that it is a toss up if it changed. Hence why you shuffle forward and backwards at least once.
I think, when I was in college, we mathematically proved that if you shuffle a deck 4 times you get the best distribution. So going through forward, then backward, then forward, than backward should give you the best distribution along with less predictable odds.
That shouldn't take up much processing.
If you wanted to only do one shuffle then the deck will have to start out shuffled. The best way to do that is on program init create list of cards (a list, not an array). Set deck array index to 0. Randomly pick a card from the list and put it into the deck array. Increment deck array index. Keep doing this until you run out of cards in the list.
If that process is fast enough that would be a better shuffle routine than swapping. However, it takes up more memory.
If you didn't want to use a list (<vector> in c++) you can do it with an array. Have an array of you cards along with a cardcount variable. Set cardcount to 51. Get a random number from 0-51 and put it in randnum variable. Put that card into the deck array. Starting from randnum, goto cardcount-1 putting the next card in the current spot. Decrement cardcount by 1. Then when you are done you can reclaim the memory of that list and use the other shuffle routine from then on.
#114548 - keldon - Mon Jan 08, 2007 10:51 pm
You really need to think about the statistics that you need to be concerned with. Every card must have an equal chance of being at any position in the deck. If there is a 50/50 chance of an ace being the first card then that goes against the odds.
Look at it from another angle, if I picked a number between 1 and 52 what would it be? You propose that 1 should have a higher chance.
The chance it is not is the inverse probability of the chance that it is. You really need to think about this one again; you definately want that probability that there is 51/52 chance of the card not being an ace, or any other card for that matter. Trust me you definately want those odds.
In fact if you really shuffled a deck 1'000'000 times you would have the same chance as getting an ace as if you shuffled it once! When we shuffle real cards we often do not shuffle cards the cards properly. I think that the best shuffle that randomizes the order is when you lay all of the cards out on the table and shuffle them by sliding the cards over each other. The split/merge type shuffle actually keeps the top cards near the top near the top after the shuffle. The cards nearest to the middle get moved the most!
#114554 - sirpoonga - Mon Jan 08, 2007 11:44 pm
| keldon wrote: |
| You really need to think about the statistics that you need to be concerned with. Every card must have an equal chance of being at any position in the deck. If there is a 50/50 chance of an ace being the first card then that goes against the odds. |
Sorry, I worded it incorrectly. As you said, you need an even chance at all positions for it to be a particular card. That's what I meant by 50/50. But, in reality, there needs to be a 1/52 chance for EACH position.
Crap, when I was doing my calcs I had an off by one error. Yeah, all positions have a 1/52 chance with that second algorithm.
The choose a door thing still works though :)
#114555 - Miked0801 - Mon Jan 08, 2007 11:53 pm
BTW, there are whole books devoted to 'shuffle tracking' in blackjack. Basically, you watch the deck to see where a group of aces are and bet higher when they are about to appear as the odds of a black increase.
#114561 - sirpoonga - Tue Jan 09, 2007 12:04 am
Heh, I looked over my post again. Doh, I realize the error in my ways. LOOOOONG day at work. Sorry about that.
#114617 - sgeos - Tue Jan 09, 2007 4:04 pm
The notion of a language to express shuffle behaviors amuses me somehow. Why not make it a little more general? Or is it? I only glanced at the page, but it appears to be tetris specific.
-Brendan
#114795 - tepples - Wed Jan 10, 2007 8:48 pm
| sgeos wrote: |
The notion of a language to express shuffle behaviors amuses me somehow. Why not make it a little more general? Or is it? I only glanced at the page, but it appears to be tetris specific. |
By no means is it just for Tetris. The examples are Tetris-specific because it's posted on a Tetris-related wiki, but if you replace I,J,L,O,S,T,Z with S9,S10,SJ,SQ,SK,SA,D9,D10,DJ,... you have a shuffler for euchre.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#114907 - keldon - Thu Jan 11, 2007 2:07 pm
Music playlists! Never even thought about that until I was just playing a collection of music I made on shuffle, and then it occured to me that the 'shuffle' feature actually did 'shuffle' the songs!
#114926 - tepples - Thu Jan 11, 2007 6:44 pm
Except does your favorite music player's shuffle mode operate on "bag" or "history" basis?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#114978 - sgeos - Fri Jan 12, 2007 12:35 am
| tepples wrote: |
| Except does your favorite music player's shuffle mode operate on "bag" or "history" basis? |
As far as I can tell, winamp uses random(1, numSongs). "Bag" would be much better.
-Brendan
#115004 - APL - Fri Jan 12, 2007 3:45 am
For me, by far the most eye-opening part of the article linked in the original post was this passage here :
| Quote: |
| Recall that in a real deck of cards, there are 52! (approximately 2^226) possible unique shuffles. Also recall that the seed for a 32-bit random number generator must be a 32-bit number, meaning that there are just over 4 billion possible seeds. Since the deck is reinitialized and the generator re-seeded before each shuffle, only 4 billion possible shuffles can result from this algorithm. Four billion possible shuffles is alarmingly less than 52!. |
This means that if you only seed your random number generator at the start of the shuffle then you've got a severely limited number of possible decks.
(Sure, after each call to rand() (or whatever) it reseeds itself, but that seed is deterministically based on the previous seed, so the entire shuffle, taken as a whole, only gets one seed.)
Assume you're using an unsigned 32bit number as your random seed then at the very least you're going to need a new random seed after the first 5 calls to rand(). (52!/46! breaks 32bits.) And then again after your second five calls to rand(). (46!/40! breaks 32bits.) At that point you might as well standardize on a fresh seed for every five cards.
This is particularly a problem when programming on a system like the GBA where getting a truly random seed is difficult. Sure, no one is going to be using complicated mathematics to break the statistics in a GBA game, but since the vast majority of decks (and therefore some number of hands) will never appear players may notice this problem over time. Especially if one of the impossible hands is a recognizably good one.
I've never written a card-game before, but I'm not entirely sure this problem would have occurred to me. Now, if I were to write a card game program, I think I'd have to write a pseudo-random number generator that uses 64bit seeds. And then come up with a way of generating seeds that are truly 64bit. (Perhaps by concatenating a number of 8 bit values, and perhaps caching seeds until they are needed.)
_________________
-Andy L
http://www.depthchasers.com
#115036 - sgeos - Fri Jan 12, 2007 11:58 am
| APL wrote: |
| Now, if I were to write a card game program, I think I'd have to write a pseudo-random number generator that uses 64bit seeds. |
More than one commercial game uses the mersenne twister.
If you'd perfer a LCG, 0x100000DCD (4294970829) will work well as a multiplier, IIRC. Maybe. =P
| Code: |
| seed64bit = seed64bit * 0x100000DCD + 1; |
-Brendan
#115106 - tepples - Sat Jan 13, 2007 12:53 am
| sgeos wrote: |
| APL wrote: | | Now, if I were to write a card game program, I think I'd have to write a pseudo-random number generator that uses 64bit seeds. |
More than one commercial game uses the mersenne twister. |
Doesn't Mersenne Twister have a significant CPU pause at certain points in the sequence? Perhaps that wouldn't matter for card games, but it does matter for action games.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#115154 - sgeos - Sat Jan 13, 2007 9:16 am
| tepples wrote: |
| Doesn't Mersenne Twister have a significant CPU pause at certain points in the sequence? |
Supposedly it's faster than a LCG that doesn't use an implicit modulus (the word size).
| tepples wrote: |
| Perhaps that wouldn't matter for card games, but it does matter for action games. |
Not at all. How often do you use your RNG in an action game? Do you call it every frame in an action game? Multiple times a frame, every frame? If so I'd like to know what you are doing. I have not noticed any problems.
-Brendan
#115181 - Optihut - Sat Jan 13, 2007 3:30 pm
As per this thread I would use something similar to the entropy gatherer to avoid the problem of having so-and-so many possible combinations, but only a limited number of random number seeds.
#115247 - APL - Sun Jan 14, 2007 4:01 am
So, for a theoretical mathematically perfect card game you'd keep some sort of buffer of known entropy and use to generate your random numbers?
I assume you mean either by hashing them or by using them to seed a standard generator.
I follow that, as far as it goes. But where are you going to get a source for the entropy on a portable system? In theory You're going to need 226bits of random data (Just over 28 bytes) to properly perfectly randomize a deck of cards*. And that's the theoretical best answer. I'm not 100% sure off the top of my head how best to apply those bits.
Where do you get the data to fill up your entropy pool? I suppose on the DS you could just keep polling the microphone and take the least significant bit. (possibly with skew correction added in.) That's probably pretty random.
I realize this is an overkill for virtually any game that you're not going to gamble on. But it's still an interesting question.
-Andy
* According to the Counting Argument, there must be at least as many variations in the source data as in the output data. 226 is the first whole number that satisfies this. 52! <= 2^226
_________________
-Andy L
http://www.depthchasers.com
#116943 - Lardarse - Wed Jan 31, 2007 5:02 am
| sgeos wrote: |
| tepples wrote: | | Perhaps that wouldn't matter for card games, but it does matter for action games. |
Not at all. How often do you use your RNG in an action game? Do you call it every frame in an action game? Multiple times a frame, every frame? If so I'd like to know what you are doing. I have not noticed any problems. |
How about 2 random numbers per shotgun pellet?
#116948 - tepples - Wed Jan 31, 2007 6:44 am
| sgeos wrote: |
| tepples wrote: | | Doesn't Mersenne Twister have a significant CPU pause at certain points in the sequence? |
Supposedly it's faster than a LCG that doesn't use an implicit modulus (the word size).
| tepples wrote: | | Perhaps that wouldn't matter for card games, but it does matter for action games. |
Not at all. How often do you use your RNG in an action game? Do you call it every frame in an action game? Multiple times a frame, every frame? If so I'd like to know what you are doing. I have not noticed any problems. |
True, Mersenne Twister is faster on average (amortized) than many other algorithms, but real-time programming is about worst case timing, not amortized timing. If you happen to pull the last pseudorandom number in this part of the sequence so that MT has to do another big iteration, and this iteration introduces a pause, then you've just violated the real-time constraint. Algorithms where every call takes about the same number of cycles are preferable in a real-time environment such as a video game.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#116963 - keldon - Wed Jan 31, 2007 12:05 pm
How about doing a part of the iteration each frame.
#116998 - sgeos - Wed Jan 31, 2007 6:33 pm
If you skip a frame every now and then, I'm not convinced that it is a big deal. Chances are, nothing will happen. If something does happen, and unreproduceable bug will be in your database. The bug will be marked as "could not reproduce", the game will ship, and it will affect very few users. I can't see a mersenne twister hiccup causing data corruption or anything like that. If this were a pacemaker, things would be different.
-Brendan
#117018 - keldon - Wed Jan 31, 2007 8:19 pm
A pace maker with a random number generator!!! Sounds like a setup line for a Mitch Hedberg joke. Well there is an application for it, if your pacemaker could join with a network (for whatever reason) you would need a random number generator to allow multiple devices to negotiate who can send first.
#117022 - sgeos - Wed Jan 31, 2007 8:47 pm
Wow, I missed that. My point was that upredictable timing hiccups in a game often are not a big deal. In a medical device, they probably are. Then again, I don't know if a one frame delay every now and then would kill a person.
-Brendan
#117029 - tepples - Wed Jan 31, 2007 9:52 pm
| keldon wrote: |
| A pace maker with a random number generator!!! Sounds like a setup line for a Mitch Hedberg joke. |
That, or it has a 1-bit DAC and it needs a random stream to dither the signal going into the electrodes.
| sgeos wrote: |
| My point was that upredictable timing hiccups in a game often are not a big deal. |
Until they start causing your networked (GBA Game Link, DS Ni-Fi, or DS WFC) game to fall out of sync.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#117034 - sgeos - Wed Jan 31, 2007 10:03 pm
| tepples wrote: |
| sgeos wrote: | | My point was that upredictable timing hiccups in a game often are not a big deal. |
Until they start causing your networked (GBA Game Link, DS Ni-Fi, or DS WFC) game to fall out of sync. |
If the network is in sync, shouldn't they all hiccup at the same time? That is a good point.
-Brendan