a simple random games model for a better analysis of deterministic game-solving algorithms

View the PDF of the article AlphaBeta Isn’t as Good as You Think: A Simple Random Games Model for Better Analysis of Deterministic Game Solving Algorithms, by Rapha\”el Boige (LORIA) and two co-authors

View PDF

a summary:Deterministic game solving algorithms are traditionally analyzed in terms of average state complexity against a distribution of random game trees, where leaf values ​​are sampled independently from a fixed distribution. This simplified model allows a neat mathematical analysis, and reveals two key properties: root value distributions collapse asymptotically to a single constant value for finite value trees, and all plausible algorithms achieve global optimality. However, these results are a product of the model’s design: the long-criticized independence assumption strips games of structural complexity, resulting in trivial cases where no algorithm faces meaningful challenges. To address this limitation, we introduce a simple probabilistic model that incrementally builds game trees using a fixed-level conditional distribution. By enforcing ancestor dependencies, an important structural feature of real-world games, our framework generates problems of adjustable difficulty while retaining some form of analytical power. For several algorithms, including AlphaBeta and Scout, we derive frequentist formulas that characterize the complexities of the average case under this model. This allows us to accurately compare algorithms on deep game trees, where Monte Carlo simulation is no longer possible. While all algorithms appear to be convergent and converge to an identical bifurcation factor (a result similar to that of independence-based models), deep bounded trees reveal stark differences: AlphaBeta includes a much larger constant multiplicative factor compared to algorithms like Scout, which leads to a significant practical slowdown. Our framework sheds new light on classic game-solving algorithms, providing rigorous evidence and analytical tools to advance understanding of these approaches within a richer, more challenging, and easy-to-follow paradigm.