Cheating detection algorithms - hints and ideas

[socoban]

Hi all,

I am developing anticheating software for online chess server http://www.chessfriends.com . I did some investigation on other servers, playchess, chesscube, icc, etc... and none of them has automatic software detection of cheaters based on analysis of games. Most of them are using only checking focus of window, time per move, etc, but none can track human + engine cheating, if human is smart enough. We tried to play there and we were able to cheat in houndrets of games without ban. My goal is to write some algorithm based on move analysis by strong engines. Can you write down all ideas you have, that I should focus on? Not just checking first lines, or blunder checks, but more complex ideas. And also big problem is, that today there are houndrets of chess engines. Maybe I can analyze game with multiple engines to have more exact results. But than the analysis of game will be very CPU time consuming.

Thanks for any ideas.

[Michel]

I am curious. Why is chessfriends.com anonymously registered?

Registrant:
Domains by Proxy, Inc.
DomainsByProxy.com
15111 N. Hayden Rd., Ste 160, PMB 353
Scottsdale, Arizona 85260
United States

[socoban]

I am just developer, not owner. Why do you ask? In my opinion if it was my domain, I would feel saver anonymous. World is full of jerks. Imagine you have to ban some cheaters, they will hate you. They take it personal. We had such problems with few cheaters from Romania. After we banned one, he started to send spam emails to our users using our mail adress. Than he did DOS attack. And than he copied our texts and started to develope his own server:), it has negative impact on our SEO, since he stole our texts. World is dangerous, if you cut of addicted jerk from his drug:(

[Dave Mitchell]

You put yourself on a treadmill when you try to eliminate cheating in on-line play.

You do X, the cheaters do Y to work around it, you do X2, the cheaters respond with Y2.

If you ban someone who is NOT cheating (a false positive), then they're angry about it. If you ban someone who IS cheating, then they're angry about it. Both will bad-mouth your site, at the least.

It's easy to tell a raw beginner from a computer in over the board play, but once you get into the more talented players, it's a real struggle.

[Laskos]

You put yourself on a treadmill when you try to eliminate cheating in on-line play.

You do X, the cheaters do Y to work around it, you do X2, the cheaters respond with Y2.

If you ban someone who is NOT cheating (a false positive), then they're angry about it. If you ban someone who IS cheating, then they're angry about it. Both will bad-mouth your site, at the least.

It's easy to tell a raw beginner from a computer in over the board play, but once you get into the more talented players, it's a real struggle.

Is it entirely hopeless? For example, check with Stockfish on 20 consecutive moves (preferably in the middlegame) for >0.30 deviation from the best move. If there are none, he is very, very probably a cheater, if we are talking about blitz or bullet.

Kai

[socoban]

There is no other way, we have to detect and ban users. Every server does it. The reason is simple, let say 90% never try to cheat, 9% will try it, but if we detect them, they stop. 1% will try it always, but, are all of them smart enougt to cheat undetected? The more complicated cheating is, the less people will do it. And yes, there will be people who will claim they are not cheating, doesn't matter they really cheat or not. Impotant is to create trust in our server, that we are in open war with all kind of cheating. It is more marketing problem, than technical problem. With good maketing you can create trust even if you detect few of them manually. We already anounce to everyone that we banned some account and why. It makes them feel saver and prevent many cheaters to try it.

[socoban]

Is it entirely hopeless? For example, check with Stockfish on 20 consecutive moves (preferably in the middlegame) for >0.30 deviation from the best move. If there are none, he is very, very probably a cheater, if we are talking about blitz or bullet.

Kai

We already have such algorithm. Problem is that it is not working. Let say they are cheating with some automatic cheating application, and the engine has limited time to calculate move. So in short time it finds different moves than my detection algorithm, since my engine try to find best moves by longer searching. There are too many engines and some prefer different possitions than other.

So generally the idea is clear, checking if it is best move, or evaluation is <X . This simple blunder check is not working correctly in some possitions. (Openings, Endgames - without database engines do blunders, closed midle games, ... )

Let say it will choose only those possitions for detection, where all engines usually have similar results, than this idea can work. As engine developers, don't you have some hints how to easyly detect such possitions? I am using UCI interface, so maybe engines can give me some information about position which I can use to desite if the possition is worth to be checked. (Like, number of checked possitions, searched deep, number of possible good moves etc...)

[Michel]

What if the cheater uses a virtual engines which, every move, randomly queries one engine from a collection of top engines?

Writing such a thing is only a few lines in a scripting language.

[hgm]

You could sample games, and subject them to a blunder check by a strong engine with 1 sec/move. People that blunder most likely have not been using an engine, so you have filtered out those. (If needed, you could analyze the position just before and after their 'blunder candidate' at a larger depth, to make sure it is truly a blunder, rather than misevaluation by the engine because of the limited time.)

The games that pass the blunder test can be analyzed with somewhat larger time per move (say 10 sec), and remain suspect when there are almost no moves where the evaluation drops much. Moves that do decrease the evaluation can be analyzed with longer time, by a handfull of engines, to see if any of them suggests the move that was played. Games without such moves, or where such moves are all suggested by the same engine, remain suspect.

If you have reduced the number of suspect games enough, you can probably afford to analyze each position with the most-likely used engine at the actual time, to generate hard prove. The trick is to reduce the number of candidates first by much faster tests.

People that cheat, are likely to cheat consistently. If one of their games is sampled, and found suspect, you can subject all their earlier games that were not sampled to the test procedure.

In all cases it will remain very difficult to catch people that cheat with weak engines, such as (say) Fairy-Max. But thenature of cheaters is that when they cheat, they are likely to cheat with the strongest engine they can get their hands on. And would you really care when they do? If it plays like an average player on your server, who cares if it actually was a computer?

[socoban]

If user uses multiple engines and switches them randomly, it can be solved be analyzisng every position by multiple engines and checking if it is best move in some of them, or by using the blunder interval only abs(moveMovedValue - BestMoveValue )< X , where X is somathins small like 0.3 .