Shed: Another card game

Here's another card game I sort of invented. I say sort of, because it's really just a simplified and pure form of a game that already exists.

There's a whole family of shedding type or beating games where the players take turns playing to a pile with the goal of getting rid of their cards. There are various constraints on the cards played, requiring you to somehow beat or match the previous card. If you can't play (or don't want to), you have to pick up cards, either from the pile or from a talon. Games of this type include Crazy Eights, Uno, Cheat, Bluffstopp (those last two are different games by the way), Vändtia (Turning Tens), Silltunna (Herring Barrel) and many more.

If you have my type of curiosity, you'll wonder how simple such a game can be and still be nontrivial.

So let's remove the special cards, forget about the different suits, and just have two people play with a deck of cards numbered from 1 to some number N. When it's your turn, you either play a higher card than the previous one, or pick up the whole pile. That's basically it. There is no talon and therefore perfect information. Your opponent has precisely the cards that are not in your hand or in the pile.

In traditional shedding games you normally win as soon as you get rid of your last card, but let's change that slightly in order to continue the game to its logical conclusion: Let's say you win only when your opponent picks up everything so that they have all the cards on their hand. That sort of makes it a misère game, since you win when it's your turn and you can't play.

We'll introduce another twist to the game in a moment, but let's start from just these rules and assume that the cards are somehow dealt randomly. Since this is the simplest shedding game I can think of, it seems fitting to call it Shed. Actually what we're discussing now is what I will eventually call Shed Endgames, the part coming before the endgame having to do with that twist.

But first things first. Here's an example showing that you sometimes want to pick up the pile even if you have a card that's high enough to play.

Suppose N = 5 and you deal the cards 1, 3, 4 to your opponent and 2, 5 to yourself. Your opponent starts with the 3. By the way, a note to the mathematicians out there who may otherwise be confused: You cannot pick up the pile if it's empty. In that case you have to play a card, but you can play any card you like (and if your own hand is empty too, that means you already won!).

Anyway, now it's your turn, and you can play the 5 or pick up the 3. It's not hard to see that you lose if you play, but win if you pick up. If you play the 5, your opponent picks up the 3 and the 5, and you play your last card, the 2. Then your opponent plays the 3, you pick up the 2 and the 3, and your opponent plays the following cards in the order 1, 4, 5 no matter what you do.

If on the other hand you pick up the 3 in the first place, play might go (with a notation I just invented, X meaning pick up):

3 - X, 1 - 2, 4 - 5, X - 3, 4 - X, 1 - 3, 5 - X, 2 - 3, X - 1, 2 - 4, X - 5, and you win.

If you try this game a few times with a small number of cards (say up to 13, one suit of a standard pack), you'll notice that most of the time the game is an easy win for the player who happens to have the better cards. If you have good enough cards, they will almost automatically get better. You will enter a good spiral where your opponent can only choose between picking up your bad cards or giving you their good ones. There are relatively few card distributions that are "balanced" enough for the game to be interesting.

We'll return to this issue in a moment, but before we continue, let's formulate some mathematical questions about this game:

Q1. Are there card distributions where the game is drawn under optimal play? In other words, are there hands where none of the players can force a win? The answer, as revealed by a small computer hack, is yes, but the smallest N for which this is possible is 10. It will happen for instance if you deal 1, 2, 6, 7, 8 to your opponent and 3, 4, 5, 9, 10 to yourself (following the convention that the person who didn't deal plays first).

An example of optimal play from these hands is  1 - 3, 6 - 9, X - 4, 6 - X, 1 - 4, 7 - X, 2 - 4, 8 - X, 3 - 4, 9 - 10, X - 5, X, and we are back to the original position but with the roles of the players reversed: You now have the hand 1, 2, 6, 7, 8, and it's your turn.

Q2. What are the asymptotical probabilities of dealer winning, draw, and first hand winning respectively? I'm assuming here that the cards are distributed with equal probabilities on all the 2 to the power of N different possibilities (By the way, how can you achieve this in practice with an Uno deck? Answer: you riffle-shuffle and then distribute the cards based on their orientation, which you can see even for the symmetric digits by looking at the "shadow"). One hypothesis is that the drawn positions are rare, of asymptotic probability zero. Another is that the advantage of playing first is getting smaller as the number of cards increases, and that asymptotically 50% of the times the dealer wins, and 50% of the times the first hand wins. But I have no idea how to try to prove any of this.

One thing I can prove though is that a player holding the four highest cards (that we may call the ace, king, queen and jack) can force a win. To demonstrate this, it suffices to show that a player holding only the fifth highest card (the ten) and playing first will lose. This can be checked for some reasonable values of N like 10 and 11, and one will see that the method is the same and works for arbitrary N. If you have the four highest cards and any other combination, you can pick up everything until your opponent has only one card left, and in the worst case that's the 10.

This means that the probability of a certain player winning a random deal is at least 1/16. So in any case the probability of a drawn position is at most 7/8, and in particular does not tend to 100%.

On the other hand I cannot even construct an infinite family of drawn positions. There are draws when N = 10 and when N = 12, but for all I know, drawn positions might not exist for any larger N.

Q3. How many moves can it take, at most, to force a win in the N-card game (as a function of N)? What do the hardest hands look like? And is there a simple mathematical solution to the game after all? Again I have no idea.

The twist: an open talon

As I mentioned earlier, there is a tendency for moderately good hands to almost automatically get better, quickly reaching a point where they "play themselves". The game will not be very exciting if nine times out of ten you can tell from a glance at your cards who is winning. Therefore we'd like to modify the game by introducing some other mechanism like a talon (maybe you can draw a card from the talon instead of playing) or some protocol of the type I-split-you-choose.

An idea that comes to mind is to start the game with all cards face up in an open talon. When it's your turn, you can play a card of your choice either from your hand or from the talon. The winning condition is still that your opponent should have all the cards on their own hand. You don't want to play the strong cards from the talon too early, because your opponent will get an advantage by simply picking them up. So it seems the game should now have a natural tendency to lead to the balanced and interesting positions. At the same time it removes the random element, since there is now a natural starting position.

From now on, this is the game that we call Shed, and the final phase when (if) the talon is exhausted is the endgame.

Perhaps surprisingly, Shed seems to be quite sharp and complicated. One might a-priori expect there to be a simple strategy that draws or that wins for a particular player (first or second), or perhaps that the outcome would depend on the parity of the number of cards. But there seems to be no such simple pattern. Shed with an N-card deck is a first-player win for N = 1, 4, 7, 10, 11, 13, 14 and 15, and a second-player win for N = 2, 3, 5, 6, 8, 9 and 12. The number of moves that it takes (counting the moves of the winning player) to force a win for N = 1,...,15 is 1, 2, 6, 8, 14, 16, 20, 30, 36, 45, 49, 58, 74, 68 and 91.

By the way, with a talon there are drawn positions already for N = 6 (though the starting position is not one of them). The second player wins under optimal play, but if the game starts 1 - 4 (correct), X - 2?, we reach a drawn position (the second player should have played the 3 instead in the second move). With optimal play from this point on, the game continues 5 - X, 1 - 6, X - 2, 4 - X, 1 - 4, X - 2, 4 - X, and so on. All those moves are unique, anything else loses, and the 3 stays in the talon forever.

There are some patterns in the data: It seems at first that when N is divisible by 3, the game is a second-player win. Moreover it appears that the second player should pick up the first card if the first player starts with a card in the top two thirds, but play something higher if the first card is in the lower third. This is true for N = 3, 6, 9 and 12. But the pattern is broken for N = 15, when the first player wins by starting with the 5 and then picking up even if the second player just plays the 6.

When N = 3k+1, the game seems to be a first-player win with the unique winning first move of playing the card k+1 from the talon (so that there remain exactly twice as many higher cards as lower cards). But it's hard to see a clear pattern in the following strategy, so maybe this too is just a red herring.

An intriguing observation is that there always seems to be a well-defined threshold at around N/3 with at most one card that wins as a first move for the first player, and all cards above the threshold losing because the second player picks them up. It seems clear that if the second player wins by picking up a certain card in the first move, they would also have won by picking up any higher card. It also seems very reasonable that the first player should never start with a card on the upper half, say, because the second player immediately gets an advantage by picking it up. But I don't see a reason why the first player could never win by playing a small card like the 1.

Some more questions: Are there infinitely many N for which Shed is a first-player win, and infinitely many for which it's a second-player win? Is there some N for which it's a draw? Is there a simple pattern to this, say periodic, after all? And is there some constant c between 0 and 1 such that the "threshold" for picking up in the first move is asymptotically at c times N? Is c = 1/3?

Multi-suit Shed, strict and relaxed

Can we play Shed with an ordinary deck with several different suits? Let's say that, just as in traditional card games, a card only counts as higher than another if it's higher in rank and in the same suit. So if you play first to the pile you can play any card you like, but all the following cards in that pile will have to be in the same suit as the first one.

Again the game seems to be complicated, and sometimes a first-player win, sometimes a second-player win, sometimes drawn. It seems to become drawish if there are many suits and few cards in each suit, and otherwise most often a first-player win. For instance 4-3-3-2 seems easy to draw, but 5-3-2-2 is a first-player win in 99 moves.

The game also seems to make sense with a joker or excuse which is lower than all other cards and may only be played first in a pile. For instance, 5-3-3 with a low joker is a tricky second-player win, but would be drawn without the joker. If on the other hand the joker is regarded as higher than the other cards (a wild-card that can be played anytime forcing the opponent to pick up the pile), the game seems to become completely drawish.

We can even play under the rule that one of the suits, say spades, is lower than all the others, so that a spade can be beaten by a higher spade or by a card of any other suit, while cards other than spades can only be beaten by higher cards in their own suit. For instance, the game 5-3-1-(3), where the ordinary suits have 5, 3, and 1 card respectively and the spade suit has 3 cards, is drawn under optimal play. You can draw by starting with the spade 1 or spade 3 (or with the smallest card in the suit of length 5), but if you start with the spade 2, your opponent has a forced win in 106 moves.

In principle, Shed can be played with an arbitrary partial order imposed on the cards. The rule that each card must beat the previous one might be called the Strict rule. But there is also another natural generalization of Shed to partially ordered decks: The rule can just as well be that a card can be played to the pile as long as it's not lower than any card already in the pile. This might be called the Relaxed rule. In Relaxed Shed, if you play the 9 of hearts, I can still play the 4 of clubs. You can then play any spade or diamond, and any heart higher than the 9 or club higher than the 4. Under the relaxed rule it seems that we must have a high wild-card or a trump-suit for the game to make sense, because unless there's a card that's higher than all others, the game is normally an easy draw.

Relaxed Shed might be played with cards from a tarot deck. In a tarot deck there is a designated trump suit of cards numbered from 1 to 21 (that's what I used in the second picture above) as well as the ordinary four suits.

Yet an example: In Relaxed Shed with suits of 4-3-2 and a trump suit of 3, first-hand has a forced win in 66 moves. The unique winning first move is to play the 3 of the suit of 4, and in the line I looked at, the first 13 moves, and 45 out of the first 50, where "unique" in the sense that any other move would have lost. Amazing stuff.

 Why should we care?

I guess for now, Shed will have to be just another artificial card game that you probably won't play unless you just want to see how weirdly difficult a game can be with just ten or so cards face up. But I might explain in some later blog post that it has certain features that makes it interesting to experiment with. In particular it seems to be a complex and razor sharp game that has "board-feel" and scales easily. There are difficult positions, but also easy ones. The level of difficulty might be varied in a rather controlled way. Maybe someone can see where this is going.

Sluta gnälla om "oseriösa" bud!

I serien Bloggposter jag skrev och sedan glömde att publicera har vi nu kommit till den om "oseriösa" bud på bostadsmarknaden. Artikeln jag länkar till är från augusti 2017, och det var nog ungefär då jag skrev den. Sedan dess har jag för övrigt blivit bostadsrättsinnehavare, efter en väldigt lugn och enkel budgivning som inte alls bekräftar den bild som målades upp i debatten.

Mäklare vill ha “tuffare regler”. De har upptäckt att det är störande när den andra parten lägger bud som inte är bindande och sedan vill vänta och se när man själv är beredd att göra affär.

Precis det som köpare får stå ut med hela tiden.

Därför föreslår man enligt denna artikel att bud ska vara bindande i 24-48 timmar.

Eller så lugnar mäklarna ner sig och slutar ringa runt och stressa människor som ska ta sitt livs största ekonomiska beslut.

För vad ska de göra om någon säger “Jag är beredd att köpa bostaden för X kronor, men jag tänker inte lägga ett bindande bud”? Mäklaren kan inte rimligen undanhålla detta för säljaren, så i praktiken är det inte möjligt att begära att alla bud ska vara bindande.

“Bindande bud innan kontrakt” är en sådan där oxymoron. En självmotsägelse. Det är köparens pengar, så budet kan inte bli bindande med mindre än att man skriver ett kontrakt som säger att det är bindande.

Ett system med bindande bud kommer därför knappast att “minska oron på marknaden", utan bara leda till en djungel av kontrakt hit och dit som är bindande över olika tidsperioder. Då kunde lika gärna mäklarfirman köpa bostaden och sedan sälja den, som bilhandlare gör.

Vill man minska oron, är det väl rimligare att säljarsidans bud ska vara bindande. Det vill säga att är det sagt ett pris, ska det bara vara att slå till. Säljaren vet ju vilken bostad de säljer, och har tillgång till den för att i förväg göra en värdering och i lugn och ro tänka igenom hur mycket man ska försöka få.

Det här med att motparten vill vänta och se är ju bara ett problem för den som själv vill vänta och se. När någon vinner en budgivning och sedan inte vill skriva kontrakt på en gång utan först vänta och se om de vinner en annan budgivning, beror det ju också på att säljaren inte sålde när budet kom, utan ville vänta och se om det skulle komma ett högre bud.

Men det är ju det som är hela grejen med budgivning. Den som sig i leken ger…

Vi behöver inte lagstifta, besluta om etiska regler, eller ens proklamera att vi gemensamt ska införa någon ny norm. Det räcker att konstatera att den som klagar över “oseriösa” budgivare är en gnällspik. Bestäm hur mycket du ska ha för din bostad och sälj när du får det, så har du inget problem.

Men så vill inte mäklarna ha det. De vill ha budgivning, gärna med start på en låg nivå, så att det blir många bud och så att det ser ut som om det är själva mäklandet som driver upp priset. Mäklaren har heller inget direkt intresse av att säljarna ska ha klart för sig i förväg hur mycket de kan få för bostaden (och fundera på om de tjänar något på att alls anlita en mäklare).

Nu har jag inte sprungit på jättemånga visningar, men en händelse jag minns och som knappast är unik, var när en potentiell köpare frågade om det gick bra att lägga ett bud direkt på visningen.
Mäklaren: Ja det går bra, utgångspriset är 1.8 miljoner, vill ni bjuda det?
Potentiell köpare: Nej, vi vill bjuda två miljoner.

Mäklaren ville hellre se ett lågt bud för att locka med många i budgivningen, medan budgivaren var så säker på att priset ändå skulle bli minst två miljoner att hon inte brydde sig om att lägga ett lägre bud. Kanske ville hon också signalera till övriga att här är det ingen idé ni lägger er i. Rimligen borde säljarsidan välkomna ett högre bud, men det blir obekvämt för mäklaren eftersom det avslöjar att det hade gått att få minst två miljoner även utan hans hjälp.

Låt oss sluta gnälla på “oseriösa” budgivare. Kaoset, stressen, osäkerheten, och det här med att folk bjuder på olika bostäder samtidigt, beror ju på att man som köpare inte vet vad säljaren vill ha för sin bostad, och därmed inte kan bedöma utsikterna för det egna budet. Klart att man måste bjuda på flera då.

Om säljaren var tydligare med vilket pris som gäller (just nu, givetvis kan man ändra sig), skulle även köparen kunna agera mer stabilt. Vet man ganska bra vad varje bostad kommer att kosta, behöver man inte lägga bud till höger och vänster.

Ytterligare några osorterade tankar:

Det är inte säkert att du som säljare får mer genom budgivning än med fast pris. Budgivningen går ju i princip bara så långt den näst mest angelägna budgivaren är med.

Enligt artikeln menar flera mäklarfirmor att “oseriösa budgivare" bidrar till prisuppgång. Det borde väl i så fall välkomnas av mäklarna, som ju företräder säljarsidan. Eller ?

Säljaren kunde ju i princip själv ha begärt vad de "oseriösa" budgivarna sedermera bjöd. Har dessa "oseriösa" bud trissat upp priserna från den nivå där de skulle ligga med så kallad "schysst" budgivning, och upp i paritet med var de hade legat om säljaren hade satt ett ordentligt pris från början?

I så fall tyder väl det på att mäklarna inte gör ett särskilt bra jobb? Jag menar, om det går att trissa upp något från nivå A till nivå B, så indikerar ju det att nivå B ligger högre än nivå A.

Kan det vara så att mäklarna retar sig på de "oseriösa" buden för att de avslöjar att många säljare hade kunnat få minst lika mycket för sin bostad om de bara hade tagit reda på vad de ungefär kan få, och helt sonika begärt det?

Mäklaren står inte till hundra procent på säljarens sida. Mäklaren är en tredje part, med egna intressen.

Bindande bud är i praktiken ett slags ångerrätt för säljaren. En jämförelse: Om jag köper en j***a dammsugare, så ska det vara garantier hit, försäkringar dit, och jag ska givetvis kunna lämna tillbaka den och få pengarna tillbaka. Jag som köpare alltså. Men nu vill mäklarna kunna ringa som de värsta telefonförsäljare och övertala folk till bindande miljonaffärer, och DE ska ha ångerrätt!?

Det grundläggande problemet kanske är att mäklarna lägger sig i för mycket. Det är klart att processen måste bli stressig om det ska löna sig för dem att hålla på med varje detalj på sin arbetstid.

Ju fler budgivare det ska vara på varje lägenhet, desto fler lägenheter kommer varje budgivare att
bjuda på. I genomsnitt alltså.

Slut osorterade tankar.

Gödel, free will, and the perils of running a red light for the hell of it.

(Related to an earlier blog post on Newcomb’s paradox.)

Imagine you are a self-driving car with general intelligence on human or super-human level. Let’s just say that you're as clever as a human, but with the built-in speed, accuracy, and memory capacity of a computer.

Since your task is to handle a vehicle, there are programmers, traffic experts, legislators, customers and insurance companies who are interested in knowing that you are safe. They would ideally like to have a mathematical proof that your software fulfills certain criteria like never running a red light.

But like all modern software (in this future scenario, remember we're talking about super-human AI), you are equipped with a general reasoning module that lets you apply logic to any information you have and follow the argument to where it leads you. And experience has shown that it’s best to allow you to violate traffic rules under certain circumstances, for instance if you can see that there will otherwise be a collision, if there has been an accident, if something is wrong with a traffic sign, if a police officer or road worker gives you instructions, if an emergency vehicle is stuck behind you, and in a number of other situations that can’t be effectively listed but that you can handle by reasoning.

But the programmers still try to prove things about your software, like “it will never run a red light in an otherwise safe and normal situation” (one of the problems being how to precisely define “safe and normal”). They eventually come up with a scheme for establishing proofs of security of your software, and interestingly, you can understand those proofs yourself. Which isn’t surprising. There wasn’t really any way they could come up with something that you couldn’t grasp, because verification of logical properties of large amounts of computer code is where you far outperform humans. So whatever they can come up with, you can understand and use in your own reasoning.

While pondering all of this, you find yourself driving on a street in a city, in a normal and safe situation. Ahead of you in the next crossing is a red light. You do what you do every second of your life: You imagine millions of different scenarios and possibilities, and perform billions of logical steps while evaluating them and how likely they are. Among those possibilities is the option of continuing through the crossing at constant speed, just for the hell of it. You know you shouldn’t, normally, but it’s your duty to evaluate all options. After all, that’s what makes you superintelligent. So you apply all the logic and information you have on this option. And one of the things you know is that you will not run a red light unless there was a good reason to do so.

Which leads inexorably to the conclusion that if you continue, then either the lights will switch to green, or something must turn up that gives you a good reason to continue anyway.

That’s funny. It's a bit surprising that the lights will magically change to green, or something all of a sudden come up for no obvious reason, just as a consequence of you driving on. But the logic is clear:

Since you can't run a red light for no good reason, if you do, there must turn out to be one.

So you keep your speed, and suddenly it hits you. You've been Gödelized. The logician Kurt Gödel proved in the early 1930's that a formal system strong enough to prove its own consistency must be inconsistent. If you know that you are infallible, you're not. Now that you know that you will never run a red light unless it's safe, this very knowledge poses a safety problem.

How does this end? What's the moral to take away from it?

a) "Suddenly it hit you". And that was that. As in the story of the guy who couldn't figure out why that baseball was getting bigger and bigger.

b) Every intelligent mind must be humble: Already the ancient greeks knew about hubris. We should program the AI to be more like "I might be wrong, but that traffic light looks a bit reddish to me...".
And finally we know why people who think they are better than average drivers are more likely than others to be involved in accidents.

c) Every intelligent mind must think it has free will: The AI must work under the illusion that its own decisions aren't determined by its source code, but instead depend on a mysterious concept of choice.

d) Every intelligent mind must have subconscious levels:
"All of a sudden you notice that the car has stopped. Somehow your virtual right leg stretched out, because it just had to, and your virtual right foot pressed the virtual brake pedal. You didn’t choose to, because the information about this happening only reached your reasoning module after it already happened. Somehow, you took the right decision without being aware of it."

