Shuffle Algorithm for my Poker application

[D8TMGNh0]

I am in doing a school-related project which requires that I incorporate various elements of what we have learned in class, into my project, which is a simple game of Poker.

I have a shuffle algorithm that I am using to randomize the position of each card within a deck of 52 cards.

The problem is that whenever I run the code below (Note: I am in Xcode just in case)

I EITHER get the error saying "Thread 1: EXC_BAD_ACCESS (code=1, address=0x118005238)" whenever line getSuitName() of card.h is hit,

OR the destructor is activated, and the program ends WITHOUT DISPLAYING ANYTHING.

OR the display function displays WAY MORE THAN NECESSARY and displays only ace of hearts

I think it might be an issue with the numbers I am using for the shuffle function, but I am not sure exactly what is wrong.

I am unsure of what is causing the issue and need a second set of eyes to help identify the issue, if not possible causes.




int main

#include <iostream>
#include "deck.h"
#include <cstdlib>
#include <cmath>

using namespace std;

const int sizeOfDeck = 51;

int main(int argc, const char * argv[]) {
    
    Deck deck;
    
    cout << "\n\nSHUFFLED DECK:\n\n";
    
    deck.shuffle(sizeOfDeck);
    deck.display();
    
    return 0;
}

card.h

#ifndef card_h
#define card_h

// I define some enums here in order to help represent
// certain attributes of the cards. Such as Rank and Suit.
//
// I also create some string arrays to help represent each item
// contained within the enums
enum Suit {
    hearts, spades, diamonds, clubs
};
std::string suit[] = {
    "hearts", "spades", "diamonds", "clubs"
};

enum Rank {
    ace, two, three, four, five, six, seven,
    eight, nine, ten, jack, queen, king
};
std::string rank[] = {
    "ace", "two", "three", "four", "five", "six",
    "seven", "eight", "nine", "ten", "jack",
    "queen", "king"
};


// Constant variables to represent the amount
// of ranks and suits
const int maxRank = 13;
const int maxSuit = 4;


// This class will be used to create a card
class Card{
public:
    Card();
    Card(const int &suit, const int &rank);
private:
    int getSuit() const;
    std::string getSuitName() const;
    int getRank() const;
    std::string getRankName() const;
    int generateSuit();
    int generateRank();
    int m_rank;
    int m_suit;
    
    // Deck will need to be able to access attributes of the card,
    // but the card will not need to access deck at all
    friend class Deck;
};



// Default constructor generates a random card
Card::Card(){
    m_suit = generateSuit();
    m_rank = generateRank();
}

// Generates a card based on values given through for...loop in deck.h
Card::Card(const int &suit, const int &rank): m_suit(suit), m_rank(rank){};


// Get the value of m_rank
int Card::getRank() const{
    return m_rank;
}

// Get the value of m_suit
int Card::getSuit() const{
    return m_suit;
}

std::string Card::getRankName() const{
    return rank[getRank()];
}

std::string Card::getSuitName() const{
    return suit[getSuit()];
}

// Generate a value for m_rank
int Card::generateRank(){
    return rand() % maxRank;
}

// Generate a value for m_suit
int Card::generateSuit(){
    return rand() % maxSuit;
}

#endif /* card_h */ 

deck.h

#ifndef deck_h
#define deck_h
#include <iostream>
#include <fstream>
#include <vector>
#include "card.h"

using namespace std;

// This class will represent a standard
// deck of 52 playing cards
class Deck{
public:
    // Default constructor to generate the deck
    Deck();
    // Destructor to deallocate memory
    ~Deck() {cout << "Deleting deck...\n\n"; delete m_deck;}
    // display the deck for test purposes
    void display() const;
    // Access the deck and grab a card off the end
    void getCard();
    // This is vital for randomness factor of the game!!!
    // The shuffle function will shuffle the deck so that
    // it is never the same!
    // There is about 1 / 1x10^68 chance that the deck will
    // be the exact same after it is shuffled!
    void shuffle(int sizeOfDeck);
private:
    // The vector will dynamically store the deck
    vector<Card> * m_deck = new vector<Card>;
};





// This will generate a deck of cards by generating
// 13 of each suit of card.
Deck::Deck(){
    // Start with the suit
    for (int suit = 0; suit < maxSuit; ++suit)
    {
        // then generate all ranks for each suit
        for (int rank = 0; rank < maxRank; ++rank)
        {
            // create the card
            Card card(suit, rank);
            // Then store the card in a deck
            m_deck->push_back(card);
        }
    }
}



void Deck::shuffle(int sizeOfDeck){
    // To be sure of the randomness factor...
    srand(static_cast<uint>(time(nullptr)));
    int *random = new int;
    
    for(int index = 0; index < sizeOfDeck; index++){
        *random = index + (rand() % (sizeOfDeck - index));
        swap(m_deck[index], m_deck[*random]);
    }
    
}


void Deck::display() const {
    std::string *suitName = new std::string;
    std::string *rankName = new std::string;
    int count = 0;
    
    
    
    for(int i = 0; i < m_deck->size(); i++){
        *suitName = m_deck->at(i).getSuitName();
        *rankName = m_deck->at(i).getRankName();
        cout << "Card " << i+1 << " is: " << *rankName << " of " << *suitName << endl;
        count++;
        if(count == 13){
            cout << "\n";
            count = 0;
        }
    }
    
    
}

#endif /* deck_h */ 

[Albatross]

Dear oh dear. Your code is treating std::vector like it's a block of memory that can be grown and used like an array. It is not that. It is more accurately a manager for said blocks of memory (and the objects in them). A practical upshot of this is that you do not need to do this: vector<Card> * m_deck = new vector<Card>;

Misuse of that pointer is where all of your problems come from (as far as I can tell from a quick glance). Take this bit, for example: m_deck[index]. This does not get elements from the vector. It gets you the "manager" part of std::vector as if m_deck was a pointer to an array of such objects. Since it's not that, you are basically swapping garbage on line 63.

This problem is easily resolved by changing m_deck to just be an std::vector and changing your ->s for .s when accessing it.

For more information, here's an article on the topic that I wrote forever ago: http://www.cplusplus.com/articles/37Mf92yv/

-Albatross

EDIT: Also, your program leaks memory everywhere. Every time display is called, two strings (of varying lengths) are leaked. Every time shuffle is called, one integer is leaked. I won't comment on other ways your program can be improved unless you ask, but please, at least fix those as well.

[Repeater]

To summarise part of what Albatross said; there is no need for any of this code to use new. Do not use new. Do not use new. Do not use new.

[KishoreG]

I agree with Albatross. I would also suggest that you look at C++ smart pointers instead of using new and delete. They make life so much easier:

http://www.cplusplus.com/reference/memory/unique_ptr/
http://www.cplusplus.com/reference/memory/shared_ptr/

An std::vector is a dynamic array that handles dynamic memory internally. Meaning, that it is an array that doesn't have a fixed size and grows as you push_back elements into it. All the dynamic allocations are handled by the std::vector class itself. Everytime a std::vector needs to be resized to add new elements it will automatically copy/move all the elements from the old std::vector, allocate a new, bigger one, copy/move it in, and deallocate the old std::vector. This is done automatically so there is no need to bring dynamic memory into it the way you are doing it. In modern C++, you will mostly not have to manually use new and delete unless you are writing your own algorithms that use dynamic memory. It can all be handled if you use standard library implementations like smart pointers and std::vector.

[D8TMGNh0]

Thank you for the feedback concerning my use of 'new' and memory leaks.

I am trying to dynamically allocate memory, but after looking into it a bit further, I can see that most likely, the destructor will handle things such as std::string, etc.

I will edit what you guys have suggested and come back with either an answer, or more questions.

Thank you for such quick feedback.

EDIT: I have changed all of the variables that I was trying to dynamically allocate memory with, to standard, declared variables.

So far this seems to be working so thank you for that.

If you have any other suggestions as to how I could change my code, I am open to criticism. I am still a student and believe it is important to learn how I could have written this better

[George P]

Why invent your own shuffle routine when <algorithm> already provides one that works with containers. std::shuffle() if you want the current routine using a C++ random number engine, or std::random_shuffle() using the C library's rand().

https://en.cppreference.com/w/cpp/algorithm/random_shuffle

When writing C++ code you should avoid using C's srand()/time()/rand(). The C library's ability to generate random numbers with minimal bias stinks. <chrono> let your program obtain the system clock's current interval (milliseconds) with greater accuracy than time() (seconds in many instances) can do.

What does that mean for you? The greater likelihood your program will obtain a different time count for seeding the random number generator even if run multiple times per second.

<random> provides multiple engines for generating pseudo random numbers, and one that produces true random numbers if the implementation ensures it is working.

There are multiple means for generating distributions of a sequence of random numbers. Either uniform or with known biases.

