論文の概要: 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は広範囲なドメイン固有の知識と無関係に成功することが示された。

関連論文リスト

• Approximate Dec-POMDP Solving Using Multi-Agent A* [8.728372851272727]
  有限水平DEC-POMDPに対するポリシを計算するためのA*アルゴリズムを提案する。 私たちのゴールは、より大きな地平線に対するスケーラビリティを優先して、最適性を犠牲にすることです。
  論文  参考訳（メタデータ） (2024-05-09T10:33:07Z)
• Research Re: search & Re-search [0.0]
  本研究では,深度優先アルゴリズムのABと最良優先アルゴリズムのSSSについて詳しく検討する。 これらのアルゴリズムの一般的な意見は、SSSはより効率的な探索の可能性をもっているが、その複雑な定式化と指数記憶の要求はそれを非現実的にしている。
  論文  参考訳（メタデータ） (2024-03-20T16:08:57Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)

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

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