5

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?

7

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;
  }
6
  • 2
    +1 for the “saying”!
    – fartgeek
    Jun 13 at 12:21
  • Could you conceptually unpack the part of the algorithm relating to delta a little please? (assuming you understood this part of the code better than I did!) It's clearly the random component but I didn't really understand std::min, the comparison to PawnValueMg, or the % weakness... Jun 18 at 17:08
  • 1
    @MobeusZoom I added an explanation based on my understanding to the answer.
    – qwr
    Jun 18 at 17:47
  • 1
    Yes, the deterministic part makes the move scores closer together (harder to distinguish), and weakness also randomly boosts move scores by a random quantity between 0 and k-1 (then divided by 128).
    – qwr
    Jun 18 at 20:07
  • 1
    I added a note about k. As for blunders, I see the computer make obvious blunders, but I guess at a beginner level like I am it's hard to notice your own blunders until it's too late.
    – qwr
    Jun 18 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.