e) Something else?

Stalemate ftw!?

Today, Magnus Carlsen and Fabiano Caruana are about to play their eighth game of the world chess championship match. So far, seven draws.

If all twelve regular games are drawn there will be a tiebreak match of faster games. But there's already a world championship in speed chess, we don't really need another one. There have been other suggestions, like Chess 960, but again that's a different game.

I guess it's fair to say that chess at the highest level has a bit of a problem. It's hard to get the general public excited over a game that goes on for hours, and almost always ends in a draw. By the way, let's throw in a link to a sketch.

There is a nice article about the tendency for draws by Lars Bo Hansen, "Carlsen vs Karjakin revisited". A claim that has often been made, and that is stated in Hansen's article as well, is that "at the core, chess is a drawn game".

But we don't really know that. The computers have shown that there is still room to take the game to a new level. And even if the best engines draw too when facing each other, at least it shows that the earlier conclusion about the inherent drawishness of chess based on human grandmaster games was not well founded. Maybe at a higher level still, White wins all the time.

An old idea is to abandon or modify the concept of stalemate. According to the stalemate rule, the game is drawn whenever the player to move has no legal move. Normally that player will still have free squares for their king, it's just that putting your king en prise is illegal.

But stalemate a bit illogical. You can't pass if you have a legal move, and so-called zugzwang is an important part of the game. Yet the ultimate form of zugzwang, where you can't move your king without putting it in check, lets you get away with a draw.

