論文の概要: Set-Based Retrograde Analysis: Precomputing the Solution to 24-card Bridge Double Dummy Deals

• arxiv url: http://arxiv.org/abs/2411.09089v1
• Date: Wed, 13 Nov 2024 23:43:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:22:19.468760
• Title: Set-Based Retrograde Analysis: Precomputing the Solution to 24-card Bridge Double Dummy Deals
• Title（参考訳）: セットベース逆行解析:24カードブリッジダブルダミーディールへの解法前処理
• Authors: Isaac Stone, Nathan R. Sturtevant, Jonathan Schaeffer,
• Abstract要約: 逆行解析はゲーム終了時の状態を解くためにゲームプレイングプログラムで使用される。 我々は,同じゲーム値を持つ状態の集合を演算することで,同じ結果が得られるセログレード解析を導入する。
• 参考スコア（独自算出の注目度）: 11.732829185059801
• License:
• Abstract: Retrograde analysis is used in game-playing programs to solve states at the end of a game, working backwards toward the start of the game. The algorithm iterates through and computes the perfect-play value for as many states as resources allow. We introduce setrograde analysis which achieves the same results by operating on sets of states that have the same game value. The algorithm is demonstrated by computing exact solutions for Bridge double dummy card-play. For deals with 24 cards remaining to be played ($10^{27}$ states, which can be reduced to $10^{15}$ states using preexisting techniques), we strongly solve all deals. The setrograde algorithm performs a factor of $10^3$ fewer search operations than a standard retrograde algorithm, producing a database with a factor of $10^4$ fewer entries. For applicable domains, this allows retrograde searching to reach unprecedented search depths.
• Abstract（参考訳）: 逆行解析は、ゲームの終了時の状態を解決するためにゲームプレイングプログラムで使われ、ゲームの開始に向かって後方に進む。 このアルゴリズムはリソースが許す限り多くの状態の完全再生値を反復して計算する。 我々は,同じゲーム値を持つ状態の集合を演算することで,同じ結果が得られるセログレード解析を導入する。 このアルゴリズムはブリッジダブルダミーカードプレイの正確な解を計算することで実証される。 残った24枚のカード($10^{27}$)の取引は、既存の技術を使って10^{15}$状態に還元できるので、すべての取引を強く解決します。 セログレードアルゴリズムは、標準的な逆行アルゴリズムよりも10^3$の検索操作を減らし、10^4$のエントリを減らしたデータベースを生成する。 適用可能なドメインに対しては、逆行検索が前例のない検索深度に達することができる。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• History Filtering in Imperfect Information Games: Algorithms and Complexity [16.23892847804002]
  本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。 サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。 また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
  論文  参考訳（メタデータ） (2023-11-24T18:34:36Z)
• Game Solving with Online Fine-Tuning [17.614045403579244]
  本稿では,探索中のオンラインファインチューニングの適用について検討し,ゲーム問題解決のための最適設計計算を学習するための2つの方法を提案する。 実験の結果,オンラインファインチューニングを用いることで,ベースラインに比べて23.54%の時間しか利用できない7x7 Killall-Goの課題が解決できることがわかった。
  論文  参考訳（メタデータ） (2023-11-13T09:09:52Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Optimizing $\alpha\mu$ [7.715389335184684]
  $alphamu$は、Perfect Information Monte Carlo searchのデフォルトである戦略融合と非局所性の2つを修復する検索アルゴリズムである。 本稿では、Bridgeのゲームに$alphamu$を最適化し、無駄な計算を避ける。
  論文  参考訳（メタデータ） (2021-01-29T15:20:03Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  モンテカルロ・ツリー・サーチ(MCTS)と深部強化学習の組み合わせは,2プレイヤー完全情報ゲームにおける最先端の手法である。 本稿では,MCTS の変種を利用した探索アルゴリズムについて述べる。1) 潜在的に有界な報酬を持つゲームに対する新たなアクション値正規化機構,2) 効果的な探索並列化を可能にする仮想損失関数の定義,3) 世代ごとのセルフプレイによって訓練されたポリシーネットワークについて述べる。
  論文  参考訳（メタデータ） (2020-05-22T18:02:36Z)

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

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