6
$\begingroup$

I am playing Warlight online (something like Risk), and my goal is to create a bot which plays against other bots.

n=100 attacking troops will on average kill 60 (p=0.6) troops each turn, 
n=100 defending troops will on average kill 70 (p=0.7) troops each turn.
They attack exactly at the same time.
Binomial distribution such that variance=n*p*(1-p)

My question is the following: imagine we have 40 troops and the enemy has 25 troops. I am interested in the case that I continuously attack. What would be the chance that I have won by turn X (e.g. X=5)?

For turn = 1, it is simply the cumulative sum from at least 25 kills:

$$\sum_{i=25}^{40} {40 \choose i} * 0.6^i * (1-0.6)^{(40-i)} = 0.440$$

I have played around with the binomial distribution, but I find it difficult to calculate because of this "in X turns"; it seems it really explodes the amount of calculations needed (by lack of a smart trick).

Can this be done analytically or am I best off just to simulate this (which I assume will be much slower)?

EDIT: Perhaps it can simply be done by using the 60% and 70%?

$\endgroup$
17
  • $\begingroup$ I find the description confusing on two counts: (1) It would seem that if an attacker has a 60% chance of winning, then a defender would only have a 100-60% = 40% chance of winning, not 70%. What is wrong with this understanding of the situation? (2) When there are multiple attackers and defenders, what do the foregoing individual chances mean? Do they mean that each attacker has a 60% chance of defeating some enemy troop or that this attacker will attack each enemy troop in turn and independently have a 60% chance of defeating each one of them? Please edit your post to clarify. $\endgroup$
    – whuber
    Commented Mar 29, 2014 at 20:44
  • 2
    $\begingroup$ @whuber They are pre-determined, like mentioned p=0.6 when attacking and p=0.7 when defending. I now understand that from the way I give the example it might seem like it depends on troops, but it was just posed like this for illustrative purposes. $\endgroup$ Commented Apr 2, 2014 at 18:32
  • 2
    $\begingroup$ For the record, I found an explanation of this mechanism at wiki.warlight.net/index.php/Combat_basics. Although the explanation is vague, and some of the things it states are mathematically incorrect, the three examples it offers clarify what is going on. $\endgroup$
    – whuber
    Commented Apr 2, 2014 at 21:54
  • 1
    $\begingroup$ @whuber Note that they implement a luck factor on Warlight online. I looked into the code, and the way the bot website theaigames.com/competitions/warlight-ai-challenge implements this, is that they simply draw from a binomial distribution. $\endgroup$ Commented Apr 2, 2014 at 21:58
  • 1
    $\begingroup$ There is no analytical solution in closed form. $\endgroup$
    – whuber
    Commented Apr 2, 2014 at 22:15

2 Answers 2

7
$\begingroup$

The basic rules of engagement provide the probability distribution for transitions from $a$ attacking armies and $d$ defending armies to $a^\prime$ attackers and $d^\prime$ defenders, where $0 \le a^\prime \le a$ and $0 \le d^\prime \le d$. Beginning with $A$ attacking armies and $D$ defending armies, there are therefore $(A+1)(D+1)$ possible states indexed by $a=0, 1, \ldots, A$ and $d=0, 1, \ldots, D$. This is a Markov Chain on these states. All the information about outcomes is therefore contained in its transition matrix $\mathbb{P}_{A,D}$. In particular, after $k$ transitions ("turns" in the battle) from an initial state vector $s$, the distribution of resulting states $s^\prime$ is given by $\mathbb{P}_{A,D}^k\cdot s$. Because $\mathbb{P}_{A,D}$ can be large but $k$ is likely small, it may be most expedient simply to calculate this distribution iteratively via

$$s(k) = \mathbb{P}_{A,D}\cdot s(k-1)$$

beginning with the initial state $s(0) = s$.

