2
$\begingroup$

Suppose you have two players $X$ and $Y$ fighting, both of which have $n\in \mathbb{N}, n\geq1$ life.

Each player has a probability $p_i$ of doing $i$ damage for all $i\in[0, n]$. Note that $p_0$ is the probability of doing no damage, and all $p_i$ should sum to 1. $X$ and $Y$ both share probabilities, so all $p_i$ for $X$ equals $p_i$ for $Y$.

Now play the game as follows (each step is one turn):

  1. Player $X$ attacks, and randomly deals $i$ damage to player $Y$ according to the distribution $p_i$. This means that $Y$ decreases their life by $i$.
  2. Player $Y$ attacks, and randomly deals $i$ damage to player $X$ according to the distribution $p_i$. This means that $X$ decreases their life by $i$.

The game ends when a player's life is $\leq 0$.

Now a person watching this game would like for it to end after about $t\in \mathbb{N}, t\geq 1$ turns. In what ways can they assign the probabilities $p_i$ such that the expected number of turns is $t$?

Edit: To be clear I am looking for all possible $p_i$ such that the expected number of turns is $t$.

$\endgroup$
  • $\begingroup$ Set $p_{n/t}=1$? I guess you want to rule that out... $\endgroup$ – Nate Eldredge Sep 18 '15 at 5:33
  • $\begingroup$ Another simple example is $p_n=1/t$ and $p_0=1-1/t$ (if by "turn" you mean a single attack - if "turn" means a pair of attacks one by each player, then you can adjust appropriately). $\endgroup$ – James Martin Sep 18 '15 at 12:24
  • $\begingroup$ So I'm looking for a description of the set of all possible $p_i$'s, not just one example. $\endgroup$ – Phylliida Sep 18 '15 at 12:32
  • $\begingroup$ You're asking for the expected damage each turn to be $n/t$. This condition is $\sum_{i=0}^n i\cdot p_i = n/t$. That exactly characterizes distributions you want. $\endgroup$ – usul Sep 18 '15 at 13:41
  • 2
    $\begingroup$ How is this unclear what I am asking? It is presented formally and has a precise answer. $\endgroup$ – Phylliida Sep 19 '15 at 4:56
6
$\begingroup$

Let $A(x,y)$ be the expected length of the game (counting each player's turn as $1$) if you start with the players having life points $x$ and $y$ respectively, the player with $x$ going next. Conditioning on the result of the first player's turn,

$$A(x,y) = 1 + \sum_{i < y} p_i A(y-i, x)$$

You're interested in $A(n,n)$, which this recursion will determine as a rather complicated rational function in the $p_i$. For example, I get

$$ A({2,2})={\frac {{p_{{0}}}^{3}-{p_{{0}}}^{2}p_{{1}}-{p_{{0}}}^{2}+{p _{{1}}}^{2}-p_{{0}}+p_{{1}}+1}{ \left( p_{{0}}+1 \right) \left(1 - p_{{0 }} \right) ^{3}}} $$ while $A(3,3)$ is of the form $P(p_0, p_1, p_2)/((1+p_0)^3 (1-p_0)^5)$ where $P$ is a polynomial in $p_0, p_1, p_2$ of total degree $7$ with $39$ terms. The condition $A(n,n) = t$ then determines a surface in $(p_0, \ldots, p_{n-1})$ space.

EDIT: For example, here are the curves $A(2,2) = t$ in $(p_0,p_1)$ space for $t = 2$ to $10$ (from left to right). Note that in this case any damage $\ge 2$ is immediately lethal, and $\sum_{i \ge 2} p_i = 1 - p_0 - p_1$. For $A(2,2) = 1$ you'd need $p_0 = p_1 = 0$.

enter image description here

$\endgroup$
  • $\begingroup$ So recursive probability is really cool, I didn't know you could do that. And yes, I was manually playing with A(2, 2) and the solutions weren't pretty and I was confused. This fully describes all of them though, thanks =) $\endgroup$ – Phylliida Sep 18 '15 at 18:33
  • $\begingroup$ However to be fair, this does have one flaw. My question didn't assume that a player can only deal lethal damage, they might do more than lethal damage, since the condition is simply that life is $\leq 0$. $\endgroup$ – Phylliida Sep 18 '15 at 18:36
  • $\begingroup$ That's taken into account. The sum is over $i < y$ precisely because any $i \ge y$ ends the game. $\endgroup$ – Robert Israel Sep 18 '15 at 18:39
  • $\begingroup$ Also it's fun because this can easily be expanded to any number of players to get a very unhealthy function. $\endgroup$ – Phylliida Sep 18 '15 at 18:52

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.