論文の概要: Monte-Carlo Graph Search for AlphaZero
- arxiv url: http://arxiv.org/abs/2012.11045v1
- Date: Sun, 20 Dec 2020 22:51:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-01 04:46:43.280059
- Title: Monte-Carlo Graph Search for AlphaZero
- Title(参考訳): alphazero に対するモンテカルログラフ探索
- Authors: Johannes Czech, Patrick Korus, Kristian Kersting
- Abstract要約: 探索木を有向非巡回グラフに一般化する,新しい改良されたalphazero探索アルゴリズムを提案する。
評価では、チェスとクレイジーハウスでCrazyAraエンジンを使用して、これらの変更がAlphaZeroに大きな改善をもたらすことを示す。
- 参考スコア(独自算出の注目度): 15.567057178736402
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The AlphaZero algorithm has been successfully applied in a range of discrete
domains, most notably board games. It utilizes a neural network, that learns a
value and policy function to guide the exploration in a Monte-Carlo Tree
Search. Although many search improvements have been proposed for Monte-Carlo
Tree Search in the past, most of them refer to an older variant of the Upper
Confidence bounds for Trees algorithm that does not use a policy for planning.
We introduce a new, improved search algorithm for AlphaZero which generalizes
the search tree to a directed acyclic graph. This enables information flow
across different subtrees and greatly reduces memory consumption. Along with
Monte-Carlo Graph Search, we propose a number of further extensions, such as
the inclusion of Epsilon-greedy exploration, a revised terminal solver and the
integration of domain knowledge as constraints. In our evaluations, we use the
CrazyAra engine on chess and crazyhouse as examples to show that these changes
bring significant improvements to AlphaZero.
- Abstract(参考訳): AlphaZeroアルゴリズムは様々な独立した領域、特にボードゲームでうまく適用されている。
それは、モンテカルロ木探索の探索を導くために、価値とポリシー関数を学ぶニューラルネットワークを利用する。
モンテカルロ木探索では、過去に多くの探索改善が提案されてきたが、そのほとんどは、計画にポリシーを使用しない木アルゴリズムの高信頼境界の古い変種を参照している。
探索木を有向非巡回グラフに一般化する,新しい改良されたalphazero探索アルゴリズムを提案する。
これにより、異なるサブツリー間の情報フローが可能になり、メモリ消費を大幅に削減できる。
モンテカルログラフ探索と並行して,epsilon-greedy exploration,修正ターミナルソルバ,制約としてのドメイン知識の統合など,さらに多くの拡張を提案する。
評価では、チェスとクレイジーハウスでCrazyAraエンジンを使用して、これらの変更がAlphaZeroに大きな改善をもたらすことを示す。
関連論文リスト
- Learning in games from a stochastic approximation viewpoint [82.74514886461257]
ゲームにおけるオンライン学習の長期的行動を分析するための統合近似フレームワークを開発した。
我々のフレームワークは,多種多様なゲーム理論学習アルゴリズムを含む,"プリマルデュアル"ミラーリングされたRobins-Monro(MRM)テンプレートに基づいている。
論文 参考訳(メタデータ) (2022-06-08T14:30:38Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3~5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳(メタデータ) (2022-05-28T06:08:07Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。
木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文 参考訳(メタデータ) (2022-01-25T17:37:34Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳(メタデータ) (2022-01-25T00:10:03Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳(メタデータ) (2022-01-18T11:16:40Z) - Structure learning in polynomial time: Greedy algorithms, Bregman
information, and exponential families [12.936601424755944]
DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。
DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。
この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
論文 参考訳(メタデータ) (2021-10-10T06:37:51Z) - Batch Monte Carlo Tree Search [9.114710429587479]
この性質に基づいて,バッチ推論を用いたモンテカルロ木探索アルゴリズムを提案する。
転置テーブルは推論の結果を含むが、検索ツリーはモンテカルロツリー検索の統計情報を含む。
また、検索を改善する複数のアルゴリズムを分析することも提案している:$mu$ fpu、仮想平均、反復、第2の移動は続く。
論文 参考訳(メタデータ) (2021-04-09T09:54:21Z) - Stabilized Nested Rollout Policy Adaptation [7.715389335184684]
Nested Rollout Policy Adaptation(NRPA)は、モンテカルロのシングルプレイヤーゲームのための検索アルゴリズムです。
アルゴリズムの安定性を向上させるため,NRPAの修正を提案する。
論文 参考訳(メタデータ) (2021-01-10T15:05:14Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳(メタデータ) (2021-01-08T18:55:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。