These ideas were used to produce graphs of the winning chances for the attacker (blue) and defender (red) as a function of the number of turns played. (The gray lines are the chances that the battle remains unresolved after each turn.) The total time needed to do these computations using the brute-force method described below was five seconds. This is more than competitive with a Monte-Carlo simulation. For much larger numbers of armies, simulation will be superior in its use of time and RAM, but even so it is helpful to have a way to compute exact results, if only to test a simulator.

Figure

It is interesting that the attacker needs relatively few additional armies in order to secure a huge advantage. In particular, one might naively expect to need $0.7/0.6$ times as many attacking armies. The randomness of the outcomes magnifies a small initial superiority, however. Also, attackers have one slight advantage: they still win if they are wiped out, provided the defenders are also wiped out. (The actual rules might differ on this account; if so, the code would need slight modification to accommodate any additional restrictions concerning minimum numbers of attackers.)


An Algorithm

A solution with brute-force computation takes only a few seconds even when $A=100$, $D=60$, and $k=5$ as in the question. The only difficulties concern how to index the states. Because R appears to be preferred and it organizes arrays by columns, I have written the transition vectors as columns and multiply state vectors by the transition matrix from the left (which is the opposite of the usual convention). I index the states $1, 2, \ldots, (A+1)(D+1)$ by letting the first coordinate vary fastest from largest to smallest. For instance, with $(A,D)=(2,1)$ the states are $(2,1), (1,1), (0,1), (2,0), (1,0), (0,0)$. The transition matrix $\mathbb{P}_{2,1}$ is computed in R as

     From
To      2:1  1:1 0:1 2:0 1:0 0:0
  2:1 0.048 0.00   0   0   0   0
  1:1 0.112 0.12   0   0   0   0
  0:1 0.000 0.28   1   0   0   0
  2:0 0.252 0.00   0   1   0   0
  1:0 0.588 0.18   0   0   1   0
  0:0 0.000 0.42   0   0   0   1

using the command mc(2, 1)$transition (whose source is given below). For instance, the entry in row 1:0 and column 2:1 asserts there is a chance of 0.588 that two armies attacking one defender (the state $(2,1)$) will, in one turn, reduce to one attacking army and no defending armies (the state $(1,0)$).

To check the validity of this calculation, we need to know the rules. The transition from $(a,d)$ yields a pair of random variables $(a^\prime, d^\prime)$. Let $X$ be a Binomial$(a, p)$ variable, where by default $p = 0.6$, and $Y$ be an independent Binomial$(d, q)$ variable with $q = 0.7$ by default. Then $a^\prime = \max(0,a-Y)$ and $d^\prime = \max(0,d-X)$. We say that the attacker "wins" provided $a\gt 0$ and $d^\prime=0$ and that the attacker "loses" provided $a\gt 0,$ $a^\prime=0$, and $d^\prime\gt 0$. In the case of a win or loss the engagement ends. Otherwise it may continue (at the attacker's option).

Returning to the example, beginning in the state $(2,1)$ we find that $X$ has a Binomial$(2,0.6)$ distribution, whence

$$\Pr(X=0)=0.4^2=0.16,\Pr(X=1)=2(0.4)(0.6)=0.48, \Pr(X=2)=0.6^2=0.36.$$

Consequently

  • When $X=0, d^\prime=\max(0,1-0) = 1$, so ${\Pr}_{2,1}(d^\prime=1) = 0.16.$

  • When $X=1, d^\prime=\max(0,0)=0$; and

  • When $X=2, d^\prime=\max(0,-1)=0$, so ${\Pr}_{2,1}(d^\prime=0) = 0.48+0.36=0.84.$

Likewise $Y$ has a Binomial$(1,0.7)$ distribution, giving it a $0.3$ chance of being $0$ and a $0.7$ chance of being $1$. Accordingly

  • ${\Pr}_{2,1}(a^\prime=2)=\Pr(Y=0)=0.3$ and

  • ${\Pr}_{2,1}(a^\prime=1)=\Pr(Y=1)=0.7$.

Because $X$ and $Y$ are independent, the chances multiply. For example, the chance of arriving at $(a^\prime, d^\prime) = (1,0)$ is

$${\Pr}_{2,1}\left((a^\prime, d^\prime)\right) = {\Pr}_{2,1}(a^\prime=1){\Pr}_{2,1}(d^\prime=0) = 0.7\times 0.84 = 0.588.$$

The other entries in the transition matrix are similarly verified. Notice that the terminal states $(0,1), (2,0), (1,0),$ and $(0,0)$ just make transitions to themselves. The first is a loss for the attacker while the rest are counted as wins.


Working code

To implement this I have used auxiliary functions fight to compute the probabilities, transition to produce the distribution of transitions from a single state, and mc to assemble those into a transition matrix. The function battle repeatedly applies this transition matrix to the initial distribution where state $(A,D)$ has probability $1$ and all other states have probability $0$. It summarizes the attacker's chances of winning and losing. Finally, by iterating battle over plausible choices of $A$, it becomes a tool to help with game strategy, which amounts to selecting an appropriate number of armies from among those available in order to attack a defender. The only applicable rule is that the number of armies must be strictly less than the number of available (because any attacking armies available after the engagement will be moved into the defender's territory but at least one army must be left behind).

