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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Adapting MCTS Algorithms for Stochastic Games - An Example on EinStein Würfelt Nicht!

  • Tzu-Yang Hsu,
  • Hung-Jui Chang,
  • Jun-Ping Chen,
  • Jr-Chang Chen,
  • Tsan-sheng Hsu

摘要

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.