One neat feature of <random> is the ability to generate a sequence of real number random numbers. The C library you can reliably generate only ints.

https://en.cppreference.com/w/cpp/numeric/random

[Duthomhas]

Making a random number generator for your program is very, very easy, but very, very undersold in examples on the *net. Let’s write one!

#include <chrono>
#include <random>

// Here is our GLOBAL random number generator (initialized with a wall-clock-based seed)
std::ranlux48 rng( std::chrono::system_clock::now().time_since_epoch().count() );


// Here is a function to get a random integer value in a range
template <typename T>
T random( const T& min, const T& max )
{
  return std::uniform_int_distribution <T> ( min, max )( rng );
}

// Here is a function to randomize a container
template <typename Container>
Container& random_shuffle( Container& xs )
{
  using std::begin;
  using std::end;
  std::shuffle( begin(xs), end(xs), rng );
  return xs;
}

Yes, that is a global. This is one of the few places using a global object is Not A Bad Thing™.
Some functional purists might be offended. Ignore them. They’re extremists.

Let’s put that little collection to work:

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
  // Random integer in range
  std::cout << " random integer in 1..100:  " << random( 1, 100 ) << "\n";
  
  // Randomize a container
  int xs[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  random_shuffle( xs );

  std::cout << " { 1..10 } in random order:";
  for (int x : xs)
    std::cout << " " << x;
  std::cout << "\n";
}

Yeah!

Now, a suggestion on your Poker game. Generate a shoe of cards and randomize that. That way, when your players wind up looking at each other’s hands, they don’t all have an Ace of Clubs and a Three of Spaces, or some other suspicious collection that makes them start wondering if the game could be stacked.

That means, first, that a Card must represent a single, distinct, ordered card value. This also makes it a much simpler class:

struct Card
{
  int value;
  Card( int value ): value(value) { }
  int getSuit() { return value / 13; }
  int getRank() { return value % 13; }
};

Once you have that, then you can easily create a complete deck of them. Or, in the case of a poker game, a shoe:

struct Shoe
{
  std::vector <Card> cards;

  ...

  Card draw()
  {
    // (re)initialize the shoe as needed
    if (cards.size() < minimum_number_of_cards_in_a_shoe)
    {
      for (int d = 0; d < number_of_decks_in_a_shoe; d++)
      for (int n = 0; n < 52; n++)
        cards.emplace_back( Card( n ) );
    }
    // draw a card
    Card card = cards.back();
    cards.pop_back();
  }

};

You’ll notice a couple of variables in there. You can either hard-code them or give the user the option to configure it, or just make the game adjust itself for the number of players. An easy selection is 2 decks per shoe with a minimum of 50 cards, IIRC. (I don’t gamble, and it has been years since I studied poker.)

Hope this helps.

[D8TMGNh0]

To Duthomhas:

Thank you for the feedback. I will say that I have written some more to this code in order to deal a hand to each player. To do that (which might sound complicated, but this is for a c++ class), I created a class called Hand, and set it so that it generates a hand of 5 cards from the top of the deck. Every time it adds a card from the top of the deck to the player's hand, the program then removes that card from the deck entirely. This way, there is only one of each unique card in any players hand.

When I am done with the hand, the cards left from both players hands will be shuffled, and stored at the bottom of the deck of cards, later to be used as needed.


To Albatross:

Again, thanks for the info on the memory leaks. I was much careful this time to use dynamically allocated memory in my program. I am keeping any inside of main(), just to keep things simple.


To KishoreG:

I have heard about the use of smart pointers in c++, however, my teacher only touched on them and mainly went over the usage of the keyword 'new' and expects us to use it. I will do some research on smart pointers because they sound like they take a lot of the dynamically allocated headache away!


To Furry Guy:

I would have liked to use <algorithm> inside of my program, however, because this project is for a class, the teacher prefers that we write out shuffle algorithms on our own, etc. to show our understanding of the material gone over during the course. I will, however, be sure to use it in the future! As for using <chrono> instead of <ctime>, that sounds interesting. I have not heard of it yet and I will look into it and do a bit of research into its usage. It does sound as though it does work a lot more accurately than using <ctime>.


Let me just say that I can't believe how helpful you guys were for this project. And not just for a solution, but for teaching me why that solution worked!

StackOverflow would never have been that helpful. They would have criticized the way I formatted my post instead, ha!

[George P]

@therealconnor,