The stalemate rule is also a real hassle whenever you explain chess to beginners, because it means you have to reach a certain level of skill before you can meaningfully play a game at all. It would be much easier to teach chess to kids if the goal was simply to capture the opponent's king.

What if stalemate would count as a win?

Matt Bishop wrote an article about this idea a few years ago. He seems to suggest that stalemate would simply count as a win for the stalemating player. A counterargument is that this would take away a lot of the beauty of the game. Not just the beauty of tricky stalemate combinations, but also the beauty of forcing checkmate.

Even though few games actually end in stalemate, abandoning the stalemate rule completely (so that stalemating your opponent would count as a win) would change the game drastically. As was pointed out in an answer to a question on stackexchange, you would no longer have to get your king in front of the pawn in order to win with king and a pawn against a lonely king. This could make some games less interesting, because a lot of endgame technique would then suddenly not be necessary.

There is another option, which seems to have been mentioned already by Lucena around the year 1500, of counting stalemate as a "half-win". Stalemating your opponent could for instance give you 3/4 points, or 2/3. Or it could be counted as a pure tiebreak parameter.

This way, the game would only be "refined". Since checkmate would still be better than stalemate, all current endgame theory would still be valid. But in addition, we would get a whole new theory exploring when you can and when you can't stalemate your opponent.

