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?

Hastigheten i kvadrat ... eller ännu värre?

Nu tittade jag på ännu en Numberphilevideo med en tankeväckande räkneövning. Här vill jag återge den fast med lite snyggare siffror och utan videons brasklappar om "slightly dodgy".

Gåtan är följande: Två bilister i likadana bilar kör i 40 respektive 50 kilometer i timmen åt samma håll på en väg. När de är jämsides (dvs när den snabbare precis kör om) dyker ett hinder upp och båda tvärnitar. Vi bortser från reaktionstid, dvs vi antar att de är jämsides när de börjar bromsa. Vi antar också att de har likadana bilar med lika effektiva bromsar, däck osv. 

Om den långsammare bilen nätt och jämnt hinner stanna för att undvika en kollision, dvs stannar precis vid hindret, vilken hastighet har då den snabbare bilen när den kolliderar med hindret? 

Ett resonemang som nog de flesta inser är för naivt och optimistiskt är att om den långsammare bilen får ner hastigheten från 40 till noll, hinner den snabbare bromsa från 50 till 10. 

Det stämmer inte, men notera att vi faktiskt antar att bilarna hinner bromsa bort 40 km/h på samma tid. Detta är det antagande som ligger bakom standardfrågorna på körkortsprovet, som går ut på att dubbelt så hög hastighet ger fyra gånger så lång bromssträcka osv. Antagandet är att man bromsar med samma kraft vid alla hastigheter. Detta kan knappast stämma exakt, men är nog en hyfsat bra approximation för vanliga trafiksituationer.

Problemet för den snabbare bilisten är att han (det är oftast en man) hinner längre på denna tid. Så kraschen blir definitivt i mer än 10 km/h. 

Nästa tanke är att räkna ut hur bromssträckorna förhåller sig till varandra. När hastigheterna har förhållandet 4 till 5, blir bromssträckorna som 16 till 25. Det är egentligen ganska enkelt och hör som sagt till teoriprovet: Sträckan är tiden gånger hastigheten, och både tiden och den genomsnittliga hastigheten under inbromsningen kommer att ha förhållandena 4 till 5. 

När den snabbare bilen kraschar in i hindret har den alltså 9/25 av sin hypotetiska bromssträcka kvar. Kanske borde den då även ha nio tjugofemtedelar av sin ursprungliga hastighet? Det blir i så fall 18 km/h, rejält mycket mer än de 10 som det naiva tankesättet ledde till. 

Men det är faktiskt betydligt värre! När vi har 9/25 av bromssträckan kvar, får vi dra kvadratroten ur 9/25 för att få andelen av hastigheten vi har kvar. Detta enligt exakt samma princip som nyss! Och när vi drar roten ur ett tal mellan 0 och 1, får vi ett större tal, i det här fallet 3/5. 

Svaret är alltså att den snabbare bilen inte ens hinner halvera sin fart, utan kraschar in i hindret i 30 km/h! 

Det här kan vara något att tänka på när vi pratar hastigheter i tätorter. Det har ofta påpekats att riskerna för oskyddade trafikanter ökar dramatiskt i ett fönster runt 30-40 km/h, och då pratar vi alltså om hastigheten vid själva kollisionen (även om det nog är svårt att få fram exakta data). Men dessutom kan alltså hastigheten vid en kollision i sin tur öka dramatiskt även vid en liten skillnad i hastighet före inbromsning.

Men tillbaka till vår räkneövning. Den som kan sin Pythagoras sats känner säkert igen både förhållandena 3:4:5 och kvadrerandet följt av kvadratrotsutdragning. Och det stämmer generellt. Närhelst vi har en Pythagoreisk trippel, dvs tre tal som uppfyller \[ a^2 + b^2 = c^2,\] får vi motsvarande slutsats: Om bilarna hade hastigheterna $b$ och $c$ där $b$ är det mindre talet, kommer den snabbare bilen att ha hastigheten $a$ efter den sträcka som den långsammare bilen behövde för att stanna. 

Vi kan till exempel vända på det och jämföra två bilar med hastigheterna 30 kontra 50 km/h. Då blir slutsatsen att den som kör i 50 kraschar i 40 när den som kör i 30 hinner stanna!

Nästa Pythagoreiska trippel, $5^2 + 12^2 = 13^2$, handlar lika pedagogiskt om vad som händer när någon blir stående på motorvägen. 120 eller 130 kan väl kvitta kanske man tänker. Men händer det en olycka framför och den som kör i 120 precis hinner stanna, så kommer den som höll 130 att braka in med en kvarvarande hastighet av 50 km/h.

  

Zero to the zeroth power

