Właśnie tego określałem zwycięzcę bitwy w moim aplecie Lords of Conquest Imitator. W tej grze, podobnie jak w twojej sytuacji, jest tylko wartość ataku i wartość obrony. Prawdopodobieństwo, że atakujący wygra, jest tym większe, im więcej punktów ma atakujący, i tym mniej punktów ma obrona, przy równych wartościach stanowiących 50% szans na udany atak.
Algorytm
Rzuć losową monetą.
1a. Głowy: obrona traci punkt.
1b. Ogony: głowy tracą punkt.
Jeśli zarówno obrona, jak i atakujący nadal mają punkty, wróć do kroku 1.
Kto ma 0 punktów, przegrywa bitwę.
3a. Atakujący do 0: Atak kończy się niepowodzeniem.
3b. Obrona do 0: Atak się udaje.
Napisałem to w Javie, ale powinno być łatwe do przetłumaczenia na inne języki.
Random rnd = new Random();
while (att > 0 && def > 0)
{
if (rnd.nextDouble() < 0.5)
def--;
else
att--;
}
boolean attackSucceeds = att > 0;
Przykład
Załóżmy na przykład, że att = 2 i def = 2, aby upewnić się, że prawdopodobieństwo wynosi 50%.
Bitwa zostanie rozstrzygnięta w maksymalnej n = att + def - 1liczbie rzutów monetą lub 3 w tym przykładzie (w zasadzie jest to najlepsza z 3 tutaj). Istnieją 2 n możliwych kombinacji rzutów monetą. Tutaj „W” oznacza, że atakujący wygrał rzut monetą, a „L” oznacza, że atakujący stracił rzut monetą.
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
Atakujący wygrywa w 4/8, czyli 50% przypadków.
Matematyka
Prawdopodobieństwa matematyczne wynikające z tego prostego algorytmu są bardziej skomplikowane niż sam algorytm.
Liczba kombinacji, w których dokładnie x Ls jest podana przez funkcję kombinacji:
C(n, x) = n! / (x! * (n - x)!)
Atakujący wygrywa, gdy są pomiędzy 0i att - 1L. Liczba zwycięskich kombinacji jest równa sumie kombinacji od 0do att - 1, skumulowanego rozkładu dwumianowego:
(att - 1)
w = Σ C(n, x)
x = 0
Prawdopodobieństwo atakującego wygranej w podzielonej przez 2 n , skumulowanego dwumianowego prawdopodobieństwa:
p = w / 2^n
Oto kod w Javie do obliczenia tego prawdopodobieństwa dla wartości arbitralnych atti defwartości:
/**
* 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;
}
Kod testowy:
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));
}
Wynik:
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
Spostrzeżenia
Prawdopodobieństwa są, 0.0jeśli atakujący ma 0punkty, 1.0jeśli atakujący ma punkty, ale obrona ma 0punkty, 0.5jeśli punkty są równe, mniej niż 0.5jeśli atakujący ma mniej punktów niż obrona, i większy niż, 0.5jeśli atakujący ma więcej punktów niż obrona .
Biorąc att = 50i def = 80musiałem przełączyć się na BigDecimals, aby uniknąć przepełnienia, ale dostaję prawdopodobieństwo około 0,0040.
Możesz zbliżyć prawdopodobieństwo do 0,5, zmieniając attwartość na średnią z wartości atti def. Att = 50, Def = 80 staje się (65, 80), co daje prawdopodobieństwo 0,1056.
