12
\$\begingroup\$

I am in the process of creating a new simple game in mobile and I've spent several days on the following part.

For simplicity, let's say that I have two fighters. The only attribute of them is Attack and Defence. When the first attacks, the only thing that matters is the attack of him and the defence of the opponent. And vice versa.

They don't have equipment, items, stamina or health. Just Attack vs Defence.

Example:

  • Fighter 1:

    Attack:50, Defence: 35

  • Fighter 2:

    Attack 20, Defence: 80

The fighting process will be just a single attack which will determine the winner. So, no multiple attacks or rounds. I don't want to make it deterministic, but add a light version of unexpected. A fighter with lower attack will be able to win another fighter with higher defence (but of course not every time)

My first idea was to make it linear and call a uniform random number generator.

If Random() < att1 / (att1 + def2) {
    winner = fighter1
} else {
    winner = fighter2
} 

Example with attack 50 and defence 80, the attacking fighter will have about 38% to win. However, it seems to me that the unexpected is too far and worst fighters will win a lot.

I was wondering how you have worked on similar situations.

P.S. I searched a lot in this QnA and other sources and I found similar questions mentioned as too broad for SE. But those have had many attributes, weapons, items, classes etc that could make it too complicated. I think my version is far simpler to fit it in the QnA style of the SE.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ What are the cases you are looking for? What range of values for attack and defence are you looking at and should any two numbers in those ranges ever have a fixed outcome? For example, can a fighter with attack 10 defeat a fighter at defence 90? \$\endgroup\$
    – Niels
    Feb 24, 2016 at 10:05
  • \$\begingroup\$ @user2645227 I could say that the range is between 1 and 400. No, I don't want to have any deterministic decisions and give the possibility to attack 1 win the defence 400, but in really rare cases. \$\endgroup\$
    – Tasos
    Feb 24, 2016 at 10:15
  • 1
    \$\begingroup\$ So if you Take Att(min)-def(max) and Att(max)-def(min) that gives you a range of 800 from -400 to +400. You'll want your random range to cover the entire range. Defence - Attack will give you a scaling margin in the form of a threshold you'll need to hit to win. This should reduce the randomness a bit. To further centralize the results you can use Philipps example or fiddle around in anydice until you hit the curve you are looking for. \$\endgroup\$
    – Niels
    Feb 24, 2016 at 11:56

3 Answers 3

24
\$\begingroup\$

If you want your fight results to be more predictable but not completely deterministic, have a best of n system.

Repeat the fight n times (where n should be an uneven number) and declare the combatant the winner who won more often. The larger your value for n the less surprise wins and losses you will have.

const int FIGHT_REPETITONS = 5 // best 3 of 5. Adjust to taste.

int fighter1wins = 0;
int fighter2wins = 0;

for (int i = 0; I < FIGHT_REPETITONS; I++) {

    If (Random() < att1 / (att1 + def2)) {
        fighter1wins++;
    } else {
        fighter2wins++;
    } 

}

If (fighter1wins > fighter2wins) {
    winner = fighter1
} else {
    winner = fighter2
} 

This system only works in the special case where a fight is a simple binary result of win or lose. When a combat has more complex results, like when the winner still loses some hit points depending on how close the win was, this approach doesn't work anymore. A more general solution is to change the way you generate random numbers. When you generate multiple random numbers and then take the average, the results will cluster near the center of the range and more extreme results will be more rare. For example:

double averagedRandom3() {
    return (Random() + Random() + Random()) / 3.0;
}

will have a distribution curve like this:

Distribution of 3d20 / 3

(picture courtesy of anydice - a really useful tool for designing game mechanic formulas which involve randomness, not just for tabletop games)

In my current project I am using a helper-function which allows to set an arbitrary sample size:

