Friday, December 4, 2020

The twists and turns of random turn chess

It's time for another item of the series Posts I wrote a while ago and "forgot" to publish.

Random turn chess is a chess variant where the move order is random: Before every move, a coin flip decides who will play. If you're lucky you get to play several moves in a row, but you never know, when you make a move, whether it's you or your opponent who will make the next one. There are no special rules for check (or checkmate or stalemate). Instead the goal is simply to capture your opponent's king. Whenever you give a check, you have a 50% chance of winning on the spot. And if you're struggling, your best chance might involve deliberately putting your king en prise - there's no rule that says you can't.

As the name suggests, random turn is quite random. It has a non-random cousin, bidding chess, where the players bid for the right to make the next move. I won't explain it here, but they're basically manifestations of the same game. For the background, see this article by Jay Bhat and Sam Payne.

A few years ago I wrote an article with former student Urban Larsson about endgames in random turn/bidding chess. It's in the book Games of No Chance 5 which is freely available online. 

One thing that sets random turn chess apart from most other chess variants is that the game is amazingly complex already with just the two kings and one more piece!

For instance, look at the following position:


In standard chess this would be a draw, as it's impossible to construct a checkmate. In random turn on the other hand, not only can White possibly win, but so can Black! 

Figuring out the best way to play is a challenge on several levels, even with a computer. One of the quirks is that even in theory, there might be a difference between playing for a win and playing for a draw. Conceivably it might be, for instance, that White's best winning probability is 60%, and that Black's best winning probability is 30%, but that White, in order to win with probability 60%, has to allow Black to win with probability 40%. Moreover, in many positions the best strategy will not force a conclusion of the game in any fixed number of moves.

My computer program eventually sorted out the king + knight versus king endgame (and it turns out that with three pieces, there is never a conflict between playing for a win and playing for a draw). But in order to do so it had to backtrack 2644 moves before the values stabilised. If we compare this to "half-moves" in standard chess, it's more than twice as long as the record forced checkmate of the current endgame databases!

In the diagram, White's winning probability with best play from both sides is exactly ... let's see how to write it on this page...

118149099210761088839658071450928865980708175943671062283570061370088990297242487312344048797827448187146592684262495193145202761460197371
\[\Big /\] 200453006658428905551436939930457127472327950605425153085344343480681727125595119114980629492845444447049929082740309543514434854453248000.

That's a rational number with a numerator and denominator of 138 digits each, approximately 0.5894104617. 

Finally a puzzle that makes sense to us humans. What will happen here, and what's Black's probability of winning? Hint: with best play, the game will end in at most 13 moves.


Spoiler alert
.
.
.
Black's winning chances are \[ \left(\frac34\right)^6\cdot \frac12 = \frac{729}{8192}.\] Can you see why?