論文の概要: Relevance-Zone Reduction in Game Solving

• arxiv url: http://arxiv.org/abs/2510.00689v1
• Date: Wed, 01 Oct 2025 09:10:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.486497
• Title: Relevance-Zone Reduction in Game Solving
• Title（参考訳）: ゲーム解決における関連ゾンの低減
• Authors: Chi-Huang Lin, Ting Han Wei, Chun-Jui Wang, Hung Guei, Chung-Chin Shih, Yun-Jui Tsai, I-Chen Wu, Ti-Rong Wu,
• Abstract要約: 本稿では,領域を徐々に制限しながら,同じ位置を繰り返す反復RZ低減手法を提案する。 7x7 Killall-Goの実験では,RZの平均サイズを85.95%に削減した。
• 参考スコア（独自算出の注目度）: 13.335750959467056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Game solving aims to find the optimal strategies for all players and determine the theoretical outcome of a game. However, due to the exponential growth of game trees, many games remain unsolved, even though methods like AlphaZero have demonstrated super-human level in game playing. The Relevance-Zone (RZ) is a local strategy reuse technique that restricts the search to only the regions relevant to the outcome, significantly reducing the search space. However, RZs are not unique. Different solutions may result in RZs of varying sizes. Smaller RZs are generally more favorable, as they increase the chance of reuse and improve pruning efficiency. To this end, we propose an iterative RZ reduction method that repeatedly solves the same position while gradually restricting the region involved, guiding the solver toward smaller RZs. We design three constraint generation strategies and integrate an RZ Pattern Table to fully leverage past solutions. In experiments on 7x7 Killall-Go, our method reduces the average RZ size to 85.95% of the original. Furthermore, the reduced RZs can be permanently stored as reusable knowledge for future solving tasks, especially for larger board sizes or different openings.
• Abstract（参考訳）: ゲーム解決は、すべてのプレイヤーにとって最適な戦略を見つけ、ゲームの理論的結果を決定することを目的としている。 しかし、ゲームツリーの指数的な成長により、AlphaZeroのような手法がゲームプレイにおける超人的レベルを示しているにもかかわらず、多くのゲームは未解決のままである。 Relevance-Zone (RZ) は、検索を結果に関連する領域のみに制限し、検索スペースを大幅に削減するローカル戦略再利用技術である。 しかし、RZはユニークではない。 異なる解は、様々な大きさのRZをもたらす。 より小さなRZは、再利用の機会を増やし、プルーニング効率を向上させるため、一般的により好ましい。 そこで本研究では,各領域を徐々に制限しながら,繰り返し同じ位置を解消し,より小さなRZへ導く反復RZ削減手法を提案する。 我々は3つの制約生成戦略を設計し、過去のソリューションを完全に活用するためにRZパターンテーブルを統合する。 7x7 Killall-Goの実験では,RZの平均サイズを85.95%に削減した。 さらに、縮小されたRZは、特により大きなボードサイズや異なる開口部において、将来の問題解決タスクのための再利用可能な知識として永久に保存することができる。

関連論文リスト

• Dominated Actions in Imperfect-Information Games [0.0]
  不完全情報ゲームにおける支配的行動の概念を定義し,研究する。 我々の主な成果は、アクションが混合戦略に支配されているかどうかを実証的に決定するアルゴリズムである。 我々は、"All In or Fold" No-Limit Texas Hold'em ポーカー変種における支配的な行動の役割を探求する。
  論文  参考訳（メタデータ） (2025-04-13T20:48:44Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Efficient Policy Space Response Oracles [61.71849698253696]
  ポリシー空間応答 Oracle 法 (PSRO) は、2プレイヤーゼロサムゲームにおけるナッシュ均衡の一般解を提供する。 我々の開発の中心は、制限なし(URR)ゲームにおけるミニマックス最適化の導入である。 壁面時間, 10倍のデータ効率, および既存のPSRO法と同様のエクスプロイザビリティを, Kuhn と Leduc Poker のゲームで50倍高速化したことを報告した。
  論文  参考訳（メタデータ） (2022-01-28T17:54:45Z)
• A Novel Approach to Solving Goal-Achieving Problems for Board Games [18.627167345021835]
  本稿では、まず、GoのL&D問題を解決するために、RZベースサーチ(RZS)と呼ばれる新しいRZベースのアプローチを提案する。 RZSは、Nullがポストホックであるかどうかを決定する前に動きを試みます。 また、AlphaZeroを改良してより高速に勝利させるFTL(Faster to Life)という新たなトレーニング手法を提案する。
  論文  参考訳（メタデータ） (2021-12-05T13:23:10Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  ターン型戦略ゲーム(Tribes)のためのプログレッシブアンプランによるPortfolio Monte Carlo Tree Searchを提案する。 品質分散アルゴリズム(MAP-Elites)を使用して異なるプレイスタイルを実現し、競争レベルを維持しながらパラメータ化する方法を示します。 その結果,このアルゴリズムは,トレーニングに用いるレベルを超えて,幅広いゲームレベルにおいても,これらの目標を達成できることが示された。
  論文  参考訳（メタデータ） (2021-04-17T20:33:24Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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