Saturday, 9 June 2012

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.