7
\$\begingroup\$

I wrote a Risk battle simulator that returned the odds of every possible outcome and put it up to be reviewed here. I used the comments to improve it, and am wondering if it can be optimized further.

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

using namespace std;

class battle {
    public:
        int attackers;
        int defenders;
        float odds;
               battle (int a, int d, float o) {
            attackers = a;
            defenders = d;
            odds = o;
        }
};

void submain(int, int);
void cleaner(vector<battle>&);
void sorter(battle);
void a1d1(battle);
void a1d2(battle);
void a2d1(battle);
void a2d2(battle);
void a3d1(battle);
void a3d2(battle);
void giveoutput();
int oddssize();

vector<float> attack_wins, defend_wins;
vector<battle> outcomes;

int main() {
    int attackers, defenders;
    cout << "Enter number of attackers: ";
    cin >> attackers;
    cout << "Enter number of defenders: ";
    cin >> defenders;

    submain(attackers, defenders);

    giveoutput();
}

// The main part of the program
// Has the list of possibilities condensed, then has each possibility ran
void submain(int attackers, int defenders){
    attack_wins = vector<float>(attackers,0);
    defend_wins = vector<float>(defenders,0);
    outcomes.push_back(battle(attackers, defenders, 100));

    while (!outcomes.empty()){
        vector<battle> list = outcomes;
        outcomes.clear();
        cleaner(list);

        for (int l = 0; l < list.size(); l++){
            //cerr << "    " << l << endl;
            sorter(list[l]);
        }
    }
}

// Condenses the list of outcomes
// The sum of the attackers and defenders needs to equal the static number,
// otherwise it's kept to the side
void cleaner(vector<battle>& list){
    static int count;
    static bool fastshrink = 1;
    count -= 1 + fastshrink;

    if(count < list[0].attackers + list[0].defenders){
        count = list[0].attackers + list[0].defenders;
        fastshrink = 1;
    }
    if(min(list.back().attackers, list[0].defenders) <= 1)
        fastshrink = 0;

    for (int l1 = 0; l1 < list.size(); l1++){
        battle& b1 = list[l1];

        if (b1.attackers + b1.defenders < count) {
            outcomes.push_back(b1);
            list.erase(list.begin() + l1--);
            continue;
            }

        for (int l2 = l1+1; l2 < list.size(); l2++){
            battle b2 = list[l2];
            if (b1.attackers == b2.attackers && b1.defenders == b2.defenders){
                b1.odds += b2.odds;
                list.erase(list.begin() + l2--);
            }
        }
    }
}

// Either puts the odds into the correct array (if the battle is over)
// or decides which function to use (if the battle is still going on)
void sorter(battle fight) {
    switch(fight.attackers) {
        case 0:
            defend_wins[fight.defenders-1] = fight.odds;
            break;
        case 1:
            switch(fight.defenders) {
                case 0:
                    attack_wins[fight.attackers-1] = fight.odds;
                    break;
                case 1:
                    a1d1(fight);
                    break;
                default:
                    a1d2(fight);
                    break;
            }
            break;
        case 2:
            switch(fight.defenders) {
                case 0:
                    attack_wins[fight.attackers-1] = fight.odds;
                    break;
                case 1:
                    a2d1(fight);
                    break;
                default:
                    a2d2(fight);
                    break;
            }
            break;
        default:
            switch(fight.defenders) {
                case 0:
                    attack_wins[fight.attackers - 1] = fight.odds;
                    break;
                case 1:
                    a3d1(fight);
                    break;
                default:
                    a3d2(fight);
                    break;
            }
            break;
    }
}

