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?

  • $\begingroup$ 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? $\endgroup$ – John Doucette Nov 20 '19 at 23:22
  • $\begingroup$ Yes, that is what I'm asking. $\endgroup$ – hoffee Nov 21 '19 at 14:01
  • 1
    $\begingroup$ 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. $\endgroup$ – mirror2image Nov 22 '19 at 9:00
  • $\begingroup$ I am aware of that paper but I will revisit that chapter, thanks for the suggestion. $\endgroup$ – hoffee Nov 22 '19 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.