Friday, May 11, 2007

Programing: Card Game War (Part 5 of 5)

This is the last post in my first series about the card game of war. I used C++ to implement this game and it is a computer playing itself. The basic concept here is to not determine who the winner is, rather, how many rounds it took to complete the game. My first post was about the RandomGenerator class I used to shuffle the deck of cards. The next class I made was a card class. This class simply represented a single playing card. Obviously, the deck class followed which was used to make an entire deck, shuffle it, then deal it. Lastly, was the war class which actually played the game and could return the number of rounds.

The concept here is to find, if any, mathematical anomalies that appear while playing the game War. These are the minimum and maximum number of tricks along with any trends that involve the frequency of a game ending after a specific number of tricks.

The remaining code calls on all of the previous classes. In my implementation I used header files which each post gives examples of what they should be named. Here is the final portion of code that will play 50,000 games of war.


#include <cstdlib>
#include <iostream>
#include <cstdlib> //Used for rand() & srand()
#include <string>
#include <fstream>
//Used to just make all kinds of crazy random numbers
#include "randomNumbers.h"
//Used to make an individual card object
#include "card.h"
//Used to hold an entire deck of cards
#include "deck.h"
//A game of War
#include "war.h"

using namespace std;


int main()
{
//An array containing the number of hits for each number
int winNumber[10001];
for(int i = 0; i < 10001; i++)
{
winNumber[i] = 0;
}
int max = 0;
int min = 10000;
long total = 0;
int successfulRuns = 0;
int trys = 50000;
int ties = 0;
for(int i = 0; i < trys; i++)
{
//srand(rand());
war myWar;
int rounds = myWar.returnRounds();
winNumber[rounds]++;
if(rounds < 10000)
{
//outFile << rounds <<"\n";
total += rounds;
successfulRuns++;
if(rounds > max)
max = rounds;
if(rounds < min)
min = rounds;
}
else
{
ties++;

}
cout << double(i)/double(trys)*100 << "\r";

}
cout << "100.0" << endl;
//outFile.close();

//Save the distribution of the number of rounds
ofstream outFile1;
outFile1.open("myfile1.txt");
for(int i = 1; i < 10001; i++)
{
outFile1 << winNumber[i] << endl;
}
outFile1.close();

//Save the results of the game
ofstream outFile2;
outFile2.open("myfile2.txt");
outFile2 << "The Number of Games Calculated Is: " << trys << endl;
outFile2 << "The Number of Ties is: " << ties << endl;
outFile2 << "The Maximum Number of Rounds Is: "<< max << endl;
outFile2 << "The Minimum Number of Rounds Is: " << min << endl;
outFile2 << "The # of Total Rounds Is: " << total << endl;
outFile2 << "The Average Number of Rounds Is: " << total/double(successfulRuns) << endl;

//Display the results of the game
cout << "The Number of Games Calculated Is: " << trys << endl;
cout << "The Number of Ties is: " << ties << endl;
cout << "The Maximum Number of Rounds Is: "<< max << endl;
cout << "The Minimum Number of Rounds Is: " << min << endl;
cout << "The # of Total Rounds Is: " << total << endl;
cout << "The Average Number of Rounds Is: " << total/double(successfulRuns) << endl;

system("PAUSE");
return EXIT_SUCCESS;
}


Finally, time for some results. First, to preface all of these results, I do not believe them to be accurate. I am confident that they are in no way comprehensive as I have earlier talked about the number of possible games to be in the order of 52!, a number many magnitudes larger than 50,000. I've already started work on a more accurate and simpler way of playing war, although less like the actual game, more useful for statistical purposes.

My first discovery when I ran the code is that I would run into infinite loops. Basically, I came to the conclusion that a game of war could be a tie based on the fact the players eventually run into a cycle where they end up playing the same hands over and over again.

Here are the results that were returned by my program:

The Number of Games Calculated Is: 50000
The Number of Ties is: 382
The Maximum Number of Rounds Is: 9798
The Minimum Number of Rounds Is: 9
The # of Total Rounds Is: 19431676
The Average Number of Rounds Is: 391.626


I simply put the cap on the game at 10,000 because I was not able to find a game which lasted longer than 9798 rounds. However, this is not to say that a game could last longer than this. I was not able to identify a game which lasted longer than this in my testing.

The horizontal axis is the number of rounds the game took to complete.
The vertical axis is the number of times out of 50,000 that the game was competed in that number of rounds.


The above graph is generated form the raw data on the number on the amount of times each game went a certain number of rounds. Notice the dot at 10,000 this is the games that tied or whose number of rounds is greater than 10,000. It is obvious that there is a very sharp spike to the left of the graph. The number of rounds that occurred the most (ignoring the 10,000 maximum) in the data was 61 rounds. A game of War ended after 61 rounds 314 times out of the 50000 games total. That is equal to 0.628% of the time.

The above graph begins to indicate some broader trends but is not percice enough to actually identify them. Lets focus in on only games that took less than 1000 rounds to complete.

The horizontal axis is the number of rounds the game took to complete.
The vertical axis is the number of times out of 50,000 that the game was competed in that number of rounds.

The above graph clearly indicates that there are two distinct curves: the first is a lower curve which has more frequency of happening but a wider range, the second is a higher curve which has less frequency, but a much steeper slope.

Another interesting point to note is the fact the shortest game lasted only 9 rounds. This is interesting to point out because it is definitely possible to have even fewer rounds. This only further emphasizes the fact that my data set is not comprehensive.

I would also like to note that in my program the game is played perfectly. That is, no cards are mixed up and a player puts the cards back into his deck in a very predictable manner.

I would like to do further analysis on this data, but it will have to wait. Due to me fears that this algorithm is not accurate, I will post a much more through analysis of the game of War after I rewrite my code from scratch. I expect to publish my new (more through) findings after I complete the code and get some free time to actually think about some of the intricacies of the problem.

No comments: