論文の概要: Fast Algorithms for Poker Require Modelling it as a Sequential Bayesian Game

• arxiv url: http://arxiv.org/abs/2112.10890v1
• Date: Mon, 20 Dec 2021 22:34:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-22 14:49:46.135600
• Title: Fast Algorithms for Poker Require Modelling it as a Sequential Bayesian Game
• Title（参考訳）: ポーカーのための高速なアルゴリズムは、シーケンシャルベイズゲームとしてモデル化する必要がある
• Authors: Vojt\v{e}ch Kova\v{r}\'ik, David Milec, Michal \v{S}ustr, Dominik Seitz, Viliam Lis\'y
• Abstract要約: 逐次ベイズゲームは不完全情報結果を一般化するための自然な種類のゲームであると主張する。 公立CFRで107状態のポーカーサブゲームを解決するのに3分700MBを要し、バニラCFRの同等バージョンでは5.5時間20GBを要した。 我々は、公開状態 CFR を一般的な広義のゲームに拡張し、この拡張は、連続ベイズゲームに対するバージョンの効果のいくつか(すべてではないが)を楽しむと主張した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many recent results in imperfect information games were only formulated for, or evaluated on, poker and poker-like games such as liar's dice. We argue that sequential Bayesian games constitute a natural class of games for generalizing these results. In particular, this model allows for an elegant formulation of the counterfactual regret minimization algorithm, called public-state CFR (PS-CFR), which naturally lends itself to an efficient implementation. Empirically, solving a poker subgame with 10^7 states by public-state CFR takes 3 minutes and 700 MB while a comparable version of vanilla CFR takes 5.5 hours and 20 GB. Additionally, the public-state formulation of CFR opens up the possibility for exploiting domain-specific assumptions, leading to a quadratic reduction in asymptotic complexity (and a further empirical speedup) over vanilla CFR in poker and other domains. Overall, this suggests that the ability to represent poker as a sequential Bayesian game played a key role in the success of CFR-based methods. Finally, we extend public-state CFR to general extensive-form games, arguing that this extension enjoys some - but not all - of the benefits of the version for sequential Bayesian games.
• Abstract（参考訳）: 不完全な情報ゲームに関する最近の多くの結果は、liar's diceのようなポーカーやポーカーのようなゲームのためにのみ定式化された。 逐次ベイズゲームはこれらの結果を一般化するための自然な種類のゲームであると主張する。 特に、このモデルは反事実的後悔最小化アルゴリズム(public-state cfr (ps-cfr) と呼ばれる)のエレガントな定式化を可能にする。 経験上、パブリックステートcfrによる10^7状態のポーカーサブゲームでは3分700mb、同等バージョンのvanilla cfrでは5.5時間20gbである。 さらに、CFRの公的な定式化は、ドメイン固有の仮定を利用する可能性を開放し、ポーカーや他のドメインにおけるバニラCFRよりも漸近的複雑性(およびさらに経験的なスピードアップ)が2次的に減少する。 全体として、ポーカーをシーケンシャルベイズゲームとして表現する能力は、CFRベースの手法の成功に重要な役割を果たしたことを示唆している。 最後に、パブリックステートのcfrを一般的な広義のゲームに拡張し、この拡張は、シーケンシャルベイズゲームのバージョンの利点を全て享受するものではない、と主張している。

関連論文リスト

• History Filtering in Imperfect Information Games: Algorithms and Complexity [16.23892847804002]
  本稿では,サブゲーム分解のためのフィルタリング履歴の計算的側面とトラクタビリティについて述べる。 サブゲームのルートから単一の履歴を構築することは、一般的には難解であることを示す。 また,トリックテイクカードゲームのためのマルコフチェインモンテカルロベース生成アルゴリズムについても紹介する。
  論文  参考訳（メタデータ） (2023-11-24T18:34:36Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Spatial State-Action Features for General Games [5.849736173068868]
  汎用ゲームのための空間状態対応機能の設計と効率的な実装を定式化する。 これらは、局所的な状態の変数にマッチするかどうかに基づいて、アクションをインセンティブまたは非インセンティブ化するようにトレーニングできるパターンである。 任意の機能セットに対して,アクティブな機能を評価するための効率的なアプローチを提案する。
  論文  参考訳（メタデータ） (2022-01-17T13:34:04Z)
• Student of Games: A unified learning algorithm for both perfect and imperfect information games [22.97853623156316]
  Students of Gamesは、ガイド付き検索、自己学習、ゲーム理論推論を組み合わせたアルゴリズムである。 学生ゲームは,計算能力と近似能力が増大するにつれて,完全プレイに収束し,健全であることを示す。 学生はチェスと囲碁で強い成績を収め、無期限のテキサスホールディングスのポーカーで最強の公開エージェントを破り、スコットランドヤードで最先端のエージェントを倒した。
  論文  参考訳（メタデータ） (2021-12-06T17:16:24Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。 品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。 その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
  論文  参考訳（メタデータ） (2021-04-17T20:33:24Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)

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

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