21
$\begingroup$

This is an entry to the 17th 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

      enter image description here

      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 his 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.

$\endgroup$
  • 11
    $\begingroup$ I want to play this now. $\endgroup$ – dcfyj Oct 5 '16 at 18:59
  • 3
    $\begingroup$ Isn't solving Monte Carlo Chess comparable in complexity to solving chess? Even with the change to check and the "50 moves rule", answering this would require a monumental undertaking. $\endgroup$ – Aaron Oct 5 '16 at 19:08
  • 5
    $\begingroup$ Optimal play algorithms in normal chess are already unknown, which makes me think this puzzle is impossible/ill defined. $\endgroup$ – monoRed Oct 5 '16 at 19:19
  • 1
    $\begingroup$ I agree that it's improbable for there to be a completely optimal strategy and thus completely and exhaustively solve the game. Unless op has done otherwise... $\endgroup$ – greenturtle3141 Oct 5 '16 at 19:32
  • $\begingroup$ I would say the added probability from capturing pieces would make it more difficult to calculate a winner using probability, no? One probability plus two probability is more to consider now? $\endgroup$ – jmb-mage Oct 5 '16 at 20:30
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi Gareth. Maybe the sentence you mentioned above is something about martingales? Basically you play a fair (gambling) game every time you put two pieces against each other. $\endgroup$ – Puzzle Prime Oct 5 '16 at 22:31
  • $\begingroup$ It feels like there should be a way of putting it that's more elementary, with the "something about martingales" in the background rather than the foreground. $\endgroup$ – Gareth McCaughan Oct 5 '16 at 22:53
  • $\begingroup$ I'm not sure your theory is correct, since winning is not determined by the score alone. If it were as easy as you say, then $1$ queen would be evenly matched against $9$ pawns, however in actuality the queen wins only $39\%$ of the time. This means that there is in fact some strategy involved as to how you pick your battles, which means there is further complex strategy involved as to how to make sure you trigger those battles you pick. $\endgroup$ – Anon Oct 5 '16 at 23:15
  • 1
    $\begingroup$ @McFry right: it literally doesn't make any difference to your winning chances what moves you make. $\endgroup$ – Gareth McCaughan Oct 5 '16 at 23:38
  • 3
    $\begingroup$ @McFry I doubt your conjecture. Consider only power-1 pieces. Consider the case where each side has one piece. Clearly even. Now suppose there are two black and one white. If there is a battle, either black wins the battle thus the game, or loses the battle and the game is 1-on-1, so overall, black will win 3:1. But, if white can evade a battle indefinitely, and force the 50-move clock, it is resolved by chance, and black will win 2:1. So it now depends on position and not just total power. $\endgroup$ – deep thought Oct 6 '16 at 1:56

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.