Answers.Body: <p>Let's begin with what <em>position evaluation</em> means, as it is the core of everything.</p>
  <blockquote>
  <p>AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs.</p>
  </blockquote>
  <p>In beginner Chess we are probably taught that pawn is worth 1 point, 3 for knight and 9 for Queen. This is a quick way to evaluate how good/bad our situation is. Similarly in Bridge, we count Ace as 4 points, King as 3 and etc.. This is the <em>position evaluation</em> function, indicates how advantage/disadvantage a side is given a certain board situation.</p>
  <p>Obviously, the above-mentioned evaluation methods are very elementary and do not account for all the complexity. Say I can be a Queen and a Rook less but can surely checkmate (win) in 20 steps. Or I have a hand with only 10 points (A,K,Q,J) but with all 13 cards of Spades and thus easily make a 7S major slam.</p>
  <p>To accommodate these situations, human experts invent a lot of 'patches' to the evaluation: e.g. 2 pawns on same line gives a -1, a long suit adds +2 points etc.. All in all, these are <em>handcrafted features</em> create manually via careful engineering. 'Typical chess programs' e.g. Stockfish use them under the hood.</p>
  <p>Regardless, these position evaluations are <em>linear</em>: they are composed of a bunch of if-else statements, e.g. 'if I have a Pawn, adds 1 point', 'if I have no card in a suit, adds 4 points'. This is what the paper means by <em>linear function approximation</em>.</p>
  <p>In contrary, AlphaZero's position evaluation function does <strong>not</strong> rely on any hard-coded rules, but directly evaluate the board position. For example in Go, the function takes the position of all pieces on the board as input, feeds through a deep neural network (with a lot of layers e.g. convolution, residue blocks, max-pooling etc.) and returns a score of position advantage (e.g. 60% chance Black is leading).</p>
  <p>Notice that:</p>
  <ol>
  <li>The DNN is not static - it keeps updating during training and (hopefully) improves.</li>
  <li>The evaluation function is non-linear; this is where the <strong>non-linear function approximation based on a deep neural network</strong> comes from.</li>
  </ol>
  <blockquote>
  <p>approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.</p>
  </blockquote>
  <p>The 'averages over' part is essentially how MCTS works - compute the positional evaluations of all subtrees of a branch, and (weighted) average the results as the score of the branch. While in Alpha-Beta, there is no 'average' - only the best is kept else pruned.</p>
  <blockquote>
  <p>MCTS returns visit counts for each of the moves</p>
  </blockquote>
  <p>AFAIK, visit counts is used to approximate the confidence of position evaluation (similar to the role of sample size and confidence level in statistics). The actual scores combines both visit counts and evaluation scores of subtree.</p>
  <p>Finally,</p>
  <blockquote>
  <p>why AlphaZero uses MCTS instead of Alpha Beta search?</p>
  </blockquote>
  <p><strong>[Updated]</strong></p>
  <p>There are at least 2 reasons as per this <a href="https://hal.inria.fr/hal-00695370v3/document" rel="nofollow noreferrer">reference papar</a>:</p>
  <blockquote>
  <p>(section 3.2) In some games of interest, e.g., in the game of Go, it has proven hard to encode or learn an evaluation function
  of sufficient quality to achieve good performance in a minimax search.</p>
  </blockquote>
  <p>It claims that minimax is more sensitive to evaluation function vs. MCTS, and for complex games it makes a significant impact. The fundamental reason probably lays between the statistic used: max/min vs. mean.</p>
  <blockquote>
  <p>(section 4.3) Classical game-tree-search algorithms, such as minimax search with α − β pruning, are notoriously difficult to parallelize effectively. Fortunately, MCTS lends itself much more
  easily to parallelization.</p>
  </blockquote>
  <p>A practical consideration: MCTS is easier to parallelize.</p>
  <p>Finally, I recommend going over the AlphaGo paper first as it spells out more details (especially the value and policy network part), then AlphaGo Zero (which merges the value and policy network) before jumping into AlphaZero. Things should get a lot clearer this way as the authors skip some details in later papers.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-17T13:43:46.770Z
