論文の概要: Proof Number Based Monte-Carlo Tree Search

• arxiv url: http://arxiv.org/abs/2303.09449v1
• Date: Thu, 16 Mar 2023 16:27:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-17 14:47:06.530915
• Title: Proof Number Based Monte-Carlo Tree Search
• Title（参考訳）: 証明数に基づくモンテカルロ木探索
• Authors: Elliot Doe, Mark H. M. Winands, Jakub Kowalski, Dennis J. N. J. Soemers, Daniel G\'orski, Cameron Browne
• Abstract要約: 本稿では,モンテカルロ木探索(MCTS)とProof-Number Search(PNS)を組み合わせた新しいゲーム検索アルゴリズムであるPN-MCTSを提案する。 本研究は,MCTS木に蓄積された証明値と防腐数によって得られる付加的な知識を,最終移動選択,部分木の解法,UTT式という3つの領域で定義する。 実験の結果、PN-MCTSは6つのゲームドメインのうち5つ(すべてゴモクを除く)でMCTSを確実に上回り、ライン・オブ・アクションでは96.2%の勝利率を記録した。
• 参考スコア（独自算出の注目度）: 5.3338328682907985
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes a new game search algorithm, PN-MCTS, that combines Monte-Carlo Tree Search (MCTS) and Proof-Number Search (PNS). These two algorithms have been successfully applied for decision making in a range of domains. We define three areas where the additional knowledge provided by the proof and disproof numbers gathered in MCTS trees might be used: final move selection, solving subtrees, and the UCT formula. We test all possible combinations on different time settings, playing against vanilla UCT MCTS on several games: Lines of Action ($7$$\times$$7$ and $8$$\times$$8$), MiniShogi, Knightthrough, Awari, and Gomoku. Furthermore, we extend this new algorithm to properly address games with draws, like Awari, by adding an additional layer of PNS on top of the MCTS tree. The experiments show that PN-MCTS confidently outperforms MCTS in 5 out of 6 game domains (all except Gomoku), achieving win rates up to 96.2% for Lines of Action.
• Abstract（参考訳）: 本稿では,モンテカルロ木探索(MCTS)とProof-Number Search(PNS)を組み合わせた新しいゲーム検索アルゴリズムであるPN-MCTSを提案する。 これら2つのアルゴリズムは、様々な領域における意思決定にうまく適用されている。 我々は,mcts木に収集された証明と不完全数によって提供される付加的な知識が,最終移動選択,部分木解,uct公式の3つの領域を定義できる。 さまざまな時間設定で可能な組み合わせをすべてテストし、いくつかのゲームでVanilla UCT MCTSと対戦する: Lines of Action(7$\times$7$と8$\times$8$)、MiniShogi、Knightthrough、Awari、Gomoku。 さらに,新たなアルゴリズムを拡張して,MCTSツリー上にPNSの付加層を追加することで,Awariのようなドローを持つゲームに適切に対処する。 実験の結果、PN-MCTSは6つのゲームドメインのうち5つ(すべてゴモクを除く)でMCTSを確実に上回り、96.2%の勝利率を記録した。

関連論文リスト

• Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions [89.89612827542972]
  本稿では,モンテカルロ木探索 (MCTS) の変種を提案する。 9倍のGoボードゲームとAtariゲームの性能と計算結果を評価した。 実験の結果,提案手法は,平均検索時間50%以下で,元の検索アルゴリズムに匹敵する性能が得られることがわかった。
  論文  参考訳（メタデータ） (2022-10-23T06:39:20Z)
• Continuous Monte Carlo Graph Search [79.0972258753576]
  連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンライン計画への拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。 CMCGSは、いくつかの複雑な連続DeepMind Control Suiteベンチマークと2Dナビゲーションタスクで比較方法より優れている。
  論文  参考訳（メタデータ） (2022-10-04T07:34:06Z)
• 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)
• 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)
• Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction [63.595545216327245]
  木探索(TS)における2つの大きな課題に取り組む。 我々はまず、TSと事前学習された値関数による行動選択が、元の事前学習されたエージェントと比較して性能を低下させるという、反直感的な現象を発見し、分析する。 Batch-BFS(Batch-BFS)は,木の各深さのすべてのノードを同時に前進させるGPUワイドファースト検索である。
  論文  参考訳（メタデータ） (2021-07-04T19:32:24Z)
• Dual Monte Carlo Tree Search [0.0]
  我々はDual MCTSが、様々な対称ゲームや非対称ゲームにおいて最も広く使われているニューラルMCTSアルゴリズムであるAlphaZeroよりも優れていることを示す。 デュアルMCTSは、2つの異なる検索木、単一のディープニューラルネットワーク、PUCB、スライドウィンドウ、およびepsilon-greedyアルゴリズムの組み合わせを使用して検索木のための新しい更新技術を使用しています。
  論文  参考訳（メタデータ） (2021-03-21T23:34:11Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search [66.34387649910046]
  モンテカルロ木探索(MCTS)は、囲碁やアタリゲームなど多くの領域で最先端の結果を得た。 我々は,現在の検索状況の不確かさを予測し,その結果を用いて検索をやめるべきかどうかを判断することで,この目標を達成することを提案する。
  論文  参考訳（メタデータ） (2020-12-14T19:49:25Z)
• Playing Carcassonne with Monte Carlo Tree Search [0.0]
  我々は,モンテカルロ木探索 (MCTS) とラピッドアクション値推定 (MCTS-RAVE) をカーカッソンヌのゲームで使用することを検討した。 MCTSをベースとした手法とStar2.5アルゴリズムの長所を比較し,カーカッソンヌのゲームにおける競争結果が得られたことを報告した。
  論文  参考訳（メタデータ） (2020-09-27T22:35:53Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  モンテカルロ・ツリー・サーチ(MCTS)と深部強化学習の組み合わせは,2プレイヤー完全情報ゲームにおける最先端の手法である。 本稿では,MCTS の変種を利用した探索アルゴリズムについて述べる。1) 潜在的に有界な報酬を持つゲームに対する新たなアクション値正規化機構,2) 効果的な探索並列化を可能にする仮想損失関数の定義,3) 世代ごとのセルフプレイによって訓練されたポリシーネットワークについて述べる。
  論文  参考訳（メタデータ） (2020-05-22T18:02:36Z)

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

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