論文の概要: Monte Carlo Permutation Search

• arxiv url: http://arxiv.org/abs/2510.06381v1
• Date: Tue, 07 Oct 2025 18:59:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.15522
• Title: Monte Carlo Permutation Search
• Title（参考訳）: モンテカルロ置換探索
• Authors: Tristan Cazenave,
• Abstract要約: GRAVEアルゴリズムを改良した汎用モンテカルロ木探索 (MCTS) アルゴリズムを提案する。 MCPSは、深層強化学習が選択肢ではない場合や、プレイ前に利用可能なコンピューティングパワーが実質的でない場合に関係している。 私たちは、ボードゲーム、ウォーゲーム、投資ゲーム、ビデオゲーム、マルチプレイヤーゲームなど、様々なゲームでMCPSを広範囲にテストしています。
• 参考スコア（独自算出の注目度）: 3.046576641182083
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose Monte Carlo Permutation Search (MCPS), a general-purpose Monte Carlo Tree Search (MCTS) algorithm that improves upon the GRAVE algorithm. MCPS is relevant when deep reinforcement learning is not an option, or when the computing power available before play is not substantial, such as in General Game Playing, for example. The principle of MCPS is to include in the exploration term of a node the statistics on all the playouts that contain all the moves on the path from the root to the node. We extensively test MCPS on a variety of games: board games, wargame, investment game, video game and multi-player games. MCPS has better results than GRAVE in all the two-player games. It has equivalent results for multi-player games because these games are inherently balanced even when players have different strengths. We also show that using abstract codes for moves instead of exact codes can be beneficial to both MCPS and GRAVE, as they improve the permutation statistics and the AMAF statistics. We also provide a mathematical derivation of the formulas used for weighting the three sources of statistics. These formulas are an improvement on the GRAVE formula since they no longer use the bias hyperparameter of GRAVE. Moreover, MCPS is not sensitive to the ref hyperparameter.
• Abstract（参考訳）: GRAVEアルゴリズムを改良した汎用モンテカルロ木探索 (MCTS) アルゴリズムであるモンテカルロ置換探索 (MCPS) を提案する。 MCPSは、深層強化学習が選択肢ではない場合や、例えばGeneral Game Playingのように、プレイ前に利用可能なコンピューティングパワーが実質的でない場合に関係している。 MCPSの原理は、ノードの探索項に、ルートからノードへの経路上のすべての移動を含む全てのプレーアウトに関する統計を含ませることである。 私たちは、ボードゲーム、ウォーゲーム、投資ゲーム、ビデオゲーム、マルチプレイヤーゲームなど、様々なゲームでMCPSを広範囲にテストしています。 MCPSはGRAVEより成績が良い。 プレイヤーの強みが異なる場合でも本質的にバランスが取れているため、マルチプレイヤーゲームに匹敵する結果が得られる。 また,MCPS と GRAVE のどちらにも有益であり,置換統計量や AMAF の統計量の改善が期待できることを示す。 また、3つの統計源の重み付けに用いられる式を数学的に導出する。 これらの公式は、GRAVEのバイアスハイパーパラメータをもはや使用しないため、GRAVE式の改善である。 さらに、MCPSはrefハイパーパラメータに敏感ではない。

関連論文リスト

• Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing [1.2882480196517305]
  本稿では,汎用ゲームプレイング(GVGP)におけるモンテカルロ木探索(MCTS)の8つの拡張について論じる。 これらのいくつかは既存の文献から知られており、拡張またはGVGPの文脈で導入されている。 ほとんどの拡張は、個別に適用された場合の勝利率の統計的に有意な増加をもたらすことが示されている。
  論文  参考訳（メタデータ） (2024-07-03T12:18:28Z)
• Regret Matching+: (In)Stability and Fast Convergence in Games [68.13214224119024]
  RM+とその予測バージョンは不安定であり,他のプレイヤーが大きな後悔を味わう可能性がある。 これらの修正は、RM+による通常のゲームにおいて、個々の後悔に対して$O(T1/4)$$と$O(1)$の社会的後悔を得るのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-05-24T04:26:21Z)
• Proof Number Based Monte-Carlo Tree Search [1.93674821880689]
  本稿では,モンテカルロ木探索(MCTS)とProof-Number Search(PNS)を組み合わせた新しいゲーム検索アルゴリズムであるPN-MCTSを提案する。 本研究は,MCTS木に蓄積された証明値と防腐数から得られる付加的な知識を活用可能な3つの領域を定義する。 実験の結果、PN-MCTSは全てのテストされたゲーム領域でMCTSを上回り、ライン・オブ・アクションで96.2%の勝利率を達成した。
  論文  参考訳（メタデータ） (2023-03-16T16:27:07Z)
• A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games [104.3339905200105]
  この研究は、ミラー降下と非ユークリッド近位勾配アルゴリズムにインスパイアされた、磁気ミラー降下と呼ばれるアルゴリズムを研究する。 我々の貢献は、2人のプレイヤーゼロサムゲームにおける平衡解法および強化学習へのアプローチとしての磁気ミラー降下の利点を実証することである。
  論文  参考訳（メタデータ） (2022-06-12T19:49:14Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers? [156.5760265539888]
  我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。 そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。 オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-27T05:41:14Z)
• MCTS Based Agents for Multistage Single-Player Card Game [0.0]
  この記事では、カードゲームLord of the RingsにおけるMonte Carlo Tree Searchアルゴリズムの使用について紹介する。 主な課題はゲーム力学の複雑さであり、各ラウンドは5つの決定段階と2つのランダムステージから構成される。 様々な意思決定アルゴリズムをテストするために,ゲームシミュレータが実装されている。
  論文  参考訳（メタデータ） (2021-09-24T10:56:54Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。 品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。 その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
  論文  参考訳（メタデータ） (2021-04-17T20:33:24Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  モンテカルロ・ツリー・サーチ(MCTS)と深部強化学習の組み合わせは,2プレイヤー完全情報ゲームにおける最先端の手法である。 本稿では,MCTS の変種を利用した探索アルゴリズムについて述べる。1) 潜在的に有界な報酬を持つゲームに対する新たなアクション値正規化機構,2) 効果的な探索並列化を可能にする仮想損失関数の定義,3) 世代ごとのセルフプレイによって訓練されたポリシーネットワークについて述べる。
  論文  参考訳（メタデータ） (2020-05-22T18:02:36Z)

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

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