Zarf Updates

It was a sharp grey London morning that begins my story. I was meeting my friend at the Xenocrates Club -- not my habitual retreat, but Xerloc said he had a matter for my memoirs.

The doorward squinted and eventually allowed me to the Club's sanctum, an indefinite smoke-stained sprawl of nooks, books, and gaslamps. The low tables were covered with scraps of paper and half-eaten crumpets. But the only figure in evidence was Xerloc, peering around with evident satisfaction.

"Ah, you are just in time. Everyone has left."

"I know these social clubs are often more like anti-social clubs, but really, Xerloc. What are you on about?"

"I'm sure you are aware of the famous Chess Mysteries of my famous cousin Sherlock Holmes." (My friend is of the O'Xolmes branch of the family, distant relatives of Basque extraction.)

"I am, indeed. Chess problems of retrograde analysis. I find them impenetrable."

"As do I, as do I. Thus I thought we might repair here for a more tractable challenge."

I gestured him to continue, but of course he already had. "You stand in the meeting place of the infamous Xenocrates Noughts-and-Crosses Club!"

"You mean to say--"

"Yes! The most devoted Tic-Tac-Toe players in all of London. And this," (he waved around the room), "is the remains of their latest tournament. A fiendish affair!"

"Great Heavens, Xerloc. What are the stakes?"

"A round of drinks at the nearest pub."

"At ten in the morning!?"

"I said it was fiendish," Xerloc said, rubbing his hands. "At any rate, they have all decamped. We may inspect... the evidence."

My friend gestured me over to a table. "Let us start here."

The paper on the table was scrawled with this design:

"What do you observe?" my friend asked, with altogether too much anticipation.

"Well... X is about to win."

"To be sure," Xerloc said impatiently, "but never mind that. What was X's most recent move?"

I stared at the board in dismay.

"Oh, I should set the stage." Xerloc clasped his hands. "You must understand that the Xenocrates is comprised entirely of pretty good Tic-Tac-Toe players."

"I... see?"

"Yes. A pretty good player, when making a move, will infallibly review all available options. If there is a move which gives them an immediate win, they will always take it. Failing that, if there is a move which will allow their opponent an immediate win, they will always block it."

"What if there is more than one such move?" I asked.

"Then they will pick one of them, preferring an immediate win if possible. But, you understand, a pretty good player will not necessarily look beyond the immediate situation. They may make a move that allows the opponent a future win -- just not on the upcoming turn. They are not very bright!"

I kept my first response to myself, and said only, "Ah."

"Also," my friend added, "it is the firm custom of the Xenocrates that X always goes first. So now, back to our board."

I looked again. "X threatens a win on two lines. If X's last move were in the center, then X would have had a right-side threat on the previous move, and O would have blocked it. But O did not."

"Very good."

"Similarly," I said, getting into my stride, "if X's last move were in the bottom right, X would have had a diagonal threat on the previous move. Similarly impossible. Therefore X's last move was in the top right!"

"Just so -- square c." At my frown, Xerloc waved at a plaque on the wall:

"Is that... a fragment of the Lost Pigpen Cipher?" I gasped. "The most secret encryption scheme of the Masonic Brotherhood? Never to be revealed to the knowlessman?"

"Is it? I hadn't noticed," my friend replied. "It's just a handy way to refer to the squares. Top right is c."

"Here is another example. This game is complete; O has won. But which was O's winning move?"

I glanced at the next table, and my brow furrowed. "Didn't you say that X always goes first?"

"Yes." Xerloc peered carefully at the paper. "Ah, I see. There should be three X's, not two. One of the X moves was erased after this game was abandoned... or won, as the case may be."

I scoffed. "X couldn't have won this game, my friend, because O made the last move!"

"Indeed, the missing X is not at g," Xerloc nodded. "So where is it?"

"Ah, now this is interesting. You've noticed that the Club's players don't always start in the center space. But I recognize X's handwriting here; this particular player does always start in the center space."

"All right..."

"Knowing that, can you determine the sequence of X's following moves?"

"Good heavens."

Xerloc emitted his irritating pedantic cackle. "Well, this must be a valid game, or the paper would have been ritually burnt! But it's true that nothing in the Club rules forbids playing in Greek."

"So then -- which symbol is X and which is O?"

"I have never studied the rules of Hellenic Tic-Tac-Toe. But you should be able to deduce which is which."

Which?

"Is every Tic-Tac-Toe game susceptible to retrograde analysis?" I asked.

"Not at all. Look at this board. Can you tell where the first move was?"

I shook my head.

"No more can I. Any of X's moves could have been first. What about the last move?"

I considered. "Clearly either c or d, which block threats. But I can't tell which."

"Neither can I," said Xerloc.

"Nor I," added a sepulchral voice. An equally sepulchral figure stepped from the gloom.

"Oh no," my friend muttered. He turned to me. "May I introduce my... relative... Myxroft O'Xolmes."

"Not the distant cousin of the famous Mycroft Holmes!"

"The same," Myxroft said wryly. "But you were saying?"

"I was about to observe that knowing the first move of this game might help resolve our conundrum."

"I'm afraid not," said Myxroft. "As it happens, I was present earlier. I saw the first move of this game, which wmfffgrrgff!" For Xerloc had just stuffed a crumpet into his mouth.

Xerloc turned to me, smiling. "My illustrious relative was about to say that the game's first move was at..."

Where?

At this point the prospect of crumpets began to sound tempting to all of us. (Except for Myxroft, who was still brushing stale crumbs out of his moustaches.) We departed the premises and made for the Zeno Club, at which Xerloc maintains a membership.

Unfortunately, we only made it halfway there. But the circumstances of our interruption -- and the shocking tale of the League of Red-Headed Stepchildren -- will have to wait for another volume of my excellent memoirs.

Afterword

Thanks to Nathan Curtis for playtesting.

I am an enormous Smullyan fan, and I treasure my copies of The Chess Mysteries of Sherlock Holmes and The Chess Mysteries of the Arabian Knights. However, I am absolute pants at solving them. I can barely follow along when reading the printed solutions to the puzzles.

I started writing this post in the hope that tic-tac-toe would be easier for me to get a grip on. As it turns out, I'm terrible at these puzzles too! I wound up creating them with the help of a Python script. The script just analyzes a given position and lists every move sequence that could get there, given the restrictions of Pretty Good Players. (Or declares the position impossible.) This makes finding interesting puzzles fairly easy, or at least tractable.

(I'll leave the script as an exercise for the reader.)

The idea of "retrograde tic-tac-toe" is an obvious punchline if you know Smullyan's books. I'm certainly not the first one to invent it. Alain Brobecker posted an article on the subject in 2007. However, his article concerns expert players (they never allow the opponent an opportunity to force a win). So his puzzles come out different from mine.

Joe Kisenweather has an older page on retrograde analysis of various games.

I also found a reference to a retrograde tic-tac-toe article in the 1970s, in the Journal of Recreational Mathematics. I haven't read that one, though.