Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T03:16:59.247Z
Answers.LastActivityDate: 2019-02-15T03:16:59.247Z
Answers.UserDisplayName: Inertial Ignorance
Answers.Body: <h2>Speed</h2>
  
  <p>Neural networks operate much more slowly than handcrafted evaluation functions. In the <a href="https://tcec.chessdom.com/" rel="noreferrer">TCEC Superfinal</a>, 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.</p>
  
  <p>While modern engines have a huge selection of <a href="https://www.chessprogramming.org/Selectivity" rel="noreferrer">techniques to cut off unnecessary branches</a>, alpha-beta tree search is still very much a brute force technique, requiring vast numbers of positions to be searched to determine good moves.</p>
  
  <p>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.</p>
  
  <h2>Worst-case behaviour</h2>
  
  <p>One of the key requirements of the evaluation function for an engine based around alpha-beta search is that it must have <a href="http://www.talkchess.com/forum3/viewtopic.php?topic_view=threads&amp;p=135133&amp;t=15504#p135133" rel="noreferrer">good worst-case behaviour</a>. 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.</p>
  
  <p>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 <a href="http://legacy-tcec.chessdom.com/archive.php" rel="noreferrer">match 80 of the TCEC Season 14 Superfinal</a>, 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. </p>
  
  <p>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.</p>
  
  <h2>Quiescence</h2>
  
  <p>All strong alpha-beta engines use a technique called <a href="https://www.chessprogramming.org/Quiescence_Search" rel="noreferrer">quiescence search</a>, 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.</p>
  
  <p>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.</p>
  
  <p>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 <a href="http://talkchess.com/forum3/viewtopic.php?f=2&amp;t=69891#p789773" rel="noreferrer">using short alpha-beta searches anyway</a>, to get quiescent positions and hence allow its handcrafted evaluation to return a reasonable score)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-21T21:36:09.733Z
Answers.LastActivityDate: 2019-02-21T21:36:09.733Z
Answers.UserDisplayName: konsolas
Body: <p>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.</p>
  <p>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?</p>
  <p><strong>Edit:</strong> for anyone who sees this question today (2023), it is <strong>outdated</strong>, because Stockfish uses <a href="https://en.wikipedia.org/wiki/Efficiently_updatable_neural_network" rel="nofollow noreferrer">NNUE evaluation</a> these days instead of its handcrafted eval, and top engines are NN + MCTS &amp; AB + &quot;NN&quot;.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-16T12:41:15.030Z
Comments.Text: 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.
Comments.UserDisplayName: John Coleman
Tags: <engines>
Title: Why does NN + MCTS & AB + handwritten eval dominate engine chess?
ThreadText: # Why does NN + MCTS & AB + handwritten eval dominate engine chess?
  
  (Asked by: username_0 on 2019-02-14)
  
  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](https://en.wikipedia.org/wiki/Efficiently_updatable_neural_network) these days instead of its handcrafted eval, and top engines are NN + MCTS & AB + "NN".
  
  **Tags:** engines
  
  > **Comments:**
  > **username_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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-02-21. Score: 16 | Accepted answer
  
  ## Speed
  
  Neural networks operate much more slowly than handcrafted evaluation functions. In the [TCEC Superfinal](https://tcec.chessdom.com/), 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](https://www.chessprogramming.org/Selectivity), 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](http://www.talkchess.com/forum3/viewtopic.php?topic_view=threads&p=135133&t=15504#p135133). 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](http://legacy-tcec.chessdom.com/archive.php), 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](https://www.chessprogramming.org/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](http://talkchess.com/forum3/viewtopic.php?f=2&t=69891#p789773), to get quiescent positions and hence allow its handcrafted evaluation to return a reasonable score)
  
  
  ---
  
  ### Answer by username_2 on 2019-02-15. 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.
  
  
  ---
  
  