論文の概要: Generalized Proof-Number Monte-Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2506.13249v1
- Date: Mon, 16 Jun 2025 08:45:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-17 17:28:47.888216
- Title: Generalized Proof-Number Monte-Carlo Tree Search
- Title（参考訳）: 一般化Proof-Number Monte-Carlo Tree Search
- Authors: Jakub Kowalski, Dennis J. N. J. Soemers, Szymon Kosakowski, Mark H. M. Winands,
- Abstract要約: 一般化Proof-Number Monte-Carlo Tree Search:最近提案されたProof-Number Search(PNS)とMCTS(MCTS)の組み合わせの一般化
本稿では,従来のPNSとMCTSの組み合わせの3つのコア修正を提案する。
これにより、もはや無防備な数を必要としないという意味でコードの複雑さを減らし、2人以上のプレイヤーを持つゲームに適用可能なテクニックを一般化する。
- 参考スコア（独自算出の注目度）: 2.052209054561478
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper presents Generalized Proof-Number Monte-Carlo Tree Search: a generalization of recently proposed combinations of Proof-Number Search (PNS) with Monte-Carlo Tree Search (MCTS), which use (dis)proof numbers to bias UCB1-based Selection strategies towards parts of the search that are expected to be easily (dis)proven. We propose three core modifications of prior combinations of PNS with MCTS. First, we track proof numbers per player. This reduces code complexity in the sense that we no longer need disproof numbers, and generalizes the technique to be applicable to games with more than two players. Second, we propose and extensively evaluate different methods of using proof numbers to bias the selection strategy, achieving strong performance with strategies that are simpler to implement and compute. Third, we merge our technique with Score Bounded MCTS, enabling the algorithm to prove and leverage upper and lower bounds on scores - as opposed to only proving wins or not-wins. Experiments demonstrate substantial performance increases, reaching the range of 80% for 8 out of the 11 tested board games.
- Abstract（参考訳）: 本稿では,最近提案されたProof-Number Tree Search (PNS) とMonte-Carlo Tree Search (MCTS) の組み合わせの一般化について述べる。
本稿では,従来のPNSとMCTSの組み合わせの3つのコア修正を提案する。
まず、プレイヤーごとの証明番号を追跡する。
これにより、もはや無防備な数を必要としないという意味でコードの複雑さを減らし、2人以上のプレイヤーを持つゲームに適用可能なテクニックを一般化する。
第2に,証明数を用いて選択戦略を偏り,実装や計算が容易な戦略で高い性能を達成する方法を提案し,広く評価する。
第三に、我々はScore Bounded MCTSと手法を融合させ、アルゴリズムがスコアの上下境界を証明し活用できるようにする。
実験は大きなパフォーマンス向上を示し、11のボードゲーム中8の80%に到達した。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Robust Collaborative Filtering to Popularity Distribution Shift [56.78171423428719]
本稿では,テストデータに仮定することなく,インタラクションワイドな人気ショートカットを定量化し,削減する,シンプルで効果的なデバイアス対策であるPopGoを提案する。
IDとOODの両方のテストセットにおいて、PopGoは最先端のデバイアス戦略よりも大幅に向上している。
論文 参考訳（メタデータ） (2023-10-16T04:20:52Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - 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) - Combining Monte-Carlo Tree Search with Proof-Number Search [5.354801701968199]
Proof-Number Search (PNS) と Monte-Carlo Tree Search (MCTS) は様々なゲームにおいて意思決定に成功している。
本稿では,この2つの木探索手法を組み合わせたPN-MCTSという新しい手法を提案する。
実験の結果、PN-MCTSはLines of Action、MiniShogi、Knightthrough、Awariなどいくつかのゲームで基本MCTSを上回っ、94.0%の勝利率を記録した。
論文 参考訳（メタデータ） (2022-06-08T15:28:42Z) - Sample Complexity of Tree Search Configuration: Cutting Planes and
Beyond [98.92725321081994]
最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。
本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
論文 参考訳（メタデータ） (2021-06-08T00:57:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。