分散型 Go/Gomoku ボットを作成しています。
基本的に重要なのは、ツリー検索を多くのコンピューターに分散させることです。DFS のような基本的なツリー検索アルゴリズムを使用すると、検索スペースをサブツリーに分割するだけで済むので、これは非常に簡単です。私はむしろアルファベータプルーニングを備えたミニマックスのように、より効率的なものを望んでいますが、私の理解では、共有メモリがなければまったく無意味です。だから私はちょっと立ち往生しています。
効率的で簡単に配布できるアルゴリズムを使用できるアイデアはありますか? さらに重要なことに、その (疑似) コードまたは実装をどこで見つけることができますか?
ありがとう、
モンテカルロ木検索についてよく読む必要があります。これは、本質的に配布が容易だからではなく (別の木検索よりも簡単でも難しいわけでもありません)、それが最新技術であり、問題に取り組んでいる人々が分散に取り組んでいるからです。そのアルゴリズムのバージョン。
苦労して分散アルゴリズムを作成する場合は、より小さなアルゴリズムから始める必要はありません。教育的な理由で分散アルゴリズムを作成している場合を除き、基本的なアルゴリズムを配布して、分散されていない最先端のアルゴリズムよりもパフォーマンスが悪いことを確認する実験には、非常に教育的なものがあります。 :)
MoGoホームページ
computer go のウィキペディア ページの「最近の開発」セクションを参照してください。
Map Reduce アプローチを試してください。たとえば、次を参照してください。
DDS*とABDADAは、2 つの分散/並列ミニマックス アルゴリズムです。ある程度の通信が必要ですが、これは特定の結果をコントローラーに中継することで実現できます。
あなたが言及したように、より簡単なアプローチは、異なる検索ツリーのルートを使用した map reduce のようなものです。
@Pascal Cuoq が正しく言及しているように、Monte Carlo Tree Search は Go の最先端です。
ここでは、MoGo の検索アルゴリズムとその並列化についての適切な説明を見つけることができます。
http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf
ランダムプレイに基づいてより良い結果でプレイしているノードは、より深く調査されます。各ステップで、1 層展開用にリーフ ノードが選択されます。これは、展開する別のリーフを各マシンに選択させることで分散できます。
モンテカルロ木検索の概要は次のとおりです。
http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf