A new kind of ‘liar’ puzzle using Freestyle chess

 Cropped from source

Raymond Smullyan is probably the world’s greatest expert on the logic of lying and the logic of chess. He is still writing books well into his 10th decade. Last year he published a new textbook, A Beginner’s Guide to Mathematical Logic, and in 2013 a new puzzle book named for Kurt Gödel. His 1979 book The Chess Mysteries of Sherlock Holmes introduced retrograde analysis—taking back moves from positions to tell how they could possibly have arisen—to a wide public.

Today Ken and I wish to talk about whether we can ever play perfect chess—or at least better chess than any one chess program—by combining output from multiple programs that sometimes might “lie.”

We will start with Smullyan-style puzzles today, but they are prompted by an amazing and serious fact. Even though human players have been outclassed by computers for over a decade, humans judging between multiple programs have been able to beat those programs playing alone. This happens even when the human player is far from being a master—someone who would get crushed in minutes by programs available on smartphones. We want to know, how can this be?

By coincidence, yesterday’s New York Times Magazine has a feature on Terry Tao that likens discovering and proving theorems to “playing chess with the devil”—quoting Charles Fefferman:

The devil is vastly superior at chess, but […] you may take back as many moves as you like, and the devil may not. … If you are sufficiently wily, you will eventually discover a move that forces the devil to shift strategy; you still lose, but—aha!—you have your first clue.

On this blog we have previously likened perfect programs to “playing chess against God”—this was quoting Ken Thompson about endgames where perfect tables have been computed. Since the programs we consider here occasionally err—one can say lie—we will reserve the “devil” term in yesterday’s Times for them.

Freestyle Chess

We, that is I and my Tech colleague Dr. Kathryn Farley, just visited Ken at his home base in Buffalo and had a great time. Of course the weather up there is near perfect this time of year and his family was wonderful to us. Plus we got to visit Wegmans—our pick for the greatest supermarket chain in the world.

One afternoon I was honored to sit in on a video conference in which Ken presented some of his research on using computer programs to evaluate the play of humans. Joining him via the Internet were two experts in so-called freestyle chess where humans are allowed access to multiple chess programs during a game. One-on-one the programs totally dominate the humans—even on laptops programs such as Stockfish and Komodo have Elo ratings well above 3100 whereas the best humans struggle to reach even 2900—but the human+computer “Centaurs” had better results than the computers alone. In the audience were representatives of defense and industrial systems that involve humans and computers.

Ken got into freestyle chess not as a player but because of his work on chess cheating—see this for example. Freestyle chess says “go ahead and cheat, and let’s see what happens…” The audience was not interested in cheating but rather in how combining humans and computers changes the game. While chess programs are extremely strong players, they may have weaknesses that humans can help avoid. Thus, the whole point of freestyle chess is:

Are humans + computers > computers alone?

That is the central question. Taken out of the chess context it becomes a vital question as computers move more and more into our jobs and our control systems. The chess context attracts interest because it involves extreme performance that can can be precisely quantified, and at least until recently, the answer has been a clear “Yes.”

At the beginning of the video conference Ken spoke about the history of computer chess, giving his usual clear and precise presentation, and then reviewed his joint paper showing the good results for human-computer teams were no fluke—they really made better moves. Ken used some of the slides from the end of his TEDxBuffalo talk. Then two Freestyle experts spoke, including a winner of three tournaments who doesn’t even have a human chess rating, and an interesting discussion followed on how they actually used the computer chess programs.

I must admit at first I was a skeptic: how could weak players, humans, help strong players, computers? Part of it was that when two or more programs disagreed on the best move the human could make the choice. This kind-of means saying the programs whose move you don’t choose are wrong.

As Ken and I mulled over the idea of freestyle chess we realized it raises some interesting puzzles. I wrote a first draft, then Ken took over adding more detail and tricks to what follows. Let’s take a look at the puzzles now.

Puzzle I

Suppose Alice has one program ${X}$ that is perfect except that there is one position ${Q}$ in which ${X}$ makes a error. To simplify, let’s suppose the only outcomes are win (${W}$) or loss (${L}$). An error means that ${Q}$ is a winning position for the player to move—it could be Bob not Alice—but ${X}$ chooses a move ${m_1}$ leading to a position ${R}$ that is losing for that player.

Let Alice start in a position ${P}$. She wants to play perfect chess using ${X}$ as guide. Can she do so? The bad position ${Q}$ might be reached in a game played from ${P}$, indeed might be ${P}$ itself.

Alice of course cannot tell by herself whether a given position has value ${W}$ or ${L}$, unless the position is right near the end of a game. But she has one advantage that ${X}$ lacks. She can play ${X}$ against itself from any position ${R}$. If ${R}$ is beyond ${Q}$—at least if ${Q}$ is not reachable in a correctly-played sequence of moves from ${R}$—then Alice will get the correct value ${V(R)}$ of ${R}$.

This is like the power of a human centaur to try a program deeper on the moves it is suggesting. In symbols, Alice executes ${X^*(R)}$, which generates a game sequence

$\displaystyle G_R = (R,R_1,R_2,\dots,R_n)$

of positions where ${R_n}$ is checkmate for one side. The cost of this is ${\Theta(n)}$. You might think we could let ${X}$ do the same thing, but ${X}$ is not like “Satan” in Smullyan’s story, “Satan, Cantor, and Infinity.” ${X}$ is not trying to out-psych Alice or correct itself; ${X}$ is just given as-is and by-hook-or-by-crook makes that error in some position ${Q}$.

So Puzzle I is:

Can the “centaur” Alice + X play perfectly, even though neither Alice nor X plays perfectly alone? And at what cost compared to X?

The answer is, yes she can. Let the legal moves in ${P}$ be ${m_1,\dots,m_\ell}$ going to positions ${Q_1,\dots,Q_{\ell}}$ with ${m_1}$ the move recommended by ${X}$. Her algorithm exemplifies a key idea that bridges to the more interesting puzzles.

• Alice runs ${X^*(Q_1),\dots,X^*(Q_{\ell})}$.

• If ${X^*(Q_1) = W}$, or if all values are ${L}$, then Alice plays ${m_1}$.

• If ${X^*(Q_1) = L}$ and ${X^*(Q_i) = W}$ for some other ${i}$ then Alice plays ${m_i}$.

We claim this algorithm, whose running time ${O(n\ell)}$ we count as linear in ${n}$, plays perfectly in any ${P}$. If all values are ${L}$ but ${m_1}$ is wrong then some other ${Q_i}$ is really a winning position. But then ${X}$ is wrong both at ${P}$ and at some position in the game from ${Q_i}$ which is a contradiction. If ${X^*(Q_1) = W}$ but ${m_1}$ is wrong anyway then ${X}$ is wrong both at ${P}$ and somewhere at ${Q_1}$ or beyond.

Finally if the “switch” ${m_i}$ is wrong then ${X}$ errs somewhere beyond ${Q_i}$ and ${X}$ either errs beyond ${Q_1}$ or ${X}$ erred by choosing ${m_1}$ in ${P}$ after all. (If ${X^*(Q_i)}$ is wrong and all other ${Q_j}$ are losing then ${V_P = L}$ and so ${m_i}$ wasn’t a mistake by Alice since it didn’t matter.)

There is one loophole that needs attention. ${X^*(Q_1)}$ and ${X^*(Q_i)}$ could both be wrong because their games go to a common position ${R}$ in which ${X}$ makes an error. However, that lone error cannot simultaneously flip a true ${W}$ to ${L}$ in ${Q_1}$ and a true ${L}$ to ${W}$ in ${Q_i}$, because ${Q_1}$ and ${Q_i}$ have the same player (Bob) to move. There is also the possibility that play from ${Q_i}$ could go through ${Q_1}$ (perhaps via ${P)}$ or through some other ${Q_i}$, which we leave you to analyze. We intend to rule out the latter, and we could also rule out the former by insisting that the “game tree” from positions ${P}$ really be a tree not a DAG.

Boiled down, the idea is that ${X^*(Q_1) = L \;\wedge\; X^*(Q_i) = W}$ where ${X}$ goes to ${Q_1}$ is an “error signature” that Alice can recognize. If ${X}$ errs at ${P}$ then the signature definitely happens because ${X}$ is perfect at each ${Q_i}$ and one of the ${Q_i}$ must be winning. If the signature happens yet ${X}$ did not err at ${P}$ then ${P}$ must be a losing position. Hence once the signature happens then Alice can trust ${X}$ completely. The only way the error could possibly lie in her future is if she was losing at ${P}$ but lucks into a winning position—but then the error happened on Bob’s move not hers.