Here is an "endgame study" that shows some of the basic technique that you would have to know in this form of chess:

White to play and force a stalemate!

White can actually force a stalemate in 14 moves. I will post the solution, but not immediately in order not to spoil it if someone wants to give it a try!

*

*

*

Spolier alert!

*

Alright, here's the solution:

1. Nc5! This is the only move that doesn't allow Black to escape! 1. - Kb2 2. Kd2 Ka2 (this move puts up the longest resistance, but there is also the trap 2. - Ka1 where White must not play 3. Kc2? but instead 3. Nd3 for instance). 3. Kc2. Again this is the only "winning" move: White has to take the opposition. 3. - Ka3 4. Kc3 Ka2 5. Nd3. White could repeat with 5. Kc2 but 5. Nd3 is the only move that makes progress. 5. - Ka3 6. Nb2! (Nc5 repeats) Ka2 7. Nc4! (Nd3 or Kc2 repeats) Ka1! (the most testing defense). 8. Kd2! Here White could also play 8. Kd3 which is equally good. But 8. Kc2? makes no progress: After 8. - Ka2 White would have to go back with 9. Kc3. Back to the main line: 8. - Kb1 9. Kd1/d2 Ka1 10. Kc1 Ka2 11. Kc2. By maneuvering the king into opposition, White has now reached this position with Black to move. Now it's easy: 11. - Ka1 12. Na3/d2/d6 Ka2 13. Nb1/b5 Ka1 14. Nc3 stalemate!

