Wednesday, October 07, 2009

[ruptwqra] How to cheat at chess

A spectre is haunting chess -- the spectre of cheating using computers, because computers these days can play chess much better than people. There is an escalating war between cheaters and anti-cheating countermeasures. It may be interesting to consider the problem of cheating in chess information theoretically.

In the presence of countermeasures, the communication channel between a cheating player and a computer (possibly a confederate consulting a computer) is very limited. Given bidirectional parameters on the communication channel, exactly what information should be sent across the channel to maximize the increase in performance of the player? This is an interesting general problem in its own right; let me present a possible solution for a specific case.

We consider one very minimal situation: the channel capacity or bandwidth from the computer to the player is a very small one bit per move, and the bandwidth from the player to the computer is zero (no communication possible in this direction, the player is under intense scrutiny, and any unusual behavior will be spotted). Actually, it's the covert bandwidth from the player to the computer that is zero; we assume the game is live and public, so the confederate, a member of the audience, can see the moves as they are made. Thus, the channel is such that the player cannot ask, "is this such-and-such a move a good move?" (because of the zero covert bandwidth in that direction), nor can a confederate signal "such-and-such a move is the best move in this position" (because such a message requires more than one bit per move). Nevertheless, one bit of information will be enough to provide a significant advantage to the cheater.

This "one bit of information" may be transmitted, for example, by the player seeing the confederate in the audience. It is helpful if the confederate situates him or herself where the player does not have turn his or her head and adjust his or her gaze. The confederate performs a subtle pre-agreed signal to transmit the bit: perhaps arms crossed left-over-right versus arms crossed right-over-left.

My proposal for the one bit that is transmitted is, "Did the opponent just blunder?" Computers excel at discovering blunders, and a human, armed with the information that an opponent has just just blundered, can engage in a radically different thought process than searching for a "normal" move in a normal situation. Instead, the player can conceptually search for the flaw in the opponent's previous move, and search for a specific attack to punish the mistake. I predict a strong player can become a lot stronger with just this one bit.

The naive confederate may consult a computer after every opponent move, checking if it was a blunder. A more sophisticated confederate, consulting a more powerful computer, can explore and memorize several ply deep at a time, so only having to consult the computer occasionally.

Technically, because blunders happen rarely, the actual entropy in the channel averages less than one bit per move, so perhaps a even cleverer and more subtle encoding than suggested above is possible and even less likely to be caught.

However, the moral of the story is, catching cheaters in chess is going to be very, very difficult, needing to block extremely tiny amounts of information which is enough to gain a significant edge.

P.S.: A nice article: Cheating in Chess, by Frederic Friedel (This paper appeared as a contribution to the book "Advances in Computer Games 9", edited by Professors H. J. van den Herik, University Maastricht, and B. Monien, University of Paderborn. It was published by the Universiteit Maastricht in 2001. The paper on Cheating was written and submitted by Frederic Friedel in 2000.)


Anonymous said...

Do you know of any automated countermeasures -- computer programs analyzing moves to detect the use of computer programs based on correlation with the moves of programs of various strengths and statistical likelihood that a human opponent would do same? Such analysis might have to be subsequent to a game, but such a thing seems possible. Do you know of any research or discussion of such a thing?

Anonymous said...

This blog was mentioned on Bruce Schneier's blog recently which led me here. I think a better question would be: "Is there a clearly superior move in this position?" This covers the blunder scenario, but also could indicate a strong positional move.