20

As I understand it engines can be divided into four groups right now: those that use Alpha-beta (AB) + those that use Monte Carlo Tree Search (MCTS) for search, and those that use handwritten functions + those that use neural networks for eval. The two strongest engines are Leela and Stockfish. Leela uses MCTS + NN, while Stockfish uses AB + handwritten.

Why these two combinations? Why not NN + AB, or MCTS + handwritten? If MCTS is better than AB, why isn't Komodo MCTS stronger than Komodo AB? If AB is better than MCTS, why isn't Leela using AB instead?

Edit: for anyone who sees this question today (2023), it is outdated, because Stockfish uses NNUE evaluation these days instead of its handcrafted eval, and top engines are NN + MCTS & AB + "NN".

1
  • Just speculating: NN are pattern-recognizers. Since MCTS casts a wider net, it is more likely to encounter patterns that the NN has been trained to recognize as either good or bad. Feb 16, 2019 at 12:41

2 Answers 2

16

Speed

Neural networks operate much more slowly than handcrafted evaluation functions. In the TCEC Superfinal, Leela Chess Zero, running on two GPUs each with dedicated tensor cores, is able to search around 60 thousand positions per second. By contrast, Stockfish, on a single core on my PC, searches over 2 million positions per second.

While modern engines have a huge selection of techniques to cut off unnecessary branches, alpha-beta tree search is still very much a brute force technique, requiring vast numbers of positions to be searched to determine good moves.

MCTS, by contrast, is far more selective, and only expands its search tree towards the most promising moves, which allows it to make the most of the more limited number of nodes that can be searched.

Worst-case behaviour

One of the key requirements of the evaluation function for an engine based around alpha-beta search is that it must have good worst-case behaviour. This is because any large error in evaluation, however rare, can easily be propagated to the root and lead to a horrendously incorrect move being played.

By nature of their complexity, neural networks are prone to overfitting and can only be as good as the data used to train them. For example, in match 80 of the TCEC Season 14 Superfinal, on move 47 Lc0 was apparently unfazed by Stockfish's extra queen, evaluating the position as a cool +0.77, while Stockfish (and most other engines) sported an evaluation of +8.31. A popular explanation for this is that Lc0 may not have had a significant number of games with multiple queens on the board in its training set.

Neural networks, therefore, have poor worst-case behaviour, and hence are likely to perform poorly with alpha beta search. MCTS, by contrast, allows an incorrect score assigned to one position to be offset by averaging it out with reasonable scores assigned to positions nearby in the search.

Quiescence

All strong alpha-beta engines use a technique called quiescence search, a restricted form of alpha-beta search applied at leaf nodes, in acknowledgement that their handcrafted evaluation functions only work well in "quiet" positions, where there are no pending captures or checks.

For example, immediately after the first half of a queen exchange, a handcrafted evaluation function might tell you that the side which just had their queen taken is completely lost, whereas a neural network may be able to understand that the queen will be recaptured soon.

This makes handcrafted evaluation functions similarly unsuitable for MCTS due to absence of quiescence search, resulting in the handcrafted functions performing poorly much of the time (although Komodo 12 MCTS gets around this restriction by using short alpha-beta searches anyway, to get quiescent positions and hence allow its handcrafted evaluation to return a reasonable score)

2

AB and MCTS aren't necessarily better than each other on their own merits. It's just that they are different search algorithms that work better with different foundations. For the NN, MCTS works well since it allows the engine to explore branches that are doing better. This gives the engine more freedom to look at what it "wants" to.

Meanwhile with AB, all branches in principle have to be looked at. This is because even with iterative deepening, the engine only looks so far on each branch in each iteration. So it doesn't know if one branch is actually winning for one side, even if it seems losing at a limited depth.

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.