論文の概要: Dominated Actions in Imperfect-Information Games

• arxiv url: http://arxiv.org/abs/2504.09716v1
• Date: Sun, 13 Apr 2025 20:48:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:49:25.574314
• Title: Dominated Actions in Imperfect-Information Games
• Title（参考訳）: 不完全情報ゲームにおける支配的行動
• Authors: Sam Ganzfried,
• Abstract要約: 不完全情報ゲームにおける支配的行動の概念を定義し,研究する。 我々の主な成果は、アクションが混合戦略に支配されているかどうかを実証的に決定するアルゴリズムである。 我々は、"All In or Fold" No-Limit Texas Hold'em ポーカー変種における支配的な行動の役割を探求する。
• 参考スコア（独自算出の注目度）: 0.4895118383237099
• License:
• Abstract: Dominance is a fundamental concept in game theory. In strategic-form games dominated strategies can be identified in polynomial time. As a consequence, iterative removal of dominated strategies can be performed efficiently as a preprocessing step for reducing the size of a game before computing a Nash equilibrium. For imperfect-information games in extensive form, we could convert the game to strategic form and then iteratively remove dominated strategies in the same way; however, this conversion may cause an exponential blowup in game size. In this paper we define and study the concept of dominated actions in imperfect-information games. Our main result is a polynomial-time algorithm for determining whether an action is dominated (strictly or weakly) by any mixed strategy in n-player games, which can be extended to an algorithm for iteratively removing dominated actions. This allows us to efficiently reduce the size of the game tree as a preprocessing step for Nash equilibrium computation. We explore the role of dominated actions empirically in the "All In or Fold" No-Limit Texas Hold'em poker variant.
• Abstract（参考訳）: 支配はゲーム理論における基本的な概念である。 戦略形式ゲームでは、支配的な戦略は多項式時間で特定できる。 その結果、ナッシュ平衡を計算する前にゲームのサイズを縮小する前処理ステップとして、支配戦略の反復的削除を効率的に行うことができる。 不完全情報ゲームが広範に行われる場合、ゲームは戦略形式に変換され、同じ方法で支配的な戦略を反復的に取り除くことができるが、この変換はゲームサイズの指数的な爆発を引き起こす可能性がある。 本稿では,不完全情報ゲームにおける支配的行動の概念を定義し,研究する。 本研究の主な成果は,n-playerゲームにおける混合戦略により,動作が支配的(あるいは弱い)か否かを決定する多項式時間アルゴリズムであり,支配的動作を反復的に除去するアルゴリズムに拡張することができる。 これにより,Nash平衡計算の前処理ステップとしてゲームツリーのサイズを効率的に削減できる。 我々は"All In or Fold" No-Limit Texas Hold'em ポーカー変種における支配的行動の役割を実証的に探求する。

関連論文リスト

• Adapting Beyond the Depth Limit: Counter Strategies in Large Imperfect Information Games [4.56754610152086]
  オンラインプレイ中に、合理的な対戦相手に頑健なまま、既知のサブリレーショナルな対戦相手に適応する問題について検討する。 既存の手法では、奥行き制限を超えた合理的なプレーを前提としており、相手の行動の極めて限られた部分しか適応できない。 本稿では,行列値状態と呼ばれる戦略ポルフォリオ手法を用いて,深度限定探索を行うアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-01-15T14:04:27Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Are AlphaZero-like Agents Robust to Adversarial Perturbations? [73.13944217915089]
  AlphaZero(AZ)は、ニューラルネットワークベースのGo AIが人間のパフォーマンスを大きく上回ることを示した。 私たちは、Go AIが驚くほど間違った行動を起こさせる可能性のある、敵対的な状態が存在するかどうか尋ねる。 我々は、Go AIに対する最初の敵攻撃を開発し、探索空間を戦略的に減らし、効率よく敵の状態を探索する。
  論文  参考訳（メタデータ） (2022-11-07T18:43:25Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。 品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。 その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
  論文  参考訳（メタデータ） (2021-04-17T20:33:24Z)
• Collaborative Agent Gameplay in the Pandemic Board Game [3.223284371460913]
  Pandemicは、すべてのプレイヤーがゲームの進行中に発生する出来事によって引き起こされる課題を克服するために調整する模範的な共同ボードゲームです。 本稿では,すべてのプレイヤーの行動を制御し,この高度に進化した環境において勝つ確率と負けるリスクをバランスさせる人工エージェントを提案する。 提案アルゴリズムは,様々な難易度を持つ異なるゲームにおいて,より一貫した勝利戦略を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-03-21T13:18:20Z)
• Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games [16.43565579998679]
  伝統的なゲーム理論の解の概念は、完全に合理的なプレイヤーを前提としており、従って、従属的な相手を活用できる能力は限られている。 本稿では,通常のゲームや広角ゲームにおいて,量子的対戦相手に対する効果的で堅牢な戦略を計算するためのスケーラブルなアルゴリズムを解析し,提案することを目的とする。
  論文  参考訳（メタデータ） (2020-09-30T09:14:56Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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