1

I'm looking for some reference for the number of lookahead steps typically used by chess agents (Stockfish / Leela Chess Zero / others?)

From a quick search I found that: the answer depends on:

  1. complexity of position,
  2. computer hardware/processor speed,
  3. efficiency of software/graphics interface,
  4. time given to the chess engine.

with somewhat mediocre hardware a depth around 15 ply's in one second is typical.

the NPS value for the Stockfish engine: 49,473 kN/s (calculating 49,473,000 positions (nodes) per second).

source:

  1. https://www.quora.com/What-is-Stockfishs-depth-when-analysing-a-chess-position
  2. https://chessify.me/blog/nps-what-are-the-nodes-per-second-in-chess-engine-analysis
4
  • 1
    Seems like you already have the answer, what is the question then?
    – Allure
    Commented Dec 20, 2022 at 16:31
  • I am looking for a valid reference, academic work would be best. Also I am not sure about the answer I got and I would like to get a validation.
    – Cohensius
    Commented Dec 20, 2022 at 19:02
  • 3
    I can confirm the answers are right, but I can't give you a reference, because it's sort of common knowledge among the chess engine community.
    – Allure
    Commented Dec 21, 2022 at 0:18
  • If you need a citable academic reference for the lookahead steps of chess engines on typical hardware, this sounds a bit like an XY problem because the answer is largely meaningless/not very well defined.
    – gcp
    Commented Mar 14, 2023 at 20:10

1 Answer 1

5

Up to date reference is practically impossible to give, since engines and hardware change on yearly basis.

You identified most important conditions, but I would like to add two more:

  1. Presence of tablebases (vastly improves evaluation depth in late endgames);
  2. NNUE (slower) or hand-tuned evaluation function (faster).

Introduction of NNUE techniques vastly improved accuracy of evaluation function, but also made it slower. If you compare stockfish versions before NNUE and after you will see in same time frame difference of as many as 10-20 ply. Newest stockfish is still stronger than older, because it gains more in evaluation accuracy than loses in depth (in most positions! in some endgames this tradeoff is not so good).

From my experience (running time 1-2 minutes):

  • SF before NNUE in middlegame on reasonably strong computer: 30-40 ply
  • SF with NNUE in middlegame on reasonably strong computer: 20 ply
  • SF with NNUE in middlegame with 64 cores and 128gb ram: 30-40 ply
  • SF with 6 piece tablebases in endgame with ~8 pieces: 60+ ply or (more often) forced win/draw found.

Note that in early openings engines are very unreliable, no matter the (contemporarily achievable) depth.


As @Polytropos pointed out in comment, meaning of depth depends on choice of tree search algorithm. Possible moves and possible replies to them (and replies to them ...) can be arrayed into tree structure, so question of finding the best move is question of finding route to victory. Since this tree is too big to cover entirely we need to cheat - stop searching before we find the goal, evaluate positions and calculate approximate scores.

Additionaly chess is a zero sum game - this means, that your position can only be as good for you as it is bad for your opponent (and vice versa). This means that minimax search can be used.

Detailed explanation of tree search algorithms is out of scope for this answer. If interested, consult pages for minimax, Alpha-Beta pruning and Monte-Carlo tree search (MCTS). I will focus on practical consequences of choice of algorithm. Theoretically given infinite time they all lead to optimal solution.

Minimax in pure form cannot be used practically, since it's too time intensive. So in practice it's optimized by Alpha-Beta pruning. This way of searching is used by Stockfish, currently strongest publically available engine. Depth here means number of plys before reaching evaluation, with some moves ignored at each ply based on preliminary evaluations. Practically it optimizes for greater depth by sacrificing some breadth.

Consequence is that it may miss some good moves, which look bad to preliminary evaluation. Consequently human skill still matters in engine-assisted correspondence chess, since humans can force engine to consider moves that it would disregard to early (most commonly sacrifices with long-term positional compensation). It also leads to engines being weaker in (at least quiet) openings compared to (at least forcing) middlegames, since breadth is larger in openings, so more of it has to be pruned.

MCTS is used most notably by AlphaZero and Lc0. It's based on probabilistic methods. Practically it leads to lower search depths but better breadth than minimax with Alpha-Beta pruning.

Consequently play of these engines is slightly better in openings, but slightly worse in endgames (but this may also be attributed to evaluation function).

Depth for Lc0 is average depth reached for move, based on considered sample.

In short, don't compare depths reached by one engine to depths reached by different engine. Depth is inaccurate heuristic for accuracy, as such it can only tell you, that if same engine reaches depth 20 and depth 40, evaluation at depth 40 is most probably more accurate.


More pedantically Lc0 uses PUCT not MCTS, since pure MCTS uses random playouts for evaluation, while Lc0 uses neural network based evaluation function. For pure MCTS depth has not a lot of meaning, since better heuristic for accuracy is number of random playouts.

Another thing that makes comparision between Lc0 and Stockfish harder is difference in hardware. Lc0 runs on GPU, Stockfish on CPU.

2
  • 4
    I would suggest adding as information that for MCTS-based engines like LC0, the notion of calculation depth doesn't make much sense (this is to a lesser extent also true for modern Alpha-Beta based engines, as the intuition that they perform something remotely equivalent to full minimax search within some fixed depth horizon is very wrong; but at least, the notion of depth has some historical continuity going for it there).
    – Polytropos
    Commented Jan 9, 2023 at 22:38
  • 2
    MCTS implementations with policy networks such as used in Leela Zero (Chess) have a much more selective search (less breadth) than alpha-beta based engines. PUCT is a version of UCT with Priors (given by the policy network), and UCT is just a formula to steer a MCTS. So Leela certainly still uses MCTS, it accelerates the playouts by estimating the result of them with a neural network. The MCTS doesn't "know" we optimized away the playouts, so it's not suddenly another algorithm.
    – gcp
    Commented Mar 14, 2023 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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