Second post in 1 day!
Wow, so many things to post, so little time! This time I'm going to be briefly explaining my final project for a summer class I took called Data Structures.
I've always been a fan of Yahtzee, since a kid my parents have engrained the full scorecard into my mind. Whether I'm in a pub or at a friends house, I still have the ability to write down a Yahtzee scorecard on nearly anything. So, when it came to doing a self created final project for a C++ Data Structures, I naturally jumped at the chance to emulate my favorite game. The purpose of the project was to create a program on your own design and do a complexity analysis. A complexity analysis is simply a data representation of how a program performs if you increase the input size dramatically. For instance, in my Yahtzee program, I varied the number of players from 1 to 100, then counted the number of overall operations and operations of each statistically significant function. An operation counted as anything that accessed or changed a current data structure.
The backbone for this program are 4 main data structures. The first two structures are the most
basic. They are structs called Dice and yahtStats. The Dice struct contains two arrays which are used to
save and roll the dice.
struct Dice{
array<int,5> dice;
array<int,5> savedDice;
};
YahtStats contains most of the statistics involved with the program, including the
number of operations. RollsPerNumber, which is an array of the yahtStats struct, is particularly interesting
because it shows the distribution of each value of dice rolled over the course of the entire game.
struct yahtStats{
int operations = 0;
int autoPlay = 0;
int mainOp = 0;
int rollDiceOp = 0;
int printDiceOp = 0;
int printRollwithSavedOp = 0;
int autoSaveDiceOp = 0;
int saveDiceOp = 0;
int getQtysOfDiceOp = 0;
int autoConfirmScoreOp = 0;
int confirmScoreOp = 0;
int autoScoreTurnOp = 0;
int scoreTurnOp = 0;
int autoPlayTurnOp = 0;
int playTurnOp = 0;
int numPlayers = 0;
int playerTurn = 0;
int turnRolls = 0;
bool keepRolling = true;
int totalRolls = 0;
int turns = 0;
array<int,6> rollsPerNumber;
};
The next data structures are two classes called Scorecard and Score. Scorecard uses the object Score as a data type to fill a 2D array of width 18 and height of the number of players in the game.
Score has two attributes, score and hasBeenScored. ”score” contains the actual integer value of the Score, while hasBeenScored is a boolean field which is set to true if the score is set for the first time. The reason for this
is to allow to check if scores equal to 0 have already been scored as 0, and are not just empty categories.
class scorecard{
private:
int numPlay;
Score ** playerScores;
array<string,100> playerNames;
public:
scorecard(int numPlayers);
~scorecard();
void setNumPlay(int num);
void setPlayerScore(int player,int section, int score);
void setPlayerName(int player, string name);
int getNumPlay();
Score getPlayerScore(int player, int section);
string getPlayerName(int player);
void printDivider(int numPlayers);
void print(int numPlayers);
};
class Score{
private:
int score;
bool hasBeenScored;
public:
Score();
~Score();
void setScore(int s);
void setHasBeenScored(bool hBS);
int getScore();
bool getHasBeenScored();
string getHasBeenScoredStr();
};
Below is a dependency chart for the main method. Simply put, the main method gathers the mode of which the user would like to play, either standard or auto-play, and the number of players. Based on these inputs, it iterates through either playTurn or autoPlayTurn enough times to fill the scorecard with scores.
The pseudocode for playTurn and autoPlayTurn are shown below.
void playTurn(yahtStats * stats, Dice * myDice, scorecard * myScorecard){
1. Roll the dice between 1 and 3 times.
2. Save the dice between 1 and 3 times.
3. Score the turn.
}
void autoPlayTurn(yahtStats * stats, Dice * myDice, scorecard * myScorecard){
1. Find a random number of rolls between 1 and 3.
2. Iterates through for the number of rolls indicated by the randomly generated number.
3. AutoSave the dice.
4. autoScore the turn.
}
A critical portion of this project was to do a complexity analysis. I chose to do my analysis based on the number of players. Because my independent variable was linear, and each player had a set number of turns to complete, I hypothesized that the program's complexity would increase linearly. To test this, I made the auto-play mode. Since the outcome score-wise was irrelevant, I chose to randomize the player input at any opportunity. In this way, I simulated the average game with players. While convenient, it did not replace the high scores of an actual AI player. To keep track of the operations, I placed incrementing counters at places inside of each local function inside main.cpp.
These counters can be found in the yahtStats struct.
Originally, I had the autoPlayTurn function print off the scorecard each time. For reference, the scorecard looked like something below.
By printing the scorecard each time a turn was finished, I printed off the scorecard numPlayers^2 times. This resulted in the following exponential complexity plot based on operations.
After removing the offending quadratic printing, the complexity plot became very linear, which proved my original hypothesis.
In the end, this project taught me the value of complexity analysis and data structures. It was good project to work on because it had a medium high code complexity and great "Fun Factor". For those of you who would like to try out the program, it is available here:
Yahtzee.
-John "My computer is at 1% so I have to FINISH THIS QUI"