We claim also that all this logic is unaffected if “draw” is a possible outcome. Indeed, we could play with the old Arabian rules that giving stalemate is a win—counting it 0.8 points say—and that occupying the center with one’s king after leaving the opponent with a bare king is a win—worth say 0.7 points. It all works with “${W}$” being the true value of position ${P}$ (aside from a total loss) and “${L}$” being any inferior value.

Puzzle II

Now suppose ${X}$ is allowed to make errors in two positions. Can Alice modify her algorithm to still play perfectly?

First suppose the errors are related. Call two positions ${Q,R}$ related if ${R}$ can occur in a game played from ${Q}$ where all intervening moves are not errors. Per above we will always suppose that two positions ${Q_i,Q_j}$ reached in one move from ${P}$ are unrelated (else we would say the two options ${m_i,m_j}$ are not fully distinct). Related errors are ones that occur in related positions.

If Alice knows this about ${X}$, then we claim she can solve Puzzle II. She plays the game ${X^*(P)}$ through ${Q_1}$ as before, but now she looks for the error signature at all nodes in the game. If she never finds it then she plays ${m_1}$. If she does, then she lets ${R}$ be the last position at which it occurs. Then she knows that either ${X}$ errs at ${R}$ or ${X}$ errs somewhere beyond ${R}$. Either way, she can use this knowledge to whittle down the possibilities at ${P}$. Or at least we think she can.

Notice, however, what has happened to Alice’s complexity. She is now running ${X^*}$ at every node in a length-${n}$ game path. Her time is now quadratic in ${n}$. This is still not terrible, not an exponential blowup of backtracking. But in honor of what Alberto Apostolico cared about, we should care about it here. So there is really a second puzzle: can Alice play perfectly in time ${O(n)}$?

If the errors are unrelated then we would like Alice to carry out the same algorithm as for Puzzle I. The logic is not airtight, however, because of the case where there were unrelated errors at ${Q_1}$ and ${Q_i}$. Worse, what if Alice doesn’t know whether the errors are related?

Puzzle III: Two Programs

Here comes the “Freestyle” idea of using multiple programs. Let us have two programs, ${X}$ and ${Y}$. Suppose one of them can make up to ${2}$ errors but the other is perfect. Alice does not know which is which. Now can she play perfectly—in ${O(n)}$ time?

If the errors are related then she can localize to ${P}$ and have the same linear time complexity as before. For simplicity let’s suppose there are just ${2}$ legal moves, i.e., ${\ell = 2}$. Here is her algorithm:

• Run both ${X^*}$ and ${Y^*}$ on the positions ${Q_1}$ and ${Q_2}$, getting two pairs ${(V^X(Q_1),V^X(Q_2))}$ and ${(V^Y(Q_1),V^Y(Q_2))}$ of values.

• If the values for ${Q_1}$ are both ${W}$ then one of them comes from the perfect program, so Alice plays to ${Q_1}$. Likewise if they are both ${W}$ for ${Q_2}$ then Alice goes to ${Q_2.}$

• If the values are both ${L}$ for ${Q_1}$ then again by perfection the true value of ${Q_1}$ is ${L}$, so Alice cannot err by going to ${Q_2}$. If they are both ${L}$ for ${Q_2}$ she goes to ${Q_1}$.

The remaining case is that one pair is ${(W,L)}$ and the other is ${(L,W)}$. This cannot happen, because it means that one of the programs is making two unrelated errors.

This is the idea Dick originally had after the videoconference on Freestyle chess. It shows the advantage of using multiple programs to check on each other like the centaur players do. But what happens if the errors are unrelated? Call that Puzzle III.

Puzzles IV and V

Now let’s allow both programs ${X}$ and ${Y}$ to make up to ${k}$ errors. Can Alice still play perfectly? We venture yes, but we hesitate to make this a formal claim because Puzzles II and III are already proving harder than expected.

How much does having a third program ${Z}$ that is perfect help?—of course not knowing which of the three programs is perfect. If instead ${Z}$ too can make up to ${k}$ errors, how much worse is that? Even if Alice can still play perfectly in polynomial time, we wonder if the exponent of ${n}$ will depend on ${k}$. Call all of this Puzzle IV.

We can add a further wrinkle that matters even for ${k = 1}$: we can consider related errors to be just one error. This makes sense in chess terms because an error in a position ${R}$ that is reachable from a position ${Q}$ can affect the search by a program ${X}$ in ${Q}$. Thus the error at ${R}$ knocks-on and makes the play at all nodes between ${R}$ and the root unreliable. Let ${E}$ be the set of all positions at which ${X}$ makes errors. Then we can define ${k(E)}$ to be the minimum ${k}$ such that there are positions ${R_1,\dots,R_k \in E}$ such that ${E}$ is contained in the union of the positions from which some ${R_j}$ is reachable. This is well-defined even when the positions form a DAG not a tree.

Thus programs could err in multiple positions but still count as having a single branch error if those positions are all on the same branch. Anything with branch errors counts as Puzzle V. This is where our error model is starting to get realistic, but as we often find in theory, there is a lot of already-challenging ground to cover before we get there. It is time to call it a day—or a post.

Open Problems

Our puzzles have some of Smullyan’s flavor. In a typical logic puzzle of his, Alice would be confronted by ${X}$ and ${Y}$ that have different behaviors in telling the truth to arbitrary questions. The solutions in his case rely on the ability to ask questions like:

If you are a person of type … , then what would you say to the question … ?

Our situations seem different, but perhaps there are further connections between our puzzles and Smullyan’s. What do you think?

Can you solve the puzzles of kinds II or III or higher? If you or we find a clear principle behind them then this will go into a followup post.

Our condolences on the loss of a colleague

 Cropped from TCS journal source

Alberto Apostolico was a Professor in the Georgia Tech College of Computing. He passed away on Monday after a long battle with cancer.

Today Ken and I offer our condolences to his family and friends, and our appreciation for his beautiful work.

Workshop on Infinite State Systems at the Bellairs Institute on Barbados

 Cropped from source

Joel Ouaknine is a Professor of Computer Science at Oxford University and a Fellow of St. John’s College there. He was previously a doctoral student at Oxford and made a critical contribution in 1998 of a kind I enjoyed as a student in the 1980s. This was contributing a win in the annual Oxford-Cambridge Varsity Chess Match, which in 1998 was won by Oxford, 5-3.

Today I’d like to report on some of the wonderful things that happened at a workshop on “Infinite-State Systems” hosted by Joel at the Bellairs Institute of McGill University last March 13–20 in Barbados, before we finally opened a chess set and played two games on the last evening.

A small idea before the fireworks show

Thoralf Skolem was a mathematician who worked in mathematical logic, set theory, and number theory. He was the only known PhD student of Axel Thue, whose Thue systems were an early word-based model of computation. Skolem had only one PhD student, Öystein Ore, who did not work in logic or computation. Ore did, however, have many students including Grace Hopper and Marshall Hall, Jr., and Hall had many more including Don Knuth.

Today Ken and I try to stimulate progress on a special case of Skolem’s problem on linear sequences.

You like tomato and I like tomahto

Oded Green, Marat Dukhan, and Richard Vuduc are researchers at Georgia Institute of Technology—my home institution. They recently presented a paper at the Federated Conference titled, “Branch-Avoiding Graph Algorithms.”

Today Ken and I would like to discuss their interesting paper, and connect it to quite deep work that arises in computational logic.

Plus visiting Michael Rabin and talking about Gödel’s Theorems

Michael Ben-Or and Michael Rabin have won the 2015 Dijkstra Prize for Distributed Computing. The citation says,

In [two] seminal papers, published in close succession in 1983, Michael Ben-Or and Michael O. Rabin started the field of fault-tolerant randomized distributed algorithms.

Today Ken and I wish to congratulate both Michaels for the well deserved recognition for their brilliant work.

A new approach to protecting data and identity

 Cropped from src1, src2

David Sanger and Julie Davis are reporters for the paper of record—the New York Times. Their recent article starts:

WASHINGTON—The Obama administration on Thursday announced what appeared to be one of the largest breaches of federal employees’ data, involving at least four million current and former government workers in an intrusion that officials said apparently originated in China.

The compromised data was held by the Office of Personnel Management, which handles government security clearances and federal employee records. The breach was first detected in April, the office said, but it appears to have begun at least late last year.

The target appeared to be Social Security numbers and other “personal identifying information,” but it was unclear whether the attack was related to commercial gain or espionage. …

Today Ken and I want to suggest a new approach to data breaches like this.