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

• arxiv url: http://arxiv.org/abs/2506.21996v1
• Date: Fri, 27 Jun 2025 08:07:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-30 21:12:23.128542
• Title: AlphaBeta is not as good as you think: a new probabilistic model to better analyze deterministic game-solving algorithms
• Title（参考訳）: AlphaBetaは、あなたが思うほど良くない:決定論的ゲーム解決アルゴリズムをよりよく分析する新しい確率モデル
• Authors: Raphaël Boige, Amine Boumaza, Bruno Scherrer,
• Abstract要約: 固定レベル条件分布を用いてゲームツリーを漸進的に構築する新しい確率モデルを提案する。 我々のフレームワークは、古典的なゲーム解決アルゴリズムに新たな光を当て、厳密な証拠と分析ツールを提供する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 決定論的ゲーム解決アルゴリズムは、通常、葉の値が固定分布から独立してサンプリングされるランダムなゲームツリーの分布に対して、平均ケースの複雑さの点から解析される。 根値分布は漸近的に有限値木に対して1つの固定値に崩壊し、すべての合理的アルゴリズムが大域的最適性を達成する。 しかしながら、これらの発見はモデルの設計の成果物であり、長く批判された独立性の仮定は、構造的な複雑さのゲームを取り除き、アルゴリズムが意味のある課題に直面することのない自明なインスタンスを生成する。 この制限に対処するために、固定レベル条件分布を用いてゲームツリーを漸進的に構築する新しい確率モデルを導入する。 実世界のゲームにおいて重要な構造的特徴である祖先依存を強制することにより,解析的トラクタビリティを保ちながら,調整可能な難易度を有する問題を発生させる。 AlphaBetaやScoutなど、いくつかのアルゴリズムでは、このモデルの下での平均ケースの複雑さを特徴付ける再帰的な公式が導出されます。 これにより、モンテカルロシミュレーションがもはや実現不可能なディープゲームツリー上のアルゴリズムを厳格に比較することが可能になります。 漸近的に、全てのアルゴリズムは同一分岐因子(独立系モデルに類似した結果)に収束するように見えるが、深い有限木はスターク差を示す。 我々のフレームワークは古典的なゲーム解決アルゴリズムに新たな光を当て、厳密な証拠と分析ツールを提供し、より現実的で挑戦的で、難解なモデルの下でこれらの手法の理解を促進する。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (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) ゲームは最適制御の基本である。 本研究では,より単純な入れ子ゼロ階法 (NPG) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-08T11:47:31Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  本研究では, サンプルの一定割合が逆向きに破壊されるような外乱条件下で, ドブルシンの条件を満たすIsingモデルの学習問題について検討する。 我々の主な成果は、ほぼ最適誤差保証を伴うこの問題に対して、計算効率のよい最初の頑健な学習アルゴリズムを提供することである。
  論文  参考訳（メタデータ） (2021-02-03T18:00:57Z)
• Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
  最適な$O(n ln n/epsilon2)$サンプルから,$n$-variable tree-structured Isingモデルが全変動距離$epsilon$の範囲内で計算効率良く学習可能であることを示す。 我々の保証は、Chow-Liuアルゴリズムの既知の結果に従わない。
  論文  参考訳（メタデータ） (2020-10-28T10:17:48Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Robust Estimation of Tree Structured Ising Models [20.224160348675422]
  我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。 しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
  論文  参考訳（メタデータ） (2020-06-10T01:32:45Z)
• Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis [14.863027146736696]
  最悪のケース分析と比較して、平均ケース分析はアルゴリズムの典型的な振る舞いをよりよく表す。 これは、一階法で訓練された大規模問題のクラスには当てはまらないことを示す。 数値シミュレーションは、この普遍性はアルゴリズムと問題のより一般的なクラスに当てはまることを示唆している。
  論文  参考訳（メタデータ） (2020-06-08T00:47:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。