Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a practical question that was asked on a correspondence chess site. The site struggles with chess engine users, who are considered cheaters. The method people use to determine whether someone is a cheater is this. Take a large enough number $x$ of games the person has played; analyze them with an engine (starting from the point where the game leaves online chess databases, whose use is allowed) and find the average match-up rates, for example:

  • 1st choice - 50% match-up rate,
  • 2nd choice - 65% match-up rate,
  • 3rd choice - 80% match-up rate,

where the first number is the ratio $$\frac{\text{the number of analyzed moves that are considered best by the engine}}{\text{the number of analyzed moves}},$$

the second number is the ratio $$\frac{\text{the number of analyzed moves that are considered best or second best by the engine}}{\text{the number of analyzed moves}},$$

and the third number is found in a similar way.

The question is how large $x$ must be in order for these numbers to approximate the overall match-up rates well.

I think the right way to ask this question more precisely is to fix a small error $\varepsilon$ and a small probability $p$, and ask how large $x$ must be for the probability of the actual error exceeding $\varepsilon$ to be less than $p$.

I did do a course in statistics, but I remember almost nothing of it. Could you help me with this?

share|improve this question
    
Your question is not entirely clear. Is it correct that "analyzed moves" refers only to moves that the suspected cheater has actually played, while "considered best by the engine" means the unique move found best by the engine among the options at that point in play? So as an extreme case, if the cheater just was using the engine blindly, the first number would be 100% (and the other a fortiori also). The idea is that if a player is doing very well (by the engine's standards), then it must be a cheater. At least in cycling this appears to be fairly sound reasoning. –  Marc van Leeuwen Nov 16 '12 at 14:32
    
Don't you get into trouble when there is a long sequence of exchanges? Then every move is obvious to a human and computer: would they be flagged as cheaters? –  Fixee Nov 16 '12 at 15:09
    
@Marc Yes, that's what I meant. –  Bartek Nov 17 '12 at 13:03
    
@Fixee Well, the idea is to analyze many games, not just one. The match-up rates are hoped to become more and more meaningful as the number of analyzed games grows. –  Bartek Nov 17 '12 at 13:06
add comment

1 Answer 1

up vote 6 down vote accepted

Binomial or multinomial models will not work well in practise here, and you need to do some serious empirical work to get good tests for detecting cheaters. The problem is that chess players do not have fixed probabilities for choosing the computer's recommendations. In particular, if the computer considers one move to be much stronger than all other alternatives, then it is much more likely that a human player will arrive at the same conclusion.

Ken Regan at the University of Buffalo has done some serious work on this question, which you can read about on his home page.

share|improve this answer
add comment

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.