Risk battle simulator v1

Question

I've written a program to find the odds of either side winning a battle in Risk, and how many men they would have left. I've finished, but I feel that it can be improved since it doesn't function if the battle gets too big (with "too big" being ridiculously small, to the point of being near-useless). Can anybody find any ways to improve it?

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;

struct Fraction {  //Fraction class used for adding/multiplying the odds of rolls together
    unsigned long long top;
    unsigned long long bottom;
};

struct FractionMathException : public exception {  // Error code (to keep the system from creating bad numbers)
  const char * what () const throw ()
  {
    return "C++ Exception";
  }
};

void sorter(int attackers,int defenders,Fraction odds);    //Declaring functions to use later
void a1d1(int attackers,int defenders,Fraction odds);
void a1d2(int attackers,int defenders,Fraction odds);
void a2d1(int attackers,int defenders,Fraction odds);
void a2d2(int attackers,int defenders,Fraction odds);
void a3d1(int attackers,int defenders,Fraction odds);
void a3d2(int attackers,int defenders,Fraction odds);
unsigned long long LCM(unsigned long long a, unsigned long long b);
Fraction Add(Fraction a, Fraction b);
Fraction Multiply(Fraction a, Fraction b);
Fraction Frac(int a,int b);

vector<Fraction> attack_wins,defend_wins; //Keeps track of how many times the attackers and defenders win. Which slot is determined by how many men are left standing.

int main(){
    int attackers,defenders;

    cout << "Enter number of attackers: "; // find out how many men we're dealing with
    cin >> attackers;
    cout << "Enter number of defenders: ";
    cin >> defenders;

    attack_wins = vector<Fraction>(attackers,Frac(0,1));  // Set attack_wins and defend_wins to the correct sizes, and set every slot to 0/1 (so 0)
    defend_wins = vector<Fraction>(defenders,Frac(0,1));

    try{
        sorter(attackers,defenders,Frac(1,1));   // Run the main part of the program using the number of attackers, defenders, and a 100% chance of this happening.

        cout << endl << fixed;
        for(int loop=attack_wins.size()-1; loop>=0; loop--){                                     // Output attacker wins
            cout << "A:" << left << setw(2) << loop+1 << " | D:0  | Odds:" << right;
            cout << setw(9) << 100.0 * attack_wins[loop].top / attack_wins[loop].bottom << "%\n";
        }

        for(int loop=0; loop<defend_wins.size(); loop++){                                        // Output defender wins
            cout << "A:0  | D:" << left << setw(2) << loop+1 << " | Odds:" << right;
            cout << setw(9) << 100.0 * defend_wins[loop].top / defend_wins[loop].bottom << "%\n";
        }

        cout << endl;
    }
    catch(FractionMathException){
        cout << endl << "I'm sorry, but those numbers are too big for me to handle. Please try again." << endl;
    }
}

void sorter(int attackers,int defenders,Fraction odds){  // The main part of the program, either adds the odds to attack/defend_wins 
    switch(attackers){                                   // or sends it's input to the correct subfunction depending on the number of dice that can be rolled
        case 0:
            defend_wins[defenders-1] = Add(defend_wins[defenders-1],odds);  // If the attackers are dead, add the odds to the correct defenders slot
            break;
        case 1:
            switch(defenders){
                case 0:
                    attack_wins[attackers-1] = Add(attack_wins[attackers-1],odds); // If the defenders are dead, add the odds to the correct attackers slot
                    break;
                case 1:
                    a1d1(attackers,defenders,odds);
                    break;
                default:
                    a1d2(attackers,defenders,odds);
                    break;
                }
            break;
        case 2:
            switch(defenders){
                case 0:
                    attack_wins[attackers-1] = Add(attack_wins[attackers-1],odds); // See above
                    break;
                case 1:
                    a2d1(attackers,defenders,odds);
                    break;
                default:
                    a2d2(attackers,defenders,odds);
                    break;
            }
            break;
        default:
            switch(defenders){
                case 0:
                    attack_wins[attackers-1] = Add(attack_wins[attackers-1],odds); // See above
                    break;
                case 1:
                    a3d1(attackers,defenders,odds);
                    break;
                default:
                    a3d2(attackers,defenders,odds);
                    break;
            }
            break;
    }
}

void a1d1(int attackers,int defenders,Fraction odds){  // If the attacker uses 1 die and the defender uses 1 die
    sorter(attackers,defenders-1,Multiply(odds,Frac(5,12))); // Defender loses 1
    sorter(attackers-1,defenders,Multiply(odds,Frac(7,12))); // Attacker loses 1
}

void a1d2(int attackers,int defenders,Fraction odds){  // If the attacker uses 1 die and the defender uses 2 dice
    sorter(attackers,defenders-1,Multiply(odds,Frac(55,216))); // Defender loses 1
    sorter(attackers-1,defenders,Multiply(odds,Frac(161,216))); // Attacker loses 1
}

void a2d1(int attackers,int defenders,Fraction odds){  // If the attacker uses 2 dice and the defender uses 1 die
    sorter(attackers,defenders-1,Multiply(odds,Frac(125,216))); // Defender loses 1
    sorter(attackers-1,defenders,Multiply(odds,Frac(91,216))); // Attacker loses 1
}

