Body: <p>The basic Monte-Carlo Tree Search algorithm uses the tree policy:</p>
  <pre><code>while v is nonterminal:
    if v is not fully expanded:
      expand v
    else:
      v = v.best_child
  </code></pre>
  <p>By always expanding a node as long as it is expandable a lot of time is consumed to explore the direct next move. When there are a large number of possible moves it can be time (and space) consuming to create nodes for all move candidates and if many of them may have similar outcome it would be preferable to descend in existing subtrees even when the node is not fully expanded yet.</p>
  <p>The closest related method that I found is first-play urgency, but as far as I see it also creates the nodes for the actions and also only modifies the algorithm which children are selected to use more exploitation than exploration, but doesn't reduce the amount of move candidates that are created when inserting a node.</p>
  <p>I thought about removing the check if the node is expandable and treating it like its children, but I think the UCT of a parent node doesn't get larger than the UCT of its best child because the values of the children are propagated to the parent and the visit count of the parent is always larger than the visit counts of the children, so the parent node would not be selected again later.</p>
  <p>Should I try to find a modification for the UCT or are there other methods to allow for exploring subtrees of not fully expanded nodes while still allowing to further expand the parent node from time to time?</p>
  <p>Another alternative would be to stochastically only generate a subset of all possible moves at the risk of missing out on a good move, so I would prefer to find a modification of UCT or the descend / expansion algorithms to revisit inner nodes that are still expandable.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-28T14:01:25.163Z
Comments.Text: When you need to expand a node, you just need to add all its children (with 0 visits). Then you select one of the children for rollout.
  Is this already a problem (to add all the children as nodes)?
Comments.UserDisplayName: Oren
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-30T09:27:51.867Z
Comments.Text: You can't do it with the standard UCT formula because $n_i$ is in the denominator. I also think it is there for a reason and the standard approach basically says that evaluating if an unexplored node leads to a good solution has infinite priority. The equivalent to what you're thinking of would probably be not adding a node and then you again need to make sure that the algorithm doesn't always descend in the tree to add the missing node.
Comments.UserDisplayName: allo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-30T14:36:51.617Z
Comments.Text: I would add all children (with 0 visits) altogether. Then before testing for UCT I would check if any has 0 visits and choose from those. None with 0 visits? Then fall back to UCT.
Comments.UserDisplayName: Oren
Tags: <monte-carlo-tree-search>
Title: What method to use for Monte-Carlo Tree Search to prefer depth search
UserDisplayName: allo
ThreadText: # What method to use for Monte-Carlo Tree Search to prefer depth search
  
  (Asked by: username_0 on 2023-03-03)
  
  The basic Monte-Carlo Tree Search algorithm uses the tree policy:
  while v is nonterminal:
    if v is not fully expanded:
      expand v
    else:
      v = v.best_child
  
  By always expanding a node as long as it is expandable a lot of time is consumed to explore the direct next move. When there are a large number of possible moves it can be time (and space) consuming to create nodes for all move candidates and if many of them may have similar outcome it would be preferable to descend in existing subtrees even when the node is not fully expanded yet.
  The closest related method that I found is first-play urgency, but as far as I see it also creates the nodes for the actions and also only modifies the algorithm which children are selected to use more exploitation than exploration, but doesn't reduce the amount of move candidates that are created when inserting a node.
  I thought about removing the check if the node is expandable and treating it like its children, but I think the UCT of a parent node doesn't get larger than the UCT of its best child because the values of the children are propagated to the parent and the visit count of the parent is always larger than the visit counts of the children, so the parent node would not be selected again later.
  Should I try to find a modification for the UCT or are there other methods to allow for exploring subtrees of not fully expanded nodes while still allowing to further expand the parent node from time to time?
  Another alternative would be to stochastically only generate a subset of all possible moves at the risk of missing out on a good move, so I would prefer to find a modification of UCT or the descend / expansion algorithms to revisit inner nodes that are still expandable.
  
  **Tags:** monte-carlo-tree-search
  > **Comments:**
  > **username_1**: When you need to expand a node, you just need to add all its children (with 0 visits). Then you select one of the children for rollout. Is this already a problem (to add all the children as nodes)?  
  > **username_0**: You can't do it with the standard UCT formula because $n_i$ is in the denominator. I also think it is there for a reason and the standard approach basically says that evaluating if an unexplored node leads to a good solution has infinite priority. The equivalent to what you're thinking of would probably be not adding a node and then you again need to make sure that the algorithm doesn't always descend in the tree to add the missing node.  
  > **username_1**: I would add all children (with 0 visits) altogether. Then before testing for UCT I would check if any has 0 visits and choose from those. None with 0 visits? Then fall back to UCT.  
  
  ---
  
  ## 0 answers
  
  