Reports | March 21, 2012 14:35

Using math to detect cheating

Using math to detect cheating

Kenneth Regan, associate professor of computer science at the University at Buffalo, has developed a program that can assist in discovering cheating. This was reported yesterday in the New York Times.

For the New York Times, Dylan Loeb McClain, spoke with Regan, who has been researching the problem for five years. The Toiletgate scandal during the Topalov-Kramnik 2006 World Championship match was a starting point. Back then, Veselin Topalov and his manager Silvio Danailov accused Vladimir Kramnik of cheating, arguing that the Russian grandmaster went to the toilet dozens of times during a game.

I thought that the chess world needed someone to try to help investigate these accusations. I felt I was qualified. I felt some definite responsibility,

Dr. Regan told the Times. Normally, he studies the epic P vs NP problem, but being an International Master himself, it's no surprise that Regan often combines his research with chess topics. 

He started to work on a way to have mathematical proof that someone is cheating. This eventually led to a model of how often the moves of players of varying ability match those of chess programs. To test someone for cheating, he runs that player’s Elo rating against the comparative model.

What Regan used for his model are games all the way back to the 19th century. By now, he’s analysed almost 200,000 games, mostly from top tournaments. His computer program will predict moves, and he can then compare these moves with the ones of the alleged cheater.

At the moment, Regan's model is at a stage where it can be used only as support in cases in which cheating is alleged. It cannot conclusively say whether a player is really cheating; all it can do is say that the move the player chose is strangely similar to those chosen by a chess engine.

The chess world has seen many cheating scandals in recent years, including the French case at the Olympiad in 2010. In February 2009, Shakhriyar Mamedyarov accused Igor Kurnosov of cheating, and based hs claims on the similarity with Rybka's moves.

Dr. Regan's research has great potential value beyond chess, according to Jonathan Schaeffer, a professor of computer science at the University of Alberta and the inventor of Chinook, the computer that solved checkers. The New York Times quotes him as saying

What he is doing, what these people are doing, is they are trying to model how people make decisions.

Peter Doggers's picture
Author: Peter Doggers

Founder and editor-in-chief of ChessVibes.com, Peter is responsible for most of the chess news and tournament reports. Often visiting top events, he also provides photos and videos for the site. He's a 1.e4 player himself, likes Thai food and the Stones.

Chess.com

Comments

Jan's picture

How can a programm evaluate human playing? The programm would have to be able to judge whether a move is "human" or not. But therefor it has to understand how a humen thinks, when he plays a position, in fact: which moves are natural.
And I believe that this is not possible for a computer programm.
Also players could have analized the moves at home with an engine and would be designated as cheaters.

This all seems for me like the attempt to accuse a student of cheating, who normally has bad grades, just because he wrote a good grade. You could argue, that his writing style was different but this can never be proven, maybe he was just well prepared or he advanced. The only thing you do is to accuse him unjustified.

But this is just what I think about this without knowing how this programm works...

test's picture

>> How can a programm evaluate human playing? The programm would have to be able to judge whether a move is "human" or not.

The system is not trying to do that. It just compares how many moves match those of the computer.

>> Also players could have analized the moves at home with an engine and would be designated as cheaters.

That is probably one of the reasons the percentages are so high in professional chess.

But they would not automatically be designated as cheaters; read the article: "At the moment, Regan's model is at a stage where it can be used only as support in cases in which cheating is alleged."

Henk de Jager's picture

I think it would work comparing players of different calibers making closer to ´best´ moves according to the computer programm. For example a 2600-player would have 90% of his choices in the top 3 of computer candidate moves, 80% in the top-2 and 70% would be ´first choice´. For a 2300-player these numbers would look like 80-70-60 etc. The percentages are arbitrary of course and might be different in practice. This is also one of the methods used to determine cheating online.

Jan's picture

But this is senceless. The computer doesn't know which position is easy to play for a human. I have looked over games with the engine of two 1800 players and they made the best moves nearly all the time. This is possible if the position is not very komplex.

RuralRob's picture

