論文の概要: Runtime analysis of a coevolutionary algorithm on impartial combinatorial games
- arxiv url: http://arxiv.org/abs/2409.04177v1
- Date: Fri, 6 Sep 2024 10:39:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-09 16:05:19.669108
- Title: Runtime analysis of a coevolutionary algorithm on impartial combinatorial games
- Title（参考訳）: 等分的組合せゲームにおける共進化アルゴリズムの実行時解析
- Authors: Alistair Benford, Per Kristian Lehre,
- Abstract要約: 進化的アルゴリズム(CoEA)は、現代人との相互作用に基づいて最強を反復的に選択し、次の世代で両親として選択した個体群を用いて、個体群を進化させる。
しかし,CoEAのゲームプレイへの応用はサイクリングなどの病理的行動のため,実行時のペイオフ状況において特に問題となる。
本稿では,解析の範囲を推し進め,公平なゲームのための最適な戦略を見出す。
この結果はどんな公平なゲームにも当てはまり、多くのゲームでは、インプリッド・バウンドは数の関数として、あるいは準ポリノミアルである。
- 参考スコア（独自算出の注目度）: 1.104960878651584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). CoEAs evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation (via randomised mutation and crossover). However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with intransitive payoff landscapes. Insight into how to design CoEAs to avoid such behaviours can be provided by runtime analysis. In this paper, we push the scope of runtime analysis to combinatorial games, proving a general upper bound for the number of simulated games needed for UMDA (a type of CoEA) to discover (with high probability) an optimal strategy for an impartial combinatorial game. This result applies to any impartial combinatorial game, and for many games the implied bound is polynomial or quasipolynomial as a function of the number of game positions. After proving the main result, we provide several applications to simple well-known games: Nim, Chomp, Silver Dollar, and Turning Turtles. As the first runtime analysis for CoEAs on combinatorial games, this result is a critical step towards a comprehensive theoretical framework for coevolution.
- Abstract（参考訳）: 複雑なダイナミクスのため、組合せゲームはゲームプレイエージェントを訓練するアルゴリズムの鍵となるテストケースと応用である。
セルフプレイでトレーニングするアルゴリズムには、CoEA(Coevolutionary Algorithm)がある。
CoEAは、同時代人との相互作用に基づいて最強の個体群を反復的に選択し、(ランダム化された突然変異と交叉を通じて)次の世代で両親として選択された個体群を使用することによって、個体群を進化させる。
しかし,CoEAのゲームプレイへの応用はサイクリングなどの病理的行動のため困難であり,特に過渡的なペイオフシーンを持つゲームにとって重要な問題である。
このような振る舞いを避けるためにCoEAを設計する方法についての洞察は、実行時分析によって得られます。
本稿では, UMDA (CoEAの一種) に必要なシミュレーションゲーム数に対して, 初期組合せゲームに対する最適戦略を(高い確率で) 発見するために, 一般上界を証明し, 実行時解析の範囲を組合せゲームに推し進める。
この結果は任意の公平な組合せゲームに適用され、多くのゲームでは、インプリッド境界はゲーム位置の数の関数として多項式あるいは準ポリノミカル(英語版)である。
主な結果を証明した後、Nim、Chomp、Silver Dollar、Turning Turtlesといった単純なゲームにいくつかの応用を提供している。
組合せゲーム上でのCoEAの最初のランタイム解析として、この結果は共進化の包括的な理論的枠組みへの重要なステップである。
関連論文リスト
- 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) - Learning in Congestion Games with Bandit Feedback [45.4542525044623]
我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。
まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。
次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-04T02:32:26Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。
これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳（メタデータ） (2021-11-07T21:15:35Z) - Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。
品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。
その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
論文 参考訳（メタデータ） (2021-04-17T20:33:24Z) - 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) - Finding Core Members of Cooperative Games using Agent-Based Modeling [0.0]
エージェント・ベース・モデリング(ABM)は、社会現象の洞察を得るための強力なパラダイムである。
本稿では,エージェントが連立関係を見つけられるように,AIMに組み込むアルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-08-30T17:38:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。