Answers.Text: "My view is although Alpha-Beta (and Minimax) is theoretically optimal, it requires a predefined (handcrafted) position evaluation function." It would be possible to develop AB with the help of DNN as evaluation function. That would mean no such handcrafted position evaluation function.
Answers.UserDisplayName: Dimanjan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-18T03:26:36.687Z
Answers.Text: @Dimanjan yes I see no obvious obstacle along this line, but TBH I am no expert. Haven't find a solid, satisfying answer yet, my speculation is there is some practical consideration which fuse MCTS and DNN together better than Alpha-Beta + DNN.
Answers.UserDisplayName: lpounng
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-18T06:19:16.623Z
Answers.Text: I look at the AlphaGo paper again. In "Prior Work" section it mentions *"minimax search with α − β pruning has achieved super-human performance
  in chess..., but it has not been effective in Go"*, and *"The strongest current Go programs are based on MCTS"*. Unfortunately no study on the reason why. Probably need to dig deeper in the citations.
Answers.UserDisplayName: lpounng
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-18T10:16:50.040Z
Answers.Text: found a good reference, updated the answer.
Answers.UserDisplayName: lpounng
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-19T08:43:44.003Z
Answers.Text: I have accepted your answer. I would also add the possibility that the exact reason may not be known. AlphaZero probably used it because it gave good results in their own experiments and others researchers previous experiments. But maybe a solid reasoning behind its effectiveness is not yet formulated. Its possible that they themselves do not know for sure.
Answers.UserDisplayName: Dimanjan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-20T06:30:07.247Z
Answers.Text: Plausible. Anyway, why not drop an inquiry (e.g. email) to the paper authors? They must have a lot of thoughts about it.
Answers.UserDisplayName: lpounng
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-22T12:54:17.380Z
Answers.Text: hmm, I will consider doing that, Probably won't get a response though.
Answers.UserDisplayName: Dimanjan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-17T10:17:55.830Z
Answers.LastActivityDate: 2022-10-18T10:27:33.623Z
Answers.LastEditDate: 2022-10-18T10:27:33.623Z
Answers.UserDisplayName: lpounng
Body: <p>I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search.
  Some <a href="https://news.ycombinator.com/item?id=19552286" rel="nofollow noreferrer">analysis</a> claim that its because MCTS is a lot more humanlike. I disagree because I don't think AlphaZero was really concerned about becoming humanlike. The fact that it ended up playing like humans was just a coincidence but it was never the goal behind its design choice.</p>
  <p>In the AlphaZero paper,</p>
  <p><strong>MCTS and Alpha-Beta Search</strong></p>
  <blockquote>
  <p>For at least four decades the strongest computer chess programs have
  used alpha-beta search (18, 23). AlphaZero uses a markedly different
  approach that averages over the position evaluations within a
  subtree, rather than computing the minimax evaluation of that subtree.
  However, chess programs using traditional MCTS were much weaker than
  alpha-beta search programs, (4, 24); while alpha-beta programs based
  on neural networks have previously been unable to compete with
  faster, handcrafted evaluation functions. AlphaZero evaluates
  positions using non-linear function approximation based on a deep
  neural network, rather than the linear function approximation used in
  typical chess programs. This provides a much more powerful
  representation, but may also introduce spurious approximation errors.
  MCTS averages over these approximation errors, which therefore tend to
  cancel out when evaluating a large subtree. In contrast, alpha-beta
  search computes an explicit minimax, which propagates the biggest
  approximation errors to the root of the subtree. Using MCTS may allow
  AlphaZero to effectively combine its neural network representations
  with a powerful, domain-independent search.</p>
  </blockquote>
  <p>What do they mean by</p>
  <blockquote>
  <p>approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.</p>
  </blockquote>
  <p>What does it mean to <strong>average</strong> over position evaluations within a subtree?</p>
  <p>Also in the next part,</p>
  <blockquote>
  <p>AlphaZero evaluates positions using non-linear function approximation based on a deep
  neural network, rather than the linear function approximation used in typical chess programs.</p>
  </blockquote>
  <p>How is alphazero's evaluation non linear and how are the typical programs linear?</p>
  <p>Could someone dumb these down?</p>
  <p>My own guess behind MCTS over AB is because MCTS returns <strong>visit counts</strong> for each of the moves, and this data can be used to train the Policy Network in Alphazero. A minimax(AB) would return just that one best move, which could be used to train value network, but it cannot be used to train Policy network. So MCTS exists to train policy network in Alphazero. Is this a good or a bad guess?</p>
  <p>Also, please do not mark these as multiple questions, I believe all these are a part of the same question.</p>
  
