Thread: Shuffling a deck?

  1. #1
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964

    Shuffling a deck?

    Code:
    #include <iostream>
    #include <ctime>
    
    #define LOW 2
    #define HIGH 52
    
    void Swap(unsigned int &A, unsigned int &B)
    {
    	int C = A;
    	A = B;
    	B = C;
    }
    
    class Deck {
    	private:
    		unsigned int Cards[52][2];
    		time_t Seconds;
    		unsigned int DeckSize;
    	public:
    		Deck();
    		void Shuffle();
    };
    
    Deck::Deck()
    {
    	DeckSize = 52;
    	
    	time(&Seconds);
    	srand((unsigned int) Seconds);
    	
    	unsigned int Values[13] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    	int i = 0, j = 0 , k = 1;
    	
    	for(i; i < 52; i++)
    	{
    		Cards[i][0] = Values[j];
    		
    		(j == 12) ? j = 0 : j++;
    	}
    	
    	for(i = 0; i < 52; i++)
    	{
    		Cards[i][1] = k;
    		
    		(j == 12) ? (k++, j=0) : j++;
    	}
    }
    
    void Deck::Shuffle()
    {
    	DeckSize = 52;
    	int i = 52, RandomIndex = 0;
    	
    	for(i; i >= 2; i--)
    	{
    		RandomIndex = (rand() % (HIGH - LOW + 1) + LOW) % i;
    		Swap(Cards[i][0], Cards[RandomIndex][0]);
    		Swap(Cards[i][1], Cards[RandomIndex][1]);
    	}
    	
    	for(i = 0; i < 52; i++)
    	{
    		std::cout << Cards[i][0] << " " << Cards[i][1] << std::endl;
    	}
    }
    
    int main()
    {
    	Deck Foo;
    	Foo.Shuffle();
    	std::cin.get();
    }
    This is my code so far. The shuffle() function is not really supposed to print the deck but i did that for debugging purposes, so i could check how the deck got shuffled.

    My deck is as you can see a 2 dimensional array of 52x2 unsigned integers. The first row is the Face Value of the card (Jack, Ace, 5 etc.), the second row is the suit of the card (Diamonds, Clubs and so on).

    The algorithm i used loops through the deck from 52 to 2. It gets a random number (mod the loop index), and swaps the corresponding element in the array with the element of the index loop.

    The output i get is almost what i wanted, the deck is shuffled, quite randomly. But one of the elements contains a huge number, instead of 2-14, and the suit element of that card contains 52 (or MAX). The number i get looks like an overflow error, but i've gone over the loops a million times, with no results.

    1. Is my shuffling algorithm valid, or is there a better one i can use?

    2. Where is the overflow error, i for sure as hell can't find it, and i'ts been bugging me for hours!

  2. #2
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    use the standard library.

    Code:
    class card
    {
        enum Suite
        {
             Spades,
             Hearts,
             Clubs,
             Diamonds
         };
     
         enum Value
         {
               TWO,
               THREE, 
               //etc...
               Jack,
               Queen,
               King,
               Ace
         };
    
         explicit Card(Suite s, Value v);
    };
    
    int main()
    {
        std::vector<card> deck(52);
        deck.push_back(Card(Card::Spades, Card::Ace));
        deck.push_back(Card(Card::Hearts, Card::Queen));
        // add all the cards
    
       std::random_shuffle(deck.begin(), deck.end());
    }
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  3. #3
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by ChaosEngine View Post
    use the standard library.

    Code:
    class card
    {
        enum Suite
        {
             Spades,
             Hearts,
             Clubs,
             Diamonds
         };
     
         enum Value
         {
               TWO,
               THREE, 
               //etc...
               Jack,
               Queen,
               King,
               Ace
         };
    
         explicit Card(Suite s, Value v);
    };
    
    int main()
    {
        std::vector<card> deck(52);
        deck.push_back(Card(Card::Spades, Card::Ace));
        deck.push_back(Card(Card::Hearts, Card::Queen));
        // add all the cards
    
       std::random_shuffle(deck.begin(), deck.end());
    }
    I'd rather write my own functions than using premade ones, even if they are more efficient and well-written, i'm only doing this because i want to learn, the day i wan't to make important software, i promise to use the std library for stuff like this

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    int i = 52, RandomIndex = 0;
    	
    	for(i; i >= 2; i--)
    Here your first index will be 52 - out of bounds.

    Another thing: you probably don't need the defines. You already have a data member DeckSize which equals 52. And you seem to use LOW only in one place (but not in the for expression), so it's probably specific to this algorithm.

    To improve the class:
    Code:
    class Deck {
    	private:
             const static unsigned int Decksize = 52; 
    		unsigned int Cards[Decksize][2];
    		//time_t Seconds; //has nothing to do with a deck
    		
    	public:
    		Deck();
    		void Shuffle();
    };
    * Use Decksize instead of HIGH.
    ** Card might be a class/struct of its own.
    Last edited by anon; 07-12-2007 at 06:11 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    This looks like you're going too far:
    Code:
    void Deck::Shuffle()
    {
    	DeckSize = 52;
    	int i = 52, RandomIndex = 0;
    
    	for(i; i >= 2; i--)
    	{
    		RandomIndex = (rand() &#37; (HIGH - LOW + 1) + LOW) % i;
    		Swap(Cards[i][0], Cards[RandomIndex][0]);
    		Swap(Cards[i][1], Cards[RandomIndex][1]);
    	}
    Try setting i to 0 to begin with.

    [edit] Too late. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Why do you have two arrays of size 52? You should have one array of size 52 since there are only 52 cards in the deck, and then use / or &#37; to determine the face and suit. When you shuffle separately, you might end up getting two aces of clubs but no ace of diamonds.

    Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).

    I would not set i to 0 to begin with. Start it at 52 and work down to 1, making sure you get a random number in that range of [0,i). That way you'll stay in bounds.

  7. #7
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    You guys are right, i was too busy going through the loops too look at the index variables, i replaced the 52 with a 51 and it's working like a charm now, thanks a bunch

  8. #8
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by Daved View Post
    Why do you have two arrays of size 52? You should have one array of size 52 since there are only 52 cards in the decl, and then use / or % to determine the face and suit. When you shuffle separately, you might end up getting two aces of clubs but no ace of diamonds.

    Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).
    Nope, i will only get one of each suit, because when i shuffle, i swap both the Value and the Suit to the same position, i don't shuffle them seperatly.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> working like a charm now
    Are you sure your random numbers are distributed evenly? I'm not sure they will be.

  10. #10
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by Daved View Post
    >> working like a charm now
    Are you sure your random numbers are distributed evenly? I'm not sure they will be.
    Try and run the code then

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).
    Actually that should be [0, i] - including i: it should be possible for a card to stay in the same place while shuffling.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Actually that should be [0, i] - including i
    I guess either you start at 51 and include i or you start at 52 and swap with i-1.

    >> Try and run the code then
    Sorry, I don't have time, but you won't be able to tell by running the code once. You need to put the whole thing in a loop and run it hundreds or thousands of times keeping track of which numbers get in which spots and how many times. Then you can see if there are any issues. It is very common when implementing this yourself, especially when you don't follow the common formats, for the distribution to be slightly off. For example, maybe aces end up being dealt first 10&#37; of the time and 8's only 5%.

  13. #13
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by Daved View Post
    >> Actually that should be [0, i] - including i
    I guess either you start at 51 and include i or you start at 52 and swap with i-1.

    >> Try and run the code then
    Sorry, I don't have time, but you won't be able to tell by running the code once. You need to put the whole thing in a loop and run it hundreds or thousands of times keeping track of which numbers get in which spots and how many times. Then you can see if there are any issues. It is very common when implementing this yourself, especially when you don't follow the common formats, for the distribution to be slightly off. For example, maybe aces end up being dealt first 10% of the time and 8's only 5%.
    I thought you meant that i would have an uneven number of cards in the different suits.

    I have run the code around 200 times, and the second card in the array always seem to be either a 3, 4 or 5, not random at all. So i guess this must mean that i did something wrong within my shuffling algorithm right?

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I can't observe this pattern.

    I don't understand, though, why it must be so compliated to pick a number [0, i]

    Why not
    Code:
    RandomIndex = rand() % (i + 1);
    Daved may be referring to the fact that if (i + 1) in above statement is not a factor of RAND_MAX, the results tend to be biased but I don't think it would make that much difference here.

    Once you are happy with what the code does, you might also consider cleaning it up style-wise.

    * No need for the #defines.
    * Once you have set DeckSize in the constructor, use it instead of magic 52 everywhere.
    * Seconds makes no sense as a member of Deck class. In fact you don't need a separate time_t variable for srand() anyway.
    * In for statements such as this:
    Code:
        for (i; i < x; ++i)
    the first expression (i;) does absolutely nothing (except producing a compiler warning if you have warnings enabled. Therefore you can just omit it:
    Code:
        for (; i < x; ++i)
    In C++, however, the loop counter is usually declared inside the for-expression:
    Code:
        for (int i = qqq; i < x; ++i)
    * Consider making Card a separate class / struct. (This will also help you get rid of the ugly 2D array and switch to random_shuffle more easily.)
    * Consider using std::vector instead of the raw array.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  15. #15
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by anon View Post
    I can't observe this pattern.

    I don't understand, though, why it must be so compliated to pick a number [0, i]

    Why not
    Code:
    RandomIndex = rand() % (i + 1);
    Daved may be referring to the fact that if (i + 1) in above statement is not a factor of RAND_MAX, the results tend to be biased but I don't think it would make that much difference here.

    Once you are happy with what the code does, you might also consider cleaning it up style-wise.

    * No need for the #defines.
    * Once you have set DeckSize in the constructor, use it instead of magic 52 everywhere.
    * Seconds makes no sense as a member of Deck class. In fact you don't need a separate time_t variable for srand() anyway.
    * In for statements such as this:
    Code:
        for (i; i < x; ++i)
    the first expression (i does absolutely nothing (except producing a compiler warning if you have warnings enabled. Therefore you can just omit it:
    Code:
        for (; i < x; ++i)
    In C++, however, the loop counter is usually declared inside the for-expression:
    Code:
        for (int i = qqq; i < x; ++i)
    * Consider making Card a separate class / struct. (This will also help you get rid of the ugly 2D array and switch to random_shuffle more easily.)
    * Consider using std::vector instead of the raw array.
    I am going to use this code for a console based BlackJack game, and i am using the DeckSize variable to keep track of how many cards are left in the deck after i draw the top one, that is also why i didn't declare it as a constant.

    About the time_t variable: The code i used is just something i basically copied from the FAQ on this site, i figured there would be nothing wrong with it then. I'll make sure i get rid of it though.

    Thanks for the tips though, i will go through the game and alter my code once i got it done and it's working 100%, i'd rather not start rebuilding it before i've even finished writing it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about engine design.
    By Shamino in forum Game Programming
    Replies: 9
    Last Post: 01-29-2008, 10:53 AM
  2. Blackjack
    By Tommo in forum C Programming
    Replies: 10
    Last Post: 06-20-2007, 08:07 PM
  3. Deck Shuffle
    By pjharris in forum C++ Programming
    Replies: 51
    Last Post: 01-06-2006, 04:59 PM
  4. Problem with deck class.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 12-13-2005, 06:00 PM
  5. Replies: 2
    Last Post: 11-07-2003, 12:21 AM