Detecting cheaters --- a statistical approach (I): creating a measurement

Cheating is a basic problem occuring in digital game. The idea of cheating is based on the ability to change the statistics easily. In reality the statistics is based on matter (action can be regarded as movement of matter) in a specified period. For example, one of the statistics --- money --- in a narrow sense --- legal tender, is measured by the amount of matter that you own that is recognised as legal tender. You can't "create" a $100 note from nothing and the cost of producing one is far too high.

In digital game, statistics are represented by configurations of electrons only. You can simply change the level from 1 to 2 by 01 to 10. The electrons are so cheap and the cost of changing it is very low. In single player game they are very common, like the GBA or NDS simulator in which (value):(position) cheating code is not even hard for a non-programmer to process.

However it causes problems in multiplayer game. As long as cheating players aren't the only group of players in the game, fair play should be enhanced. (You have to admit that fair play is the basis of commercial activity based on the game in typical MMORPG unless the added-value services is unachieveable by cheating like the osu!supporter tag) Cheating raises the level of achievement to an unreachable level for manual players, and eventually they are despaired and leave the game.

Definition 1. Cheating is a process that makes benefit from approaches that is not permitted in a certain system.

And therefore, cheating should be stopped.

So how?

In fact I'm writting this for something happened in osu!, so I'll take osu! as example.

Quantification or an exact measurement on player's ability is needed. Sometimes it's very hard to determine one's ability especially in MMORPG because different occupation can have advantage on each other, or they have different position in battle team as a whole. We say that the capability of MMORPG character is not well-ordered. However in games that promotes extreme techniques, the power of a player can be easily revealed.

Definition 2. If the elements a_i in the set S is well-ordered, for a_i =/= a_j a > or < relation can be set up (search "definition of inequalities in this blog for further information about < and >) and the relation is transisive for all elements in the set. In reality we define a_i > a_j if there is a probability larger or equal to k that a_i plays better than a_j (trivially k > 0.5). For some reason we call it confidence constant first. If k = 1 they are absolutely well-ordered. Note that the "definition of well-ordered measurement in reality" is not properly well-ordered in mathematics.

The measurement of power of player should be clear and exact. Let S be the set of players and f is the mapping from players to measurement of power of player, then f: S -> R+ U {0} (non-negative real, and f(x)=0 if the player has no playing record). Considering the upper level of playing, assuming player plays enough many maps so that the overall power shows the ability to play all maps with different characteristic and difficult pattern. i.e., the measurement of power is not affected by the strength and weaknesses of players because they offset each other.

And now we go into some calculations.



Denote the measurement of ability to play of player x be P(x). Since they are not well-ordered in the sense of mathematics but in the definition in reality defined, treat P(i) as a distribution or generalized function. Since the play count is large enough treat P as normal distribution and the apparent numerical value of P(i) is the mean.

Even in these games the players' strength aren't absolutely well-ordered. Then it's clear that when the value of is small the chance of player i playing better than player j in more than k of the time is not true. Then we say that their difference in ability to play is not significant, denote by ~ . Trivially if k is larger then the range of P that the two player has no significant difference is smaller.

Recall the confidence level for difference between two distribution:
  <  <

m is the multiplying factor of P (reducing decimal and ease comparason in reality). The standard deviation can be treated as stability of playing and n is the play count. To make life easier we can set up a regression relationship mapping ability to stability and play count. i.e., and , and to simplify it further let .

Substituting the confidence level, letting , , and assume x is far greater than d, then and the relation is simplified as:

  <   <

Now there's a chance that falls out of the lower limit of the confidence interval. Set the lower limit be zero then we have .

By solving LHS = 0 we have and that's the difference between two players so that their ability can be clearly distinguished.

Let us substitute some true value into it. Let , at the same time stability is proportional to P (no proportionality constant) while play count is modelled as . Then !!! Very suprising (not really) it's a constant function --- in fact not very suprising because we have ignored the effect in difference in stability in playing different maps in the calculation so as here, so stability and play count has no effect in the calculation.

and this is a very satisfying result concerning the reality situation of osu!. Now someone may worry that the assumption made that x is far greater than d is not valid but we don't need to worry about it because we find that g(x) is a constant function so that assumption is no longer needed, then we don't care if it's valid now.

Now we have discussed technical problem on setting up measurement based on known statistics, and next time we will do it all inversely, from know measurement to a suspected cheating statistics.