The Problem of Catching Chess Cheaters
The detection game
Howard Goldowsky is the author of this month’s Chess Life cover story. Every month this magazine is mailed to about a quarter of a million players, but this cover story was deemed so important by Daniel Lucas, Chess Life’s editor, that he made it available online, free of charge.
Today I want to talk about this story because it is interesting, important, and it raises some novel theory questions.
The cover picture and the story is about the work that our own Ken Regan is doing to help stop chess cheaters.
Of course cheating at games of all kinds, at sports of all kinds, at almost all human endeavors is ancient. I would be shocked if cave dwellers did not cheat at something. Yet in my quest to find an article on the first known examples of cheating ended in failure. I would be lying—cheating?—if I said that I found the earliest example. I did discover that cheating occurred during the first Olympics in around 776 BCE. Most athletes were honest, although some cheated in various ways. The penalties then were fines or more severe forms of punishment—do not ask.
One of the funniest examples of cheating at an Olympics occurred much more recently during the 1960 Rome Games. One team did the following:
If at first you can’t succeed, cheat. Words to live by for this inept pentathlon team in the 1960 Rome Games. In the first event, the entire team fell off their horses. One athlete almost drowned during the swimming competition, and the team was forced out of the shooting event after a team member nearly grazed the judges. For the fencing event, they decided to secretly send out their expert swordsman each time and hoped no one looked behind the mask. The third time the same fencer came out, however, the hoax was discovered.
An example of really “unmasking the cheater.”
How To Cheat At Chess
We have talked before about cheating at chess. No drugs are needed, no bribery, no fencing masks; one needs only to use a computer to play the moves for you. The world’s best chess players today have ratings in the range from 2700 to 2820, except for world champion Magnus Carlsen at 2880. The world’s best chess programs, or engines as they usually are called, play at 3100 or above. Put simply: the best humans cannot beat the chess engines.
Hence, the recipe for cheating at chess is simple. Get access to a computer during the game, use its suggested moves, and easily defeat your opponent. The computer can be at a remote site run by a confederate or can be on your person. Even a mobile phone can run a program that will play better than anyone you will likely face in your tournament.
The easy of cheating is a major issue for organized chess. The number of cases in professional tournament play is, according to Ken, roughly one per month—one case happen at a tournament in Romania just last month. Ken knows this because he routinely runs his detection methods, more on those shortly, on most major tournaments. So quoting Goldowsky’s article:
“ when a tournament director becomes suspicious for one reason or another and wants to take action, Regan is the first man to get a call.”
Ken also answers a second class of requests. Sometimes a player will voice suspicions in public. In all that Ken has heard, including several times this year, his work has given evidence that everything was above board—pun intended. The player voicing the suspicion usually lost to an apparently weaker opponent, who seemed to make some very strong moves. No one likes to lose, but Ken discovers that in most of these cases the answer is innocent. The weaker player either made strong moves because they were forced or the accuser made quantifiable mistakes.
Obviously some cheaters are caught red-handed. Just like the unmasking of the fencer they are caught in the act, with a computer in hand. These are easy cases. But more and more the cases are becoming quite sophisticated, making it difficult for tournament directors to obtain direct evidence.
This is where Ken’s research enters, where the problem of detecting cheating becomes a theory problem. A hard and interesting theory problem. One that I would like to abstract and explain in my own way.
Consider that a player is faced with many decisions of the form: what move should I make in this position? We can imagine that the player is faced with a series of positions
and for each the player has to make a choice of what move to make. We can assume that the positions are not related, that is not followed by : this is a simplifying assumption, but is a reasonable one to make.
The difficult question is: how do we rate the move the player selects? The trouble is that in many positions there many be only one legal move. For example, if your king is in check there may be one move to get it out of check. There are many other cases where the move is forced or almost forced, so that even a weak player, like myself, would get the right move.
Another difficulty is that the chess engines suggest not one move but several top moves. If the position is a winning one for the player, there may be little difference in playing any of the top moves. Of course, the opposite often happens too. Sometimes there is a unique move that wins and all the other moves lose.
These complications make scoring how well a player is following the chess engine, that is how much the player is cheating, a nontrivial statistic issue. The principal theory question is:
How should we rate how well a player matches the chess engine as a method to detect cheating?
The short answer is very carefully.
Ken has spend years working on the right scoring method given these issues and others. I believe that his method of scoring is powerful, but is probably not the final answer to this vexing question. You can read more about it in posts by Ken on this blog: March 2012, May 2012, January 2013, July 2013, September 2013, and April 2014, with more to come.
The Cheater’s Strategy
The problem facing Ken in detecting cheating is hard because the cheater may use many different strategies. Suppose that the player is cheating and the chess engine suggests
Here is a move and the value the engine assigns to the move. We can assume that the higher the value the better the engine thinks the move is: there is a slight issue that I am skipping here, since the machine uses the sign of the value to suggest which of black or white is ahead if the move is used. We can safely ignore this for our discussion.
The problem is what strategy might a cheater use? A naïve strategy is to always select the top ranked move, i.e. the move with the largest value. This strategy would be easy for Ken to detect. A superior strategy might be to select moves based on their values: higher values are selected more frequently. This clearly would be more difficult for Ken to detect, since it is randomized.
Another twist is the cheater could use a cutoff method. If several moves are above a value, say , then these could be selected with equal probability. If is large enough this is essentially using the insight that there may be many ways to win a won game. Indeed in many discussions about chess cheating a related method is suggested: simply randomly take one of the top three ranked moves—it is called the “Top-3 Cheating” method.
I could go on, but the key is that Ken is not able to assume that the cheater is using a known strategy. This makes the detection of cheating much harder, more interesting, and a still open problem. It is essentially a kind of two player game. Not a game of chess, but a game of the cheater against the detector; some player against Ken’s program.
Does the detection of cheating in chess seem to be interesting? Will we see cheating start to occur in other mental tasks in the future as computers get better in those areas? Will people start to cheat at other tasks soon? Or have they started already?
Will one day your STOC/FOCS paper be rejected because it looks like it was written by a computer? Or even worse that the theorems were proved by computer and written up by them? For the record this was all created by me—no cheating at all.