How would you determine that the player is cheating in online chess?

Question

There are a lot of online websites, where players can play chess in real time with each other. Most of the games are 5-10 minutes long. With the availability of chess software one can take an advantage by using Fritz or Rybka to suggest a move for him.

For instance, I can just enter every move of my opponent and see what software will suggest for me.

I was thinking about a few features which can suggest that the player is cheating:

• number of times he switches the screen
• speed of play (in easy and in really hard positions)
• accuracy of the game

Does anyone have any other ideas?

P.S.: It does not matter for me, which perspective you are thinking from (server or the client side).

Answer 1

This is actually a very complex question, and not one which has been solved in a satisfying way, to my knowledge. Essentially, we're asking for an algorithm to perform a kind of reverse Turing-test, to differentiate between human players and computers.

First, client-side checks will always have weaknesses, unless you are in complete control of the client environment. Let's take the first idea - checking for switching between windows, it sounds good. Unfortunately, it's trivially worked around by running a chess engine on a separate computer, or integrating my engine with the client so that no "window switching" takes place, or changing the client to report 0 changes in window, or... There's no real way to be sure that it's your code running on the client, really.

What we're left with is physically tightly controlled client environments (which isn't going to happen for any online games), or server-side checking, i.e. looking at the actual moves that were played (and perhaps the time between the moves, as you say), and trying to deduce the computer or human aspect.

Server-side checking can also split a couple of ways. You could probably try a "top-down" approach, which would be something along the lines of "from past games in history, only 2% of humans made that move, while 50% of computers make it". This would actually be a pretty good way to do it, if we had enough data for "any given position". The search space of chess is so large, however, that even very large data sets will not have a significant number of games matching your position, once you get past the early mid-game.

Assuming that we don't have any reliable statistics on the human side of the equation, you could still present the position to a number of chess engines (with a number of different time settings each), and see how closely the players' moves match that of a computer. By itself, this would also lead to many false-positives, however, repeated positives for the same chess engine and time settings would make it more and more probable that the player was cheating. To further enhance this, I would probably look into a "bottom-up" approach of analysing chess positions; in short, trying to figure out why humans and computers play differently. E.g. humans tend to recognise common patterns. In a game with "odd" patterns, or unlikely situations, a human would be less likely to be able to play very accurately. None of these, by itself, are particularly damning, but given large numbers of games, it would highlight trends to administrators.

To add a few specifics to your list, I would go along the lines of how professors detect plagarism in papers - by detecting a sudden change. In chess, this is extremely difficult to define, but a sudden change in play style or play strength may indicate cheating. Specifically, I'd look for uncharacteristically aggressive moves which tend to just "work out", and have no downside for the player (too accurate). Forced mates in 4+ moves from a player who normally puts knights on the edge of the board, etc (it's possible... just not likely). How exactly this would work sounds like it could take up an entire book (or more), however.

EDIT: There was an article about cheating and detection in top-level chess recently.

Answer 2

In blitz, you can tell by how much time they're using. People using engines use a consistent amount of time for every move, instead of blitzing through the opening and slowing down to a crawl in the middlegame like most normal players. In particular, they can't play the opening fast, because they have to update their computer board after every opening move. If they take five seconds on move two and five seconds on move twenty, they're probably using an engine.

Answer 3

Number of screen switches and speed of play are meaningless. If you use these to complain to the organizers of an online chess playing website they will laugh at you.

There are two ways to tell if someone is cheating. The first is the "smoking gun". Consider this game section -

[White "Allwermann,Clemens (1900) "]
[Black "Kalinitschev,Sergey (2505) Boeblingen (9), 30.12.1999"]
[FEN "r6k/1p3Rpp/p2p1bq1/3N4/2P5/1P6/P1b2QPP/5RK1 w - - 0 1"]

1.Qa7 Rg8 2.Qxb7 Be4 3.Nf4 Qf5 4.Qd7 Qe5 5.Kh1 g5 6.Nh3 g4 7.Nf2 Bf5 8.Nxg4 Be4 9. R7xf6 Bxg2+ 10. Kxg2 Qe4+ 11. Kh3 

The question is what would you play in the that position? The situation is that a win in this, the last round of the competition, will win you the tournament ahead of a string of grandmasters. Not bad for a mere 1900. I suspect most of us would play something reasonably solid which keeps the win. Moves like Rxb7 or Rd7 or (for cowards like me ;-) Rxf6. Qa7 is a heart-stopper of a move, a smoking gun. Fritz rates as the best move in the position, a whopping 0.1 ahead of the next best move, Rd7.

Smoking gun #2 game at the end of the game when black resigned leaving the 1900 rated player as the tournament outright winner. What would you say to Kalinitschev in that position?

This is how the conversation went:

Allwermann: "It's mate in 8"

Kalinitschev: "I don't think so"

Allwermann: "“Check it out, you'll find I'm right"

Allwermann was right, of course. Can you find the mate in 8 in the final position? Without silicon assistance?

So, you have your smoking gun and you take it to the organizers. What will they do?

Well, then comes the second way of detecting and proving beyond reasonable doubt that cheating is going on.

They will need to collect at least 20 games each with at least 20 non-database moves and feed them into an engine for checking. Basically what they are looking for is the percentage of the time the suspect chooses a non-database move which matches the engine's first pick, one of first 2 picks, one of first 3 picks. The "proof" thresholds are -

Top 1 65%

Top 2 80%

Top 3 90%

A recent example is the furore over the performance of Borislav Ivanov.

Here are his statistics -

