Winning strategies: working a game backwards from its end

0:00Here is a game you can play right now, with no board, no dice, and nothing to write on. Two players. The first one says a number: one, two or three. Then you take turns. Each turn you add one, two or three to whatever the other person just said, and you say the new total. So it might go: three. Five. Eight. Nine. Twelve. And whoever says twenty-one has won.

0:27That is all of the rules. Your book prints them in about four lines. Go and play it a few times. I mean that — the rest of this works much better if you have lost a few first. Because here is what happens. If one of the two of you works out what is going on, that person wins every single time. Not usually. Every time. From either seat, against any play at all.

0:56And this is a game with no chance in it. No dice, no hidden cards. Everything is on the table. Which means somebody can be guaranteed a win before the first word is spoken. The question is who — and how they know. Now, the natural thing is to think forwards. I say two, then they might say three, four or five, and then from each of those… And that dies almost immediately.

1:26After one turn there are three possibilities. After two turns, nine. After three, twenty-seven. After four, eighty-one. By six turns you are past seven hundred. And if you count every complete game — every possible way the numbers could run from nothing up to twenty-one — there are two hundred and twenty-three thousand, three hundred and seventeen of them. You are not holding that in your head. Neither is anybody else.

1:58So thinking forwards is not merely hard. It is the wrong direction. So turn the question round. Do not ask what you should say first. Ask what you want to be saying at the end. Which is easy. You want to be saying twenty-one, because that is what wins. Good. Now ask the next question backwards. What do you want to be saying just before that? You want to leave your opponent somewhere they cannot reach twenty-one, whatever they choose to do.

2:30And that is a very specific place, because they can only add one, two or three. Suppose you say seventeen. Now it is their turn. They can add one, two or three, so they can say eighteen, nineteen, or twenty. Not one of those is twenty-one. They cannot get there. They are not allowed to add four. And whatever they do say, you can finish. If they say eighteen, you add three. If they say nineteen, you add two. If they say twenty, you add one.

3:05Every single one of those lands you on twenty-one. So seventeen is a trap. Say seventeen and you have already won — your opponent just has not noticed yet. And look where seventeen came from. Twenty-one, minus four. One more than the biggest move anybody is allowed. Which means you can do it again. If seventeen wins, then seventeen is what you want to be saying. So what traps them into handing you seventeen?

3:38Same argument, same gap. Seventeen minus four is thirteen. And thirteen minus four is nine. Nine minus four is five. And five minus four is one. One, five, nine, thirteen, seventeen, twenty-one. That is the ladder. Six rungs, four apart. If you can say every one of those in turn, you cannot lose, because every rung is a place your opponent cannot escape from. So who gets onto the ladder?

4:11Look at the bottom rung. One. And the first player is allowed to say one, two or three on the opening move. So the first player simply says one. And then keeps stepping. Whatever the opponent adds, the first player adds whatever makes it up to four. They add one, you add three. They add three, you add one. One, five, nine, thirteen, seventeen, twenty-one. Game over, and the second player never had a move that mattered.

4:43By the way, this is why playing greedily loses. Add three every time and you go three, eight, twelve, sixteen, twenty. You never touch a rung. Now your book gives you a second game, and it looks a great deal harder. The opener may say anything from one to ten. After that, each player adds anything from one to ten. Whoever says ninety-nine has won. Bigger target, bigger moves, far more choices on every turn.

5:17But it is the same construction, and it takes about ten seconds. The biggest move is ten, so the gap between rungs is eleven. Count back from ninety-nine in elevens. Eighty-eight. Seventy-seven. Sixty-six. Fifty-five. Forty-four. Thirty-three. Twenty-two. Eleven. Nine rungs, and the bottom one is eleven. And now look hard at that bottom rung, because this is where the second game parts company with the first. In game one the bottom rung was one, and the opener was allowed to say it.

5:56Here the bottom rung is eleven. And the biggest opening move is ten. The first player cannot reach it. They cannot get onto the ladder at all. Whatever they say — anything from one to ten — the second player tops it up to eleven and takes the bottom rung. So in game two, the second player wins. Going first is not an advantage here. It is a handicap. And now the whole thing collapses into a single division.

6:28Take the target. Divide it by one more than the biggest move allowed. Game one. Twenty-one divided by four. Five, remainder one. There is a remainder, so the first player wins — and should open by saying exactly that remainder. One. Game two. Ninety-nine divided by eleven. Nine, remainder nothing. No remainder, so the first player cannot get on, and the second player wins. That is both games, entirely, in one division each. And it works just as well on a target you have never seen before.

7:09Let's test that, because your book changes one thing at the very end. Same game, same moves — one, two or three — but the target is twenty-two now, instead of twenty-one. And you might well expect the winner to swap over. One more step, so surely the other person gets it. Do the division. Twenty-two divided by four is five, remainder two. There is a remainder. So the first player still wins.

7:39What changed is not who wins. It is what they have to say. The whole ladder shifts up by one. Two, six, ten, fourteen, eighteen, twenty-two. So they open with two instead of one, and everything else is the same. Which is exactly why you do the division, rather than trusting your feeling about it. So go and make one up. Pick a biggest move. Pick a target. Say: add anything from one to five, and first to reach fifty wins.

8:13The gap is six. Fifty divided by six is eight, remainder two. There is a remainder, so the first player wins, and opens by saying two. Then two, eight, fourteen, twenty, twenty-six, thirty-two, thirty-eight, forty-four, fifty. You have just predicted the winner of a game that nobody has ever played. And that is the last idea in this chapter, and it is a large one. Work out a procedure in advance, and then simply follow it. Your book calls it computational thinking.

8:50Which is the whole chapter, really. Find the structure once, and you never have to search again. That is chapter three. I will see you in the next one.