論文の概要: History Filtering in Imperfect Information Games: Algorithms and Complexity

• arxiv url: http://arxiv.org/abs/2311.14651v1
• Date: Fri, 24 Nov 2023 18:34:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-27 14:09:37.601230
• Title: History Filtering in Imperfect Information Games: Algorithms and Complexity
• Title（参考訳）: 不完全な情報ゲームにおける履歴フィルタリング:アルゴリズムと複雑性
• Authors: Christopher Solinas, Douglas Rebstock, Nathan R. Sturtevant, Michael Buro
• Abstract要約: 本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。 サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。 また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
• 参考スコア（独自算出の注目度）: 16.23892847804002
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Historically applied exclusively to perfect information games, depth-limited search with value functions has been key to recent advances in AI for imperfect information games. Most prominent approaches with strong theoretical guarantees require subgame decomposition - a process in which a subgame is computed from public information and player beliefs. However, subgame decomposition can itself require non-trivial computations, and its tractability depends on the existence of efficient algorithms for either full enumeration or generation of the histories that form the root of the subgame. Despite this, no formal analysis of the tractability of such computations has been established in prior work, and application domains have often consisted of games, such as poker, for which enumeration is trivial on modern hardware. Applying these ideas to more complex domains requires understanding their cost. In this work, we introduce and analyze the computational aspects and tractability of filtering histories for subgame decomposition. We show that constructing a single history from the root of the subgame is generally intractable, and then provide a necessary and sufficient condition for efficient enumeration. We also introduce a novel Markov Chain Monte Carlo-based generation algorithm for trick-taking card games - a domain where enumeration is often prohibitively expensive. Our experiments demonstrate its improved scalability in the trick-taking card game Oh Hell. These contributions clarify when and how depth-limited search via subgame decomposition can be an effective tool for sequential decision-making in imperfect information settings.
• Abstract（参考訳）: 歴史的に完全な情報ゲームにのみ適用されるが、値関数による深度制限付き検索は、不完全な情報ゲームのためのAIの最近の進歩の鍵となっている。 強力な理論的保証を持つ最も顕著なアプローチは、サブゲーム分解(サブゲームが公的な情報やプレイヤーの信念から計算されるプロセス)を必要とする。 しかし、サブゲーム分解自体は非自明な計算を必要とする可能性があり、そのトラクタビリティは、サブゲームの根を形成する全列挙またはヒストリーの生成のための効率的なアルゴリズムの存在に依存する。 それにもかかわらず、そのような計算のトラクタビリティに関する公式な分析は過去の研究で確立されておらず、アプリケーションドメインはしばしばポーカーのようなゲームで構成されており、現代のハードウェアでは列挙は自明である。 これらのアイデアをより複雑なドメインに適用するには、そのコストを理解する必要がある。 本研究では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。 サブゲームの根元から1つの履歴を構築することは一般に難解であり、効率的な列挙のために必要かつ十分な条件を提供する。 また、カードゲームのためのMarkov Chain Monte Carloベースの新しい生成アルゴリズムについても紹介する。 我々の実験はトリックテイクカードゲームOh Hellにおけるスケーラビリティの向上を実証した。 これらのコントリビューションは、サブゲーム分解による深度制限探索が、不完全な情報設定におけるシーケンシャルな意思決定に有効なツールとなる時期と方法を明らかにする。

関連論文リスト

• Improve Value Estimation of Q Function and Reshape Reward with Monte Carlo Tree Search [0.4450107621124637]
  強化学習は、GoやAtariといった完璧な情報ゲームで大きな成功を収めた。 不完全な情報ゲームのための強化学習の研究は、より複雑なゲーム構造とランダム性のために比較的限られている。 本稿では,不完全な情報ゲームであるUnoに着目し,Q値過大評価を減らし,報酬関数を書き換えることにより,これらの問題に対処することを目的とする。
  論文  参考訳（メタデータ） (2024-10-15T14:31:54Z)
• SPRING: Studying the Paper and Reasoning to Play Games [102.5587155284795]
  我々は,ゲーム本来の学術論文を読み取るための新しいアプローチ,SPRINGを提案し,大言語モデル(LLM)を通してゲームの説明とプレイの知識を利用する。 実験では,クラフトオープンワールド環境の設定下で,異なる形態のプロンプトによって引き起こされる文脈内「推論」の品質について検討した。 我々の実験は、LLMが一貫したチェーン・オブ・シークレットによって誘導されると、洗練された高レベル軌道の完成に大きな可能性があることを示唆している。
  論文  参考訳（メタデータ） (2023-05-24T18:14:35Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms [0.6749750044497732]
  不完全な情報の下でのシーケンシャルな意思決定アルゴリズムの進歩は、大きなゲームで顕著な成功を収めている。 これらのアルゴリズムは伝統的に広義のゲーム形式を用いてゲームを形式化する。 プレイヤー固有の情報状態木に基づく特殊表現の使用が,一般的な回避策であることを示す。
  論文  参考訳（メタデータ） (2021-12-20T22:34:19Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

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

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