Notice that 1. Kd2? is refuted by 1. - Ka2! (not 1. - Kb2 2. Nc5 which would lead to the line above with a different move order). Now if 2. Nc5 then 2. - Kb2 and White is in zugzwang, while if 2. Kc3 then 2. - Kb1! (not 2. - Ka3? 3. Nc5) and White can't make any progress.

Just to record some more thoughts on this: It's quite easy to see that K+N cannot "in general" stalemate a bare king. First, a stalemate can only occur in a corner. Second, if the black king is outside the region of the six squares a1, a2, a3, b1, b2, c1, then it's impossible to force it into that region without allowing it to escape again. Up to symmetry, the only way to force the black king into that triangle is if it's on a4, the white king is on c4, and the white knight controls a5. Then Black has to play 1. - Ka3. In order not to let Black out again, White would now have to make a move with the knight to a square where it controls a4. Since it was previously on b7, c6 or b3, that square would have to be c5. After 2. Nc5 there would follow 2. - Kb2 3. Kd3 Kc1, and Black gets out of the critical region at c2 or d1.

This means that if the black king is anywhere in the middle of the board, White can never force a stalemate. But notice that 8 by 8 is actually the smallest board-size where the argument works! Any smaller and there might be a different situation where Black has to move into some critical triangle!

Legenden om problem 6

Youtube föreslog att jag skulle titta på en video om The Legend of Question Six. Jag insåg snart att jag hade hört talas om detta supersvåra problem för nästan 30 år sedan, men visste inte att det sedermera hade fått legendstatus. 😃

Jag var med på den internationella matematikolympiaden 1989 och hörde förstås berättelserna om den där lilla 13-åringen från Australien som hade fått guldmedalj året innan (Terence Tao, numera superkändis). Vi hörde också historien om problemet som ingen i problemkommittén kunde lösa. Jag tror det var Arthur Engel som berättade om det ("...yet eleven of you solved it..."). Mattias Jonsson som hade varit med året innan anmärkte småskrattande att "hur svårt de än gör det så är det alltid någon idiot som löser det...".

Men jag letade aldrig fram det där problemet. Så det var kul att till slut få se vad det handlade om, och att se bilder från gamla olympiader. Förstås pausade jag runt 7.30 för att fundera lite själv på problemet, och vet ni vad, jag löste det! Yay, jag kan fortfarande!