Tags: <monte-carlo-tree-search><function-approximation><alphazero><alpha-beta-pruning>
Title: The reason behind using MCTS over Alpha Beta Pruning in Alphazero
UserDisplayName: Dimanjan
ThreadText: # The reason behind using MCTS over Alpha Beta Pruning in Alphazero
  
  (Asked by: username_0 on 2022-10-14)
  
  I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search.
  Some [analysis](https://news.ycombinator.com/item?id=19552286) claim that its because MCTS is a lot more humanlike. I disagree because I don't think AlphaZero was really concerned about becoming humanlike. The fact that it ended up playing like humans was just a coincidence but it was never the goal behind its design choice.
  
  In the AlphaZero paper,
  
  **MCTS and Alpha-Beta Search**
  
  > For at least four decades the strongest computer chess programs have
  > used alpha-beta search (18, 23). AlphaZero uses a markedly different
  > approach that averages over the position evaluations within a
  > subtree, rather than computing the minimax evaluation of that subtree.
  > However, chess programs using traditional MCTS were much weaker than
  > alpha-beta search programs, (4, 24); while alpha-beta programs based
  > on neural networks have previously been unable to compete with
  > faster, handcrafted evaluation functions. AlphaZero evaluates
  > positions using non-linear function approximation based on a deep
  > neural network, rather than the linear function approximation used in
  > typical chess programs. This provides a much more powerful
  > representation, but may also introduce spurious approximation errors.
  > MCTS averages over these approximation errors, which therefore tend to
  > cancel out when evaluating a large subtree. In contrast, alpha-beta
  > search computes an explicit minimax, which propagates the biggest
  > approximation errors to the root of the subtree. Using MCTS may allow
  > AlphaZero to effectively combine its neural network representations
  > with a powerful, domain-independent search.
  
  What do they mean by
  
  > approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.
  
  What does it mean to **average** over position evaluations within a subtree?
  
  Also in the next part,
  
  > AlphaZero evaluates positions using non-linear function approximation based on a deep
  > neural network, rather than the linear function approximation used in typical chess programs.
  
  How is alphazero's evaluation non linear and how are the typical programs linear?
  
  Could someone dumb these down?
  
  My own guess behind MCTS over AB is because MCTS returns **visit counts** for each of the moves, and this data can be used to train the Policy Network in Alphazero. A minimax(AB) would return just that one best move, which could be used to train value network, but it cannot be used to train Policy network. So MCTS exists to train policy network in Alphazero. Is this a good or a bad guess?
  
  Also, please do not mark these as multiple questions, I believe all these are a part of the same question.
  
  **Tags:** monte-carlo-tree-search, function-approximation, alphazero, alpha-beta-pruning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-17. Score: 1 | Accepted answer
  
  Let's begin with what *position evaluation* means, as it is the core of everything.
  
  > AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation used in typical chess programs.
  
  In beginner Chess we are probably taught that pawn is worth 1 point, 3 for knight and 9 for Queen. This is a quick way to evaluate how good/bad our situation is. Similarly in Bridge, we count Ace as 4 points, King as 3 and etc.. This is the *position evaluation* function, indicates how advantage/disadvantage a side is given a certain board situation.
  
  Obviously, the above-mentioned evaluation methods are very elementary and do not account for all the complexity. Say I can be a Queen and a Rook less but can surely checkmate (win) in 20 steps. Or I have a hand with only 10 points (A,K,Q,J) but with all 13 cards of Spades and thus easily make a 7S major slam.
  
  To accommodate these situations, human experts invent a lot of 'patches' to the evaluation: e.g. 2 pawns on same line gives a -1, a long suit adds +2 points etc.. All in all, these are *handcrafted features* create manually via careful engineering. 'Typical chess programs' e.g. Stockfish use them under the hood.
  
  Regardless, these position evaluations are *linear*: they are composed of a bunch of if-else statements, e.g. 'if I have a Pawn, adds 1 point', 'if I have no card in a suit, adds 4 points'. This is what the paper means by *linear function approximation*.
  
  In contrary, AlphaZero's position evaluation function does **not** rely on any hard-coded rules, but directly evaluate the board position. For example in Go, the function takes the position of all pieces on the board as input, feeds through a deep neural network (with a lot of layers e.g. convolution, residue blocks, max-pooling etc.) and returns a score of position advantage (e.g. 60% chance Black is leading).
  
  Notice that:
  
  1. The DNN is not static - it keeps updating during training and (hopefully) improves.
  2. The evaluation function is non-linear; this is where the **non-linear function approximation based on a deep neural network** comes from.
  
  > approach that averages over the position evaluations within a subtree, rather than computing the minimax evaluation of that subtree.
  
  The 'averages over' part is essentially how MCTS works - compute the positional evaluations of all subtrees of a branch, and (weighted) average the results as the score of the branch. While in Alpha-Beta, there is no 'average' - only the best is kept else pruned.
  
  > MCTS returns visit counts for each of the moves
  
  AFAIK, visit counts is used to approximate the confidence of position evaluation (similar to the role of sample size and confidence level in statistics). The actual scores combines both visit counts and evaluation scores of subtree.
  
  Finally,
  
  > why AlphaZero uses MCTS instead of Alpha Beta search?
  
  **[Updated]**
  
  There are at least 2 reasons as per this [reference papar](https://hal.inria.fr/hal-00695370v3/document):
  
  > (section 3.2) In some games of interest, e.g., in the game of Go, it has proven hard to encode or learn an evaluation function
  > of sufficient quality to achieve good performance in a minimax search.
  
  It claims that minimax is more sensitive to evaluation function vs. MCTS, and for complex games it makes a significant impact. The fundamental reason probably lays between the statistic used: max/min vs. mean.
  
  > (section 4.3) Classical game-tree-search algorithms, such as minimax search with α − β pruning, are notoriously difficult to parallelize effectively. Fortunately, MCTS lends itself much more
  > easily to parallelization.
  
  A practical consideration: MCTS is easier to parallelize.
  
  Finally, I recommend going over the AlphaGo paper first as it spells out more details (especially the value and policy network part), then AlphaGo Zero (which merges the value and policy network) before jumping into AlphaZero. Things should get a lot clearer this way as the authors skip some details in later papers.
  
  > **Comments:**
  > **username_0**: "My view is although Alpha-Beta (and Minimax) is theoretically optimal, it requires a predefined (handcrafted) position evaluation function." It would be possible to develop AB with the help of DNN as evaluation function. That would mean no such handcrafted position evaluation function.  
  > **username_1**: @Dimanjan yes I see no obvious obstacle along this line, but TBH I am no expert. Haven't find a solid, satisfying answer yet, my speculation is there is some practical consideration which fuse MCTS and DNN together better than Alpha-Beta + DNN.  
  > **username_1**: I look at the AlphaGo paper again. In "Prior Work" section it mentions *"minimax search with α − β pruning has achieved super-human performance in chess..., but it has not been effective in Go"*, and *"The strongest current Go programs are based on MCTS"*. Unfortunately no study on the reason why. Probably need to dig deeper in the citations.  
  > **username_1**: found a good reference, updated the answer.  
  > **username_0**: I have accepted your answer. I would also add the possibility that the exact reason may not be known. AlphaZero probably used it because it gave good results in their own experiments and others researchers previous experiments. But maybe a solid reasoning behind its effectiveness is not yet formulated. Its possible that they themselves do not know for sure.  
  > **username_1**: Plausible. Anyway, why not drop an inquiry (e.g. email) to the paper authors? They must have a lot of thoughts about it.  
  > **username_0**: hmm, I will consider doing that, Probably won't get a response though.  
  
  ---
  
  