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
Flip a random coin.
1a. Heads: defense loses a point.
1b. Tails: heads loses a point.
If both defense and attacker still have points, go back to step 1.
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.
