With a little more from Smullyan

Maurice Ashley is an American chess grandmaster. He played for the US Championship in 2003. He coached two youth teams from Harlem to national championships and played himself in one scene of the movie Brooklyn Castle. He created a TEDYouth video titled, “Working Backward to Solve Problems.”

Today we discuss retrograde analysis in chess and other problems, including one of my own.

Raymond Smullyan popularized retrograde chess puzzles in his 1979 book The Chess Mysteries of Sherlock Holmes and its 1981 sequel, The Chess Mysteries of the Arabian Knights. Here is the second example in the first book—except that I’ve added a white pawn on b4. What were the last three moves—two by White and one by Black—and can we tell the two moves before that?

Not only is Black checkmated, Black is outgunned on material. The puzzles do not try to be fair and many are “unnatural” as game positions. The point is that the positions are legal. There can occur in games from the starting position of chess—but only in certain ways that the solver must deduce.

White’s last move must have uncovered check from the white bishop on h1 because the bishop cannot have moved there. The uncovering could have come from White’s pawn on g2 capturing a black piece on h3 except that there is no way a bishop can get to h1 locked behind a white pawn on g2. So it must have been from the pawn on d6. If the last move were d5-d6 discovered check, then what was Black’s previous move? Black’s king cannot come from being adjacent to White’s king on b8 or b7, so it came from a7—but there it would have been in an impossible double check. The whole setup looks impossible, until we realize that White could have captured a black pawn en-passant after it moved from d7 to d5 to block the check. Play could have unfolded from this position:

The game could have gone 1. Bd6-c5+ Ka7-a8 2. e4-e5+ d7-d5 3. exd6 en-passant and checkmate. So the last three moves must have been 2. e4-e5+ d7-d5 3. exd6. But what about the first two? Suppose we were told that the checkmating move is the first time a white piece ever occupied the square d6. So the game didn’t go this way. Could it have gone another way that obeys this extra condition? The answer is at the end.

Ashley’s video raises the idea of retrograde analysis for planning and problem solving in life. If your goal is ${X}$, then working backward from ${X}$ can tell you the subgoals needed to achieve it. The business executive Justin Bariso expanded on Ashley’s video even further in a neat post on his own blog. Bariso recommends to “plan your project backward,” opining that with the way things are usually done,

More time and money are scheduled for initial steps than are really needed.

Here is an example from Smullyan’s book which was also featured in a 2011 video by former world women’s champion Alexandra Kosteniuk:

How can this position come about—in particular, where was White’s queen captured? Focus on the main events—what was captured on b3, e6, h6, and in what order?—helps to plan the play. Incidentally, Kosteniuk was a hard-luck loser this past Friday in the semifinals of this year’s women’s world championship in Tehran.

What matters often in research, though, is finding the most propitious initial steps—and the time budget is open-ended. Often we build a new tool and set out to prove theorems whose statements ${Y}$ we might not know in advance. Yet for statements ${X}$ like “Is ${\mathsf{P \neq NP}}$?” the question, “Is ${X}$ a theorem?” is a classic retrograde problem: Proof steps are the moves. A legal move either instantiates an axiom or follows by a rule of deduction from one or more earlier steps. Undecidability for the underlying formal system means there is no procedure to tell whether any given position is legal.

How might retrograde analysis help in complexity theory? Dick and I once ventured a notion of “progressive” algorithms. Maybe it can be supplemented by analyzing some necessary “regressive” behavior of algorithms. Or more simply put, using retrograde analysis to show that a statement ${Y}$ is impossible may be what’s needed to prove ${X}$.

A Pebbling Example

I taught a hybrid algorithms-and-complexity short-course at the University of Calcutta last August. One of my points was to present breadth-first search (BFS) and depth-first search (DFS) as paradigms that correspond to the complexity classes ${\mathsf{NL}}$ and ${\mathsf{PSPACE}}$ in particular. I illustrated more complicated algorithms that run in deterministic or nondeterministic logspace and explained how in principle they could be reduced to one call to BFS.

I presented pebbling in the guise of Monty Python’s version of King Arthur and his fellow “riders.” They wish to conquer a network of towns connected by one-way roads. Each town ${v}$ has a defensive strength ${d}$. To conquer ${v}$, the riders need to occupy at least ${d}$ other towns with incoming roads, then any rider may occupy ${v}$. A rider can leave a town and go “in-country” at any time, but to re-enter a previously conquered town, that town must be re-conquered. Source node(s) can be freely (re-)occupied, and multiple riders can occupy the same node. Given a graph ${G}$ with source(s) s and goal node f, and an integer ${k}$, the question is:

Can f be conquered by k riders starting on s, and if not, what is the minimum k?

The case of pebbling, strictly speaking, is when ${d}$ always equals the node’s in-degree, while ${d=1}$ is basically BFS. Various forms of pebbling have been studied and all were instrumental to various complexity results. Here is a simple example:

The answer is ${k = 3}$: Three riders can conquer ${f}$ in the order ${s,u,v}$, then ${s}$ moves to ${x}$ and ${u}$ enters ${w.}$ This gives the strength needed for ${x}$ to conquer ${y}$, but ${u}$ needs to be re-conquered. This is done by starting ${v}$ again from ${s}$ to ${u}$, and finally ${f}$ falls.

Now picture the following graph in which every OR gate has hit strength ${1}$ and every AND gate has hit strength ${2}$. The gate labeled b is undetermined. If it is OR, then gate f can be conquered by ${3}$ riders as follows: Two riders staring at ${x_1}$ and ${x_2}$ first conquer gate a, and then using the free entry into gate b, have a conquer d. Then the rider on b rides back to ${x_3}$ and helps the third rider go from ${x_4}$ to e in like manner. Finally the riders on d and e conquer f. That was easy—but what if b is an AND gate? Can ${3}$ riders still do it? You may wish to ponder before looking below.

I gave this as part of a take-home final to over 30 students in the course, saying to argue that when b is an AND gate, ${k = 3}$ riders are not enough. Almost all tried various forms of forward reasoning in their proofs. Many such proofs were incomplete, for instance not considering that riders could rewind to start.

Only a few found the neatest proof I know, which is retrograde: Before f is conquered, there must be riders on d and e. One of those must have been the last to arrive, say e. This means the immediately previous step had riders on d, b, and c. The only move before that must have been from a conquering d, so we have proved the necessity of the configuration (a,b,c). And this configuration has no predecessor. So three riders cannot conquer f.

Open Problems

Can a more-general, more-powerful lower bound technique be built from this kind of retrograde reasoning?

Chess answers: In the first puzzle, if no White piece had previously occupied d6, there is still a way the game could go. Look at the second diagram and picture White’s bishop on c5 with a knight on b6. White can play knight to the corner discovering check and Black’s king can take it, giving the overall moves 1. Nb6-a8+ Ka7xa8 2. e4-e5+ d7-d5 3. exd6 en-passant and checkmate.

In the second chess puzzle, the only piece White could have captured on b3 was Black’s queenside bishop. In order for it to leave its initial square c8, however, Black needed to capture on e6. The only White piece able to give itself up there was the missing knight, because White’s queen could not escape until the move a2xb3 happened. So Black’s capture on h6 was of White’s queen. I can find a legal game reaching this position (with White to play) in 18 moves; is that the minimum?

Retrograde chess puzzles become far more intricate than the examples in this column suggest. Besides Smullyan’s books, the great trove for them is maintained by Angela and Otto Janko here. Joe Kisenwether has some examples from games other than chess.

[fixed that exam problem was “to argue that…”]