This is the first of several posts digging into the internals of ChessCheaterDetector. We'll cover one signal at a time, explain what it measures, why it matters and how we calculate it.
This post is about chess position complexity: how difficult a position is to play accurately.
Why complexity matters
Suppose the engine says there's only one sensible move in a position: recapturing a queen, getting out of check or taking a free piece.
A player finding that move isn't particularly informative. A beginner and a grandmaster may both see it immediately.
Now consider a position where the engine's top five moves might all look reasonable, but after calculating deeper, one move gradually separates itself from the others. Perhaps one move, that initially looks excellent, turns out to allow a devasting hidden tactic for the opponent at the end.
A user finding the best move in that position tells us much more.
A simple way to think about it
Imagine watching Stockfish think about the same position over and over.
At a shallow search, it might rank the moves like this:
1. Move A
2. Move B
3. Move C
4. Move D
After searching deeper:
1. Move A
2. Move C
3. Move B
4. Move D
The rankings are fairly stable. Stockfish basically knew what it liked from the beginning.
Now imagine this:
Depth 5
1. Move A
2. Move B
3. Move C
4. Move D
Depth 10
1. Move C
2. Move A
3. Move D
4. Move B
Depth 15
1. Move B
2. Move D
3. Move A
4. Move C
Here the engine keeps changing its mind as it calculates further.
That's a useful proxy for complexity. A position where the strongest moves remain stable as the search gets deeper is generally easier to resolve. A position where the ranking changes substantially requires more calculation and is therefore more difficult to evaluate correctly.
Position complexity measures how much the engine's view of a position changes as it calculates more.
The approach: Biswas and Regan
This is based on a method described by Biswas & Regan, "Measuring Level-K Reasoning, Satisficing, and Human Error in Game-Play Data" (ICAART 2015). The paper gives us a way to turn this intuition into a number.
We run Stockfish at a series of search depths and record the moves it considers strongest at each depth. We then compare the rankings between consecutive depths.
The more stable those rankings are, the lower the complexity. The more they change, the higher the complexity.
Generalized Kendall tau
To compare two rankings, we use a generalized version of Kendall tau distance. The idea behind it is fairly simple: look at pairs of moves and see whether their ordering has changed.
Our version takes the engine evaluations into account. A small ranking change between two moves that are almost equal matters more than the same ranking change between moves where one is already much better.
The calculation
For each position we run the Stockfish engine with multipv=50 at every depth from 1 through 19. This gives us a ranked list of the 50 best candidate moves at each depth.
We compare each depth with the next one, calculate how similar their rankings are, and average those results:
def _compute_complexity_from_scored_moves(self, scored_moves: dict) -> float:
summed = sum(
self._kendall_tau(scored_moves[depth], scored_moves[depth + 1])
for depth in range(1, self._max_depth)
)
return 1 - ((1 / (self._max_depth - 1)) * summed)
- Stable rankings → low complexity
- Unstable rankings → high complexity
Speed/Accuracy Tradeoff
There is a practical tradeoff between how deeply we search and how quickly we can analyse a position.
The depth of the Stockfish search has a large effect on analysis time. Going from depth 10 to depth 19 requires substantially more computation. Since complexity is based on how the engine's rankings change as it searches deeper, higher depths generally give us a more complete picture of the position, but at a significant cost in processing time.
The number of candidate moves we consider has a surprisingly small effect by comparison. Increasing multipv from a small number to 50 adds relatively little analysis time compared with increasing the search depth. This makes it practical to examine a large set of candidate moves without sacrificing much performance.
For ChessCheaterDetector, this means depth is the main parameter we need to balance against analysis speed, while keeping a relatively high multipv gives us more information about the stability of the engine's rankings at comparatively little additional cost.
Our current implementation searches to depth 19 with multipv=50, giving us a reasonably detailed measure of complexity while keeping analysis time mostly manageable.
A few implementation details
There are a few details worth mentioning for completeness.
We clear Stockfish's hash table between depths. This prevents a search from influencing a later calculation through previously stored positions.
We only compare moves that appear at both depths. If a move is present at depth 10 but absent at depth 11, there isn't enough information to compare that particular move directly.
Finally, we exclude positions containing mate scores. The generalized formula is designed for centipawn evaluations, and "mate in 3" doesn't have a natural equivalent in that calculation. The handling of this may change in future iterations, as this can lead to occasional unintuitive complexity estimates.
What complexity tells us
Complexity is useful because a player playing the top engine move means different things in different positions.
Playing the engine's top move in a forced position isn't surprising.
Playing the engine's top move in a position where the engine itself has to search deeply before deciding which move is best is far more informative.
That's why we don't look at engine agreement alone. Complexity gives us some idea of how difficult the decision actually was.
We combine this signal with engine agreement, centipawn loss and rating expectations to produce the per-move suspicion score described on the how it works page.
In the next post, we'll look at how these signals are combined to estimate the probability that a move was assisted by an engine.