(This modular implementation makes it relatively easy to check the calculations by hand, at least for small cases. Doing so increases the confidence that the calculations are correct. Moreover, by limiting each module (R function) to less than a half dozen executable lines, each is sufficiently simple to undergo careful testing and review. I admit my testing has been cursory, but it did include a wide range of values of $A$, $D$, $p$, and $q$ as well as spot-checks like the example given above.)

The output of this code consists of an array of graphs showing the winning and losing chances of the attacker as a function of the number of turns. It also reports the total amount of time needed to do the calculations for each graph. On this workstation it takes under 2.5 seconds to perform the calculations for $A=100$ attackers, $D=60$ defenders, and $k=5$ turns (using the command battle(100, 60, 5)). Easy modifications of battle will enable deeper analysis, such as evaluating the numbers of attacking armies that are likely to survive any engagement: such information, more than the mere chance of winning after $k$ turns, is more important to developing an optimal game strategy.

fight <- function(n.attack, n.defend, n.defend.max, attack.p) {
  #
  # Returns a probability vector for the number of surviving defenders
  # indexed by n.defend.max down to 0.
  # NB: This is the only part that needs modification if a "luck factor"
  #     is introduced.
  #
  p.casualty <- dbinom(0:n.attack, n.attack, attack.p) 
  n.survive <- n.defend - (0:n.attack)

  if (n.attack > n.defend) {
    # Collapse the negative values into a single state with no survivors.
    p.casualty <- c(p.casualty[n.survive > 0], sum(p.casualty[n.survive <= 0]))
    n.survive <- n.survive[n.survive >= 0]
  }

  # Pad the return vector with zeros, fore and aft, as needed.
  c(rep(0, n.defend.max-n.defend), p.casualty, rep(0, max(0, n.defend-n.attack)))
}

transition <- function(attack, defend, attack.max, defend.max, attack.p, defend.p) {
  #
  # Returns the transition probabilities from the state (attack, defend),
  # in descending order with `attack` changing fastest.
  #
  a <- fight(defend, attack, attack.max, defend.p)
  d <- fight(attack, defend, defend.max, attack.p)
  return(as.vector(outer(a, d)))
}

