Answers.Body: <p>Yes it's possible to to combine AlphaZero with Minimax methods (including alpha-beta pruning). AlphaZero itself is combination of  Monte Carlo Tree Search (MCTS) and Deep Network, where MCTS is used to get data to train network and network used for tree leafs evaluation (instead of rollout as in classical MCTS). It's possible to combine selection-expansion part of AlphaZero MCTS with Minimax the same way as it was done for classical MCTS - <a href="https://dke.maastrichtuniversity.nl/m.winands/documents/paper%2049.pdf" rel="nofollow noreferrer">"Monte-Carlo Tree Search and Minimax Hybrids", pdf</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-25T06:31:18.380Z
Answers.LastActivityDate: 2019-07-25T06:31:18.380Z
Answers.UserDisplayName: mirror2image
Answers.Body: <p>AlphaGo uses MCTS.  AlphaZero does not.</p>
  
  <p>Source: <a href="https://discovery.ucl.ac.uk/id/eprint/10045895/1/agz_unformatted_nature.pdf" rel="nofollow noreferrer">Mastering the Game of Go without Human Knowledge</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T22:56:10.160Z
Answers.Text: Welcome to SE:AI!  This answer would be stronger if you quoted the relevant passages from the paper.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-10T11:55:33.157Z
Answers.Text: Alphazero certainly uses MCTS.     https://arxiv.org/pdf/1712.01815      Page 3 line 4,5 . However, it uses a modified form of MCTS (no rollouts, etc)
Answers.UserDisplayName: Dimanjan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-19T18:47:37.637Z
Answers.LastActivityDate: 2020-05-22T22:55:43.980Z
Answers.LastEditDate: 2020-05-22T22:55:43.980Z
Answers.UserDisplayName: Eddie Rowe
Answers.Body: <blockquote>
    <p>So, from this I will conclude (correct me if I'm wrong) that AlphaZero
    evaluates the current position, but uses a very powerful heuristic.
    Stockfish on the other hand searches through lots of positions from
    the current one first, and then uses a less powerful heuristic when a
    certain depth is reached.</p>
  </blockquote>
  
  <p>This is wrong. Like Stockfish, AlphaZero as well "searches through lots of positions from the current one." You hint at this yourself when you say "possibly combined with monte carlo methods", but it seems you don't understand exactly what that means, so let me explain:</p>
  
  <p>Stockfish searches through the tree of future moves using an algorithm called Minimax (actually a variant called alpha beta pruning), whereas AlphaZero searches through future moves using a different algorithm called Monte Carlo Tree Search (MCTS). Minimax is well suited to quick evaluation functions, whereas MCTS explores fewer moves and thus can handle a more expensive evaluation function. Further, MCTS works not with exact values but with probabilities, and AlphaZero uses the Neural Net not just for the value of moves but to guide which moves to explore next (it functionally is actually 2 networks, a policy network and a value network).
  To be sure, that is somewhat of a simplification. It is not impossible to use a NeuralNet in conjunction with Minimax. Its just that in practice, due to the nature of the algorithm, its simply too expensive. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-25T06:24:04.607Z
Answers.Text: AlphaZero is not using NN in tree policy but only for evaluation of leafs: https://github.com/suragnair/alpha-zero-general/blob/master/MCTS.py
Answers.UserDisplayName: mirror2image
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-25T13:21:30.127Z
Answers.Text: @mirror2image that link is to some personal implementation. It may be I confused it will alpha go I'll check the paper
Answers.UserDisplayName: chessprogrammer
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-25T06:09:25.453Z
Answers.LastActivityDate: 2019-07-25T06:09:25.453Z
Answers.UserDisplayName: chessprogrammer
Body: <p>I will explain my question in relation to chess, but it should be relevant for other games as well:</p>
  
  <p>In short terms: Is it possible to combine the techniques used by AlphaZero with those used by, say, Stockfish? And if so, has it been attempted?</p>
  
  <p>I have only a brief knowledge about how AlphaZero works, but from what I've understood, it basically takes the board state as input to a neural net, possibly combined with monte carlo methods, and outputs a board evaluation or prefered move. To me, this really resembles the heuristic function used by traditional chess engines like stockfish.</p>
  
  <p>So, from this I will conclude (correct me if I'm wrong) that AlphaZero evaluates the current position, but uses a very powerful heuristic. Stockfish on the other hand searches through lots of positions from the current one first, and then uses a less powerful heuristic when a certain depth is reached.</p>
  
  <p>Is it therefore possible to combine these approaches by first using alpha-beta pruning, and then using AlphaZero as some kind of heuristic when the max depth is reached? To me it seems like this would be better than just evaluating the current position like (I think) AlphaZero does. Will it take too much time to evaluate? Or is it something I have misunderstood? If it's possible, has anyone attempted it? </p>
  
Tags: <deep-learning><chess><alphazero><alpha-beta-pruning>
Title: Combining deep reinforcement learning with alpha-beta pruning
UserDisplayName: Mr. Eivind
ThreadText: # Combining deep reinforcement learning with alpha-beta pruning
  
  (Asked by: username_0 on 2019-04-03)
  
  I will explain my question in relation to chess, but it should be relevant for other games as well:
  
  In short terms: Is it possible to combine the techniques used by AlphaZero with those used by, say, Stockfish? And if so, has it been attempted?
  
  I have only a brief knowledge about how AlphaZero works, but from what I've understood, it basically takes the board state as input to a neural net, possibly combined with monte carlo methods, and outputs a board evaluation or prefered move. To me, this really resembles the heuristic function used by traditional chess engines like stockfish.
  
  So, from this I will conclude (correct me if I'm wrong) that AlphaZero evaluates the current position, but uses a very powerful heuristic. Stockfish on the other hand searches through lots of positions from the current one first, and then uses a less powerful heuristic when a certain depth is reached.
  
  Is it therefore possible to combine these approaches by first using alpha-beta pruning, and then using AlphaZero as some kind of heuristic when the max depth is reached? To me it seems like this would be better than just evaluating the current position like (I think) AlphaZero does. Will it take too much time to evaluate? Or is it something I have misunderstood? If it's possible, has anyone attempted it?
  
  **Tags:** deep-learning, chess, alphazero, alpha-beta-pruning
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-07-25. Score: 3
  
  Yes it's possible to to combine AlphaZero with Minimax methods (including alpha-beta pruning). AlphaZero itself is combination of Monte Carlo Tree Search (MCTS) and Deep Network, where MCTS is used to get data to train network and network used for tree leafs evaluation (instead of rollout as in classical MCTS). It's possible to combine selection-expansion part of AlphaZero MCTS with Minimax the same way as it was done for classical MCTS - ["Monte-Carlo Tree Search and Minimax Hybrids", pdf](https://dke.maastrichtuniversity.nl/m.winands/documents/paper%2049.pdf).
  
  
  ---
  
  ### Answer by username_2 on 2020-05-19. Score: 0
  
  AlphaGo uses MCTS. AlphaZero does not.
  
  Source: [Mastering the Game of Go without Human Knowledge](https://discovery.ucl.ac.uk/id/eprint/10045895/1/agz_unformatted_nature.pdf)
  
  > **Comments:**
  > **username_3**: Welcome to SE:AI!  This answer would be stronger if you quoted the relevant passages from the paper.  
  > **username_4**: Alphazero certainly uses MCTS.     https://arxiv.org/pdf/1712.01815      Page 3 line 4,5 . However, it uses a modified form of MCTS (no rollouts, etc)  
  
  ---
  
  ### Answer by username_5 on 2019-07-25. Score: 0
  
  > So, from this I will conclude (correct me if I'm wrong) that AlphaZero
  > evaluates the current position, but uses a very powerful heuristic.
  > Stockfish on the other hand searches through lots of positions from
  > the current one first, and then uses a less powerful heuristic when a
  > certain depth is reached.
  
  This is wrong. Like Stockfish, AlphaZero as well "searches through lots of positions from the current one." You hint at this yourself when you say "possibly combined with monte carlo methods", but it seems you don't understand exactly what that means, so let me explain:
  
  Stockfish searches through the tree of future moves using an algorithm called Minimax (actually a variant called alpha beta pruning), whereas AlphaZero searches through future moves using a different algorithm called Monte Carlo Tree Search (MCTS). Minimax is well suited to quick evaluation functions, whereas MCTS explores fewer moves and thus can handle a more expensive evaluation function. Further, MCTS works not with exact values but with probabilities, and AlphaZero uses the Neural Net not just for the value of moves but to guide which moves to explore next (it functionally is actually 2 networks, a policy network and a value network).
  To be sure, that is somewhat of a simplification. It is not impossible to use a NeuralNet in conjunction with Minimax. Its just that in practice, due to the nature of the algorithm, its simply too expensive.
  
  > **Comments:**
  > **username_1**: AlphaZero is not using NN in tree policy but only for evaluation of leafs: https://github.com/suragnair/alpha-zero-general/blob/master/MCTS.py  
  > **username_5**: @username_1 that link is to some personal implementation. It may be I confused it will alpha go I'll check the paper  
  
  ---
  
  