Ok, writing your own routine is a class assignment, I can understand that.

Did you at least look at the possible implementations of a shuffle routine at the cppreference link I gave you?

https://en.cppreference.com/w/cpp/algorithm/random_shuffle

For a beginner the coding can look like a lot of argle-bargle nonsense jargon.

Trying to understand how any particular compiler could implement the standard's requirement can push the boundaries of your current level of knowledge. It sure makes me appreciate the amount of work and skull sweat expended behind the scenes when I use of the C++ libraries.

[D8TMGNh0]

To Furry Guy:

I am currently looking into the possible implementation of shuffle, it actually looks easier than what I did. I do have a quick question about it though...

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>
 
int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v.begin(), v.end(), g);
 
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

This is the example on the source you linked me to...

I have a general understanding of how this works, but What is 'random_device' and 'mt19937'??

I read the source for mt19937, it sounds like it is a random number generation system? I was not very sure about that and would like a little clarification if you would spare me the time.

Thank you thus far.

[George P]

Instead of writing a loooooooong post that likely wouldn't help you to really understand how to generate random numbers in C++ I'll give you a link to LearnCPP's tutorial instead.

https://www.learncpp.com/cpp-tutorial/59-random-number-generation/

A bit of reading on your part, but it explains things much better than I could with the limitations of post length.

Here is how I might rewrite the code from your example:

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

int main()
{
   std::vector<int> my_vector = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

   // obtain a seed from the system clock:
   unsigned seed = static_cast<unsigned> (std::chrono::system_clock::now().time_since_epoch().count());

   // instantiate a pseudo-random number generator, using the system clock seed
   std::default_random_engine generator(seed);

   std::shuffle(my_vector.begin(), my_vector.end(), generator);

   // a range-based for loop works wonders when "walking" through the elements of a container
   for (const auto& itr : my_vector)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';
}

Why I don't like using C's srand()/time()/rand():
https://web.archive.org/web/20180123103235/http://cpp.indi.frih.net/blog/2014/12/the-bell-has-tolled-for-rand/
https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful

A proposal from several years ago that I found very helpful in creating my own header-only version of a simple toolkit for generating random numbers:
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3551.pdf

If you want I can post the header and some example code to show how to use the header.

If you don't I won't be offended. You've got some reading to do, along with more time to let the new info to sink in. :)

[D8TMGNh0]

I won't be offended at all! Thank you for the info. I do read through those and try to learn as much as I can from them.

It sucks being a noob at c++. But that's just reality. I will understand it sooner or later the more I work with it.

Also, I like how you rewrote the example, it is much easier to read and understand what is going on, even if it is just an abstract knowledge of the system. For now because of time restraints I am using srand() time() and rand(), but I do like the clarity of using a literal random number generator, as well as using the systems clock to seed it. I will try using that in my next project, or even to re-write the current project I am on after it has been graded.

The teacher teaching me C++ right now has been using c++ from the 80s, so she has been teaching us c++ as if we were going to try and create a large, performance heavy system. Such as an OS or financial application. This is why I have been using things like srand() and the 'new' keyword. She was trying to teach the basics, and how to make c++ do its stuff.

I'm not saying that it's bad that she teaches us that stuff though. It is good to understand basic c++ concepts such as hard memory management and random number generation. It forces you to think about things :)

And in the end, that is what programming comes down to isn't it? Thinking and solving puzzles, and figuring out whether you should throw it together or take your time when given a deadline.

[George P]

It sucks being a noob at c++.

Some of us still are. Self-taught and still learning.

random_toolkit.hpp:

/* A simple toolkit to help beginners using <random> library an easier task */

// shamelessly stolen and adapted from a C++ working paper: WG21 N3551
// http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3551.pdf

#ifndef __RANDOM_TOOLKIT_HPP__
#define __RANDOM_TOOLKIT_HPP__

#include <chrono>
#include <random>
#include <stdexcept>

namespace rtk
{
   static bool seeded = false;

   inline std::default_random_engine& urng()
   {
      static std::default_random_engine URNG { };

      return URNG;
   }

   inline void srand(bool FORCE_SEED = false)
   {
      static unsigned seed = static_cast<unsigned> (std::chrono::system_clock::now().time_since_epoch().count());

      if (!seeded || FORCE_SEED)
      {
         urng().seed(seed);

         seeded = true;
      }
   }

   inline void srand(unsigned seed, bool FORCE_SEED = false)
   {
      if (!seeded || FORCE_SEED)
      {
         urng().seed(seed);

         seeded = true;
      }
   }

   // two function overloads to obtain uniform distribution ints and doubles
   inline int rand(int from, int to)
   {
      static std::uniform_int_distribution<> dist { };

      if (from > to) { throw std::invalid_argument("bad int params"); }

      return dist(urng(), decltype(dist)::param_type { from, to });
   }

   inline double rand(double from, double to)
   {
      static std::uniform_real_distribution<> dist { };

      if (from > to) { throw std::invalid_argument("bad double params"); }

      return dist(urng(), decltype(dist)::param_type { from, to });
   }

   // function for rolling dice, and checking if the # of pips is nonstandard
   inline int roll_die(int pips)
   {
      //check to see if the number of die pips is less than 2
      if (pips < 2)
      {
         return 0;
      }

      return rand(1, pips);
   }
}

#endif 

URNG_Test.cpp:

#include <array>
#include <iostream>
#include <numeric>
#include "random_toolkit.hpp"

int main()
{
   // create a random engine and randomize it
   rtk::srand();

   using card = unsigned short;

   // manufacture a deck of cards:
   std::array<card, 52> deck;

   // create the cards, 0 (zero) to 51
   std::iota(deck.begin(), deck.end(), 0);

   // shuffle the deck:
   std::shuffle(deck.begin(), deck.end(), rtk::urng());

   // lambdas to display the card in text representation:
   auto rank = [] (card c) { return "AKQJT98765432"[c % 13]; };
   auto suit = [] (card c) { return "SHDC"[c / 13]; };

   card count = 0;

   for (card c : deck)
   {
      std::cout << rank(c) << suit(c) << ' ';
      count++;

      if (0 == (count % 13))
      {
         std::cout << '\n';
      }
   }
   std::cout << '\n';

   for (unsigned loop = 0; loop < 50; loop++)
   {
      std::cout << rtk::roll_die(6) << ' ';

      if ((loop + 1) % 20 == 0)
      {
         std::cout << '\n';
      }
   }
   std::cout << "\n\n";

   // lambda to "flip a coin," returning a text representation of coin side
   auto flip_coin = [] () { return (rtk::rand(0, 1) ? "Heads" : "Tails"); };

   for (unsigned loop = 0; loop < 25; loop++)
   {
      std::cout << flip_coin() << '\t';

      if ((loop + 1) % 8 == 0)
      {
         std::cout << '\n';
      }
   }
   std::cout << '\n';

   std::cout << "\nLet's see if we can have a non-standard die.....\nA die with 1 side: ";
   std::cout << rtk::roll_die(1) << '\n';

   std::cout << "A die with negative sides: ";
   std::cout << rtk::roll_die(-6) << "\n\n";

   // let's try to create a bad distribution
   std::cout << "Creating a bad random roll distribution, it should be be\n";
   std::cout << "encapsulated within a try/catch block.  Unless you want to crash.\n";

   try
   {
      int test = rtk::rand(5, 2);
   }
   catch (const std::exception& e)
   {
      std::cout << "\n>>> A standard exception was caught, with message '" << e.what() << "'\n";
   }
}

8D 3S 6D TH 2S 4C JS JH 7C 2D 3C 7H KC
TC 7S JD KS 2H 9D 5D 4H 4D QD 6C KH 3H
4S QC 9H KD QS 7D AS 9S 8H 6S 9C 5H AH
6H 3D AD 2C 8S 8C JC QH TS 5S 5C TD AC

6 1 4 6 3 4 3 3 5 2 4 5 5 2 5 6 1 5 3 6
6 4 4 4 5 6 3 3 6 1 6 6 6 1 1 2 3 1 4 6
6 2 4 4 6 5 2 6 4 4

Tails   Heads   Tails   Heads   Heads   Tails   Heads   Tails
Tails   Tails   Heads   Heads   Heads   Tails   Tails   Tails
Heads   Heads   Heads   Tails   Heads   Tails   Tails   Tails
Heads

Let's see if we can have a non-standard die.....
A die with 1 side: 0
A die with negative sides: 0

Creating a bad random roll distribution, it should be be
encapsulated within a try/catch block.  Unless you want to crash.

>>> A standard exception was caught, with message 'bad int params'

That my example code deals with creating and randomizes a deck of 52 cards is coincidental. This example project was created several years ago when I first read the working paper PDF.

And like Frankenstein's monster kept growing and adding more tests as I kept modifying my header.