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 mean * (1 - (standardDeviation * f)) * 100 where f is between 0 and 2. 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 a 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$
  • $\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$ – Neil Slater Nov 11 '18 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$ – GraxCode Nov 11 '18 at 20:13
  • $\begingroup$ Using a Monte Carlo Tree Search for calculating the next move in the card game Schnapsen isn't very efficient. The better idea would to take up domain-knowledge in the solver and play the game more like a human. In game AI it is possible to utilize permutation groups for that aim. It is a mathematical notation for ontology based knowledge modeling. Permutation groups were introduced for puzzle games like Rubik's cube and fifteen puzzle but can be used for Schnapsen as well. $\endgroup$ – Manuel Rodriguez Nov 11 '18 at 22:14
  • $\begingroup$ I don't see why it doesn't make sense to you. After the third trick every single move is calculated and before that random separation can be used. In my opinion it works perfectly. $\endgroup$ – GraxCode Nov 12 '18 at 6:07
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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.