How do Stockfish levels work?

Question

I read on some Lichess forum that Stockfish levels use limited computation time and search depth for lower levels. However, it seems like Stockfish also every so often inputs mistakes and blunders, because it makes some blunders a human, even a beginner, would almost certainly not make. So how are levels implemented?

Answer 1

Since I could not find any complete explanation, I followed the eternal advice "Use the source, Luke". The Stockfish authors did a great job because their code is easily followable and commented. Relevant parts from search.cpp:

  // If skill level is enabled, swap best PV line with the sub-optimal one
  if (skill.enabled())
      std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(),
                skill.best ? skill.best : skill.pick_best(multiPV)));

      // If skill level is enabled and time is up, pick a sub-optimal best move
      if (skill.enabled() && skill.time_to_pick(rootDepth))
          skill.pick_best(multiPV);

And this is the full algorithm used. Here's a summary: the algorithm considers the top-k moves, where k is multiPV, an option chosen by the user and set to at least 4 in the code. delta is computed as the score difference between the best move, ordered first, and the kth best move, however this difference is capped at the value of a pawn to ensure it is not too large. Then, each move is strengthened (has its score increased) by an amount depending on weakness and a random scaling of delta, with % weakness limiting how much effect delta has. If there are many good moves, delta will be small, so each move receives a smaller score push. The algorithm finally chooses the strongest move after these score perturbations.

  // When playing with strength handicap, choose best move among a set of RootMoves
  // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen.

  Move Skill::pick_best(size_t multiPV) {

    const RootMoves& rootMoves = Threads.main()->rootMoves;
    static PRNG rng(now()); // PRNG sequence should be non-deterministic

    // RootMoves are already sorted by score in descending order
    Value topScore = rootMoves[0].score;
    int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg);
    int weakness = 120 - 2 * level;
    int maxScore = -VALUE_INFINITE;

    // Choose best move. For each move score we add two terms, both dependent on
    // weakness. One is deterministic and bigger for weaker levels, and one is
    // random. Then we choose the move with the resulting highest score.
    for (size_t i = 0; i < multiPV; ++i)
    {
        // This is our magic formula
        int push = (  weakness * int(topScore - rootMoves[i].score)
                    + delta * (rng.rand<unsigned>() % weakness)) / 128;

        if (rootMoves[i].score + push >= maxScore)
        {
            maxScore = rootMoves[i].score + push;
            best = rootMoves[i].pv[0];
        }
    }

    return best;
  }