10
$\begingroup$

I encountered this game when I was a kid (we called it Street Fighter back when it was all the rage) and recently saw it again with my nephews playing the same game with a different name and slightly different rules.

The basic game is an RPS-style game where each participant selects one of the following actions per round.

  1. Charge
  2. Block
  3. Fireball (uses up 1 charge)
  4. Super Fireball (Uses up 5 charges)

Anyone who gets hit by a fireball while charging is dead. Blocking cancels fireballs thrown at you and two fireballs fired at each other also cancel each other out. Super fireball goes through blocks and overpowers regular fireballs to automatically kill the opponent unless he super fireballs as well.

I was wondering what the optimal strategy was, if any. During which rounds is it best to fire/block? Is it better to go for the super blast, or to catch your opponent unawares with a well-timed regular fireball?

What would be the numbers for the 2-player case? How will this increase in complexity as the number of players increase as well?

Edit: What if the number of required charges for the super fireball is increased/decreased?

$\endgroup$
11
  • $\begingroup$ (+1) I always knew this as the game without a name (to suggest playing it, you had to mime it). $\endgroup$
    – Eli Rose
    Jan 14 '16 at 17:11
  • 2
    $\begingroup$ You want an 'optimal' strategy, but that probably depends on how your opponent plays. Which we can hardly predict, unless you suppose it's 'random' or give simples rules to model it. $\endgroup$ Jan 14 '16 at 17:16
  • $\begingroup$ If a super fireball is useful in killing and killing probability is $1$ and we can use 1 per round then its obvious $\endgroup$ Jan 14 '16 at 17:17
  • 1
    $\begingroup$ @ArchisWelankar Obvious ? Why ? We need to be able to charge for 5 rounds without getting killed first $\endgroup$ Jan 14 '16 at 17:19
  • 1
    $\begingroup$ Some thoughts to add to my previous comment : clearly, if both players use the optimal strategy then on average they will win as often since the problem is exactly symmetrical. Thus, it only makes sense to search for an optimal strategy when the other player is not playing an optimal way. Which we thus have to somehow caracterize. For instance we can say that when the other has 0 charges a player will always charge, when a player has 5 charges it will automatically fire a superball (or some other variation of those rules). $\endgroup$ Jan 14 '16 at 17:56
2
$\begingroup$

Let $X_{a,b}$ be the expected payoff of this game for a player with $a$ charges when the other player has $b$ charges, where $+1$ is a win and $-1$ is a loss, and assuming optimal play. We will take the cost of a super fireball to be $M>1$. By symmetry, $X_{a,b}=-X_{b,a}$, and clearly $X_{a,a}=0$ for any $a$. From state $(0,0)$, both players will charge up to state $(1,1)$; similarly, from state $(M,M)$, both players will super-fireball back to $(0,0)$. Next, $X_{M,a}=+1$ for any $a<M$, because the first player will win immediately with a super fireball. Finally, $X_{M-1,0}=+1$, because the first player can safely charge once and then super-fireball, whatever the second player does. All other payoffs and strategies are initially unknown.

