Answers.Body: <p>It can make sense to incorporate the standard deviation of Monte-Carlo-based evaluations in some ways to reduce risk, but I don't think the way of using it that you described would work well.</p>
  
  <p>For MCTS evaluations, if you're taking a zero-sum-style approach (which you are if you are trying to estimate win/loss probabilities), it is very important that your estimates are "symmetric" with respect to the players. If you evaluate the probability of winning for player A to be <span class="math-container">$p$</span>, it is important that your algorithm simultaneously evaluates the probability of the other player B to be equal to <span class="math-container">$1 - p$</span> (or, if you prefer winning chance, if the chance of winning for one player is <span class="math-container">$p\%$</span>, it should be <span class="math-container">$100\% - p\%$</span> for the other player). This appears to be violated by your idea, which subtracts standard deviation regardless of player "perspective".</p>
  
  <p>A better place to take standard deviation (or, similarly, variance) into account would be, for example, the Selection phase of MCTS. The most common strategy for the Selection phase is using the "UCB1 equation". You can modify that to include the variance in your observations, for example using the "UCB1-Tuned" strategy as described in the beginning of Section 4 of <a href="https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf" rel="nofollow noreferrer">Finite-time Analysis of the Multiarmed Bandit Problem</a>.</p>
  
  <hr>
  
  <p>In my answer above, I assume that you were talking about evaluations "inside" the algorithm, while it is still running. If you were rather thinking of the final move selection for the "real" game after having run the algorithm for a while, the most common approach there is to simply play the move with the maximum number of <strong>visits</strong> (also referred to as <strong>robust child</strong>), rather than playing the move with the maximum score. It should not be necessary to include standard deviation at this stage anymore.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-12T17:00:06.697Z
Answers.LastActivityDate: 2018-11-12T17:50:20.777Z
Answers.LastEditDate: 2018-11-12T17:50:20.777Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>My AI (for the card game schnapsen) currently calculates every possible way the game could end and then evaluates the percentage of winning for every playable card / move. The calculation is done recursively using a tree. If a game could move on in three different ways the percentage of winning on this node would be</p>
  <p><span class="math-container">$$\mu * (1 - (\sigma * f)) * 100,$$</span></p>
  <p>where <span class="math-container">$f$</span> is between 0 and 2, <span class="math-container">$\mu$</span> is the mean and <span class="math-container">$\sigma$</span> the standard deviation. When the game can't move on and the AI wins the percentage is 100, when lost 0. I'm including the standard deviation in this formula to prevent the AI from risking too much. In other words: I'm using an MCTS that uses percentages.</p>
  <p>Is there a better formula or way of calculating the next move to maximize the chance of winning? Does including the standard deviation make sense?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-11T18:19:31.367Z
Comments.Text: What is the standard deviation taken *of* - the three different plays? So you have calculated means and stds for each branch point in the tree? Presumably these are calculated with even weights on each choice?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-11-11T20:13:52.663Z
Comments.Text: The standard deviation and mean is calculated with all different plays. If one game state has 5 different ways to continue it calculates the percentage of winning (each continuation calculated again) for each one and then uses the formula and returns the value for the previous tree node to calculate. A win returns 100 percent, a loss returns 0. (My AI returns a higher percentage for a 3 point loss and a lower one for a 1 point win but that is not that important)
Comments.UserDisplayName: Aura Lee
Tags: <game-ai><monte-carlo-tree-search>
Title: Is there a better way of calculating the chance of winning than $\mu * (1 - (\sigma * f)) * 100$ for the card game schnapsen?
UserDisplayName: Aura Lee
ThreadText: # Is there a better way of calculating the chance of winning than $\mu * (1 - (\sigma * f)) * 100$ for the card game schnapsen?
  
  (Asked by: username_0 on 2018-11-11)
  
  My AI (for the card game schnapsen) currently calculates every possible way the game could end and then evaluates the percentage of winning for every playable card / move. The calculation is done recursively using a tree. If a game could move on in three different ways the percentage of winning on this node would be
  
  $$\mu \* (1 - (\sigma \* f)) \* 100,$$
  
  where $f$ is between 0 and 2, $\mu$ is the mean and $\sigma$ the standard deviation. When the game can't move on and the AI wins the percentage is 100, when lost 0. I'm including the standard deviation in this formula to prevent the AI from risking too much. In other words: I'm using an MCTS that uses percentages.
  
  Is there a better formula or way of calculating the next move to maximize the chance of winning? Does including the standard deviation make sense?
  
  **Tags:** game-ai, monte-carlo-tree-search
  
  > **Comments:**
  > **username_1**: What is the standard deviation taken *of* - the three different plays? So you have calculated means and stds for each branch point in the tree? Presumably these are calculated with even weights on each choice?  
  > **username_0**: The standard deviation and mean is calculated with all different plays. If one game state has 5 different ways to continue it calculates the percentage of winning (each continuation calculated again) for each one and then uses the formula and returns the value for the previous tree node to calculate. A win returns 100 percent, a loss returns 0. (My AI returns a higher percentage for a 3 point loss and a lower one for a 1 point win but that is not that important)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-11-12. Score: 2 | Accepted answer
  
  It can make sense to incorporate the standard deviation of Monte-Carlo-based evaluations in some ways to reduce risk, but I don't think the way of using it that you described would work well.
  
  For MCTS evaluations, if you're taking a zero-sum-style approach (which you are if you are trying to estimate win/loss probabilities), it is very important that your estimates are "symmetric" with respect to the players. If you evaluate the probability of winning for player A to be $p$, it is important that your algorithm simultaneously evaluates the probability of the other player B to be equal to $1 - p$ (or, if you prefer winning chance, if the chance of winning for one player is $p\%$, it should be $100\% - p\%$ for the other player). This appears to be violated by your idea, which subtracts standard deviation regardless of player "perspective".
  
  A better place to take standard deviation (or, similarly, variance) into account would be, for example, the Selection phase of MCTS. The most common strategy for the Selection phase is using the "UCB1 equation". You can modify that to include the variance in your observations, for example using the "UCB1-Tuned" strategy as described in the beginning of Section 4 of [Finite-time Analysis of the Multiarmed Bandit Problem](https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf).
  
  ---
  
  In my answer above, I assume that you were talking about evaluations "inside" the algorithm, while it is still running. If you were rather thinking of the final move selection for the "real" game after having run the algorithm for a while, the most common approach there is to simply play the move with the maximum number of **visits** (also referred to as **robust child**), rather than playing the move with the maximum score. It should not be necessary to include standard deviation at this stage anymore.
  
  
  ---
  
  