The question of the number zero raised to the zeroth power comes up often enough that finally I wanted to put my response to it on the blog for future reference. In short: \[ 0^0 = 1.\] This might not seem like such a big deal, but in the broader scheme the point is: 

We should not teach that mathematics is full of things that can go wrong and that one has to be "careful". We should teach that mathematics can be trusted even if some of it looks weird at first. 

It's the former approach that tends to depict mathematics as some incomprehensible wizardry, not the latter. 

I wouldn't have written this post if everyone already agreed on the status of $0^0$, but it seems that the idea that $0^0=1$ is still the minority view even in the teacher community. In a poll among mathematics teachers last year, about 85% of the responders chose the answer "0^0 is undefined" over the alternative "0^0 = 1".

But let's first review what the problem is, so we know what we're debunking. On one hand it's generally agreed that $x^0 = 1$, at least when $x>0$. This might itself require an explanation, but is rarely disputed. For instance, $10^3$ is $1000$, which is 10 times as much as $10^2$, which is 10 times as much as $10^1$, so it makes sense that $10^0 = 1$ and that $10^{-1}=1/10$ and so on. 

On the other hand $0^x = 0$, again at least if we assume that $x>0$. For instance, $0^3 = 0\cdot 0 \cdot 0 = 0$ and $0^{1/3} = \sqrt[3]{0} = 0$. 

So if $0^0$ is to have a specific value, there will be a clash between the two rules $x^0=1$ and $0^x=0$. One of them suggests that $0^0$ should be 1, the other that it should be zero. 

Moreover, this clash manifests itself in the exercises of the typical calculus course, where we're asked to compute things like \[ \lim_{x\to 0+} (\sin x)^{1/\log x} = e \approx 2.72.\] This limit has the form of something raised to a power, where both the base and the exponent tend to zero. Many textbooks make a big deal out of the fact that this doesn't determine the limit, listing $0^0$ as an "indeterminate form" along with truly meaningless expressions like $0/0$ and $\infty - \infty$. This has led to a widespread belief that $0^0$ can't consistently be assigned a value. 

Probably algebra has a part in this too: We're taught that \[ \frac{x^5}{x^2} = x^3,\] just subtract one exponent from the other. And lo and behold, \[ \frac{x^2}{x^2} = x^0 = 1,\] except there's a problem when $x=0$, because then there's a zero in the denominator of the left hand side. So it seems that whenever $0^0$ shows up, there's something fishy going on. 

It's just that that's not true. "Indeterminate forms" aren't really a thing, they're basically just lists of common beginner's mistakes. Or if we're a bit cynical, lists of ways an examiner might try to trick you on a test. We can't make $0^0$ agree with a limit of $x^y$ at $x=y=0$, but that's not a conundrum, that's a discontinuity. Discontinuities exist. There was never a theorem that everything is continuous in the first place. And denominators that might be zero is a different matter altogether. If that's the issue, the equation $x^5/x^2 = x^3$ is just as problematic.

In reality, zero to the zeroth power is virtually omnipresent, and the pattern is the same every time: We want $x^0$ to be equal to 1 always. And we want $0$ to a power to have the exceptional value 1 precisely when the exponent is zero.

Fundamentally this is because $0^n$ answers the question "If you put an apple on a table and then $n$ times perform the operation of removing all the apples from the table, how many apples are then on the table?" (answer: If you never removed it, it's still there, otherwise it's gone). If we trace mathematics down to its logical foundations, this is the sort of thing we encounter. Everything else, like $e^{i\sqrt{\pi}}$ and so on, is built on top of that. Therefore not only is it "often useful" to let $0^0=1$. It's also completely safe and the only option that doesn't leave us with a mess of exceptions. 

Famous examples where we can't really avoid $0^0$ include Taylor series like

\[e^x = \sum_{n=0}^\infty \frac{x^n}{n!},\] and the binomial theorem \[ (x+y)^n = \sum_{k=0}^n\binom{n}{k}x^ky^{n-k}.\] In both cases we want the factor $x^0$ to be 1 if $x=0$, otherwise we get the wrong thing.

More generally, $x^0 = 1$ is a building block of polynomials and power series, which play a major role in algebra, analysis, and discrete mathematics. Powers of zero on the other hand occur naturally only when the exponent is a nonnegative integer. Therefore there's no issue of continuity in the exponent, and $x^0=1$ takes precedence over $0^n=0$.  

I recently stumbled upon something involving so-called Stirling numbers, that count ways of partitioning $n$ objects into a given number of nonempty subsets. For instance, the number of partitions of $1, 2, \dots, n$ into 3 nonempty subsets is given by the formula \[\frac{3^n - 3\cdot 2^n + 3}6,\] or so it would seem. Here if we plug in $n=1, 2, 3, 4$, we get the numbers $0, 0, 1, 6$, which makes sense: We don't distinguish the three parts (hence the division by 6), but we do require them to be nonempty, which means $n$ must be at least 3 before it's possible at all.

