論文の概要: Expected Work Search: Combining Win Rate and Proof Size Estimation

• arxiv url: http://arxiv.org/abs/2405.05594v1
• Date: Thu, 9 May 2024 07:33:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-10 14:02:33.622910
• Title: Expected Work Search: Combining Win Rate and Proof Size Estimation
• Title（参考訳）: 期待される仕事の探索: ウィンレートと証明サイズ推定を組み合わせる
• Authors: Owen Randall, Martin Müller, Ting Han Wei, Ryan Hayward,
• Abstract要約: 期待されるワークサーチ(EWS)は,新しい問題解決アルゴリズムである。 EWSはモンテカルロ木探索で用いられるような勝利率推定と、証明数探索で用いられる証明サイズ推定を組み合わせている。 EWSは、GoとHexのゲームにおいて、従来の問題解決アルゴリズムよりも優れています。
• 参考スコア（独自算出の注目度）: 5.926773091961042
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose Expected Work Search (EWS), a new game solving algorithm. EWS combines win rate estimation, as used in Monte Carlo Tree Search, with proof size estimation, as used in Proof Number Search. The search efficiency of EWS stems from minimizing a novel notion of Expected Work, which predicts the expected computation required to solve a position. EWS outperforms traditional solving algorithms on the games of Go and Hex. For Go, we present the first solution to the empty 5x5 board with the commonly used positional superko ruleset. For Hex, our algorithm solves the empty 8x8 board in under 4 minutes. Experiments show that EWS succeeds both with and without extensive domain-specific knowledge.
• Abstract（参考訳）: 我々は,新しいゲーム問題解決アルゴリズムである予測ワークサーチ(EWS)を提案する。 EWSはモンテカルロ木探索で用いられるような勝利率推定と、証明数探索で用いられる証明サイズ推定を組み合わせている。 EWSの探索効率は、期待された作業という新しい概念を最小化することに由来する。 EWSは、GoとHexのゲームにおいて、従来の問題解決アルゴリズムよりも優れています。 Go の場合、空の 5x5 ボードによく使われる位置のスーパーコルールセットで最初の解を提示する。 ヘックスにとって、我々のアルゴリズムは空の8x8ボードを4分以内で解く。 実験により、EWSは広範囲なドメイン固有の知識と無関係に成功することが示された。

関連論文リスト

• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。 また,大域的相関平衡を近似計算するアルゴリズムも提案する。 ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-22T09:12:05Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Approximate Dec-POMDP Solving Using Multi-Agent A* [8.728372851272727]
  有限水平DEC-POMDPに対するポリシを計算するためのA*アルゴリズムを提案する。 私たちのゴールは、より大きな地平線に対するスケーラビリティを優先して、最適性を犠牲にすることです。
  論文  参考訳（メタデータ） (2024-05-09T10:33:07Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。 一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。 既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
  論文  参考訳（メタデータ） (2022-10-08T05:11:47Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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