Answers.Body: <p>Famous example is <a href="https://www.nature.com/articles/nature24270.epdf?author_access_token=VJXbVjaSHxFoctQQ4p2k4tRgN0jAjWel9jnR3ZoTv0PVW4gB86EEpGqTRDtpIz-2rmo8-KG06gqVobU5NSCFeHILHcVFUeMsbvwS-lxjqQGg98faovwjxeTUgZAUMnRQ" rel="noreferrer">AlphaZero</a>. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards:</p>
  <blockquote>
  <p>The leaf <span class="math-container">$s'$</span> position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, <span class="math-container">$(P(s′ , \cdot),V(s ′ )) = f_\theta(s′ )$</span>. Each edge <span class="math-container">$(s, a)$</span> traversed in the simulation is updated to increment its visit count <span class="math-container">$N(s, a)$</span>, and to update its action value to the mean evaluation over these simulations, <span class="math-container">$Q(s,a) = \frac{1}{N(s,a)}\sum_{s,a\to s'}V(s')$</span>  , where <span class="math-container">$s, a\to s′$</span> indicates that a simulation eventually reached s′ after taking move a from position s.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-09T08:21:37.260Z
Answers.LastActivityDate: 2021-04-09T08:21:37.260Z
Answers.UserDisplayName: Kostya
Body: <p>I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS implemented in Java from <a href="https://www.baeldung.com/java-monte-carlo-tree-search" rel="nofollow noreferrer">here</a>, and I noticed that it takes a long time to actually reach a terminal node in the simulation phase.</p>
  <p>So, would it be possible to simulate games up until a specific depth?</p>
  <p>Instead of returning the winner of the game after running until the max depth, I could return an evaluation of the board (the board game is simple enough to write an evaluation function), which then back propagates.</p>
  <p>The issue I'm having is in handling the backpropagation. I'm not quite sure what to do here. Any help/resources/guidance is appreciated!</p>
  
Tags: <monte-carlo-tree-search><monte-carlo-methods><upper-confidence-bound>
Title: In MCTS, what to do if I do not want to simulate till the end of the game?
UserDisplayName: Sami
ThreadText: # In MCTS, what to do if I do not want to simulate till the end of the game?
  
  (Asked by: username_0 on 2021-04-05)
  
  I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS implemented in Java from [here](https://www.baeldung.com/java-monte-carlo-tree-search), and I noticed that it takes a long time to actually reach a terminal node in the simulation phase.
  
  So, would it be possible to simulate games up until a specific depth?
  
  Instead of returning the winner of the game after running until the max depth, I could return an evaluation of the board (the board game is simple enough to write an evaluation function), which then back propagates.
  
  The issue I'm having is in handling the backpropagation. I'm not quite sure what to do here. Any help/resources/guidance is appreciated!
  
  **Tags:** monte-carlo-tree-search, monte-carlo-methods, upper-confidence-bound
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-09. Score: 5 | Accepted answer
  
  Famous example is [AlphaZero](https://www.nature.com/articles/nature24270.epdf?author_access_token=VJXbVjaSHxFoctQQ4p2k4tRgN0jAjWel9jnR3ZoTv0PVW4gB86EEpGqTRDtpIz-2rmo8-KG06gqVobU5NSCFeHILHcVFUeMsbvwS-lxjqQGg98faovwjxeTUgZAUMnRQ). It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards:
  
  > The leaf $s'$ position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, $(P(s′ , \cdot),V(s ′ )) = f\_\theta(s′ )$. Each edge $(s, a)$ traversed in the simulation is updated to increment its visit count $N(s, a)$, and to update its action value to the mean evaluation over these simulations, $Q(s,a) = \frac{1}{N(s,a)}\sum\_{s,a\to s'}V(s')$ , where $s, a\to s′$ indicates that a simulation eventually reached s′ after taking move a from position s.
  
  
  ---
  
  