20

ツリーの作り方を教えてください。

ノードがどのように選択されるかはよく理解できましたが、より適切な説明があれば、このアルゴリズムを実装するのに本当に役立ちます。ゲームの状態を表すボードは既に持っていますが、ツリーの生成方法がわかりません。

アルゴリズムのよくコメントされた実装を教えてもらえますか (AI に使用する必要があります)。または、より良い説明/例はありますか?

ネット上で多くのリソースが見つかりませんでした。このアルゴリズムはかなり新しいものです...

4

3 に答える 3

24

ツリーを生成する最良の方法は、一連のランダムなプレイアウトです。秘訣は、探索と搾取のバランスを取ることです (ここで UCT の出番です)。ここには、いくつかの優れたコード サンプルと多数の研究論文の参照があります。

アルゴリズムを実装したとき、エンドポイントまたは終了状態に到達するまで、ランダム再生を使用しました。この時点でペイオフを計算する静的評価関数があり、この時点からのスコアがツリーに反映されます。各プレイヤーまたは「チーム」は、他のチームが自分たちにとって最善の動きをし、対戦相手にとって最悪の動きをすることを前提としています。

Chaslot の論文と彼の博士論文、および彼の研究 (基本的にそれ以降のすべての MCTS の研究) を参照するいくつかの研究もチェックすることをお勧めします。

例: プレーヤー 1 の最初の動きは、プレーヤー 1 の動きとプレーヤー 2 の動きを交互に繰り返す未来への 10 の動きをシミュレートできます。対戦相手が自分のスコアを最大化しながら、あなたのスコアを最小化しようとすることを毎回想定する必要があります。ゲーム理論として知られる、これに基づく分野全体があります。10 ゲームの最後までシミュレートしたら、再び開始点から繰り返します (1 セットの決定のみをシミュレートする意味がないため)。ツリーのこれらのブランチのそれぞれは、スコアがツリーを上って伝播する場所でスコアリングする必要があり、スコアは、他のプレーヤーも自分自身に最適な動きを選択していると仮定して、シミュレートを行うプレーヤーにとって可能な限り最高の利益を表します。

MCTS は、時間がある限り繰り返される 4 つの戦略的ステップで構成されます。手順は次のとおりです。

  1. 選択ステップでは、ツリーはルート ノードからノード E に到達するまでトラバースされます。ノード E では、まだツリーに追加されていない位置を選択します。

  2. 次に、プレイアウトステップの間、ゲームの終わりに到達するまで、セルフプレイで動きがプレイされます。この「シミュレートされた」ゲームの結果 R は、黒 (LOA の最初のプレーヤー) の勝利の場合は +1、引き分けの場合は 0、白の勝利の場合は -1 です。

  3. 続いて、拡張ステップで、E の子がツリーに追加されます。

  4. 最後に、バックプロパゲーション ステップで、E からルート ノードまでのパスに沿って R が伝播されます。時間切れになると、プログラムによって実行される手は、最高値を持つルートの子になります。(この例は、このペーパーからの抜粋です - PDF

www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf

いくつかの実装を次に示します。

一部の MCTS 実装を使用するライブラリとゲームのリスト http://senseis.xmp.net/?MonteCarloTreeSearch

Fuego と呼ばれるゲームに依存しないオープン ソース UCT MCTS ライブラリ http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html

于 2012-01-30T00:47:24.513 に答える
3

http://mcts.ai/code/index.htmlから:

Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

ジャワ

パイソン

于 2014-04-05T19:16:21.077 に答える
3

あなたが興味を持っているなら、私はこれを書きました: https://github.com/avianey/mcts4j

于 2015-03-02T12:43:54.300 に答える