問題タブ [monte-carlo-tree-search]

MCTSを使用してConnect6でプログラミングしています。

モンテカルロ木探索は、ランダム移動に基づいています。特定の動きでの勝利数をカウントアップします。(3ターンで勝つか、30ターンで勝つか)

ターン数の少ない技はターン数の多い技よりも強力ですか？だとしたら、ターン数の少ない方を重視することに意味はあるのでしょうか？

私はPythonでツリーサーチを実装していますが、これは私の使用を遅らせる方法です。どうすればこれをより速く実行できますか? numba があることを読んだことがありますが、それがどのように機能するのか、何をサポートできるのか、何をサポートできないのかについて理解できません。ツリーサーチを高速化するために numba を使用した人はいますか? よろしくお願いします！

Silver et al (2012) "Temporal-Difference Search in Computer Go"を読んで、適格性トレース アルゴリズムの更新順序を理解しようとしています。この論文のアルゴリズム 1 と 2 では、適格性トレースを更新する前に重みが更新されます。この順序は正しいのだろうか(アルゴリズム1の11行目と12行目、アルゴリズム2の12行目と13行目)。の極端なケースを考えるとlambda=0、パラメーターは初期状態とアクションのペアで更新されません (eはまだ 0 であるため)。したがって、順序が逆になる可能性があるとは思えません。

誰かがポイントを明確にすることができますか?

この論文は強化学習領域を学ぶ上で非常に参考になると思うので、この論文を詳細に理解したいと思います。

この質問をするのに適したプラットフォームがあれば、それも教えてください。

プログラムを実行すると、次のエラーが表示されます。

同じ MCTS コードを 3x3 ボード サイズに使用しましたが、これはクラッシュせず、競争力のある動きをすばやく返します。しかし、15x15 のボード サイズで使用しようとすると、1235 回の反復後にゲームがクラッシュし、上記のエラーが表示されます。

1235回の反復後にノードの拡張を許可しないことで、問題の症状に対処したと思います。これは最終的に競争力のある動きを返しますが、これが起こるまでには長い時間がかかります.

私にとって根本的な原因は、作成しようとしているツリーのサイズです。これは、同じコードが 3x3 ボードでは機能しましたが、15x15 ボードでは機能しなかったためです。すべてのノード オブジェクトを含むツリーのサイズが大きすぎます。したがって、これは私のコーディングではなく、このアプローチの問題です。

x回の繰り返しの後、ノードにy回アクセスしたが勝利スコアがz未満の場合、そのノードを削除します。私の考えでは、x回の反復の後、y回訪問されてもまだ勝利スコアが低い場合、このノードはツリー内の不要なスペースを占有している可能性が高いため、削除する余裕があります.

私の質問は：

拡張の数を減らすだけでなく、上記のチェックを実装する必要もなく、プログラムがクラッシュするのではなく移動を返すためのより良い方法はありますか? (最善の手の計算に時間がかかる場合でも)。

これが私の未編集のコードの一部です：

編集済み** MCTS 拡張機能:

MCTSPlayer 関数:

以下に新たに含まれる**

最初のノード関数を選択します (移動リストのサイズが == から 0 になるまで続行します):

"+initialNode.childrenList()); //System.out.println("残りの移動可能なノード: "+initialNode.getPossibleMovesSize()); } return initialNode; }

機能を選択:

childrenLeft 関数:

t=1,...,40 周期の有限地平線決定問題について研究しています。時間ステップ t ごとに、エージェントが状態 s(t) ∈ S(t) にある間、(唯一の) エージェントはアクション a(t) ∈ A(t) を選択する必要があります。状態 s(t) で選択されたアクション a(t) は、次の状態 s(t+1) への遷移に影響します。したがって、有限地平線マルコフ決定問題があります。

私の場合、A(t)=A および S(t)=S が成り立ち、A のサイズは 6 000 000 で、S のサイズは 10^8 です。さらに、遷移関数は確率的です。

私はモンテカルロ木探索 (MCTS) の理論に比較的慣れていないので、自問自答します: MCTS は私の問題に適した方法ですか (特に、A と S のサイズが大きく、確率的遷移関数が原因でしょうか?)

私はすでに MCTS に関する多くの論文を読みました (たとえば、progressiv widening と double progressiv widening は非常に有望に思えます) が、MCTS を同様の問題に適用した経験について、またはこの問題に対する適切な方法について教えてくれる人がいるかもしれません (大きな状態で) /アクション空間と確率的遷移関数)。