AlphaBeta is not as good as you think: a new probabilistic model to better analyze deterministic game-solving algorithms

• URL: http://arxiv.org/abs/2506.21996v1
• Date: Fri, 27 Jun 2025 08:07:17 GMT
• Title: AlphaBeta is not as good as you think: a new probabilistic model to better analyze deterministic game-solving algorithms
• Authors: Raphaël Boige, Amine Boumaza, Bruno Scherrer,
• Abstract summary: We introduce a new probabilistic model that incrementally constructs game-trees using a fixed level-wise conditional distribution.<n>Our framework sheds new light on classical game-solving algorithms, offering rigorous evidence and analytical tools.
• Score: 2.430562648940846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Deterministic game-solving algorithms are conventionally analyzed in the light of their average-case complexity against a distribution of random game-trees, where leaf values are independently sampled from a fixed distribution. This simplified model enables uncluttered mathematical analysis, revealing two key properties: root value distributions asymptotically collapse to a single fixed value for finite-valued trees, and all reasonable algorithms achieve global optimality. However, these findings are artifacts of the model's design-its long criticized independence assumption strips games of structural complexity, producing trivial instances where no algorithm faces meaningful challenges. To address this limitation, we introduce a new probabilistic model that incrementally constructs game-trees using a fixed level-wise conditional distribution. By enforcing ancestor dependency, a critical structural feature of real-world games, our framework generates problems with adjustable difficulty while retaining some form of analytical tractability. For several algorithms, including AlphaBeta and Scout, we derive recursive formulas characterizing their average-case complexities under this model. These allow us to rigorously compare algorithms on deep game-trees, where Monte-Carlo simulations are no longer feasible. While asymptotically, all algorithms seem to converge to identical branching factor (a result analogous to those of independence-based models), deep finite trees reveal stark differences: AlphaBeta incurs a significantly larger constant multiplicative factor compared to algorithms like Scout, leading to a substantial practical slowdown. Our framework sheds new light on classical game-solving algorithms, offering rigorous evidence and analytical tools to advance the understanding of these methods under a more realistic, challenging, and yet tractable model.

Related papers

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence [19.779044926914704]
  Zero-sum Linear Quadratic (LQ) games are fundamental in optimal control. In this work, we propose a simpler nested Zeroth-Order (NPG) algorithm.
  arXiv  Detail & Related papers  (2023-09-08T11:47:31Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  We develop a flexible approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite) The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, exponential/multiplicative weights for learning in finite games, optimistic and bandit variants of the above, etc.
  arXiv  Detail & Related papers  (2022-06-08T14:30:38Z)
• Certifiable Robustness for Nearest Neighbor Classifiers [6.487663563916903]
  We study the complexity of certifying for a simple but widely deployed classification algorithm, $k$-Nearest Neighbors ($k$-NN) Our main focus is on inconsistent datasets when constraints are functional dependencies (FDs) We exhibit a similar counting version of the problem, where the goal is to count the number of possible worlds that predict a certain label.
  arXiv  Detail & Related papers  (2022-01-13T02:55:10Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. Our main result is to provide the first computationally efficient robust learning algorithm for this problem with near-optimal error guarantees.
  arXiv  Detail & Related papers  (2021-02-03T18:00:57Z)
• Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
  We show that $n$-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance $epsilon$ from an optimal $O(n ln n/epsilon2)$ samples. Our guarantees do not follow from known results for the Chow-Liu algorithm.
  arXiv  Detail & Related papers  (2020-10-28T10:17:48Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors.
  arXiv  Detail & Related papers  (2020-06-10T01:32:45Z)
• Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis [14.863027146736696]
  Compared to worst-case analysis, average-case analysis is more representative of the typical behavior of an algorithm. We show that this is not the case for a class of large-scale problems trained with first-order methods. numerical simulations suggest this universality property holds for a more general class of algorithms and problems.
  arXiv  Detail & Related papers  (2020-06-08T00:47:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.