What's the optimal strategy in the following board game?

267 Views Asked by At

The following is not a homework problem. I just found it on a Chinese online community.

In the following variant of the board game Risk, suppose you and your opponent both start with armies of equal size. The battlefield consists of seven tiles numbered $1$ through $7$, with your home base at tile $1$ and your opponent's home base at tile $7$. At the start of the game, both your and your opponent's armies are on tile $4$. You win if your army reaches tile $7$, and you lose if your opponent's army reaches tile $1$.

On any given turn, you and your opponent each simultaneously decide what fraction of your total soldiers you want to deploy. Whoever deploys more soldiers wins the battle, and their army advances by $1$ tile while the opposing army retreats by $1$ tile. However, this comes at a cost: the winning army loses all soldiers that they deployed in that battle, while the losing army loses no soldiers. (Unfortunately, if you and your opponent both deploy the same number of soldiers, they win that battle.)

What's the optimal strategy for the players?

(Assume that you and your opponent can both deploy any real number of soldiers, so that divisibility of the armies is not an issue.)


I tried to use backward induction to solve the game, but it didn't work.

1

There are 1 best solutions below

0
On BEST ANSWER

Describe a state by a tuple (field, $\frac{\text{their army}}{\text{our army}}$). We don't have to worry about division by $0$ except as the result of a (pyrrhic) victory of ours, for unless this is reached while reaching field 7, the opposing army can simply sweep us all the way to field $1$.

A move in situation $(k,t)$ consists of us choosing $x\in[0,1]$ and them choosing $y\in[0,1]$ as relative proportions of armies to be deployed. That is, if the army sizes are $a$ and $b$, then we deploy $xa$ and they $yb$. If $xa>yb$, i.e., if $\frac xy>\frac ba=t$, then the next state is $(k+1,\frac{b}{a-xa})=(k+1,\frac t{1-x})$, and if $xa\le yb$, the next state is $(k-1,\frac{b-yb}{a})=(k-1,(1-y)t)$. Note that in the boundary case $xa=yb$, the latter is $(k-1,t-x)$.

For $1\le k\le 7$, let $$X_k=\{\,(t,x)\in [0,\infty)\times [0,1]\mid \text{We can win from }(k,t)\text{ by choosing }x\,\}. $$

Quite clearly, if $(t,x)\in X_k$ and $0<t'<t$, then also $(t',x)\in X_k$ for smaller $t$ does not restrict our strategy, but may restrict theirs.

Suppose $(t,x)\in X_k$. Then if they choose $y<\frac xt$, the next state $(k+1,\frac t{1-x})$ must also be won, i.e., $$(t,x)\in X_k\implies \text{some }(\tfrac t{1-x},*)\in X_{k+1} $$ On the other hand, for every $1\ge y\ge \frac xt$, the next situation $(k-1,(1-y)t)$ must be won, i.e., $$ (t,x)\in X_k, x\le t\implies \text{some }(t-x,*)\in X_{k-1}.$$ Let $$ \tau_k=\sup\{\,t\in[0,\infty)\mid \text{some }(t,*)\in X_k\,\}.$$ Then from the above, $$t>\tau_k\iff\exists x\in[0,1]\colon \frac t{1-x}\ge\tau_{k+1}\land t-x\ge \tau_{k-1}.$$ Equivalently, $$\tag1t>\tau_k\iff\exists x\in[0,1]\colon t-\tau_{k-1}\ge x\ge 1-\frac t{\tau_{k+1}}.$$ We conclude that $\tau_k\ge\tau_{k-1}$ (as if this was not obvious) and $$\tau_k-\tau_{k-1}= 1-\frac{\tau_k}{\tau_{k+1}}, $$ or: $$\tag2{\tau_{k+1}}=\frac{\tau_k}{1- \tau_k+\tau_{k-1}}$$ This recursion seems to be too little, given that we only know one initial value, namely $\tau_1=0$. How can we know $\tau_2$, which we need for $\tau_3$, etc.? But we do know more: By symmetry, we must have $\tau_4=1$ (and more generally, $\tau_{4+i}=\frac1{\tau_{4-i}}$, so that $$ 1=\tau_4=\frac{\tau_3}{1- \tau_3+\tau_{2}} =\frac{\frac{\tau_2}{1- \tau_2+\tau_{1}}}{1- \frac{\tau_2}{1- \tau_2+\tau_{1}}+\tau_{2}} =\frac{\tau_2}{1-\tau_2^2}$$ and hence $$ \tau_2^2+\tau_2-1=0,$$ or: $$\tau_2=-1+\sqrt 2$$ (because the negative solution is absurd). This makes $$\tau_3 = \frac12\sqrt 2 $$ (and $\tau_5=\sqrt 2$, $\tau_6=1+\sqrt 2$). Going back to $(1)$, the $x$ to be chosen in the state $(4,1)$ is $$x=\tau_4-\tau_3=1-\frac{\tau_4}{\tau_5}=1-\frac{\sqrt 2}2. $$

One caveat: Strictly speaking, we have only shown that we can win every $(4,1+\epsilon)$ with some $x\approx 1-\frac{\sqrt 2}2$. In fact, if the opponent always makes the optimal choice, the game goes like this: $$(4,1)\stackrel{x=1-\frac{\sqrt 2}2}\longrightarrow (3,\tfrac12\sqrt 2)\stackrel{x=1-\frac{\sqrt 2}2}\longrightarrow (2,\sqrt 2-1)\stackrel{x=\sqrt 2-1}\longrightarrow(1,0).$$ Under strict reading of the rules, this is a win for the opponent. However, if one adjusts the rules such that in order to win, one has to have a positive army left when arriving at the opponent's base, then the pendulum swings in the other direction and the solution stated above is indeed the unique winning strategy.