Body: <p>I am working on implementing MCTS for a scheduling problem where MCTS is formulated each time there are multiple jobs that need to be scheduled. When a job is executed, the resulting state of the system is random. The challenge I'm having is that the implementation I'm currently using relies on the ability to determine if a node is fully expanded. However, there are so many children of the root node that it's not feasible to expect all of them will ever be visited. Is there a suggested method of conducting MCTS in cases where nodes will not likely ever be fully expanded?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-20T23:22:18.230Z
Comments.Text: Welcome to AI.SE @hoffee. I think you're asking how to perform MCTS when actions have non-deterministic outcomes. Is that the essence of your question, or are you trying to ask something else?
Comments.UserDisplayName: John Doucette
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-21T14:01:33.690Z
Comments.Text: Yes, that is what I'm asking.
Comments.UserDisplayName: hoffee
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T09:00:45.283Z
Comments.Text: There is a great paper "A Survey of Monte Carlo Tree Search Methods". Read the chapter on stochastic MCTS. Short: introduce "random nodes" - fake player which do random actions.
Comments.UserDisplayName: mirror2image
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T16:25:09.187Z
Comments.Text: I am aware of that paper but I will revisit that chapter, thanks for the suggestion.
Comments.UserDisplayName: hoffee
Tags: <monte-carlo-tree-search>
Title: Formulating MCTS with random outcomes of actions?
UserDisplayName: hoffee
ThreadText: # Formulating MCTS with random outcomes of actions?
  
  (Asked by: username_0 on 2019-11-20)
  
  I am working on implementing MCTS for a scheduling problem where MCTS is formulated each time there are multiple jobs that need to be scheduled. When a job is executed, the resulting state of the system is random. The challenge I'm having is that the implementation I'm currently using relies on the ability to determine if a node is fully expanded. However, there are so many children of the root node that it's not feasible to expect all of them will ever be visited. Is there a suggested method of conducting MCTS in cases where nodes will not likely ever be fully expanded?
  
  **Tags:** monte-carlo-tree-search
  > **Comments:**
  > **username_1**: Welcome to AI.SE @hoffee. I think you're asking how to perform MCTS when actions have non-deterministic outcomes. Is that the essence of your question, or are you trying to ask something else?  
  > **username_0**: Yes, that is what I'm asking.  
  > **username_2**: There is a great paper "A Survey of Monte Carlo Tree Search Methods". Read the chapter on stochastic MCTS. Short: introduce "random nodes" - fake player which do random actions.  
  > **username_0**: I am aware of that paper but I will revisit that chapter, thanks for the suggestion.  
  
  ---
  
  ## 0 answers
  
  