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:

${\dots}$ 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.

## Ken’s Research

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

$\displaystyle P_{1},\dots,P_{m}$

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 ${P_{i}}$ is not followed by ${P_{i+1}}$: 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

$\displaystyle (m_{1},v_{1}),\dots,(m_{k},v_{k}).$

Here ${m_{i}}$ is a move and ${v_{i}}$ 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 ${\tau}$, then these could be selected with equal probability. If ${\tau}$ 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.

## Open Problems

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.

1. June 18, 2014 1:37 pm

My 2 cents in relation to “game and destiny” is that the game is fulfilled by willing, by diverting and guiding the course of the game according to arcane rules where the original, primitive connection to a solemn ceremony is lost. We lose the collective participation in tribal ceremonies, but we retain the interest to watch the contest whose outcome we cannot exactly predict. Similar to fertility rites, the immediate object is a cheating of nature of her tribute, for that is what death ultimately is. Otto Rank says that, “Though this cheating of the original opponent has left a strong tendency to *correiger la fortune* in games, yet in its higher developments it represents a transition from deception to domination a raising of the cosmic phenomena from the realm of necessity into that of freedom.” Okay, that’s probably confusing, but the game as related to destiny involves some interest in how to control that destiny whether it is life or some abstraction in a formal system like chess.

June 18, 2014 6:40 pm

I have a question about this method. As you know, Kerckhoff’s principle in cryptography is roughly the notion that “the enemy knows the system.” Supposing that an adversary knows Regan’s program, could the adversary still reliably win a game of chess against an opponent? For example, suppose as a cheater I have access not only to a chess playing computer, but also to a published copy of Regan’s process for detecting the cheating.

To be more specific: if this process were to use Top-3 Cheating, what if a player could simply play the fourth-best move recommended by the computer every time and still beat their opponent? Could there be some sort of game-theoretic or other solution to ensure that there is no way for the cheater to win with a computer, even if the anti-cheating system is known?

June 18, 2014 10:43 pm

The first thing that comes to mind is to use machine learning to detect cheating and there are many ways to do so. Has anyone explored using machine learning to detect cheating in chess? My guess is that machine learning would outperform any algorithm.

June 19, 2014 7:06 am

That’s a big difference between game and science. If anyone came up with a computer proof of the Riemann Hypothesis, even after the cheating was discovered they could keep the medal. He who wills the end, wills the means.

5. June 19, 2014 9:07 am

the hairstyle….

June 20, 2014 6:28 pm

I find the problem of detecting when a player plays “above his/her league” very interesting theoretically – but I find myself in disagreement with the motivation and I find the emphasis on the term “cheating” exagerrated. Of course, if the tournament rules say “no computer allowed”, then it should be respected by participants, however, another perspective is that maybe it is time to not take tournaments so seriously when this game (with somewhat arbitrary rules) have been figured out to such an extent that computers beat humans easily. Personally these days I find computer chess, and an attitude of “go at it with all you’ve got” more interesting than human chess. But go and other games harder for computers are even more interesting for the same reason.

Yes, there is an analogy with doping in athletics, but a better analogy would in my opinion be elementary geometry of the triangle (say the collinearity of special points) – the proof of (almost) all interesting statements in this field can be automatically generated, indeed, there was iteresting work that automatically generates the theorems themselves, some perhaps as interesting as the best humans could come up with in 3000 years (see work by Kimberling, Zeilberger, etc.). Do we react by trying to analyze the proofs in submitted articles and see whether they contain ideas that seem “too smart?” – no, we react by considering the field “mostly done” and moving our creative efforts elsewhere (plenty of areas where neither humans nor computers succeed at the moment). The author hints at something similar in the last paragraph, but gotta love that “even worse” in the end – personally I would find that an amazing development, even better than computer chess. I would be glad to hear counterarguments, and sorry if I came across too negative.

June 23, 2014 8:34 am

1) The cheat detection seems pretty good if a weak player is playing above his level. But what if one of the top 100 players in the world cheated- would that be very hard to detect since they may well pick very good moves anyway?

2) One way to make sure that the players do not have any electronic devices on them is to have them play naked. This might also increase interest in the game.

July 3, 2014 12:25 pm

It’s possible to set the computer to think X number of moves ahead (I think)/. Examine those moves where the computer prescribes differently for different look-ahead settings. If a weak player is playing according to (say) a 4-move look-ahead repeatedly, then it’s probably cheating.

Like the others above, I think it’s unclear how to sort out a top 100 player cheating. Metal detectors and Faraday cages all around.

• July 3, 2014 1:01 pm

Indeed. If you clear hash before each move, you can get the results of each look-ahead setting sequentially and reproducibly. I am in fact expanding the model to include a “depth of thinking” parameter specifying a distribution over X.

I did have one case with a top-100 player, and a confession confirmed results of my model, even at the level of details presented starting with the paragraph beginning “Finally”.

• July 3, 2014 1:02 pm

Oops, this is Ken.

9. September 7, 2014 12:35 am

How about playing chess in an Icelandic hot springs where one has to be wet with minimal clothing?