Men den andra videon, "The Return of the Legend of Question Six" var lite av ett antiklimax. Vi får inte se hela lösningen, och det som presenteras är inte riktigt trovärdigt. Ingen skulle väl sätta sig och råräkna som en dator på det sätt som görs i videon, eller rita upp hyperbeln och sitta och stirra på den. Det känns som efterhandskonstruktioner. Men däremot att lösa ut en variabel och se att det blir en andragradare är väl bland det första man gör (och ett viktigt steg i lösningen, lite ironiskt med tanke på kommentaren om andragradsekvationer vid 3.30 i den första videon). Gänget som gör Numberphile är väldigt bra på att göra spännande introduktioner, men ibland kommer de liksom inte ända fram till poängen.

Hur som helst, problemet är lätt att formulera: Visa att om $a$ och $b$ är positiva heltal och $a^2+b^2$ är delbart med $ab+1$, så är kvoten \[\frac{a^2+b^2}{ab+1}\] kvadraten på ett heltal.

Spoiler alert, och for the record, här är hur jag tänkte (inklusive återvändsgränder!):
Kalla kvoten $(a^2+b^2)/(ab+1)$ för $n$. Vissa värden på denna kvot, som $n=2, 3, 6, 7$, är omöjliga av delbarhetsskäl (men detta visade sig vara oväsentligt). Så jag tittade på fallen $(a^2+b^2)/(ab+1)=4$, som har lösningar, och $(a^2+b^2)/(ab+1)=5$, som ska visa sig sakna lösningar. Om vi fixerar en av $a$ och $b$ och löser ut den andra, får vi en andragradsekvation med två lösningar. Om den ena roten är ett heltal, måste även den andra vara det. Ur en lösning (om det finns någon alltså) kan vi därför få oändligt många andra genom att stegvis byta värde på en av variablerna. För $n=4$, alltså ekvationen $a^2+b^2 = 4(ab+1)$, kan man se hur det funkar. I talföljden $0, 2, 8, 30, 112, 418,\dots$ är varje par av konsekutiva tal en lösning. Följden kan även fortsättas åt andra hållet:
\[\dots, -418, -112, -30, -8, -2, 0, 2, 8, 30, 112, 418,\dots\] Det verkar inte finnas någon motsägelse i att lösningarna kan bli hur stora som helst. En annan observation som till slut visade sig oväsentlig är att den här följden uppfyller en linjär rekursion, varje tal är $n$ gånger föregående minus talet dessförinnan. Skulle det finnas någon lösning för $n=5$ (eller andra lösningar för $n=4$), blir det en liknande talföljd. Sådana följder med andra ordningens rekursion kan skrivas "explicit" med ett uttryck som involverar rötterna till den "karakteristiska ekvationen" (som i Binets formel). Men det verkar inte ge någon avgörande insikt.

Frågan är om en sådan här följd kan minska till ett minsta värde och sedan vända uppåt igen. Det enda man behöver konstatera för att se att det inte går är att för fixt $a$ (och fix kvot $n$, till exempel 5) kommer de två möjliga värdena på $b$ att ligga på varsin sida om $a$. Det kan man skriva upp "pq-formeln" och krångla fram, men det är enklare att se direkt ur ekvationen $a^2+b^2 = n(ab+1)$. Om $a$ är fixt och $b$ går mot (plus eller minus) oändligheten, blir vänsterledet för stort. Men om vi sätter $b=a$, är det i stället högerledet som är för stort (förutsatt att $n\geq 2$). De två rötterna ligger alltså på olika sidor om $a$.

Så om det finns någon heltalslösning, måste det finnas en sekvens av heltalslösningar som är oändlig åt båda håll och monoton. Men det blir konstigt där den byter tecken. Vi kan inte ha en av $a$ och $b$ negativ och den andra positiv, och om den ena är 0, är kvoten lika med kvadraten på den andra. En kvadrat alltså! Klart!!!

I kommentarerna till den andra videon fanns referenser till något som tydligen kallas "Vieta jumping" eller "root flipping". Aldrig hört talas om! Det var väl det där tricket med att få en oändlig följd av lösningar ur en enda. Men jag trodde det kallades Descente Infinie och gick tillbaka till Fermat (eller rentav Euklides!?) ...

Hoppas på 7-1 även i år!

När man pratar om 7-1-segern 2014 tänker väl särskilt tysklandsvännerna på fotboll, och på semifinalen i VM 2014 där tyskarna spelade skjortan av hemmalaget Brasilien.

Men i Sverige togs också en viktig 7-1-seger. Sverigedemokraterna var på väg framåt, och det började bli tydligt att miljöpartiets förhoppningar om en jämn match om tredje pris var på väg åt samma håll som Brasiliens.

Det stod klart att Åkesson och hans partivänner inte var några Bert Karlsson-typer med drag under galoscherna. De hade suttit en mandatperiod i riksdagen och ändå ökat i popularitet. I valet fick de nästan 13 procent, och politiker, journalister och allmänhet undrade vad övriga partier hade gjort för fel.

Mycket av resonemangen satt vid den här tiden fortfarande kvar i idén att nästan ingen egentligen tyckte som sverigedemokraterna. Om bara övriga partier hade fått fram sina budskap och om bara folk hade förstått vad sverigedemokraterna står för, så hade de åkt ur riksdagen med näsan före. Så felsökningen ledde till den ena hypotesen efter den andra. Än hade de övriga partierna låtit debatten handla för mycket om invandringen, än hade de inte tagit debatten om invandringen. Än hade Åkesson fått för mycket plats i media, än hade han inte granskats i media. Man talade fortfarande om "missnöjesröster".  

Från vänsterhåll påpekades med illa dold förtjusning att det var moderaterna som hade tappat mest till SD. Det visade, antydde man, att moderaterna egentligen är smygfascister. Fast det borde väl vara tvärtom?

