Monte Carlo Chess

Question

This is an entry to the 17^th fortnightly topic challenge.

---

Chess is an interesting game, but is so unrealistic. In real life, you couldn't tell order your knight to attack an enemy bishop and expect it win with 100% certainty. There would be a struggle, and the stronger fighter would be more likely to win, but could still get unlucky and lose.

Monte Carlo Chess is a variant which accounts for the messiness of real life by throwing probability into the mix.

Rules of Monte Carlo Chess

• All pieces move the same way as in regular chess, including en passant and castling.
• Winning: The goal is capture your entire opponent's army.
• Check: You are not required to protect your king when it is in check.
• Power Levels: Every piece has a certain power level. Initially, these are

      

      Note that the power level of a pawn will not change if it is promoted.

• Capturing moves only succeed with a certain probability proportional to the attacker's strength. If the attacking piece has a power level of $a$, and the target a level of $b$, then the attacker wins with probability $$\frac{a}{a+b}.$$ If the attacker wins, the move proceeds as normal. If not, then the attacking piece is removed from the board, while the target remains in its original position.

• Leveling up: Whenever a piece wins a battle, its power level increases by the amount of the loser. So, if a piece with power level 7 attacks one with level 15, the winner will have a power level of 22. Pencil and paper can be used to keep track of the power levels of the remaining pieces.

• 50 moves rule and stalemate: If 50 turns happen without any pawn moves, castling, or captures, the game ends, and the winner is decided by chance. This also happens if a player cannot make any legal move when it is their turn. Specifically, white wins with probability $$\frac{W}{W+B},$$ where $W$ is the total of the power levels of all white pieces, and $B$ is the black total.

---

Your task, dear puzzlers, is to solve the game of Monte Carlo chess. That is, when black and white both play optimally, what is the probability of each player winning? And what are their optimal strategies?

Source: This is heavily inspired by the puzzle "Gladiators, Version 1" from Peter Winkler's Mathematical Puzzles: A Connoisseur's Collection.

Answer 1

I initially gave a slightly rambling stream-of-consciousness answer, which I have preserved below in case anyone prefers that. Here is a slightly slicker one. (It is the same argument, just possibly clearer.)

Suppose the total army strengths are $a,b$; then say that the players' scores are $p,q:=\frac{a}{a+b},\frac{b}{a+b}$. I claim that in this case the players' expected scores after the next move is made are still $p,q$. This implies that the expected scores after any number of moves are still $p,q$; since $\Bbb{P}(\textrm{game over})\rightarrow1$ as the number of moves goes to infinity, and the scores at game end are 1 for the winner and 0 for the loser, this implies that the winning probabilities are $p,q$.

It remains to show

that your expected score after a move equals your score before it. But this is actually trivial. The denominator never changes, so we just have to show that your expected total strength doesn't change: but when a piece of strength $a$ attacks one of strength $b$, we go from $a$ with probability $1$ to $a+b$ with probability $\frac{a}{a+b}$ and the expectation is the same either way. (The defender's situation is the same.)

I have the suspicion that there is a way to express this idea that packs everything into one sentence, but I haven't quite found it yet.

---

Here's my earlier answer, which may or may not be easier to follow.

If this is soluble at all then I think the answer must be

that it doesn't matter how you play

in which case presumably

the odds of winning are just always the ratio of the army strengths or something.

Let's see whether we can

prove this by induction.

So,

suppose you have some position where the total army strengths are a,b, and you can either attempt or not attempt a capture, with your piece of strength p, of an opposing piece of strength q.

Then

if you attempt the capture then the new strengths are a+q:b-q with probability p/(p+q) and a-p:b+p with probability q/(p+q), so that your winning probability is now $\frac{p}{p+q}\frac{a+q}{a+b}+\frac{q}{p+q}\frac{a-p}{a+b}$ (note that the denominator never changes) which simplifies to $\frac{1}{(p+q)(a+b)}(p(a+q)+q(a-p))=\frac{1}{(p+q)(a+b)}a(p+q)=\frac{a}{a+b}$!

In other words

the expectation of $\frac{a}{a+b}$ never changes, capture or no capture, and therefore inductively your winning probability also never changes.

In particular,

from the initial position each player has winning probability exactly 1/2.