mc <- function(attack.max, defend.max, attack.p=0.6, defend.p=0.7) {
  #
  # Returns the transition matrix for a round in which attack.max armies
  # (not including any reserved ones) engage defend.max armies.
  # Transitions are in *columns* (not rows, which is the convention).
  # The matrix is square with dimensions (attack.max+1)(defend.max+1).
  #
  # Also returns indicator vectors $wins and $loses showing which
  # states correspond to wins and losses for the attacker, respectively.
  #
  i <- expand.grid(A=attack.max:0, D=defend.max:0) # All states
  x <- apply(i, 1, function(ad, ...) transition(ad[1], ad[2], ...),
        attack.max=attack.max, defend.max=defend.max, 
        attack.p=attack.p, defend.p=defend.p)

  # Name the indexes in `x` to assist human reading of the results.
  s <- paste(i$A, i$D, sep=":")
  dimnames(x) <- list(To=s, From=s)
  return(list(transition=x, n=dim(i)[1], wins=(i$D==0), loses=(i$A==0 & i$D > 0)))
}

battle <- function(attack, defend, k=5, ...) {
  #
  # Conduct a battle of `attack` attacking armies against `defend` defending
  # armies for `k` turns.
  # Return an array whose rows (indexed by `k`) give chances of the attacker
  # winning and losing at that turn.
  #
  # (The code is readily modified to report the distributions of numbers of
  # remaining armies.)
  #
  if (attack <= 0 || defend <= 0) stop("Both army counts must be positive.")
  #
  # Find the probability distributions after 1, 2, ..., k turns.
  #
  x <- mc(attack, defend, ...) # Transition matrix structure
  y <- c(1, rep(0, x$n-1))     # $Beginning distribution: all is in state 1.
  p <- matrix(NA, k, 3, 
              dimnames=list(Turns=1:k, Outcome=c("Wins", "Loses", "Undecided")))
  for (i in 1:k) {
    y <- x$transition %*% y          # $
    # Summarize this turn.
    p[i, "Wins"] <- sum(y[x$wins])   # $
    p[i, "Loses"] <- sum(y[x$loses]) # $
    p[i, "Undecided"] <- 1 - (p[i, "Wins"] + p[i, "Loses"])
  }
  return(p)
}
#
# Study near-equal battles involving a given number of defenders.
#
d <- 60
k <- 5
p.a <- 0.6; p.d <- 0.7
times <- numeric(0)
par(mfrow=c(2,2))
for (a in round(d * exp(seq(log(63/60), log(75/60), length.out=4)))) {
  u <- system.time(p <- zapsmall(battle(a, d, k, attack.p=p.a, defend.p=p.d)))
  times <- c(times, u[3])

  plot(p[, "Wins"], type="l", ylim=c(0,1), col="Blue",
       xlab="Turns", ylab="Probability",
       main=paste(a, "Attackers vs.", d, "Defenders"),
       sub=paste("p(Attack) =", p.a, "p(Defense) =", p.d))
  lines(p[, "Undecided"], col="Gray")
  lines(p[, "Loses"], col="Red")
}
times
$\endgroup$
8
  • $\begingroup$ Thank you a lot for this effort. I hope it has been at least a bit entertaining to you. Basically since in the game I will have limited time, I precomputed roughly 400,000 battles with the Markov chain simulator based on a sample of nsim=100 cases. Your code was actually perfect for me to give me the certainty I need: it is indeed a good approximation. I will run my simulator overnight, in 5 hours it should finish for nsim=1000 (using Python). $\endgroup$ Commented Apr 10, 2014 at 19:32
  • $\begingroup$ It is also great to see how to tackle the problem with the exact solution (and with a fast computation). Indeed you are right to be suspicious of who wins when both the attackers and defenders end up dying, in case both the attackers and defenders die, the defender actually gets favored! $\endgroup$ Commented Apr 10, 2014 at 19:34
  • $\begingroup$ Also, only after the simulations I realized that fights are over really quickly and that it is indeed not that important at which turn a territory might be captured. Again, thank you for the full answer. $\endgroup$ Commented Apr 10, 2014 at 19:35
  • $\begingroup$ I would like to suggest you could get much more useful information about strategy by studying the distributions of armies that remain after a battle. (That can be done with your simulation, too.) As far as favoring the defender when both parties are wiped out, just change the logical condition in the last line of mc so it reads wins=(i$D==0 & i$A>0), loses=(i$A==0))) at the end. $\endgroup$
    – whuber
    Commented Apr 10, 2014 at 19:39
  • $\begingroup$ Thanks. Yes, this really opens up a lot of possibilities. I'm now struggling with a minimum threshold for the probability to attack (I'm leaning towards 70%). Many people (me too earlier on) implement the linear "if my_troops * 0.6 >= enemy_troops, then attack (good chance to wipe enemy in first turn). I'm curious if you could give me a simple example when knowing the leftover distribution will give you an advantage? $\endgroup$ Commented Apr 10, 2014 at 19:57
