 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
Jani
Grandmaster Cheater
![]() Reputation: 2
Joined: 29 Dec 2006
Posts: 804
|
 Posted: Fri Jul 18, 2008 8:14 pm Post subject: Shuffling a deck. |
 |
|
Let's say I've 52 cards pushed into a vector. I'd like to shuffle it so, all the combinations are possible. Since 52! is about 8e+67, a (long) int can't handle it, so using ::srand and ::rand fail. Any ideas to shuffle the deck properly? Random times std::random_shuffle()'s or? Will it produce all the possible combinations? I guess I've been on "vacation" for too long, because my math fails here. So.. It would take at least | Code: | 52! < timesToShuffle*ULONG_MAX
timesToShuffle > 52!/ULONG_MAX
timesToShuffle > 2e+58 |
? And this isn't very wise on todays computers. Any better ideas? :>
Also, if I have N decks in the shoe, how many times I need to call std::random_shuffle() at least to get the combinations? Is this in equation true: (52*N)! < timesToShuffle*ULONG_MAX? Well.. It's if the in equation in the first paragraph is, Iono, so you tell me. :P
|
|
| Back to top |
|
 |
Flyte
Peanuts!!!!
 Reputation: 6
Joined: 19 Apr 2006
Posts: 1887
Location: Canada
|
| Posted: Fri Jul 18, 2008 9:44 pm Post subject: |
|
|
| Code: | double random = ::time(0);
::srand(::time(0));
for(int i = 0; i < 20; i++, ::srand(::time(0))) random*=::rand(); |
Should suffice, it's rather hackish though.
Edit: Should point out it can generate any number between 0 and RAND_MAX^20*::time(0);
|
|
| Back to top |
|
|
HalfPrime
Grandmaster Cheater
![]() Reputation: 0
Joined: 12 Mar 2008
Posts: 532
Location: Right there...On your monitor
|
| Posted: Fri Jul 18, 2008 10:08 pm Post subject: |
|
|
You want to make a case for each possible outcome? Why not just make a new vector and randomly put cards into it or something?
_________________
|
|
| Back to top |
|
|
Jani
Grandmaster Cheater
![]() Reputation: 2
Joined: 29 Dec 2006
Posts: 804
|
| Posted: Sat Jul 19, 2008 1:49 am Post subject: |
|
|
| Flyte wrote: | | Edit: Should point out it can generate any number between 0 and RAND_MAX^20*::time(0); |
Hmm.. I'll do some math after breakfast, etc.
| HalfPrime wrote: | | You want to make a case for each possible outcome? |
No. I just want this card game to be totally "random", so any hand can be dealt. Now, there's only ULONG_MAX different decks, whereas in real life there are 52! different decks. I mean ULONG_MAX and 52! different orders for the cards in the deck.
| HalfPrime wrote: | | Why not just make a new vector and randomly put cards into it or something? |
That's what I'm doing, but since int is limiting the order, I need a better way to do this. If you do that with basic std::random_shuffle() (ie. ::rand()), you'll have _only_ ULONG_MAX differently ordered decks. Try implementing your idea (try printing all the combinations) and you'll notice that you'll be missing many many combinations.
EDIT: If anyone is interested: http://www.secureprogramming.com/?action=view&feature=recipes&recipeid=23 So.. I guess I'll be adding a random value to the card class and then just sort the vector according to the random numbers.
Well.. Now I need to find a common library with strong PRNG. A portable one. Suggestions?
|
|
| Back to top |
|
|
HalfPrime
Grandmaster Cheater
![]() Reputation: 0
Joined: 12 Mar 2008
Posts: 532
Location: Right there...On your monitor
|
| Posted: Sat Jul 19, 2008 8:34 am Post subject: |
|
|
| Code: | int ischosen[52] = 0;
Card shuffled[52] = null;
int radnom;
for(int c=0;c<52;c+++){
random = rand()%52;
if(ischosen[random] == 0){
ischosen = 1;
shuffled[c] = Deck[random];}
} |
Something like this seems like it should work to me. I'm definitely not understanding what you're trying to accomplish.
_________________
|
|
| Back to top |
|
|
4ng3licDew
Cheater
![]() Reputation: 0
Joined: 14 Feb 2008
Posts: 28
|
| Posted: Sat Jul 19, 2008 9:54 am Post subject: |
|
|
@Jani, thanks for the link to the cards shuffle algorithm.
About pseudorandom number generator, check out this link:
http://en.wikipedia.org/wiki/Pseudorandom_number_generator
I would recommend the Mersenne twister PRNG.
A while back, I coded a simple Black Jack card game in vb .NET using visual studio 2003. My algorithm for shuffle a deck of 52 cards is:
1) to have 2 vectors. The first vector has the 52 cards. The second vector is empty.
2) I have a for loop that goes from 1 to 52.
For each iteration I randomly select a card from vector 1, remove the selected card from vector 1 and add that card to vector 2.
For example:
In the first iteration I would have to pick a random number between 1 and 52. I use this number to select the card from vector 1. Then I remove this card from vector 1 (vector 1 now only has 51 elements) and add it to vector 2 (vector 2 now has 1 element).
In the second iteration I would have to pick a random number between 1 and 51. I use this number to select the card from vector 1. Then I remove this card from vector 1 (vector 1 now only has 50 elements) and add it to vector 2 (vector 2 now has 2 elements).
In the third iteration I would have to pick a random number between 1 and 50. I use this number to select the card from vector 1. Then I remove this card from vector 1 (vector 1 now only has 49 elements) and add it to vector 2 (vector 2 now has 3 elements).
etc.
I have attacked the source vb .Net source code in this reply.
|
|
| Back to top |
|
|
samuri25404
Grandmaster Cheater
 Reputation: 7
