Highly Volatile Game Tree Search in Chain Reaction
Dafyd Jenkins, Colin M. Frayn · 2006
Chain reaction is a simple strategic board game for two or more players. Its most interesting feature is that any static evaluation for board positions is highly volatile and can change dramatically as the result of one single move. This causes serious problems for conventional game-tree search methods. In this work, we explore an innovative approach using Monte Carlo analysis to determine advantageous moves through a stochastic exploration of possible game trees. We extend the concept of Monte Carlo analysis to include round-based progressive pruning. We also investigate the concept of volatility as a bias to the alpha-beta values within a hierarchical search tree model, in order to cope with the inherent unpredictability