double averagedRandom(int averageness) {
     double result = 0.0;
     for (var i = 0; i < averageness; i++) {
         result += Random();
     }
     return result / (double)averageness;
}
\$\endgroup\$
8
  • \$\begingroup\$ Seems a better approach. One question. In the averagedRandom3() function, should you use + instead of * or I misunderstood what it does? \$\endgroup\$
    – Tasos
    Feb 24, 2016 at 10:33
  • \$\begingroup\$ @Tasos yes, should be +, not *. I also have a random-function which multiplies multiple samples. This gives you a random number function with a strong bias for lower values, which can also be useful in some situations. \$\endgroup\$
    – Philipp
    Feb 24, 2016 at 10:38
  • 1
    \$\begingroup\$ I will keep the question open for 1-2 days and if I don't have another answer, I will choose yours. I have upvoted it but want to give the chance for other answers too if you don't mind. \$\endgroup\$
    – Tasos
    Feb 24, 2016 at 10:41
  • \$\begingroup\$ I think this answer already get enough votes that makes this answer eligible for marking it as answer :P \$\endgroup\$ Feb 24, 2016 at 13:29
  • 1
    \$\begingroup\$ I would also be curious if some people comes up with alternative approaches. One person downvoted this answer. Maybe they would like to provide an alternative one. \$\endgroup\$
    – Philipp
    Feb 24, 2016 at 14:33
8
\$\begingroup\$

This is what I used to determine the winner of a battle in my Lords of Conquest Imitator applet. In this game, similar to your situation, there is just an attack value and a defense value. The probability that the attacker wins is greater the more points the attacker has, and less the more points the defense has, with equal values evaluating to a 50% chance of the attack succeeding.

Algorithm

  1. Flip a random coin.

    1a. Heads: defense loses a point.

    1b. Tails: heads loses a point.

  2. If both defense and attacker still have points, go back to step 1.

  3. Whoever is down to 0 points loses the battle.

    3a. Attacker down to 0: Attack fails.

    3b. Defense down to 0: Attack succeeds.

I wrote it in Java, but it should be easily translatable to other languages.

Random rnd = new Random();
while (att > 0 && def > 0)
{
    if (rnd.nextDouble() < 0.5)
        def--;
    else
        att--;
}
boolean attackSucceeds = att > 0;

An Example

For example, let's say that att = 2 and def = 2, just to make sure that the probability is 50%.

The battle will be decided in a maximum of n = att + def - 1 coin flips, or 3 in this example (it's essentially a best of 3 here). There are 2n possible combinations of coin flips. Here, "W" means the attacker won the coin flip, and "L" means the attacker lost the coin flip.

L,L,L - Attacker loses
L,L,W - Attacker loses
L,W,L - Attacker loses
L,W,W - Attacker wins
W,L,L - Attacker loses
W,L,W - Attacker wins
W,W,L - Attacker wins
W,W,W - Attacker wins

The attacker wins in 4/8, or 50% of the cases.

The Math

The mathematical probabilities arising from this simple algorithm are more complicated than the algorithm itself.

The number of combinations where there exactly x Ls is given by the combination function:

C(n, x) = n! / (x! * (n - x)!)

The attacker wins when there are between 0 and att - 1 Ls. The number of winning combinations is equal to the sum of combinations from 0 through att - 1, a cumulative binomial distribution:

    (att - 1)
w =     Σ     C(n, x)
      x = 0

The probability of the attacker winning is w divided by 2n, a cumulative binomial probability:

p = w / 2^n

Here is the code in Java to compute this probability for arbitrary att and def values:

/**
 * Returns the probability of the attacker winning.
 * @param att The attacker's points.
 * @param def The defense's points.
 * @return The probability of the attacker winning, between 0.0 and 1.0.
 */
public static double probWin(int att, int def)
{
    long w = 0;
    int n = att + def - 1;
    if (n < 0)
        return Double.NaN;
    for (int i = 0; i < att; i++)
        w += combination(n, i);

    return (double) w / (1 << n);
}

/**
 * Computes C(n, k) = n! / (k! * (n - k)!)
 * @param n The number of possibilities.
 * @param k The number of choices.
 * @return The combination.
 */
public static long combination(int n, int k)
{
    long c = 1;
    for (long i = n; i > n - k; i--)
        c *= i;
    for (long i = 2; i <= k; i++)
        c /= i;
    return c;
}

Testing code:

public static void main(String[] args)
{
    for (int n = 0; n < 10; n++)
        for (int k = 0; k <= n; k++)
            System.out.println("C(" + n + ", " + k + ") = " + combination(n, k));

    for (int att = 0; att < 5; att++)
        for (int def = 0; def < 10; def++)
            System.out.println("att: " + att + ", def: " + def + "; prob: " + probWin(att, def));
}

Output:

att: 0, def: 0; prob: NaN
att: 0, def: 1; prob: 0.0
att: 0, def: 2; prob: 0.0
att: 0, def: 3; prob: 0.0
att: 0, def: 4; prob: 0.0
att: 1, def: 0; prob: 1.0
att: 1, def: 1; prob: 0.5
att: 1, def: 2; prob: 0.25
att: 1, def: 3; prob: 0.125
att: 1, def: 4; prob: 0.0625
att: 1, def: 5; prob: 0.03125
att: 2, def: 0; prob: 1.0
att: 2, def: 1; prob: 0.75
att: 2, def: 2; prob: 0.5
att: 2, def: 3; prob: 0.3125
att: 2, def: 4; prob: 0.1875
att: 2, def: 5; prob: 0.109375
att: 2, def: 6; prob: 0.0625
att: 3, def: 0; prob: 1.0
att: 3, def: 1; prob: 0.875
att: 3, def: 2; prob: 0.6875
att: 3, def: 3; prob: 0.5
att: 3, def: 4; prob: 0.34375
att: 3, def: 5; prob: 0.2265625
att: 3, def: 6; prob: 0.14453125
att: 3, def: 7; prob: 0.08984375
att: 4, def: 0; prob: 1.0
att: 4, def: 1; prob: 0.9375
att: 4, def: 2; prob: 0.8125
att: 4, def: 3; prob: 0.65625
att: 4, def: 4; prob: 0.5
att: 4, def: 5; prob: 0.36328125
att: 4, def: 6; prob: 0.25390625
att: 4, def: 7; prob: 0.171875
att: 4, def: 8; prob: 0.11328125

Observations

The probabilities are 0.0 if the attacker has 0 points, 1.0 if the attacker has points but the defense has 0 points, 0.5 if the points are equal, less than 0.5 if the attacker has less points than the defense, and greater than 0.5 if the attacker has more points than the defense.

Taking att = 50 and def = 80, I needed to switch to BigDecimals to avoid overflow, but I get a probability of about 0.0040.

You can make the probability closer to 0.5 by changing the att value to be the average of the att and def values. Att = 50, Def = 80 becomes (65, 80), which yields a probability of 0.1056.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Another interesting approach. The algorithm could also be easily visualized, which could look quite exciting. \$\endgroup\$
    – Philipp
    Feb 25, 2016 at 10:11
5
\$\begingroup\$

You could modify the attack by a random number sampled from a normal distribution. This way most of the time the result will be what you expect, but occasionally a higher attack will lose against a lower defense or a lower attack will win against a higher defense. The probability of this happening will get smaller as the difference between attack and defense increases.

if (att1 + norm(0, sigma) - def2 > 0) {
  winner = fighter1;
}
else {
  winner = fighter2;
}

The function norm(x0, sigma) returns a float sampled from a normal distribution centered at x0, with standard deviation sigma. Most programming languages provide a library with such a function, but if you want to make it yourself have a look at this question. You would have to adjust sigma such that it 'feels right', but a value of 10-20 might be a good place to start.

For a few sigma values, the probability of victory for a given att1 - def2 looks like this: Probability of victory

\$\endgroup\$
1
  • \$\begingroup\$ It might also be worth pointing out that normal distributed values have no actual bounds, so when using normal-distributed random values in a game it can make sense to clamp the result to avoid the unlikely but not impossible situation of very extreme values being generated which might break the game. \$\endgroup\$
    – Philipp
    Feb 24, 2016 at 15:51

Not the answer you're looking for? Browse other questions tagged .