Joined: 04 May 2007
Posts: 955
Location: Why do you care?
|
| Posted: Sat Jul 19, 2008 10:42 am Post subject: |
|
|
Here's an old card shuffler that I'd written, for a purpose similar to that of AngelicDew's.
| Code: |
Card Tmp = null;
Random rnd = new Random(); //equivalent of srand( time( NULL ) ) //or whatever
for (int i = Shuffled.Cards.Count -1, j; i > 0; i--)
{
j = rnd.Next(0, i - 1); //equivalent of rand()
//swap cards[i] and cards[j]
Tmp = Shuffled.Cards[i];
Shuffled.Cards[i] = Shuffled.Cards[j];
Shuffled.Cards[j] = Tmp;
}
|
_________________
|
|
| Back to top |
|
|
Jani
Grandmaster Cheater
![]() Reputation: 2
Joined: 29 Dec 2006
Posts: 804
|
| Posted: Sun Jul 20, 2008 7:08 am Post subject: |
|
|
| HalfPrime wrote: | | I'm definitely not understanding what you're trying to accomplish. |
I can see that. It's not about how to shuffle a deck, but how to shuffle it properly, so all the (52*N)! combinations are possible. And the original problem was that ::rand() isn't returning enough unique random numbers ( only ULONG_MAX, whereas it's << than (52*N)! ). Btw.. Guess your code doesn't even compile :)
| 4ng3licDew wrote: | 1) to have 2 vectors. The first vector has the 52 cards. The second vector is empty.
2) I have a for loop that goes from 1 to 52.
For each iteration I randomly select a card from vector 1, remove the selected card from vector 1 and add that card to vector 2. |
Yehs, someone else suggested this method too, but I found something (which I can't remember anymore) not fitting my requirements. Saturday evening/night was kinda good reset for my brains :P
| 4ng3licDew wrote: | | I have attacked the source vb .Net source code in this reply. |
:P Sorry, but I can't bother trying to read VB.
Anyway.. My current code, still with ::rand() tho: | Code: |
class Card {
public:
// Used with std::sort. Sorts cards by m_rand
bool operator< (Card card) { return (this->m_rand<card.getRand()); }
// Used with std::unique. Compares cards by m_rand
bool operator==(Card card) { return (this->m_rand==card.getRand()); }
}
class Deck {
private:
std::vector<Card> m_cards;
...
}
Deck::Deck(unsigned int NumberOfDecks) {
// Init the random number generator, shuffle will use this.
::srand( time(NULL) );
for(int i=0; i<NumberOfDecks; ++i) // Decks
for(int j=0; j<52; ++j) // Cards in decks
this->m_cards.push_back( Card(j, ::rand()) );
// Shuffle the deck.
this->shuffle();
...
}
bool Deck::shuffle() {
// Used to iterate thru the deck to make sure every card got their unique ID.
std::vector<Card>::iterator itr;
// Keep setting the random IDs untill everyone got an unique one
do {
// Randomly choose an ID for every card in the deck
for(int i=0; i<this->m_cards.size(); ++i)
this->m_cards[i].setRand( ::rand() );
// Sort the deck according the IDs of the cards.
std::sort( this->m_cards.begin(), this->m_cards.end() );
// Make sure that every card got their unique id.
itr = std::unique( this->m_cards.begin(), this->m_cards.end() );
} while( itr != this->m_cards.end() );
return true;
}
|
And as far as I can see, it's producing fair decks. Any comments?
Maths related to probability theory is hard :< I was never good at these in school, altho got a grade of 9 out of 10 :p
|
|
| Back to top |
|
|
HalfPrime
Grandmaster Cheater
![]() Reputation: 0
Joined: 12 Mar 2008
Posts: 532
Location: Right there...On your monitor
|
| Posted: Sun Jul 20, 2008 6:38 pm Post subject: |
|
|
| Quote: | I can see that. It's not about how to shuffle a deck, but how to shuffle it properly, so all the (52*N)! combinations are possible. And the original problem was that ::rand() isn't returning enough unique random numbers ( only ULONG_MAX, whereas it's << than (52*N)! ). Btw.. Guess your code doesn't even compile  |
rofl. Then cut the brat act and explain it. My code selects one card out of 52, then 1 of 51, then 1 of 50 all the way down to 1 of 1. According to my powers of observation, that makes a deck of 52! possibilities. The only statistically unfair thing about it is that the pool of rand is not evenly divisible by 52, giving some cards a better chance of being chosen first than others. This problem can be fixed easily, though. And, just for the record, you're code is just as statistically fair as if rand had a pool of only 52 numbers. Btw.. I wrote that code in the reply box. Didn't expect you to not know how to fix errors
_________________
|
|
| Back to top |
|
|
atom0s
Moderator
 Reputation: 205
Joined: 25 Jan 2006
Posts: 8587
Location: 127.0.0.1
|
|
| Back to top |
|
|
Jani
Grandmaster Cheater
![]() Reputation: 2
Joined: 29 Dec 2006
Posts: 804
|
| Posted: Mon Jul 21, 2008 6:46 am Post subject: |
|
|
| HalfPrime wrote: | | Then cut the brat act and explain it. |
Your code relies on initializing the random generator. The PRNG can be seeded with ULONG_MAX different values and then it'll start producing the same order of cards -> The order of the cards will be the very same after ULONG_MAX games, if seeding starts from 0. And as far as I know, on modern systems ULONG_MAX is way smaller than 52!. You know, problem isn't that it's "only" pseudo-random, but that there isn't enough different values for the random number to generate all the differently ordered decks. I hope you do understand how freaking much is 52!*. Here's some code which will iterate thru every single possible deck made with your algorithm (modified a bit?). And if it finds a 0,1,2,3,4,5... deck it'll print WOOT. A 0,1,2,3.. deck should be possible IF EVERY single combination of a deck is formed: | Code: | #include <iostream>
#include <ctime>
#include <climits>
#include <algorithm>
int main( int main, char *argv[] )
{
std::cout << "ULONG_MAX: " << ULONG_MAX << std::endl;
/* Loop thru 0-ULONG_MAX testing every seed.
* I know that ULONG_MAX isn't tested, but it's because there would be an overflow, if it was.
* You may test it separately if you want.
*/
for( unsigned int i=0; i<ULONG_MAX; ++i ) {
// Init the seed
::srand( i );
// Zero the chosen array.
int ischosen[52] = {0};
// Shuffled cards will be stored here
int shuffled[52];
// Shuffle the deck. HalfPrime's algorithm modified
for( int j=0; j<52; ++j) {
int r = ::rand()%52;
if( ischosen[r] == 0 ) {
ischosen[r] = 1;
shuffled[j] = r;
}
else
--j;
}
/* Check for 0,1,2,3,4,5...
* IT SHOULD BE FOUND IF EVERY COMBINATION WAS POSSIBLE.
* Prints WOOT if found and exits.
*/
for(int j=0; j<52; ++j) {
if( shuffled[j] != j )
break;
else if( j == 51 ) {
std::cout << "WOOT!" << std::endl;
return EXIT_SUCCESS;
}
}
/* Print i every 100 000th iteration time.
* This is to make sure that the proggy is still running
* and you can calculate how long does it still take to get
* no results :P
*/
if( i%100000 == 0 )
std::cout << i << " ";
}
return EXIT_SUCCESS;
} |
I was too lazy to wait for this to finish, but it should work? Leave it over a night and tell me the results :) If it finds one, try for 51,50,49... but I doubt that it'll find the 0,1,2,3.. Tell me if you find any bugs in the code. I did test the code a bit, so it's producing good and unique decks, but that's kinda all.
Now thinking of the method I'm using, I'm wondering does this same limitation apply to it, and I think it does, so my problem isn't solved yet? Only fairness was solved with this "new" algorithm.
| HalfPrime wrote: | | I wrote that code in the reply box. Didn't expect you to not know how to fix errors :) |
:P I just wanted you to read thru your post before posting it.
| Wiccaan wrote: | | Something I read about doing things like this is using other types of generated things such as GUID's. Instead of using a random number to place the cards into the vector, generate 52 GUID's and order them into the vector. |
That's what I'm doing now, but with ::rand(), because C++ doesn't have a built-in GUID generator. [I'd prefer GUIDs, if I only had a good portable generator, because ULONG_MAX( (0xFF+1)^4 ) << (0xFF+1)^16 (GUID is 16-byte isn't it?). But still, if (0xFF+1)^16 isn't enough, if the algorithm I'm using fails, because of, the limit of different random numbers. I really can't think clearly now. This all is messing my head up >_>]
| Wiccaan wrote: | | Other methods, but not practical, would be using various system information to help with generating randomness. GetTickCount, current memory usage, current system drive size, free space, etc. Anything that would most likely be random at any given point. |
Would work, but because of the unsigned int limit, not all the combinations are possible. Altho, this is a good way against someone who would like to sync their clock with the server and then just "predict" the cards, but my point wasn't here. I just wanted all the differently ordered decks possible.
I do know that ULONG_MAX is hella lot of games/time and the limit won't be met anytime soon, but I'm just wondering this, because of.. Well.. Iono, just wondering :P
* For younger people reading this forum: Assuming there're 7,000,000,000 people in the world and there's a pool with 52! (~8e+67) ping-pong balls and the people are trying to empty the pool. If everyone picks up one ball per second, it would take 8e+67/7000000000 seconds to empty the pool. That's more than 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 (3.6e+50) years. (I hope I did count the zeroes properly, anyway, it's about that much. :P)
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
