Method to reliably determine abnormal statistical values

Question

I'm searching for a statistical method to determine if a player is cheating in an online game. The game is a Quake3 like game (ego-shooter).

Given a number of positive points and a number of negative points per player (score) and given n players (n<=64).

The score comes together like this (positive/negative seen from anti-cheat-perspective):
positive = number of time the player died himself
negative = number of opposite team's players killed


Additional available values:
t = Time in which this score has been accomplished
c = number of current number of players
m = number of times a player killed someone from the same team (teamkiller, very negative if higher than 1 or 2 over a 15 minutes period)

Each player can cheat independent of each other.

I used the standard deviation (on the value v = (negative+1)/(postive+1) per player, assigning the exceeding of 3 times standard deviation with absolute certainty (100%) of cheating - although my experience has been that exceeding stddev alone would be sufficient in most cases), which works great on a single player but fails miserably as soon as several players are cheating at the same time. Also the practise of defining 3 times stddev as 100% allows for > 100% probabilities. Unfortunately, the percentage of players cheating in an unfiltered game is roughly 70 to 80 percent or even higher, if accounting for more subtle cheats.

One more thing to consider is, if there is a group of people cheating, and one that isn't, the distribution is no longer a normal distribution, but a camel-bump like distribution. Is there any useful algorithm or formula for this problem ?

Answer 1

Your use of the stddev indicates you look at every variable seperately. If you look at them together, you might have more chance. An outlier in one dimension can be coincidence, an outlier in more dimensions is more surely an anomaly. I don't know much about games, but I reckon that you could use find extra variables like traveled distance in the game and so on.

You can use outlier theory for detecting anomalies. A very naive way of looking for outliers is using the mahalanobis distance. This is a measure that takes into account the spread of your data, and calculates the relative distance from the center. It will be less sensitive to outliers in one statistic, but can be seen as a way of finding gamers where the combination of the statistics is odd.

A similar approach is building a model and taking a look at the error terms. This does essentially the same: it looks for gamers that don't fit the general pattern. It's a technique that's also used in financial services to find fraud cases. The model can go from a basic linear model to more complex models. If you apply your algorithm to the error terms of the model fitted without player i, you essentially calculate something similar to Cook's distance of a certain player. In combination with the DFFITS measure and the leverage, it is often used for detection of outliers and/or influential points in regression.

You could as well use supervised classification: You train an algorithm with genuine gamers and known cheaters. There's a multitude of techniques available there, starting from neural networks and classification trees to support vector machines and random forests.

Genetic algorithms are used more and more as well, as they can progress in knowledge when time goes by. If you check the assumed cheaters, you could -much like a spam filter- correct the wrongly classified gamers. The algorithm will continuously learn to predict better when a gamer is a cheater.

As mbq mentioned, without example data it's impossible to give you an algorithm; I don't even know on which measurements one can work. But this should give you some ideas about the multitude of available methods, from very naive to pretty complex. Much can be learned from fraud detection if you'd like to google around a bit further.

A starter could be this article of Wheeler and Aitken. Another interesting overview of possible techniques is found in this article by Kou et al (alternative link to publication)

Answer 2

I will repost the answer I gave on math.stackexchange:

Your question needs some more information:

How is their score generated (what kind of game is it)? What should your non-cheating data look like? How do people cheat? How will their score be different (in a statistical sense) when they are not cheating? Do you know roughly the proportion that are cheating? Or is that something you also want to find out?

I would also look at outlier detection algorithms: wikipedia looks useful on this topic (link). Using a Q-Q plot on your data may also be useful if your non-cheating data should be approximately Normally distributed; points that are significantly above the line might be cheaters.