Take the 2-minute tour ×
Chess Stack Exchange is a question and answer site for serious players and enthusiasts of chess. It's 100% free, no registration required.

There are a lot of online website, 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 do suggest a move for him.

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

I was thinking about 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, from which perspective are you thinking (server or the client side)

share|improve this question
    
Excellent question and relevant problem today! But do you mean detect online blitz cheating using an algorithm or detect just as a human player while playing an opponent? –  Rauan Sagit Jan 21 at 12:13
    
Cheating detecting strategies only work when the cheater is "stupid". Adopting more clever cheating stategies (see my comment to NoviceProgrammer's answer) would make the cheating nearly impossible to even guess. –  Andrea Mori Jan 21 at 13:08

5 Answers 5

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.

share|improve this answer
    
the humans vs computers can give false positives in the opening of the game, it is very easy to memorize best plays –  ajax333221 Nov 19 '12 at 23:12
    
@ajax333221 I completely agree. To an extent, something similar may apply to the endgame, where a human might play it pretty close to perfectly, just based on prior knowledge. That said, if I can detect possible cheating in a game, I'm sure with additional information and sophisticated analysis, a computer could do the same. The forced mate in 4+ moves was an actual example from a recent online game vs a 1050 rated player - highly suggestive, to say the least... –  Daniel B Nov 20 '12 at 6:17

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer
2  
This seem to be adressing the "how to manage a server" point of view, rather than the "is my opponent cheating ?" one (not that the OP said anything about which case mattered for him). Might be worth mentionning it, as it took me a little time to understand what you meant, thinking of it from the player's POV. (Good answer… once this is understood ^_^') –  Nikana Reklawyks Nov 18 '12 at 6:07
1  
thanks @ajax . I have not thought about saving the move at which the position was copied and analyse the difference between the strength before and after. –  Salvador Dali Nov 18 '12 at 12:57

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.

share|improve this answer
    
This can be countered by an intelligent cheater which has some chess knowledge as follows: play moves that simply do not make your position worse and wait for your opponent's blunder which would compromise his/her position. If you are playing 5 to 15 minutes blitz against somebody who is not of GM strength this will definitely happen, sooner or later. If moreover you throw in an occasional bad move and/or you do not insist on winning every single game, I'm sure that your cheating would go undetected. –  Andrea Mori Jan 21 at 13:04
    
@AndreaMori: i agree that you can avoid a few situations, but as his/her rating improves he will be compelled to look up more and more and eventually will get detected. –  NoviceProgrammer Jan 21 at 13:32
    
Thank you, you have mentioned that there is software available. Can you give an example? –  Salvador Dali Jan 21 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.