2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Nov 11, 2018 at 18:19
  • $\begingroup$ 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) $\endgroup$
    – Aura Lee
    Nov 11, 2018 at 20:13

1 Answer 1

2
$\begingroup$

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.


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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .