Fugu-MT 論文翻訳(概要): Completeness of Unbounded Best-First Game Algorithms

論文の概要: Completeness of Unbounded Best-First Game Algorithms

arxiv url: http://arxiv.org/abs/2109.09468v1
Date: Sat, 11 Sep 2021 23:13:52 GMT
ステータス: 処理完了
システム内更新日: 2021-09-26 22:31:31.690641
Title: Completeness of Unbounded Best-First Game Algorithms
Title（参考訳）: unbounded best-first gameアルゴリズムの完全性
Authors: Quentin Cohen-Solal (LAMSADE, Universit\'e Paris-Dauphine, PSL, CNRS, France)
Abstract要約: 2つのゲーム検索アルゴリズムの完全性を証明する。完全情報マルチプレイヤーゲームにおいて,これらのアルゴリズムを一般化する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this article, we prove the completeness of the following game search algorithms: unbounded best-first minimax with completion and descent with completion, i.e. we show that, with enough time, they find the best game strategy. We then generalize these two algorithms in the context of perfect information multiplayer games. We show that these generalizations are also complete: they find one of the equilibrium points.
Abstract（参考訳）: 本稿では、以下のゲーム探索アルゴリズムの完全性を証明する。完了と降下を伴う無制限のベストファーストミニマックス、つまり、十分な時間をかけて、最高のゲーム戦略を見つけることを示します。次に,これら2つのアルゴリズムを完全情報マルチプレイヤーゲームという文脈で一般化する。これらの一般化も完備であることを示し、平衡点の1つを見つける。

関連論文リスト

Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge [5.071342645033634]
我々はDescentフレームワークを拡張し、完全な情報を持つ2人プレイヤゲームのコンテキストにおける学習と計画を可能にする。我々は、最先端のアルゴリズムに対してEin wurfelt!で評価する。最良の結果を得るのはDescentの一般化である。
論文参考訳（メタデータ） (2023-02-08T20:27:45Z)
Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
論文参考訳（メタデータ） (2022-10-18T15:10:25Z)
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)
Final Adaptation Reinforcement Learning for N-Player Games [0.0]
本稿では,n-tuple-based reinforcement learning (RL)アルゴリズムについて述べる。本稿では,TD-,SARSA-およびQ-ラーニングのための新しいアルゴリズムを提案する。これらのアルゴリズムにFinal Adaptation RL(FARL)と呼ばれる新しい要素を追加します。
論文参考訳（メタデータ） (2021-11-29T08:36:39Z)
Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
論文参考訳（メタデータ） (2021-06-27T22:02:26Z)
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文参考訳（メタデータ） (2021-01-21T10:35:09Z)
Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-21T17:51:57Z)
From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
論文参考訳（メタデータ） (2020-02-19T21:36:58Z)
Fast Complete Algorithm for Multiplayer Nash Equilibrium [1.7132914341329848]
マルチプレイヤー汎用ゲームにおけるナッシュ均衡計算のための新しい完全アルゴリズムについて述べる。このアルゴリズムは、以前に研究されたいくつかのゲームクラスにおいて、先行した最速の完全アルゴリズムよりもはるかに高速に動作することを示す。
論文参考訳（メタデータ） (2020-02-11T23:42:14Z)

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