But if we set $n=0$ we get the nonsense value $1/6$ which isn't even an integer. At this point I hear you asking why any sane person would consider partitioning an empty set into nonempty parts. Can I really complain about a nonsense answer to that? The problem was that this occurred inside a loop where my computer program added together some stuff that I didn't look at case by case myself. 

Or rather, that would have been the problem. But luckily I knew what the real formula is. It's not the one above, but rather \[ \frac{3^n - 3\cdot 2^n + 3\cdot 1^n - 0^n}6.\] Not only does this produce the correct value also when $n=0$, but it reveals the pattern that explains what the formula for any given number of parts will look like, as well as why it's true (if you don't see it, don't worry).  

Notice that the formula involving $0^n$ is the one that lets you sleep at night. It's if you would use the other one, or (imagine the horror!) if your computer algebra system wouldn't recognise that $0^0=1$, that you'd have to worry that something might go wrong.

But can we be certain that $0^0=1$ makes sense every time?  

A "foundational" answer (already hinted at) is yes, because arithmetic is built from just a few basic principles, one of which is that an empty product is equal to 1 (there are numerous ways of formulating the details). Since the more sophisticated stuff already rests logically on that basis, a fundamental thing like $0^0$ can't possibly jump up and bite us from behind. 

More philosophically, we can compare mathematics to things like, say, traffic regulations, English grammar, or a toolkit for the household. Those things are man-made and there's no fundamental reason they must work. If we're not careful they won't, and if something weird occurs, we might actually want to fix it with a patchwork of exceptions.  

Mathematics is not like that. It's not a mish-mash of compromises and conventions. It works whether or not we understand why. It doesn't break if we do something that wasn't intended, and it can be explored: If you establish a formula, it will give me the right answer even if I plug in some numbers that you never thought of. Like zero to the zeroth power.

Lyssna på Greta Thunberg och sprid ordet!

När jag lyssnade på Greta Thunbergs sommarprat igår kom jag att tänka på detta med att upprepa något som låter orimligt, så att det till slut känns rimligt. Mycket finns skrivet om "gas-lightning", "illusory truth effect" mm, och exemplen handlar ofta om Hitler, valkampanjer, reklam, och sociopater i parrelationer. 

Men psykologin är nog densamma även när påståendena är sanna. Så låt oss göra som Greta Thunberg och sprida klimatvetenskapens rön. 

Ska vi klara de mål som Sverige och de flesta andra länder har enats om i Parisavtalet, har vi motsvarande 7-8 år av dagens nivå kvar av hela koldioxidbudgeten. 

Det handlar alltså inte om att minska utsläppen med si eller så många procent. Det handlar inte om hur mycket vi kan släppa ut per år. Vi måste ner på väsentligen noll om vi ska undvika kollaps av klimat och ekosystem, och det måste hända saker före år 2030 om det inte ska bli väldigt, väldigt bekymmersamt. Fossila bränslen har ingen framtid överhuvudtaget. De måste fasas ut helt.

Det låter orimligt. Men om vi upprepar det tillräckligt ofta kommer det att bli så bekant att du kan säga det till vem som helst, till och med om du är politiker, utan att folk tror att du har blivit tokig.

Och till stor del är minskning av utsläppen inte ens svårt, eftersom vi kommer långt bara med att sluta göra onödiga saker. Vi behöver inte shoppa hållbart eller resa klimatsmart. Vi kan skippa det mesta helt och hållet. 

Vi avslutar med en räkneövning. Fem-sex minuter före slutet nämner Greta Thunberg en ny rapport som visar att vi måste minska våra utsläpp med 12-15% varje år för att vara i linje med Parisavtalet. Låt oss säga att vi skulle minska med 12.5% varje år. Det är en åttondel. Om vi jämför med nuvarande årliga utsläpp skulle det bli 7/8 nästa år, och 7/8 av 7/8 året därpå, och så vidare. Den totala mängden för all framtid skulle då bli

\[ 1 + 7/8 + (7/8)^2 + (7/8)^3 + \dots \]

Detta är en så kallad geometrisk serie, och summan blir inte oändlig utan stannar vid precis 8. Summan från år 2 och framåt är nämligen 7/8 av det hela, vilket innebär att den första termen är en åttondel av totalsumman. 

De 12-15 procenten stämmer alltså bra med de 7-8 år som nämndes tidigare. Med den takten skulle vi efter 10 år vara nere på 26%. Det är svårt att hävda att detta är orimligt, med tanke på att många av världens fattigare regioner aldrig har varit uppe på motsvarande 26% av vår nivå.