I really don't know what I am supposed to conclude from his published results. Hou Yifan is at the top of the list - is that supposed to mean she is the most likely cheater of the listed players? Assuming she is not, then her position on the list, indeed the entire list, seem rather meaningless.

Thomas's picture

Lasker and Botvinnik are also quite high on that list ( http://www.cse.buffalo.edu/~regan/chess/fidelity/WCallperfs.txt - took me a while to find it), and Kramnik's best result is from a rapid playoff game against Topalov when even Vlad presumably spent most of the time at the board. So this list merely reflects the quality of games from WCh matches - BTW without an indicator of complexity, i.e. how difficult is it to consistently find the best moves?

In general, I think the title of the article "Using math to detect cheating" is too strong - as mentioned later on, at the moment Regan's program can only support or refute cheating allegations which in any case would need other lines of evidence. And I don't see how this could change in the future.

In other sports, a world record might be considered suspicious and an indication for doping. That's why that athlete has to undergo a doping test, which may prove him guilty or innocent. In that case, skeptics might say that the athlete was just smarter than the doping authorities, using substances hitherto unknown or that cannot be detected. In chess it seems to be the other way around: Regan's program can only prove innocence, it cannot provide crystal-clear (and legally relevant) proof of guilt?

Morten's picture

I think you must have missed the part where he says that the 'fidelity' measure doesn't indicate cheating unless there is some physical evidence: http://www.cse.buffalo.edu/~regan/chess/fidelity/Golfers.html ...

Mike Hunt's picture
JeroenKK's picture

so whats the point?

TMM's picture

Funny how they call this 'research'.

"...It cannot conclusively say whether a player is really cheating; all it can do is say that the move the player chose is strangely similar to those chosen by a chess engine..."

How is this different from Mamedyarov claiming that his opponent's moves matched Rybka's moves a lot?

Remco G's picture

He has a lot more data to back it up. He can show what "a lot" means exactly.

test's picture

From the link Morten provided above:

"Thus the statistical analysis can only be supporting evidence of cheating, in cases that have some other concrete distinguishing mark. When such a mark is present, the stats can be effective, and can meet civil court standards of evidence"

TMM's picture

And ChessVibes, please distinguish between mathematics and computer science. I can live with computer scientists making fools of themselves, but then also 'attribute' the results to computer science. So "Using computer science to detect cheating" would be more accurate (and less insulting to mathematicians).

Eiae's picture

Haha, good point. Love your comment.

noyb's picture

Fascinating statistical analysis, but hardly a credible methodology for putting reputations at risk. This system clearly would "mark" players as cheaters who in fact are not. Back to the drawing board!

Mike's picture

"Using math to detect cheating" is, in fact, cheating....

jussu's picture

Good to hear that some people are actually doing serious research in this area.

Alex's picture

>Normally, he studies the epic P vs NP problem

sounds strange

Greco's picture

I think that something tha these researchers are missing is the fact that a cheater doesnt have to cheat on every move he makes during a game. In fact a titled and experienced player knows what the critical points in a game are or when a lot of tactial calculation is needed so in a single game a lot of his moves doesnt have to follow an engine.

Greco's picture

tactical

Jack's picture

Programmers try to build evermore human thinking into their programs So in fact the rsesult would mean that they succeeded. And, by the way, who checks the computers that are used to find the cheaters? You could now already rig your computer so that it proves that Morphy, Eeuwe etc used computers to cheat.

Foibos Iapetidis's picture

Statistics is not a prooving science. It cannot proove anything.
It can only indicate the probability for a fact to be true or not.
Also, statistics is obliged to report the exact percentage for a fact to be true.
We have AGREED (arbitrary, of cource) to accept as "true", a fact that has a
percentage of probability higher than 95% (statistically significant).
Mostly so when it exceeds 99% (statistically very significant).
But be careful. They are only working decisions.
They are, in no way, considered to be proofing evidence.
And of cource not in a law court. They are not evidence is a legal way.
They only help scientists to make decisions on how to proceed.

Foibos Iapetidis's picture

In my opinion, the title of the article should be: "Using statistics to suspect cheating".
That would say all.

Latest articles