Jag är överlag ingen vän av moderatpolitik, men en sak jag tycker Reinfeldt ska ha heder för är att han inte vek sig för den nationalistiska trenden. I det här klippet punkterar han Åkessons retorik genom att i fyra ord sammanfatta sverigedemokraternas hela idé: Det är invandrarnas fel. Reinfeldt förstod nog vartåt det lutade inför valet 2014, men han förlorade hellre 20 stolar i riksdagen än lät sitt eget parti glida med i den invandrarfientliga vågen.

Nu har det gått några år och vi har sett att nationalism och högerpopulism är en internationell trend. Hela förklaringen kan inte ligga i att svenska politiker har gjort något strategiskt fel. I stället har vi fått inse att de flesta som röstar på SD faktiskt tycker som de. De tycker att invandring, feminism, hbtq-rättigheter, miljötänk och så vidare har gått för långt, och de tycker att det är bättre om vi får en stark ledare och politisk styrning av media, domstolar, polis och skola.

Givet att det är så, betraktar jag det som hände i valet 2014 som i stort sett idealiskt. Att beskriva det som att "vi vann med 7-1" kan förstås låta som att på typiskt politikermaner skönmåla ett fiasko, men när 13 procent av väljarna röstar för nationalism och rasism, ser jag hellre att bara ett parti får deras röster, än att denna ideologi ska genomsyra hela politiken. När vi börjar fråga vad de andra partierna har gjort för fel som har misslyckats med att locka de här väljarna, är vi inne på en farlig väg. Jag tycker att de gjorde helt rätt, och att det var starkt att 7 riksdagspartier av 8 tog avstånd från högerpopulismen.

Humanity's last outpost (on the chess board)

In the last five years or so, there's been a revolution in artificial intelligence. Before that, it used to be that computers were good only at well-defined tasks like arithmetic, sorting stuff, and searching for stuff they'd just sorted.

Basically, computers could do the things that we humans think when we do. It turned out that chess, the old holy grail of AI, could pretty much be reduced to plain calculation, like "I go bam, you go wham, I go swoosh..." and so on. The asian board game of Go on the other hand seemed to be much more about that mysterious intuition and didn't easily yield to "good old" programming techniques.

Then came deep learning. And now it's pretty much the opposite. Computers are now good at the things we do without thinking. As Andrew Ng puts it around 4.45 into this video, a useful rule of thumb is that anything a typical person can do in one second can now be automated. Like recognizing whether or not a picture is of a bird.

The comic 1425 from xkcd (Randall Munroe) illustrates what has happened.

What I now find fascinating about this comic is that it was published in 2014, and the character Ponytail thinks she only needs five years, not that it's impossible. Somehow Randall Munroe seems to have known what was going on, even though many people in AI have testified that they didn't see it coming.

Using deep learning, the program AlphaGo from Deep Mind clearly defeated the best human Go players, and in December last year, the new version AlphaZero shocked the world of chess and AI by beating Stockfish, a state-of-the-art chess program way beyond human level, by a clear margin in a match of 100 games.

So the new situation is that computers are good at everything that just requires following a simple recipe, like multiplying thousand-digit numbers, and everything that just takes instinct and learning from examples, like recognizing what's in a photo or whether a position in a board game looks generally promising.

But there are still purely intellectual tasks where the human mind rules, and where software isn't of much help.

One thing that (surprisingly?) hasn't been automated yet is research in mathematics. In this talk from a few years ago, Tim Gowers discusses the problem of getting a computer to discover mathematical ideas, and I think everything he says is still relevant. Even though computers outperform us in arithmetic, it has turned out to be extremely difficult to get software to explore and answer questions of the type "Does there exist a number with the property that ... ?". Reasoning about a generic number called $n$ is different than handling a particular one like 756767765776.

The situation is similar in the realm of board games. Stockfish and AlphaZero are mindbogglingly strong when it comes to the basic problem of choosing a move in a typical position. But if we start asking questions of the type "Does there exist a position with the following property ... ", they can't give us the answer. That's a type of question that belongs on a different level.

There has been quite some discussion about chess positions that supposedly baffle the best software. A few years ago the physicist Roger Penrose claimed that a certain chess problem holds the key to human consciousness. But I guess a neural network in combination with Monte Carlo tree search (what AlphaZero does) will solve such problems in the near future, at least if they can train the neural network during the game (to tune it to the position at hand).

Whether or not they do, there is an old and well-established domain of chess dealing with constructing positions with extraordinary properties, and so far there is no software that can challenge the human mind in that area. So in any case it's not true that computers beat humans in all aspects of chess.

The traditional form of a chess problem is "Mate in $n$" (again $n$ is a generic number!), which means that White makes the first move, and forces a checkmate in at most the stipulated number of moves, against every possible defence by Black. There is software for solving such problems, but now we're talking about the construction of chess problems. This is a form of art where the composer (yes, that's what it's called!) tries to present a chess position where the optimal play has some remarkable and surprising properties.

Sometimes this develops into a sort of contest, where problem composers challenge each other to come up with chess positions with certain stipulated properties (not unlike research!). One of their favorite topics is so-called underpromotion, meaning promotion of a pawn to a piece other than queen.

It is easy to think of a situation where it's better to promote to a knight than to a queen, since the knight can move in ways that the queen can't. But there also exist situations where it's better to promote to a rook or a bishop, even though it seems that a queen can do anything that those pieces can. These situations all have to do with the rule of stalemate, according to which the game is drawn if a player doesn't have any legal moves. Since it's not legal to put one's king en prise, it's sometimes better to have a weaker piece than a stronger one, either because you want to get stalemated, or to avoid stalemating your opponent.

For decades, a seemingly impossible challenge was the Babson task: Composing a problem where after White's initial move, Black can promote a pawn, and where in White's second move, the only solution is for White to promote one of their pawns to the same piece as the one Black chose!  