void a2d2(int attackers,int defenders,Fraction odds){  // If the attacker uses 2 dice and the defender uses 2 dice
    sorter(attackers,defenders-2,Multiply(odds,Frac(295,1296))); // Defender loses 2
    sorter(attackers-1,defenders-1,Multiply(odds,Frac(35,108))); // Both lose 1
    sorter(attackers-2,defenders,Multiply(odds,Frac(581,1296))); // Attacker loses 2
}

void a3d1(int attackers,int defenders,Fraction odds){  // If the attacker uses 3 dice and the defender uses 1 die
    sorter(attackers,defenders-1,Multiply(odds,Frac(95,144))); // Defender loses 1
    sorter(attackers-1,defenders,Multiply(odds,Frac(49,144))); // Attacker loses 1
}

void a3d2(int attackers,int defenders,Fraction odds){  // If the attacker uses 3 dice and the defender uses 2 dice
    sorter(attackers,defenders-2,Multiply(odds,Frac(1445,3888))); // Defender loses 2
    sorter(attackers-1,defenders-1,Multiply(odds,Frac(2611,7776))); // Both lose 1
    sorter(attackers-2,defenders,Multiply(odds,Frac(2275,7776))); // Attacker loses 2
}

unsigned long long GCD(unsigned long long a, unsigned long long b) {  // Finds the Greatest Common Divisor (used in functions LCM, Add, and Multiply)
    unsigned long long c;                                             // Uses Euclid's algorithm (slightly modified version of stolen code)
    if(a>b){
        while (b > 0){
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    } else {
        while (a > 0) {
            c = b % a;
            b = a;
            a = c;
        }
        return b;
    }
}

unsigned long long LCM(unsigned long long a, unsigned long long b) { // Finds the Least Common Multiple (used in function Add)
    a /= GCD(a,b);
    return a*b;
}

Fraction Add(Fraction a, Fraction b){  // Adds two fractions (used to enter odds into attack_wins and defend_wins)
    unsigned long long gcd = GCD(a.bottom,b.bottom);
    unsigned long long top = ((a.top * b.bottom) + (b.top * a.bottom))/gcd;
    unsigned long long bottom = a.bottom * b.bottom / gcd;

    gcd = GCD(top,bottom);
    top /= gcd;
    bottom /= gcd;

    if (top > bottom)
        throw FractionMathException(); // If the numbers are too big for it to handle, send an error code.

    return Frac(top, bottom);
}

Fraction Multiply(Fraction a, Fraction b){ // Multiply two fractions (used to find odds between repetitions of sorter)
    if (a.top == a.bottom)
        return b;

    int gcd = GCD(a.top, b.bottom);  // Simplifies fractions (so it can handle larger numbers)
    a.top /= gcd;
    b.bottom /= gcd;

    gcd = GCD(b.top, a.bottom);
    b.top /= gcd;
    a.bottom /= gcd;

    unsigned long long top = a.top * b.top;
    unsigned long long bottom = a.bottom * b.bottom;

    gcd = GCD(top, bottom);  // Simplify again (since last time doesn't matter anymore)
    top /= gcd;
    bottom /= gcd;

    if (top > bottom)
        throw FractionMathException(); // If the numbers are too big for it to handle, send an error code.

    Fraction out={top,bottom};
    return out;
}

Fraction Frac(int a, int b){ // Just sends out a fraction (I hate making variables that I'll only use once unless they're in a loop)
    Fraction out = {a, b};
    return out;
}

Notes

• I'm sorry if it's hard to understand. I have a bad habit of not writing comments (which I've just added), so let me know if I need to explain something.
• I also have a habit of writing extremely long lines of code. I like to keep my editor at max size, and it's harder to tell when it's too long that way.
• The odds of an individual roll are correct and simplified (I found them using smaller, easier programs).
• The only reasons I feel comfortable asking are because
  1. I can't figure out how to fix this, and the concept of the fix can probably be used for other things
  2. I can't find any projects like this one anywhere on the web (I've tried, but I'll admit not as much as I could have)

---

EDIT: Thanks for all of the feedback. I've improved my program a lot, and have submitted it to be reviewed here.

Answer 1

I see a number of things that you could use to improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers).

Use appropriate #includes

This code is using std::exception but does not #include <exception>. Make sure that you #include all required headers. Even if your particular compiler doesn't complain, it's not portable code otherwise.

Be aware of numerical limitations

The code currently attempts to create a Fraction with this function

Fraction Frac(int a, int b){ 

But top and bottom within Fraction are both unsigned long long numbers which means that there is a huge range of possible numbers the can't be created with this function and that legitimate seeming fractions such as \$\frac{-1}{2}\$ will be completely misconstrued as the -1 gets silently reinterpreted as an unsigned long long.

Use object orientation

Because you're writing in C++, it would make sense to have methods that operate on a class such as Fraction be member functions rather than separate functions. You may not yet have learned about classes in C++, but they're one of the main strengths of C++ and something you should learn soon if you haven't already. For example, the code includes this:

Fraction Frac(int a, int b){ 
    Fraction out = {a, b};
    return out;
}

However, this would be much better expressed (and with fewer errors!) as a constructor:

class Fraction {
public:
    Fraction(unsigned long long numerator, unsigned long long denominator) :
        top{numerator},
        bottom{denominator}
    {}
private:
    unsigned long long top;
    unsigned long long bottom;
};

Express operations as member functions where practical

If we need to multiply two fractions together, the usual way to do that is to declare two functions; one is a member function of the Fraction class and the other is a free-standing function. In this case, the member function might be this:

Fraction &Fraction::operator*=(const Fraction &f2) { 
    top *= f2.top; 
    bottom *= f2.bottom; 
    return *this; 
}

The corresponding freestanding function is this:

Fraction operator*(Fraction f1, const Fraction &f2)
{
    f1 *= f2;
    return f1;
}

Note that in this case, the first value is passed by value (meaning that a copy is created) and the second value is passed as a const reference, which means that no copy is typically created. This is a very typical pattern for numerical objects of all kinds.

Don't Repeat Yourself (DRY)

This is a general principle that says if you find yourself writing near duplicate code mutiple times (such as a1d1 and a1d2 in this code), you should step back and consider instead how to write a single function that takes the only difference (the constant values of the odds) as a parameter. The parameters can then be stored in a const array instead of being embedded in the code, making the code shorter, easier to understand and easier to maintain.

Reconsider your algorithm

In this particular case, there doesn't seem to be much reason to create your own class of rational fractions. The code would be much simpler using simple doubles instead, with little losss of precision.

Answer 2

using namespace std;

Don't do that. You're not really saving much typing, and Risk easily avoidable name collisions. If there's one thing I know of c++, it's that using namespace std is a bad habit to lose.

void a1d1(int attackers,int defenders,Fraction odds);
void a1d2(int attackers,int defenders,Fraction odds);
void a2d1(int attackers,int defenders,Fraction odds);
void a2d2(int attackers,int defenders,Fraction odds);
void a3d1(int attackers,int defenders,Fraction odds);
void a3d2(int attackers,int defenders,Fraction odds);

It's not very clear what these methods mean at first glance. ...at second glance either. You should use meaningful identifiers - always. One shouldn't need to read the comments you put up on the implementations to know what they stand for.

That said, I think it might have been better (and a bit harder, but better) to do something more like this:

void calculate(int attackerArmies, int attackerDice, int defenderArmies, int defenderDice, Fraction odds);

And then, perhaps regroup armies and dice together into an appropriate data structure - note, I don't do c++, so take this recommendation with a grain of salt - the point I'm making is that both the attacker and the defender have armies and dice, and this looks like a great [missed] opportunity for an abstraction; this could turn the signature into something like this:

void calculate(std::tuple<int,int> attacker, std::tuple<int,int> defender, Fraction odds);

Most likely there's a more appropriate data type for this, but you get the idea. Perhaps something like this:

class Player
{
    int armies;
    int dice;

public:
    Player(int armies, int dice):
        armies(armies),
        dice(dice)
    {}
};

Which turns the signature into this:

void calculate(Player attacker, Player defender, Fraction odds);

Now, you're calling this a function, but it's returning void, and there's no indication that you're altering the parameters (this might be a language thing though, ...but it doesn't feel right anyway). How about another abstraction?

class BattleSettings
{
    Player attacker;
    Player defender;

public:
    BattleSettings(Player attacker, Player defender):
        attacker(attacker),
        defender(defender)
    {}
};

Now you could have this:

BattleSettings calculate(BattleSettings players, Fraction odds);

..and the implementation wouldn't sneakily modify the parameter values, but return a new BattleSettings value instead, containing the state (armies and dice) of each player.

As for the odds themselves, you've essentially hard-coded the whole thing - and these magic numbers stick out like a sore thumb. Best would be to actually calculate them.

Answer 3

Not being a C programmer I'm not going to try to write any code here. I still have some comments, though:

Your program is blowing up because you are trying to represent the odds as a fraction. You try to reduce the fraction but it's a hopeless task, it's quickly going to overflow. Carry your odds as a floating point value instead. Printing percentages would actually be easier to understand and it also lets you print cumulative percentages for any particular outcome, something you can't do with your fraction approach.

Second, there is a lot of code there that I would be handling with a lookup table instead. You have six possible battle conditions, each with the odds of the various possible losses. One array (2D if they're available these days, the last I touched C we didn't have them) of structures containing the outcomes. Static initialization if you have it (again, it wasn't available when I did C but that's a long, long time ago), otherwise initialize it when you start the routine.

Third, the overflow problem is masking it but you also have an O(2^n/2) algorithm here, that's going to be truly horrible for large battles. The problem is that you are walking a tree that divides three ways at every battle.

I would handle this totally differently:

Start out with an array of a pair of values: attackers lost and defenders lost. On each iteration you prepare a new array where each entry is the result of applying the results of the current battle to the previous result. This array replaces the array you were working with. Now you have an O(n^2) algorithm, it will run in sane time for any reasonable battle size.