Zadar 19th: Houdini 1.5a x64 Hash:256 Time:30s Max Depth:20ply { Borislav Ivanov (Games: 9) }

{ Top 1 Match: 210/314 ( 66.9% ) Opponents: 150/313 ( 47.9% )

{ Top 2 Match: 270/314 ( 86.0% ) Opponents: 207/313 ( 66.1% )

{ Top 3 Match: 285/314 ( 90.8% ) Opponents: 238/313 ( 76.0% )

{ Top 4 Match: 293/314 ( 93.3% ) Opponents: 267/313 ( 85.3% )

In the 8th round the live feed went down (it is suspected that this allowed his outside help get the moves) and he lost to GM Predojevic. If this result is removed then the new statistics are:

Zadar 19th: Houdini 1.5a x64 Hash:256 Time:30s Max Depth:20ply { Borislav Ivanov (Games: ) }

{ Top 1 Match: 197/287 ( 68.6% ) Opponents: 135/286 ( 47.2% )

{ Top 2 Match: 252/287 ( 87.8% ) Opponents: 188/286 ( 65.7% )

{ Top 3 Match: 265/287 ( 92.3% ) Opponents: 218/286 ( 76.2% )

{ Top 4 Match: 272/287 ( 94.8% ) Opponents: 242/286 ( 84.6% )

As you see, both sets of statistics would get him thrown of a chess server. For comparison here is the analysis for game 8 when the feed was down:

{ White: Borislav Ivanov }

{ Top 1 Match: 13/27 ( 48.1% )

{ Top 2 Match: 18/27 ( 66.7% )

{ Top 3 Match: 20/27 ( 74.1% )

{ Top 4 Match: 22/27 ( 81.5% )

{ Black: Borki Predojevic }

{ Top 1 Match: 15/27 ( 55.6% )

{ Top 2 Match: 19/27 ( 70.4% )

{ Top 3 Match: 20/27 ( 74.1% )

{ Top 4 Match: 25/27 ( 92.6% )

Note that FIDE has set up a commission to investigate ways to detect and combat computer cheating. Their guidelines are here. Note this section:

E. The FIDE Internet-Based Game Screening Tool

FIDE will supply an Internet-based Game Screening Tool, which will be accessible to all authorized FIDE officials (IO, IA, ACC members) and National Federations . It shall be hosted on a FIDE-dedicated webpage and will enable authorized parties to upload games in PGN format for a “fast test” that will identify potential outliers in a tournament . By “screening” it is understood that this provides only a preliminary test with no judgment value, except that it may be cited while rejecting allegations and declining to proceed to a manual full test .

Answer 4

To give my answer as to how I would approach this, I would use a simple idea:

• Null Hypothesis Test

The idea is that there are is a limited number of publicly available chess engines, lets say N of them. This assumption of course precludes the possibility that the cheater has written their own chess engine (or is using some publicly unavailable chess engine) but for catching casual cheaters this should be a strong enough assumption.

The application of the Null Hypothesis Test would be very simple: for each chess engine X and for each subsequence of moves of the current game compute the probability p of observing the played subsequence assuming the null hypothesis that the player is not using chess engine X to make the moves for them. A naive assumption could be made that the player moves at random (or randomly chooses from a select number of top moves d_i), then the probability for a given subsequence of length k matching moves a chess engine X would make would be computed as (d_1)/(n_1) * (d_2)/(n_2) * (d_3)/(n_3) *...* (d_k)/(n_k) where d_i is the number of possible (top) moves to make at the ith turn, as rated by engine X and n_i is the number of total moves available to the player at turn i (or some reasonable subset.)

Then simply compute

p* = minimum p over all chess engine X, all subsequences y.

If p* is less than a certain threshold label the player as a cheater since there exists a subsequence y and chess engine X that brings the probability that the player is not cheating below a desired probabiity.

Answer 5

If your site give the users one-click get FEN positions or PGN while the game is running, you should consider tracking these.

Some cheaters cheat from the beginning, but others prefer to only start cheating when they are in trouble, and they will obviously use the copy FEN/PGN feature since it is time-consuming to set up the position manually.

You should somehow store that along with the move at the time he copied it, this way you can compare from that point to the following moves and see if his strength greatly increased with the aid of chess engines.

But it is very important that you use it only to help you decide if he was cheating, it would be unfair to use a script that uses no human intervention, there can be many false-positives, for example, I often like to copy positions while I am playing to later analyze them without the need of searching for my game or finding the exact move from the PGN. And I don't always leave it in my clip-board because fear of overwriting it so I move it to notepad (which means I switch windows just after copying it).

Answer 6

I think post-game analysis gives you the best chance of identifying if a player was cheating. This can be done using what is called as the T3/T4 analysis.

This basically measures the frequency at which a player picks one of the top 3 or top 4 moves that are suggested by an engine. This largely eliminates the need to identify the target engine in use (as they will generally agree on the top 4/5 moves even if the order of preference is different).

There are software available that will run a set of games of the user against the top n moves of the engine. Edit:

I am aware of ChessAnalyse that can be used to do such an analysis. You can try the 30 day trial version.

Answer 7

FWIW, no one has mentioned Dr. Ken Regan by name, though the pointer to Lipton's blog describes another article in Chess Life that discusses his work.

That article is very informative about Regan's work, the state of detection techniques that were in effect in 2014, and FIDE's work in setting up a committee to define and promulgate standards, tools and techniques to assist TD's in stamping out cheating.

Answer 8

I added my views to http://talkchess.com/forum3/viewtopic.php?f=2&t=78146. It has some general outline.