Now, we can calculate the equilibrium strategy (and payoff) for each player in state $(a,b)$ as long as we know the payoffs for some of the neighboring states. Specifically, suppose the first player is charging with probability $c$, fireballing with probability $f$, and blocking with probability $b$, where $0 \le c,f,b\le 1$ and $c+f+b=1$, and that the second player's probabilities are $c'$, $f'$, and $b'$. Then the expected payoff for the first player satisfies $$ X_{a,b}=cc'X_{a+1,b+1}+ff'X_{a-1,b-1}+bb'X_{a,b}-cf'+fc'+fb'X_{a-1,b}+bf'X_{a,b-1}+cb'X_{a+1,b}+bc'X_{a,b+1}, $$ so $$ X_{a,b}=\frac{1}{1-bb'}\times\\ \left(cc'X_{a+1,b+1}+ff'X_{a-1,b-1}-cf'+fc'+fb'X_{a-1,b}+bf'X_{a,b-1}+cb'X_{a+1,b}+bc'X_{a,b+1}\right). $$ For this to be an equilibrium strategy, its partial derivative with respect to each probability, subject to the constraints on the probabilities, must be zero. (At the boundaries, when a probability is zero or one, its partial derivative may be nonzero if it has the correct sign.) Things are simplified when the second player has no charges, since then he cannot fireball ($f'=0$), and the first player need not block ($b=0$). In that case $$ X_{a,0}=cc'X_{a+1,1}+fc'+fb'X_{a-1,0}+cb'X_{a+1,0}. $$ Of course, further simplifications occur when the neighboring payoffs are zero.


Note that if $M=2$, then all payoffs are known, and the only unknown strategy is for state $(1,1)$. In that state, fireball beats charge, charge beats block, and block beats fireball... so the game is isomorphic to rock-paper-scissors, and the Nash equilibrium strategy in state $(1,1)$ is to choose each move with equal probability.

Things first get interesting for $M=3$. Here we have unknown payoffs in states $(1,0)$ and $(2,1)$, and unknown equilibrium strategies in states $(1,1)$, $(2,2)$, $(1,0)$, and $(2,1)$. Let's first consider the state $(1,0)$. The payoff for the first player is $$ X_{1,0}=cc'X_{2,1}+fc'+cb'=cc'X_{2,1}+(1-c)c'+c(1-c')=cc'(X_{2,1}-2)+c+c'; $$ setting the derivatives to zero yields $$ c=c'=X_{1,0}=\frac{1}{2-X_{2,1}}. $$ In the state $(2,1)$, the payoff is $$ X_{2,1}=\frac{cc'+ff'X_{1,0}-cf'+fc'+bf'+cb'}{1-bb'}=\frac{(1-f-b)(1-2f')+f(f'X_{1,0}+c')+bf'}{1-b(1-f'-c')}. $$ Setting the derivative with respect to $f$ to zero gives $$ -(1-2f')+(f'X_{1,0}+c')=f'(2+X_{1,0})+c'-1=0\implies f'=\frac{1-c'}{2+X_{1,0}}. $$ Setting the derivative with respect to $c'$ to zero gives $$ 0=\frac{f}{1-b(1-f'-c')}-\frac{b}{1-b(1-f'-c')}X_{2,1}\implies f=bX_{2,1}. $$ Setting the derivative with respect to $b$ to zero gives $$ 0=\frac{3f'-1}{1-b(1-f'-c')}+\frac{1-f'-c'}{1-b(1-f'-c')}X_{2,1}\implies f'(3-X_{2,1}) + (1-c')X_{2,1}-1=0\implies f'=\frac{1-(1-c')X_{2,1}}{3-X_{2,1}}. $$ Finally, setting the derivative with respect to $f'$ to zero gives $$ 0=\frac{-2(1-f-b)+fX_{1,0}+b}{1-b(1-f'-c')}-\frac{b}{1-b(1-f'-c')}X_{2,1}\implies -2+f(2+X_{1,0})+b(3-X_{2,1})=0\implies f=\frac{2-b(3-X_{2,1})}{2+X_{1,0}}. $$ Combining the second and fourth equations, and using the fact that $X_{1,0}=1/(2-X_{2,1})$, gives $$ b=\frac{2(2-X_{2,1})}{6-X_{2,1}^2}; \qquad f = \frac{2X_{2,1}(2-X_{2,1})}{6-X_{2,1}^2}. $$ Similarly, combining the first and third equations gives $$ c'=\frac{1+2X_{2,1}-X_{2,1}^2}{6-X_{2,1}^2}; \qquad f'=\frac{2-X_{2,1}}{6-X_{2,1}^2}. $$ Feeding everything back in to the equation for $X_{2,1}$, we find that $X_{2,1}$ is a root of the cubic equation $x^3-x^2-4x+2=0$; it must be the real root between $0$ and $1$, so numerically $X_{2,1}\approx 0.47068$. What this means is that from the state $(2,1)$, the first player can expect to win only about $3/4$ of the time. The second player can fight back... and should do so by charging $30\%$ of the time, fireballing $26\%$ of the time, and blocking the remaining $44\%$ of the time. Similarly, $X_{1,0}\approx 0.6539$, so the first player can win about $5/6$ of the time from that state; the second player should fight back by charging $65\%$ of the time. The optimal strategies follow from these numbers; the key takeaway, though, is that (1) a charge advantage does not guarantee victory, and (2) the optimal strategy uses probabilities that are non-trivial algebraic numbers in the general case.

$\endgroup$
2
$\begingroup$

Here is a very incomplete answer which might help use make some progress for two player version.

  1. I'm going to ignore super-fire-ball.

  2. I'm going to make an assumption which simplifies things a lot. If the charges are ever imbalanced, the player with more charges can force a win. (I have some serious doubts about this.)

In this case, equilibrium play involves charging whenever neither have a charge and equally randomizing otherwise.

In the first round, it is weakly dominant to charge (this doesn't rely on my assumption. Having fewer charges cannot possibly increase your probability of losing against any strategy).

In the second round,

If 1 blocks and 2 uses fireball, then 1 eventually wins (by assumption).

If 1 blocks and 2 blocks, then the game simply starts over from the same state.

If 1 blocks and 2 charges, then 2 eventually wins (by assumption)

If 1 charges and 2 uses fireball, then 2 wins

If 1 charges and 2 blocks, then 1 eventually wins

If 1 charges and 2 charges, the game continues with both at 2 charges.

If 1 uses fireball and 2 blocks, then 2 eventually wins

If 1 uses fireball and 2 charges, then 1 wins

If 1 uses fireball and 2 uses fireball, then the game returns to the original sate.

Notice that no matter what 1 does, the game either ends in a win for 1, a win for 2, or continues (with each having equal charges). These are the exact same outcomes possible in every round of a best-of-one rock-paper-scissors game. The only equilibrium is to randomize equally over all three options (ignoring super-fire-ball) in every round unless neither player has a charge in which case, both charge.

$\endgroup$
3
  • $\begingroup$ "In the second round, If 1 blocks and 2 uses fireball, then 1 wins on next turn." This IS covered under assumption #2 (so it is true if that holds) but some percentage of the time 2 can finesse out the charge by blocking and return the game to the original state. I do agree that 1 is favored from this position though. $\endgroup$
    – Javier I.
    Jan 14 '16 at 18:28
  • $\begingroup$ Thanks, I fixed it. Shouldn't say "on next turn". $\endgroup$
    – CommonerG
    Jan 14 '16 at 18:29
  • $\begingroup$ Caught by the edit! $\endgroup$
    – Javier I.
    Jan 14 '16 at 18:31
0
$\begingroup$

I'm new here, I hope it's not bad form to post a partial answer to your own question!

Thank you CommonerG for that analysis. Your post got me to think about this even more.

It seems that there are the following game states, and changes to another state based on the results of the previous round.

  1. Both players have no charges. (Initial State)
  2. Both players have at least one charge. (Charge parity)
  3. Player 1 has at least one charge and Player 2 has no charges. (Charge advantage)
  4. Inverse of State 3 (Charge disadvantage)

The reason I characterized the game states is that I kept thinking about Assumption# 2 and kept thinking that while Player 2 is disadvantaged, he can still force the game back to parity or the initial state and still have a chance. So I thought, what is that chance? How much of an advantage is it? I guess this kind of makes it more interesting. Given that the game is symmetrical from the initial state, it can still reach a point of asymmetry (unlike RPS which is symmetrical at all times). Maybe we could develop some sort of optimal mixed strategy for an advantaged player and a disadvantaged player.

So here’s my thoughts so far.

  1. Initial state - In the initial state, both players will always charge.

  2. Charge parity

    Assuming each player has an equal chance to pick each action, each of these has a 1/9 chance of happening.

Now it’s my turn to assume something that I’m not sure about. I think the number of charges over another doesn’t matter (i.e. 1-charge, 2-charge, 3-charge advantage is all the same and won’t affect the player’s strategy, except in the miniscule case that he builds up 5.) The only difference is that the state will transition to a still-disadvantaged state if the player digs himself out of it.

  1. Charge advantage / disadvantage

In this state, the advantaged player will never block because his opponent cannot shoot. The disadvantaged player will never shoot. enter image description here

*Parity with some changes in the 3rd (Fire, block) and 9th (fire, fire) squares. I think?

And then the disadvantage chart would be the opposite. enter image description here

Here’s what I will do. I will try to run scenarios where P1 and P2 pick either action 50% of the time in advantage/disadvantage scenarios. Then compute win % assuming that, and revise the probabilities accordingly in order to eventually get an optimal course of action.

$\endgroup$

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.