Optimizing $αμ$
This work addresses computational bottlenecks for researchers and practitioners in game AI, though it is incremental as it builds on existing $αμ$ methods.
The paper tackled the problem of inefficiencies in the $αμ$ search algorithm for imperfect information games by introducing multiple optimizations, including Pareto front techniques and parallelization, which resulted in faster search speeds for Bridge and other similar games.
$αμ$ is a search algorithm which repairs two defaults of Perfect Information Monte Carlo search: strategy fusion and non locality. In this paper we optimize $αμ$ for the game of Bridge, avoiding useless computations. The proposed optimizations are general and apply to other imperfect information turn-based games. We define multiple optimizations involving Pareto fronts, and show that these optimizations speed up the search. Some of these optimizations are cuts that stop the search at a node, while others keep track of which possible worlds have become redundant, avoiding unnecessary, costly evaluations. We also measure the benefits of parallelizing the double dummy searches at the leaves of the $αμ$ search tree.