Skip to main content
Chess

Return to Answer

added 26 characters in body
Source Link
ldog
ldog
  • 1.2k
  • 6
  • 11

To give my answer as to how I would approach this, I would use a simple idea:

  • Null Hypothesis Test

The idea is that there are is a limited number of publicly available chess engines, lets say N of them. This assumption of course precludes the possibility that the cheater has written their own chess engine (or is using some publicly unavailable chess engine) but for catching casual cheaters this should be a strong enough assumption.

The application of the Null Hypothesis Test would be very simple: for each chess engine X and for each subsequence of moves of the current game compute the probability p of observing the played subsequence assuming the null hypothesis that the player is not using chess engine X to make the moves for them. A naive assumption could be made that the player moves at random (or randomly chooses from a select number of top moves d_i), then the probability for a given subsequence of length nk matching moves a chess engine X would make would be computed as 1/(d_1)/(n_1) * (d_2)/(n_2) * (d_3)/(n_3) * ... * d_n(d_k)/(n_k) where d_i is the number of possible (top) moves to make at the ith turn, as rated by engine X and n_i is the number of total moves available to the player at turn i (or some reasonable subset.)

Then simply compute

p* = minimum p over all chess engine X, all subsequences y.

If p* is less than a certain threshold label the player as a cheater since there exists a subsequence y and chess engine X that brings the probability that the player is not cheating below a desired probabiity.

To give my answer as to how I would approach this, I would use a simple idea:

  • Null Hypothesis Test

The idea is that there are is a limited number of publicly available chess engines, lets say N of them. This assumption of course precludes the possibility that the cheater has written their own chess engine (or is using some publicly unavailable chess engine) but for catching casual cheaters this should be a strong enough assumption.

The application of the Null Hypothesis Test would be very simple: for each chess engine X and for each subsequence of moves of the current game compute the probability p of observing the played subsequence assuming the null hypothesis that the player is not using chess engine X to make the moves for them. A naive assumption could be made that the player moves at random (or randomly chooses from a select number of top moves d_i), then the probability for a given subsequence of length n matching moves a chess engine X would make would be computed as 1/(d_1 * d_2 * d_3 * ... * d_n) where d_i is the number of possible (top) moves to make at the ith turn.

Then simply compute

p* = minimum p over all chess engine X, all subsequences y.

If p* is less than a certain threshold label the player as a cheater since there exists a subsequence y and chess engine X that brings the probability that the player is not cheating below a desired probabiity.

To give my answer as to how I would approach this, I would use a simple idea:

  • Null Hypothesis Test

The idea is that there are is a limited number of publicly available chess engines, lets say N of them. This assumption of course precludes the possibility that the cheater has written their own chess engine (or is using some publicly unavailable chess engine) but for catching casual cheaters this should be a strong enough assumption.

The application of the Null Hypothesis Test would be very simple: for each chess engine X and for each subsequence of moves of the current game compute the probability p of observing the played subsequence assuming the null hypothesis that the player is not using chess engine X to make the moves for them. A naive assumption could be made that the player moves at random (or randomly chooses from a select number of top moves d_i), then the probability for a given subsequence of length k matching moves a chess engine X would make would be computed as (d_1)/(n_1) * (d_2)/(n_2) * (d_3)/(n_3) *...* (d_k)/(n_k) where d_i is the number of possible (top) moves to make at the ith turn, as rated by engine X and n_i is the number of total moves available to the player at turn i (or some reasonable subset.)

Then simply compute

p* = minimum p over all chess engine X, all subsequences y.

If p* is less than a certain threshold label the player as a cheater since there exists a subsequence y and chess engine X that brings the probability that the player is not cheating below a desired probabiity.

Source Link
ldog
ldog
  • 1.2k
  • 6
  • 11

To give my answer as to how I would approach this, I would use a simple idea:

  • Null Hypothesis Test

The idea is that there are is a limited number of publicly available chess engines, lets say N of them. This assumption of course precludes the possibility that the cheater has written their own chess engine (or is using some publicly unavailable chess engine) but for catching casual cheaters this should be a strong enough assumption.

The application of the Null Hypothesis Test would be very simple: for each chess engine X and for each subsequence of moves of the current game compute the probability p of observing the played subsequence assuming the null hypothesis that the player is not using chess engine X to make the moves for them. A naive assumption could be made that the player moves at random (or randomly chooses from a select number of top moves d_i), then the probability for a given subsequence of length n matching moves a chess engine X would make would be computed as 1/(d_1 * d_2 * d_3 * ... * d_n) where d_i is the number of possible (top) moves to make at the ith turn.

Then simply compute

p* = minimum p over all chess engine X, all subsequences y.

If p* is less than a certain threshold label the player as a cheater since there exists a subsequence y and chess engine X that brings the probability that the player is not cheating below a desired probabiity.