Adapting MCTS Algorithms for Stochastic Games - An Example on EinStein Würfelt Nicht!
摘要
EinStein würfelt nicht! (abbr. EWN) is a stochastic game of perfect information, where the roll of a die in each turn introduces uncertainty and complicates strategic planning. Traditional MCTS based game agent evenly simulates all outcomes of a chance node, which is not good for EWN since an outcome may be considered more often than others during the game when pieces are captured. To address this, we propose enhancements focused on the selection and simulation stages. During selection, when a chance node corresponding to a captured piece is encountered, we combine the moves of adjacent alive ones into one virtual node. We also propose a method to revise and generalize the UCB formula for move selection based on the characteristics of stochastic games and prove theorems that this gives the best possible convergence rate. The experimental results showed that our modified algorithm converges much faster than the original.