Note that the distinction between the objectives of survival and killing the opponent can be important. Suppose some $p_i(n) = 0$ (for both 1 and 2) while $p_i(n-1) > 1/2$. The player who steps forward first is very likely to be killed, so to maximize your probability of survival your best strategy at distance $n$ is always to shoot. The opponent, also wanting to survive, will also shoot, and the game will go on forever without anybody getting hurt.
But if your objective is to kill the opponent, this strategy is clearly sub-optimal: it would be better to step forward and have a positive probability of killing the opponent. But that's not optimal either: there's no need to step forward right away, you could wait a while in the hope that the opponent steps forward first. Waiting $k+1$ turns before stepping forward dominates waiting $k$ turns, so there is no optimal strategy.
To avoid such problems, let's assume $p_i(d) > 0$ for all $d$. This will ensure that the probability of both players surviving indefinitely is 0. Then an optimal strategy can be found using dynamic programming. Let $V_i(d)$ be player $i$'s probability of winning under optimal strategies, starting with distance $d$ and $i$'s turn to shoot. Then $V_i(0) = 1$, otherwise $V_i(d) = \max(1 - V_{3-i}(d-1), \min(\frac{p_i(d)}{p_1(d) W_i(d))$, where $W_i(d)=\min\left(\frac{p_i(d)}{p_1(d) + p_2(d) - p_1(d) p_2(d)}, p_i(d) +(1 - p_i(d)) V_i(d-1)))$V_i(d-1))\right)$. It is optimal to shoot if$V_i(d) W_i(d) > 1 - V_{3-i}(d-1)$, to step forward if$\lt$, and both are equally good if$=$. 2 fix latex Note that the distinction between the objectives of survival and killing the opponent can be important. Suppose some$p_i(n) = 0$(for both 1 and 2) while$p_i(n-1) > 1/2$. The player who steps forward first is very likely to be killed, so to maximize your probability of survival your best strategy at distance$n$is always to shoot. The opponent, also wanting to survive, will also shoot, and the game will go on forever without anybody getting hurt. But if your objective is to kill the opponent, this strategy is clearly sub-optimal: it would be better to step forward and have a positive probability of killing the opponent. But that's not optimal either: there's no need to step forward right away, you could wait a while in the hope that the opponent steps forward first. Waiting$k+1$turns before stepping forward dominates waiting$k$turns, so there is no optimal strategy. To avoid such problems, let's assume$p_i(d) > 0$for all$d$. This will ensure that the probability of both players surviving indefinitely is 0. Then an optimal strategy can be found using dynamic programming. Let$V_i(d)$be player$i$'s probability of winning under optimal strategies, starting with distance$d$and$i$'s turn to shoot. Then$V_i(0) = 1$, otherwise$V_i(d) = \max(1 - V_{3-i}(d-1), \min(\frac{p_i(d)}{p_1(d) + p_2(d) - p_1(d) p_2(d)}, p_i(d) +(1 - p_i(d)) V_i(d-1)))$. It is optimal to shoot if$V_i(d) > 1 - V_{3-i}(d-1)$, to step forward if$\lt$, and both are equally good if$=$. 1 Note that the distinction between the objectives of survival and killing the opponent can be important. Suppose some$p_i(n) = 0$(for both 1 and 2) while$p_i(n-1) > 1/2$. The player who steps forward first is very likely to be killed, so to maximize your probability of survival your best strategy at distance$n$is always to shoot. The opponent, also wanting to survive, will also shoot, and the game will go on forever without anybody getting hurt. But if your objective is to kill the opponent, this strategy is clearly sub-optimal: it would be better to step forward and have a positive probability of killing the opponent. But that's not optimal either: there's no need to step forward right away, you could wait a while in the hope that the opponent steps forward first. Waiting$k+1$turns before stepping forward dominates waiting$k$turns, so there is no optimal strategy. To avoid such problems, let's assume$p_i(d) > 0$for all$d$. This will ensure that the probability of both players surviving indefinitely is 0. Then an optimal strategy can be found using dynamic programming. Let$V_i(d)$be player$i$'s probability of winning under optimal strategies, starting with distance$d$and$i$'s turn to shoot. Then$V_i(0) = 1$, otherwise$V_i(d) = \max(1 - V_{3-i}(d-1), \min(\frac{p_i(d)}{p_1(d) + p_2(d) - p_1(d) p_2(d)}, p_i(d) +(1 - p_i(d)) V_i(d-1)))$. It is optimal to shoot if$V_i(d) > 1 - V_{3-i}(d-1)$, to step forward if$