1
$\begingroup$

I use this to simulate, perhaps it might give more insight and perhaps someone might come with an analytical solution.

  • When defender has equal to attacker, the defender "wins"
  • When the attacker didn't destroy defender by turn X, the attacker "loses"
  • When defender reaches 0 troops, attacker "wins"

Here, N1 is the defender troops, N2 is attacker troops.

simulateBattle <-function(N1, N2, nsim=10000, max_turn=100,verbose=F) {  
  result <- 1:nsim
  turn <- 1:nsim
  for (i in 1:nsim) {
    t <- 1
    n1 <- N1; n2 <- N2
    if (verbose) { print(paste("turn", t, "n1", n1, "n2", n2)) }
    while (n1 < n2 && n1 > 0 && t < max_turn) { 
      temp_n1 <- n1
      n1 <- n1 - rbinom(1, n2 - 1, p=0.6)  # attack with n2 - 1
      n2 <- n2 - rbinom(1, temp_n1 , p=0.7) # defend with all
      t <- t + 1
      if (verbose) { print(paste("turn", t, "n1", n1, "n2", n2)) }
    }
    turn[i] <- t
    result[i] <- n1 <= 0
  } 
  cat(paste("P(attacker_wins): ", mean(result)))
}

Results:

# Only first turn:
simulateBattle(25, 40, max_turn=2) 
[1] 0.36301

# Up until 2 turns:
simulateBattle(25, 40, max_turn=3)
[1] 0.9983

# Up until 3 turns:
simulateBattle(25, 40, max_turn=4)
[1] 0.99999
$\endgroup$
15
  • 1
    $\begingroup$ It looks like plain Monte Carlo (i.e. simulation) to me. $\endgroup$
    – Glen_b
    Commented Apr 9, 2014 at 9:25
  • $\begingroup$ @Glen_b Care to elaborate? Since each "turn" is dependent on the result of the previous enemy, it seems to match wiki's definition: "It is a random process usually characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. This specific kind of "memorylessness" is called the Markov property." $\endgroup$ Commented Apr 9, 2014 at 10:23
  • 1
    $\begingroup$ A simulation that contains a Markov Chain isn't automatically MCMC. $\endgroup$
    – Glen_b
    Commented Apr 9, 2014 at 10:37
  • $\begingroup$ @Glen_b You just called it plain Monte Carlo, we just established there is a Markov Chain involved. I'm really curious why you think it is not MCMC? $\endgroup$ Commented Apr 9, 2014 at 11:11
  • 1
    $\begingroup$ Yes, I completely agree it's Monte Carlo; I already said it was earlier, and I agreed it contains a Markov Chain - so quoting the definition of Monte Carlo or Markov Chain to me achieves nothing, since those aspects of what you're doing are not in dispute. I already explained, MCMC is not just "simulating a Markov Chain". Since you're avidly checking wikipedia, I have to wonder why you don't instead quote the first sentence of the article on Markov chain Monte Carlo. The last half of that sentence gives a crucial difference, but it may not be clear what it's getting at. $\endgroup$
    – Glen_b
    Commented Apr 9, 2014 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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