論文の概要: Massively Parallel Proof-Number Search for Impartial Games and Beyond

• arxiv url: http://arxiv.org/abs/2511.10339v1
• Date: Fri, 14 Nov 2025 01:45:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.820942
• Title: Massively Parallel Proof-Number Search for Impartial Games and Beyond
• Title（参考訳）: 不公平なゲームのための大規模並列証明探索
• Authors: Tomáš Čížek, Martin Balko, Martin Schmid,
• Abstract要約: In this present the first massively parallel version of Proof-Number Search which is presented the first of Proof-Number Search。 我々のソルバは1024コアで動作する場合の332.9$times$ speedupを大幅に改善した。 ゲームツリーサイズは指数関数的に増加するものの,42の新たな位置でSprouts Conjectureを検証し,既知の結果の2倍近い結果を得た。
• 参考スコア（独自算出の注目度）: 1.9906945320988172
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Proof-Number Search is a best-first search algorithm with many successful applications, especially in game solving. As large-scale computing clusters become increasingly accessible, parallelization is a natural way to accelerate computation. However, existing parallel versions of Proof-Number Search are known to scale poorly on many CPU cores. Using two parallelized levels and shared information among workers, we present the first massively parallel version of Proof-Number Search that scales efficiently even on a large number of CPUs. We apply our solver, enhanced with Grundy numbers for reducing game trees, to the Sprouts game, a case study motivated by the long-standing Sprouts Conjecture. Our solver achieves a significantly improved 332.9$\times$ speedup when run on 1024 cores, enabling it to outperform the state-of-the-art Sprouts solver GLOP by four orders of magnitude in runtime and to generate proofs 1,000$\times$ more complex. Despite exponential growth in game tree size, our solver verified the Sprouts Conjecture for 42 new positions, nearly doubling the number of known outcomes.
• Abstract（参考訳）: Proof-Number Searchは最も優れた検索アルゴリズムであり、多くのアプリケーション、特にゲームの解法において成功した。 大規模コンピューティングクラスタがますますアクセスしやすくなってきたため、並列化は計算を高速化する自然な方法である。 しかし、Proof-Number Searchの既存の並列バージョンは、多くのCPUコアでのスケーリングが不十分であることが知られている。 作業者間での2つの並列化レベルと共有情報を用いて、多数のCPU上でも効率的にスケールするProof-Number Searchの最初の大規模並列バージョンを提示する。 Sproutsゲームにおいて,Grundy数で拡張された解法を,長年のSprouts Conjectureに動機づけられたケーススタディに適用する。 提案手法は,1024コアで動作する場合の332.9$\times$の高速化を実現し,最先端のSproutsソルバGLOPを4桁の精度で実行し,1000$\times$より複雑な証明を生成する。 ゲームツリーサイズは指数関数的に増加したが,Sprouts Conjectureを42の新たな位置で検証し,既知の結果の2倍に近づいた。

関連論文リスト

• DeepPrune: Parallel Scaling without Inter-trace Redundancy [53.62015294143274]
  並列推論トレースの80%以上は、実質的な無駄な計算を代表して、同じ最終回答をもたらす。 動的プルーニングによる効率的な並列スケーリングを実現する新しいフレームワークであるDeepPruneを提案する。 我々の研究は並列推論のための新しい標準を確立し、高性能推論をより効率的にする。
  論文  参考訳（メタデータ） (2025-10-09T17:24:54Z)
• Parallel Spooky Pebbling Makes Regev Factoring More Practical [1.733255162390776]
  古典コンピューティングの抽象化である"Pebble Games"は、本質的にシーケンシャルなタスクに量子回路の設計に使われている。 本稿では,これらの手法をRegevの分解アルゴリズムに適用することにより,演算のコストを大幅に削減できることを示す。 我々は、整数分解以外の量子暗号解析にも応用できると信じている。
  論文  参考訳（メタデータ） (2025-10-09T16:45:58Z)
• A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS [13.186524200050957]
  本稿では,深度第一探索におけるGPU計算手法を提案する。 これは、Iterative Deepening A* (IDA*)アルゴリズムの拡張であるemphsynchronous IDA*のようなアルゴリズムを作成するために使用される。 本研究では, 3x3 の Rubik Cube と 4x4 のスライディングタイルパズル (STP) に対するアプローチを評価し,GPU 操作を DFS で効率的にバッチ化可能であることを示す。
  論文  参考訳（メタデータ） (2025-07-16T05:07:33Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。 また,大域的相関平衡を近似計算するアルゴリズムも提案する。 ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-22T09:12:05Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。 我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。 最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-04T10:33:59Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles [0.8057006406834467]
  本稿では,グラフィック処理ユニット上での大規模並列計算に適したツリーサップアルゴリズムを提案する。 我々は,最先端のマルチコアCPU実装を用いて,SHAP値の最大19倍,SHAP値の最大340倍の高速化を実現する。
  論文  参考訳（メタデータ） (2020-10-27T00:55:07Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)

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

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