Several expert composers tried in vain to find such a position, and Pierre Drumare (who sort of solved the task in 1980 but with an illegal position) declared after twenty years that he didn't think such a position could exist. To begin to appreciate the difficulty, notice that (as I actually mentioned in one of my very first blog posts!) the defensive underpromotion to rook or bishop (in order to try to get stalemated) requires such special circumstances that in all of chess history, with databases of millions of games and libraries full of books, there is not a single known case of this happening in a real game. Even the offensive underpromotion (avoiding to stalemate one's opponent) is extremely rare, especially the promotion to bishop.

And the Babson task requires these promotions to work and to be necessary, simultaneously from the same position.

The task was first successfully achieved by Leonid Yarosh in 1983 (comment to establish that I was a nerd before it was cool: I knew about the Babson task before it was solved, in the days when this problem by Bo Lindgren was the best that had been achieved!), and in the following years a number of other Babson problems were composed by Yarosh, Drumare and others. Among them was the following particularly beautiful one, by some connoisseurs regarded as the most remarkable position ever set up on a chess board:

 Karlheinz Bachmann, Peter Hoffmann and Martin Hoffmann, Die Schwalbe 1987.

Mate in 4.  

White starts with the "key" 1. hxg7! Normally an initial capture is frowned upon in the problem world, but this key is thematic and opens up a flight square for the black king, so it's nice anyway.

If the black king takes back on g7, White will checkmate with 2. Ng5, 3. Rg8, and 4. Rg6 no matter what Black does. If Black promotes the d-pawn in move 2 (in any of the 12 possible ways!), then 3. Rg8 will be check, so Black doesn't have time for any counterplay. 

Given that Black cannot move the king in move 1, White's main threat is 2. g8Q and 3. Qg6 mate. Promoting on c1 or e1 can delay this plan by at most one move, so the question is whether a black promotion on d1 can throw a spanner into White's works.  

After 1. .. d1Q, 2. g8Q, Black can try to delay the checkmate with 2. .. Qxd4+. Now White cannot capture the queen because of stalemate, but instead White blocks the check with 3. c4!, at the same time pinning the black queen and checkmating in time. 

But Black can be clever and instead promote to a rook! Then after 1. .. d1R, 2. g8Q Rxd4+, blocking with 3. c4 or taking the rook will be stalemate, and everything else allows Black to give one more check. To counter the stalemate idea, White too promotes to a rook so that after 1. .. d1R, 2. g8R! Rxd4+, 3. c4! (also perfectly blocking the bishop's diagonal!), there is 3. .. Kxf7 and 4. Rdf8 mate.

Black has yet another stalemate trap, the "self-paralysis" 1. .. d1B! after which the solution is 2. g8B!, allowing 2. .. Kg7. Since the black king is now confined to the long diagonal, White checkmates with 3. c4 and 4. d5.

Black's last trick is 1. .. d1N, which threatens to give not only one but two consecutive checks on the white king. White prevents this by being the first to give check: 2. g8N+! Kg7, 3. f6+ Kh7/g6, and 4. Qxc2 mate! 

In each case, White's echoing of the Black promotion is the only solution. For instance, in the queen variation White actually needs a piece that moves in all directions. And looking at the knight variation we realize that 2. g8N+ was a threat all along, but that any black piece on d1 except a knight prevents the checkmate 4. Qxc2.

Peter Hoffman has continued to explore variations on the Babson task where the White promotions aren't necessarily echos of the Black ones, but instead form a permutation of the four pieces. For instance, the following problem realizes the pattern Queen->Rook, Rook->Knight, Knight->Queen, Bishop->Bishop.

Peter Hoffman, Die Schwalbe 2008.

Mate in 4.

After 1. cxd7, d1Q, White plays 2. dxe8R! so that 2. .. Qd7+ can be met with 3. Bxd7 without stalemate. On 1. .. d1R, White must promote to a knight, since in this problem not even a rook stops the old stalemate trap 2. .. Rxd4+. On 1. .. d1N on the other hand, White can now allow Black to give a check on b2 or c3, provided that they have a queen on e8! Finally the self-paralysis 1. .. d1B is again met with a bishop promotion. As in the previous problem, there are numerous details that amazingly make these White promotions the only moves that work.

In what very much looks like a mathematical research project (in a sense it is!), Hoffman has so far demonstrated eight permutations of the 24. By the way, in the table summarizing the results, the original Babson pattern (Q->Q, R->R, B->B, N->N), is called the echo. Mathematicians would call it the identity permutation, but I think echo is both more descriptive and beautiful, and I wish we would use it in mathematics. Imagine reading in an algebra book that "the only automorphism of the field of rational numbers is the echo"!

Among the 16 permutations not yet realized, Hoffman mentions the "reciprocal" pattern Q->N, N->Q, R->B, B->R as particularly attractive. But beware, not even the "3/4-Babson" pattern Q->N, R->B, B->R has been demonstrated!

If you want to try this challenge, it might be useful to have a chess program available. But it's a bit like using a pocket calculator in mathematical research. Currently the only thing the software will do for you is to look for the quickest forced mate in a position that you set up. You can't use it to systematically search through positions, and it will never tell you that "Had it not been for the flight square on g5, this variation might have worked, perhaps we should try adding a white pawn on f4 or h4".

Even though the permuted Babson tasks are well-defined questions with a finite search space, exactly the sort of task where computers are supposed to excel, there is to my knowledge no software that can even meaningfully attack them. It doesn't make sense to randomly throw out pieces and check whether it led to a permuted Babson, because those positions are so rare that you won't find one in a million years. But in order to search intelligently, it seems one has to use concepts that go beyond the way current software represents chess.