// Individual battles' functions
// Figures out the number of times that the attacker/defender wins the first time it's called,
// and creates new possibilities to be condensed based on those numbers
void a1d1( battle fight) {
    static int ATK = 0;
    static int DEF = 0;
    static int SUM = 0;

    if(!SUM) {
        for(int a1 = 1; a1 <= 6; a1++){
            for(int d1 = 1; d1 <= 6; d1++){
                SUM++;
                if(a1 > d1)
                    ATK++;
                else
                    DEF++;
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 1, fight.odds * ATK /SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders, fight.odds * DEF / SUM));
}

void a1d2(battle fight) {
    static int ATK = 0;
    static int DEF = 0;
    static int SUM = 0;

    if(!SUM) {
        for(int a1=1;a1<=6;a1++){
            for(int d1=1;d1<=6;d1++){
                for(int d2=1;d2<=6;d2++){
                    int D1=max(d1,d2);
                    SUM++;
                    if(a1>D1)
                        ATK++;
                    else
                        DEF++;
                }
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 1, fight.odds * ATK / SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders, fight.odds * DEF / SUM));
}

void a2d1( battle fight) {
    static int ATK = 0;
    static int DEF = 0;
    static int SUM = 0;

    if(!SUM) {
        for(int a1 = 1; a1 <= 6; a1++){
            for(int a2 = 1; a2 <= 6; a2++){
                for(int d1 = 1; d1 <= 6; d1++){
                    int A1= max(a1, a2);
                    SUM++;
                    if(A1 > d1)
                        ATK++;
                    else
                        DEF++;
                }
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 1, fight.odds * ATK / SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders, fight.odds * DEF / SUM));
}

void a2d2(battle fight) {
    static int ATK = 0;
    static int TIE = 0;
    static int DEF = 0;
    static int SUM = 0;

     if(!SUM) {
        for(int a1=1; a1 <= 6; a1++){
            for(int a2 = 1; a2 <= 6; a2++){
                for(int d1 = 1; d1 <= 6; d1++){
                    for(int d2 = 1; d2 <= 6; d2++){
                        int A1 = max(a1, a2);
                        int A2 = min( a1, a2);
                        int D1 = max(d1, d2);
                        int D2 = min(d1, d2);
                        switch((A1 > D1) + (A2 > D2)){
                            case 0:
                                DEF++;
                                SUM++;
                                break;
                            case 1:
                                TIE++;
                                SUM++;
                                break;
                            case 2:
                                ATK++;
                                SUM++;
                                break;
                        }
                    }
                }
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 2, fight.odds * ATK / SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders - 1, fight.odds * TIE / SUM));
    outcomes.push_back(battle(fight.attackers - 2, fight.defenders, fight.odds * DEF / SUM));
}

void a3d1( battle fight) {
    static int ATK = 0;
    static int DEF = 0;
    static int SUM = 0;

    if(!SUM) {
        for(int a1=1; a1 <= 6; a1++){
            for(int a2 = 1; a2 <= 6; a2++){
                for(int a3 = 1; a3 <= 6; a3++){
                    for(int d1 = 1; d1 <= 6; d1++){
                        SUM++;
                        int A1 = max(a1, max(a2, a3));
                        if(A1 > d1)
                            ATK++;
                        else
                            DEF++;
                    }
                }
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 1, fight.odds * ATK / SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders, fight.odds * DEF / SUM));
}

void a3d2(battle fight) {
    static int ATK = 0;
    static int TIE = 0;
    static int DEF = 0;
    static int SUM = 0;

    if(!SUM) {
        for(int a1=1; a1 <= 6; a1++){
            for(int a2 = 1; a2 <= 6; a2++){
                for(int a3 = 1; a3 <= 6; a3++){
                    for(int d1 = 1; d1 <= 6; d1++){
                        for(int d2 = 1; d2 <= 6; d2++){
                            int A1 = max(a1, max(a2, a3));
                            int A2;
                            int D1 = max(d1, d2);
                            int D2 = min(d1, d2);

                            if(a1 == A1)
                                A2 = max(a2, a3);
                            else if(a2 == A1)
                                A2 = max(a1, a3);
                            else
                                A2 = max(a1, a2);

                            switch((A1 <= D1) + (A2 <= D2)){
                                case 2:
                                    DEF++;
                                    SUM++;
                                    break;
                                case 1:
                                    TIE++;
                                    SUM++;
                                    break;
                                case 0:
                                    ATK++;
                                    SUM++;
                                    break;
                            }
                        }
                    }
                }
            }
        }
    }

    outcomes.push_back(battle(fight.attackers, fight.defenders - 2, fight.odds * ATK / SUM));
    outcomes.push_back(battle(fight.attackers - 1, fight.defenders - 1, fight.odds * TIE / SUM));
    outcomes.push_back(battle(fight.attackers - 2, fight.defenders, fight.odds * DEF / SUM));
}

// Prints the results on the screen
void giveoutput() {
    cout << fixed << setprecision(4) << endl;
    float odds = 0;
    int atks = int(2 + floor(log(attack_wins.size()) / log(10)));
    int defs = int(2 + floor(log(defend_wins.size()) / log(10)));
    int odd = oddssize();

    for(int loop = attack_wins.size()-1; loop >= 0; loop--) {
        cout << "A:" << setw(atks) << loop+1;
        cout << " | D:" << setw(defs) << 0 << " | Odds: ";
        cout << setw(odd) << attack_wins[loop] << "%";
        odds += attack_wins[loop];
        cout << " | Running odds: " << setw(7) << odds << "%" << endl;
    }

    //cout << "------|-------|---------------" << endl;
    for (int l = atks + 3; l > 0; l--){
        cout << "-";
    }
    cout << "|";
    for (int l = defs + 4; l > 0; l--){
        cout << "-";
    }
    cout << "|";
    for (int l = odd + 8; l >= 0; l--){
        cout << "-";
    }
    cout << "|-----------------------" << endl;
    odds = 100 - odds;

    for(int loop = 0; loop < defend_wins.size(); loop++) {
        cout << "A:" << setw(atks) << 0 << " | D:";
        cout << setw(atks) << loop+1 << " | Odds: ";
        cout << setw(odd) << defend_wins[loop] << "%";
        cout << " | Running odds: " << setw(7) << odds << "%" << endl;
        odds -= defend_wins[loop];
    }
    cout << endl;
}

int oddssize(){
    for (int l = 0; l < attack_wins.size(); l++){
        if (attack_wins[l] >= 10)
            return 7;
    }

    for (int l = 0; l < defend_wins.size(); l++){
        if (defend_wins[l] >= 10)
            return 7;
    }

    return 6;

}

Notes

  • I know I shouldn't use 'using namespace std'. Don't bring it up.
  • I have trouble writing comments. Let me know if something is confusing.
  • The individual battle functions having find the odds only the first time they're ran. I could hard wire the odds, but some people play with extra rules, and I wanted to keep it easy to change.
\$\endgroup\$
1
\$\begingroup\$

I still believe your code is too complex and lengthy. In 62 lines (excluding whitespace and comments), this code produces the same results as yours, up to minor formatting issues.

I don't think this constitutes an "independent solution with no justification", because it really just untangles your code.

#include <iostream>

int main() {
  int attackers, defenders, i, j;
  double arun=0.;
  std::cout << "Enter number of attackers: ";
  std::cin >> attackers;
  std::cout << "Enter number of defenders: ";
  std::cin >> defenders;

  printf("\n");

  // I use the highest number as an index, so adding 1
  double odds[attackers+1][defenders+1];

  // because I'm going to print the "defense wins" section backwards,
  // I'll need to store values of running odds for defense
  double druns[defenders+1];

  // initialize all elts to 0 (annoyed C++ doesnt do this):
  // "variable-sized object `odds' may not be initialized"
  for (i=0; i<=attackers; i++) {
    for (j=0; j<=defenders; j++) {
      odds[i][j] = 0.;
    }
  }

  // the starting condition is true by definition
  odds[attackers][defenders] = 1.;

  for (i = attackers; i>=1; i--) {
    for (j = defenders; j>=1; j--) {

      // special case: 1 attacker, 1 defender
      if (i==1 && j==1) {
    odds[1][0] += 15./36.*odds[1][1];
    odds[0][1] += 21./36.*odds[1][1];
    continue;
      }

      // special case: 2 attackers, 1 defender
      if (i==2 && j==1) {
    odds[2][0] += 125./216.*odds[2][1];
    odds[1][1] += 91./216.*odds[2][1];
    continue;
      }

      // special case 1 attackers, 2+ defenders

      if (i==1 && j>=2) {
    odds[1][j-1] += 55./216.*odds[i][j];
    odds[0][j] += 161./216.*odds[i][j];
    continue;
      }

      // special case 3+ attackers, 1 defender
      if (j==1 && i>=3) {
    odds[i][0] += odds[i][j]*855./1296.;
    odds[i-1][1] += odds[i][j]*441./1296.;
    continue;
      }

      // special case 2 attackers, 2+ defenders
      if (i==2 && j>=2) {
    odds[2][j-2] += 295./1296.*odds[i][j];
    odds[1][j-1] += 420./1296.*odds[i][j];
    odds[0][j] += 581./1296.*odds[i][j];
    continue;
      }

      // general case
      odds[i][j-2] += 2890./7776.*odds[i][j];
      odds[i-1][j-1] += 2611./7776.*odds[i][j];
      odds[i-2][j] += 2275./7776.*odds[i][j];
    }
  }

  for (i = attackers; i>=1; i--) {
    arun += odds[i][0];
    printf("A: %2d | D: 0 | Odds: %.4f%% | Running odds: %.4f%%\n", i, odds[i][0]*100., arun*100.);
  }

  printf("------|------|---------------|-----------------------\n");

  // compute druns
  druns[defenders] = odds[0][defenders];
  for (j = defenders-1; j>=1; j--) {druns[j] = druns[j+1] + odds[0][j];}

  for (j = 1; j<=defenders; j++) {
    printf("A: 0 | D: %2d | Odds: %.4f%% | Running odds: %.4f%%\n", j, odds[0][j]*100., druns[j]*100.);
  }

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I'd say that it solve it in a different way (I made a class to store my results so far, you stored them in arrays as you went), but I'll admit it's cleaner and more effective. The only thing I don't think is as good is that the odds are hard-wired in, while mine uses static variables to figure out the odds for itself (which is a lot of my code). I did this to make it easy to use for alternate rules. Ones I've seen include the attacker getting +1 on their highest dice, attacker getting 3 dice (but only using the top 2), and the attacker/defender (never both though) getting an 8-sided die. \$\endgroup\$ – Nevermore Apr 7 '16 at 21:44
  • \$\begingroup\$ @Nevermore Fair enough, but it appears that you call a3d2() multiple times. Couldn't you just compute the probabilitys once and store them? Also how about attack(int attackers, int defenders) instead of a separate method for each special case combination? \$\endgroup\$ – Barry Carter Apr 8 '16 at 3:10
  • \$\begingroup\$ It does compute it once. I declare static variables in the methods, and I require them to still be 0 to compute their values. That's what the 'if(!SUM)' in every one is. I'll admit that it is nice to have only one method though. \$\endgroup\$ – Nevermore Apr 8 '16 at 3:29
3
\$\begingroup\$

Don't use using namespace std. (Yes, you said don't bring it up. Doesn't mean I have to listen to you. Similar principles tend to apply in the real world.)


Your indentation is a bit screwy; it actually took me longer than I care to admit to figure out that there wasn't a word or two blanked out in

    float odds;
           battle (int a, int d, float o) {

Also, at least for the free (non-inline-member-function) functions, I'd strongly advise putting a newline before the opening brace of the function. Almost every C++ codebase out there uses some variation on

void f()
{
    ...
}

and not

void f() {
    ...
}

There are exceptions, of course, but they're outnumbered by the non-exceptions.


Your use of global variables (lots of them) is a problem. Try to move them into the scopes of the functions that use them, instead of exposing them to the entire program.

Again I spent a few seconds staring at a line of code wondering if something was missing:

attack_wins = vector<float>(attackers,0);

This line certainly looks like it's missing an auto at the beginning! C++ isn't Python, after all. But it turns out that attack_wins is a global variable, and so this line is correct — it's merely an expensive and confusing way of writing

attack_wins.clear();

This is a code smell:

void a1d1(battle);
void a1d2(battle);
void a2d1(battle);
void a2d2(battle);
void a3d1(battle);
void a3d2(battle);

I have no specific suggestions for how to clean it up (I don't know Risk well enough, and haven't really thought about how to enumerate all the die rolls other than "run a naive simulation for each s in 1..6large number, using a random number generator that just returns the base-6 digits of s"), but it certainly smells like it could be written in about one-sixth the code you've got.

Actually, you yourself point out that each of these six functions could be a two-or-three-liner, but you wrote out all the nested loops and switches to make them "easy to change". Even so, I bet you could come up with a way to abstract out the idea of "roll M dice, roll N dice, compare them pairwise, summarize the result" that involves less code duplication than this.


void cleaner(vector<battle>& list)

Please don't use the word list to describe a std::vector. Use v, or vec, or something, but please not list. The only time you should use the word list in a C++ program is when you're referring to an actual std::list. (Which should basically never happen.)

The cleaner function has a couple of parts that I would characterize as... problematic. It's got a static int count, which looks like it wants to be a function parameter; and then it's got this static int fastshrink, which I'm not sure what that is. Turn those into function parameters, and/or get rid of them.

It seems like the non-problematic parts of this function could be replaced with just a couple lines of C++ code involving std::partition and std::accumulate (or a plain old for-loop with a += inside it, if you prefer). You definitely shouldn't need to be repeatedly eraseing from the middle of the vector; that's one of the slowest things you can do, and it's 100% unnecessary, if you start by partitioning the vector so that all the items you're eventually going to erase wind up at the end of the vector.

\$\endgroup\$
2
\$\begingroup\$

Program design

The main issues with your program is the overall design. I would recommend to study object-oriented programming on beginner level before even picking up C++, or any other programming language.

  • What's positive is that you have managed rather well to separate the user interface from the algorithms.

  • Having a function "submain", which has no purpose of it own, isn't useful. Never try to keep main() plain by simply hiding all code elsewhere "under the carpet" in another function. The worst possible way to write main() is int main() { do_stuff(); }, because it means that the do_stuff function is 100% superfluous.

    So just get rid of the "submain" and put all that code in main(), it will make your program more readable.

  • Get rid of the global variables, this is universally bad practice for many reasons. There is absolutely no need to have them global. Put them inside main.

  • You aren't writing object-oriented code. Before you write the first line of code, you should consider what classes you might have use for. For a simple program like this, you likely don't need many. It might even be best to have one single class that handles all functionality.

    You have already identified the need for a "battle" class, which might make sense. But currently you are just using it as some sort of glorified array/container where you dump data and not as an object-oriented class. A better name might be "battle_calculator" or similar.

    Picture yourself coding a Risk game. You want to integrate a battle odds calculator inside the game. It would then be handy if you had an autonomous class "battle_calculator" which you could just grab as-is. That class provides an interface to do all the work.

    Suppose you would use it like this, for example:

    battle_calculator bc (attackers, defenders, odds);  
    float result = bc.calculate();
    

    This seems to make sense. Meaning that you should include all of the functionality inside this class.

  • The class should have no public data members, this is almost always bad design (read up on private encapsulation). The only thing that needs to be public here is a default constructor (which you are currently lacking), the specific constructor and some public member functions.

    Note that you can skip the need of a default constructor if you rewrite your current one as this:

    battle (int a=0, int d=0, float o=0);
    
  • All the functions need to be integrated into the class as private members. You need to create some sort of public interface function to the caller.

  • All the functions a1d1, a1d2 etc needs to be replaced with a single function with parameters, that covers all cases. I don't know enough of the algorithm to suggest such a function, but looking at the code of those functions, it doesn't seem hard to achieve, since they are all very similar.

Dangerous practice

  • Avoid using non-conditional branching upwards in your program, with keywords such as goto or continue. Such branching is always the sign of bad program design. And it is dangerous, since it makes the code harder to read, and makes it very easy to create bugs during maintenance.

    It is best to avoid the goto and continue keywords entirely: even though they could in some circumstances be used is sensible ways, they are completely superfluous language features and can always be replaced with something else.

    In your specific case, the continue keyword could easily have been avoided with a simple if-else.

  • list is a poor choice of variable name, as C++ actually has a standard container called std::list.

  • Having multiple static variables inside functions is not a good idea, as it makes it impossible to reuse the functions over and over again in any sensible way. (Also, on a more advanced topic, it makes the code non-re-entrant.) All of these statics can likely be replaced either by function parameters or by private variables of the class.

  • Never use the ++ and -- operators together with other operators in the same expression. Because these operators introduce side effects and the language might not guarantee when and how those side effects are evaluated.

    For example list.begin() + l2-- will work, by coincidence, but something like l2++ + list.begin() + l2-- is a severe bug, there are no guarantees how such code is executed, it invokes undefined behavior.

    Instead of list.erase(list.begin() + l1--); write

    list.erase(list.begin() + l1);
    l1--;
    

    As a bonus, the code will also turn more readable.

  • Of minor note, picking the variable name l (L) is a bad idea, as it may look identical to 1 (one) in some code editors. l1 will be unreadble in such editors.

Style

  • You need to be consistent with how you name your variables, functions and types. For example, suddenly you are using CAPITALS when declaring a variable, for no apparent reason.

    This is very confusing for C++ programmers, the industry standard style is to reserve capitals for declaring constants and macros.

  • You need to be consistent with braces after if for etc statements. Sometimes you use them, sometimes you don't. Overall, it is strongly recommended to always use {} after every such statement, even if there is just a single line following, as that reduces the probability of writing bugs quite a lot. Google "Apple goto fail bug" to see how expensive it can turn out if you don't use braces.

  • You need to be consistent with how you write loops. You have these different styles in the same program:

    • for(int i=0;i<n;i++){
    • for(int i=0;i<n;i++) {
    • for(int i=0; i<n; i++){
    • for(int i=0; i<n; i++) {

    I would strongly recommend to use the last one, as it is most readable by far.

    (As for whether placing the brace on the same line or a line of it's own, that's 100% subjective opinion, so I won't comment on that. Either style is fine as they are both common.)

  • Similarly, you need to be consistent with the use of spaces when declaring functions.

  • To improve readability of very long lines, consider splitting such a line into several. Particularly when calling a function with lots of parameters, you could put each parameter on a line of its own:

    outcomes.push_back( battle(fight.attackers, 
                               fight.defenders - 1, 
                               fight.odds * ATK /SUM) );
    

    Or even more readable:

    battle b (fight.attackers,
              fight.defenders - 1,
              fight.odds * ATK /SUM);
    
    outcomes.push_back(b);
    

    Note that declaring temporary variables for readability like this, has absolutely no outcome on program performance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.