論文の概要: On the Evolution of the MCTS Upper Confidence Bounds for Trees by Means
of Evolutionary Algorithms in the Game of Carcassonne
- arxiv url: http://arxiv.org/abs/2112.09697v1
- Date: Fri, 17 Dec 2021 18:06:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-21 15:43:21.102406
- Title: On the Evolution of the MCTS Upper Confidence Bounds for Trees by Means
of Evolutionary Algorithms in the Game of Carcassonne
- Title(参考訳): カーカソンゲームにおける進化アルゴリズムによる木に対するmcts上信頼境界の進化について
- Authors: Edgar Galv\'an and Gavin Simpson
- Abstract要約: Monte Carlo Tree Search (MCTS) は最適な決定を探索するためのサンプリング最優先の手法である。
我々は、進化的アルゴリズム(EA)を用いて、木上の信頼境界(UCT)の数学的表現に代えて、数学的表現を進化させる。
ES-MCTSコントローラは、堅牢なUCTコントローラを含む、これらの10個のインテリジェントコントローラよりも優れていることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Monte Carlo Tree Search (MCTS) is a sampling best-first method to search for
optimal decisions. The MCTS's popularity is based on its extraordinary results
in the challenging two-player based game Go, a game considered much harder than
Chess and that until very recently was considered infeasible for Artificial
Intelligence methods. The success of MCTS depends heavily on how the tree is
built and the selection process plays a fundamental role in this. One
particular selection mechanism that has proved to be reliable is based on the
Upper Confidence Bounds for Trees, commonly referred as UCT. The UCT attempts
to nicely balance exploration and exploitation by considering the values stored
in the statistical tree of the MCTS. However, some tuning of the MCTS UCT is
necessary for this to work well. In this work, we use Evolutionary Algorithms
(EAs) to evolve mathematical expressions with the goal to substitute the UCT
mathematical expression. We compare our proposed approach, called Evolution
Strategy in MCTS (ES-MCTS) against five variants of the MCTS UCT, three
variants of the star-minimax family of algorithms as well as a random
controller in the Game of Carcassonne. We also use a variant of our proposed
EA-based controller, dubbed ES partially integrated in MCTS. We show how the
ES-MCTS controller, is able to outperform all these 10 intelligent controllers,
including robust MCTS UCT controllers.
- Abstract(参考訳): Monte Carlo Tree Search (MCTS) は最適な決定を探索するためのサンプリング最優先の手法である。
mctsの人気は、チェスよりはるかに難易度が高く、最近まで人工知能の手法では実現不可能と考えられていた2人のプレイヤーによるゲームgoの驚くべき結果に基づいている。
mctsの成功は、ツリーの構築方法に大きく依存し、選択プロセスがこれにおいて基本的な役割を果たす。
信頼性が証明された特定の選択メカニズムの1つは、樹上の信頼境界(一般にUCTと呼ばれる)に基づいている。
UCTは、MCTSの統計ツリーに格納されている値を考慮することで、探索と利用のバランスを良好に保とうとしている。
しかし、mcts uctのチューニングは、これがうまく機能するためには必要である。
本研究では、進化的アルゴリズム(EA)を用いて、UTTの数学的表現に代えて数学的表現を進化させる。
提案手法であるmcts(es-mcts)と,mcts uctの5つの変種,star-minimax系アルゴリズムの3つの変種,およびcarcassonneゲームにおけるランダムコントローラを比較した。
また、提案したEAベースのコントローラの変種であるESを部分的にMCTSに統合する。
ES-MCTSコントローラは、頑健なMCTS UCTコントローラを含む、これらの10個のインテリジェントコントローラよりも優れた性能を発揮することを示す。
関連論文リスト
- Can Large Language Models Play Games? A Case Study of A Self-Play
Approach [61.15761840203145]
LLM(Large Language Models)は、インターネットからの広範なデータを利用して、幅広い事前知識を格納する。
Monte-Carlo Tree Search (MCTS)は、信頼性の高い意思決定ソリューションを提供する検索アルゴリズムである。
この研究は、ターンベースのゼロサムゲームを効率的に解決するために、MCTSセルフプレイでLLMを活性化させる革新的なアプローチを導入している。
論文 参考訳(メタデータ) (2024-03-08T19:16:29Z) - An Analysis on the Effects of Evolving the Monte Carlo Tree Search Upper
Confidence for Trees Selection Policy on Unimodal, Multimodal and Deceptive
Landscapes [0.0]
モンテカルロ木探索 (MCTS) は最適決定の探索に最も適したサンプリング法である。
MCTSで特にうまく機能する選択ポリシーは、樹上の信頼境界であり、UCTと呼ばれる。
本研究は, 単項関数から多項関数, 擬似関数まで, 異なる性質の5つの関数の利用について検討する。
論文 参考訳(メタデータ) (2023-11-21T20:40:34Z) - Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。
実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
論文 参考訳(メタデータ) (2023-05-30T06:17:35Z) - 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) - Towards Understanding the Effects of Evolving the MCTS UCT Selection
Policy [0.0]
樹上信頼境界 (UCT) はモンテカルロ木探索 (MCTS) で広く使われている。
我々は,UDTの進化がマルチモーダルおよび偽装シナリオにおいてどのように有用かを示す。
論文 参考訳(メタデータ) (2023-02-07T09:50:55Z) - Evolving the MCTS Upper Confidence Bounds for Trees Using a
Semantic-inspired Evolutionary Algorithm in the Game of Carcassonne [0.0]
我々はモンテカルロ木探索(MCTS)におけるセマンティック・インスパイアされた進化的アルゴリズムを提案する。
我々は進化的アルゴリズム(EA)を用いて、木式に上信頼境界を置き換えることを目的として数学的表現を進化させる。
SIEA-MCTSは、これらの進化した表現をチューニングすることなく、UTTよりも優れた、あるいは競争的な結果をもたらす数学的表現をうまく進化させることができるかを示す。
論文 参考訳(メタデータ) (2022-08-29T13:31:06Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳(メタデータ) (2022-07-25T18:29:16Z) - Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
我々は、専門家ベースのシミュレータを使用し、MCTSのデフォルトポリシーを適用して製造プロセスに対処する。
一般的な理由は、プロセスの効率的なシミュレータが存在しないことや、MCTSをプロセスの複雑な規則に適用する際の問題があることである。
論文 参考訳(メタデータ) (2021-07-28T14:56:17Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。