Answers.Body: <p>The most "standard" implementation of MCTS probably involves storing copies of game states inside nodes. This works fine for deterministic games, but not for non-deterministic games due to the reasons you mentioned.</p>
  
  <p>In non-deterministic games, one of the easiest ways to make MCTS work is to take the perspective that every node in your tree should map to / represent / encode a <strong>trajectory</strong> or <strong>sequence of actions</strong>, rather than a <strong>state</strong>. This means that every node collects statistics (num wins / num visits etc.) for the trajectory of actions it represents, rather than for the state it represents.</p>
  
  <p>This perspective can be implemented very easily by simply not storing any game states in nodes at all. Instead, whenever you traverse the tree (in the Selection phase of MCTS), you should simply re-simulate all the actions along that path through the tree, starting from the root state again. This way, different visits through a single node can result in different game states being "observed" in that node due to nondeterministic game state transitions. In the limit (after an infinite amount of time), every node will estimate the <strong>expected value of the trajectory of actions leading to that node</strong>, rather than the game-theoretic value of a single, deterministic resulting game state. This whole idea is sometimes referred to as "Open-Loop MCTS", for example in <a href="http://www.diego-perez.net/papers/OpenLoopGVG.pdf" rel="noreferrer">this paper</a>.</p>
  
  <hr>
  
  <p>What I described above is a simple way to get better performance from MCTS in games involving nondeterministic state transitions as you described (such as random amounts of damage being dealt), but there are many much more complicated ideas out there too. I suspect more complex approaches will especially be necessary to deal with more "drastic" forms of nondeterminism (resulting from random card draws, or resulting from randomization-based approaches for dealing with imperfect information such as not knowing which cards your opponent has).</p>
  
  <p>There was a <a href="https://dockhorn.antares.uberspace.de/wordpress/" rel="noreferrer">Hearthstone AI competition</a> relatively recently, and some useful ideas may be found, for example, on this page of <a href="https://dockhorn.antares.uberspace.de/wordpress/additional-material/" rel="noreferrer">work related to that competition</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-02T22:23:43.573Z
Answers.Text: Hi @Dennis, where can I find pseudo code of open-loop approach? I've found some examples on github but, don't think they are correct.
Answers.UserDisplayName: Kadir Ercetin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-03T09:13:58.947Z
Answers.Text: @KadirCan Hmm I'm not sure about any really simple examples. I've used OpenLoop MCTS in both https://github.com/DennisSoemers/MaastCTS2 and https://github.com/Ludeme/Ludii/tree/master/AI/src/search/mcts but in both cases they're "advanced" implementations, also with lots of other optional for bells and whistles, and also including non-open-loop implementations at the same time for deterministic games
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-11T20:52:47.673Z
Answers.LastActivityDate: 2018-12-11T20:52:47.673Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I want to learn a lot about the AI of CCG, such as Hearthstone. And now I have known one of the main algorithms that used in this kind of games, MCTS. It analyses the most promising moves, and expands the search tree based on random sampling of the search space. But there are too many random events in this game that can cause different results to one battle. For example, a card can randomly deal X damage to a hero or other follower, and X is a random number from 0 to 30. The number of X is important for the next decision, but there will be a low accuracy by only using MCTS.</p>
  
  <p>So what does the AI do to deal with these random events?</p>
  
Tags: <machine-learning><game-ai><monte-carlo-tree-search>
Title: How does Hearthstone AI deal with random events
UserDisplayName: zen
ThreadText: # How does Hearthstone AI deal with random events
  
  (Asked by: username_0 on 2018-12-11)
  
  I want to learn a lot about the AI of CCG, such as Hearthstone. And now I have known one of the main algorithms that used in this kind of games, MCTS. It analyses the most promising moves, and expands the search tree based on random sampling of the search space. But there are too many random events in this game that can cause different results to one battle. For example, a card can randomly deal X damage to a hero or other follower, and X is a random number from 0 to 30. The number of X is important for the next decision, but there will be a low accuracy by only using MCTS.
  
  So what does the AI do to deal with these random events?
  
  **Tags:** machine-learning, game-ai, monte-carlo-tree-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-12-11. Score: 5 | Accepted answer
  
  The most "standard" implementation of MCTS probably involves storing copies of game states inside nodes. This works fine for deterministic games, but not for non-deterministic games due to the reasons you mentioned.
  
  In non-deterministic games, one of the easiest ways to make MCTS work is to take the perspective that every node in your tree should map to / represent / encode a **trajectory** or **sequence of actions**, rather than a **state**. This means that every node collects statistics (num wins / num visits etc.) for the trajectory of actions it represents, rather than for the state it represents.
  
  This perspective can be implemented very easily by simply not storing any game states in nodes at all. Instead, whenever you traverse the tree (in the Selection phase of MCTS), you should simply re-simulate all the actions along that path through the tree, starting from the root state again. This way, different visits through a single node can result in different game states being "observed" in that node due to nondeterministic game state transitions. In the limit (after an infinite amount of time), every node will estimate the **expected value of the trajectory of actions leading to that node**, rather than the game-theoretic value of a single, deterministic resulting game state. This whole idea is sometimes referred to as "Open-Loop MCTS", for example in [this paper](http://www.diego-perez.net/papers/OpenLoopGVG.pdf).
  
  ---
  
  What I described above is a simple way to get better performance from MCTS in games involving nondeterministic state transitions as you described (such as random amounts of damage being dealt), but there are many much more complicated ideas out there too. I suspect more complex approaches will especially be necessary to deal with more "drastic" forms of nondeterminism (resulting from random card draws, or resulting from randomization-based approaches for dealing with imperfect information such as not knowing which cards your opponent has).
  
  There was a [Hearthstone AI competition](https://dockhorn.antares.uberspace.de/wordpress/) relatively recently, and some useful ideas may be found, for example, on this page of [work related to that competition](https://dockhorn.antares.uberspace.de/wordpress/additional-material/).
  
  > **Comments:**
  > **username_2**: Hi @Dennis, where can I find pseudo code of open-loop approach? I've found some examples on github but, don't think they are correct.  
  > **username_1**: @KadirCan Hmm I'm not sure about any really simple examples. I've used OpenLoop MCTS in both https://github.com/DennisSoemers/MaastCTS2 and https://github.com/Ludeme/Ludii/tree/master/AI/src/search/mcts but in both cases they're "advanced" implementations, also with lots of other optional for bells and whistles, and also including non-open-loop implementations at the same time for deterministic games  
  
  ---
  
  