1概要

この記事では、MCTS(Monte Carlo Tree Search)アルゴリズムとその応用について説明します。

Tic-Tac-ToeのゲームをJavaで実装することで、フェーズの詳細を見ていきましょう。最小限の変更で、他の多くの実用的なアプリケーションで使用できる一般的なソリューションを設計します。


2前書き

簡単に言えば、モンテカルロツリー検索は確率的検索アルゴリズムです。

これは、無限の可能性を秘めたオープンエンド環境での効率のため、独自の意思決定アルゴリズムです。

あなたがすでにhttps://en.wikipedia.org/wiki/Minimax[Minimax]のようなゲーム理論のアルゴリズムに精通しているならば、それは現在の状態を評価するための関数を必要とします、そしてそれは見つけるためにゲームツリーの多くのレベルを計算しなければなりません最適な動き

残念ながら、https://en.wikipedia.org/wiki/Go__(game)[Go]のような高い分岐係数があるゲームでは、これを実行することは不可能です。そして、現在の状態がどれだけ良いかを計算するための良い評価関数を書くことは困難です。

  • モンテカルロツリー検索はhttps://en.wikipedia.org/wiki/Monte

    Carlo

    method[モンテカルロ法]をゲームツリー検索に適用します。それはゲーム状態の無作為抽出に基づいているので、それは各可能性からその方法を強引に強制する必要はありません。また、必ずしも評価や優れたヒューリスティック関数を記述する必要はありません。

そして、ちょっとしたメモ – それはコンピュータ囲碁の世界に革命をもたらしました。

2016年3月以降、Googleのhttps://en.wikipedia.org/wiki/AlphaGo[AlphaGo](MCTSとニューラルネットワークを使用して構築された)がhttps://en.wikipedia.org/wiki/を打破したことで、流行している研究トピックになりました。 Lee__Sedol[Lee Sedol](Goの世界チャンピオン)。


3モンテカルロ木探索アルゴリズム

それでは、アルゴリズムがどのように機能するのかを探りましょう。最初に、ルートノードを使用して先読みツリー(ゲームツリー)を構築してから、ランダムロールアウトを使用して拡張します。このプロセスでは、各ノードの訪問数と獲得数を管理します。

最後に、最も有望な統計情報を持つノードを選択します。

アルゴリズムは4つのフェーズで構成されています。それらすべてを詳細に調べてみましょう。


3.1. 選択

この初期段階では、アルゴリズムはルートノードから開始し、最大勝率でノードを選択するように子ノードを選択します。また、各ノードに公平な機会が与えられるようにします。

  • そのアイデアは、ツリーのリーフノードに到達するまで最適な子ノードを選択し続けることです** そのような子ノードを選択する良い方法は、UCT(ツリーに適用される上限信頼限界)formula:link:/uploads/formula .png[]どの



  • _w




    i_

    〜= i番目の移動後の勝ち


  • __n




    i

    〜=

    i__番目の移動後のシミュレーション数


  • c

    =探査パラメータ(理論的には√2に等しい)


  • t

    =親ノードのシミュレーションの総数

公式は、どの国も飢餓の犠牲者になることはなく、それはまた彼らの対応するものよりも有望な分岐を演じることを保証する。


3.2. 拡張

後続ノードを見つけるためにUCTを適用できなくなると、リーフノードからすべての可能な状態を追加することによってゲームツリーを拡張します。


3.3. シミュレーション

拡張後、アルゴリズムは任意に子ノードを選択し、それがゲームの結果の状態に達するまで選択されたノードからランダム化されたゲームをシミュレートします。プレイアウト中にノードがランダムまたはセミランダムに選択された場合、それはライトプレイアウトと呼ばれます。質の高いヒューリスティックや評価関数を書くことで、重いプレイアウトを選ぶこともできます。


3.4. バックプロパゲーション

これは更新フェーズとも呼ばれます。アルゴリズムがゲームの終わりに達すると、それは状態を評価してどのプレイヤーが勝ったかを把握します。それはルートまで上方にトラバースし、全ての訪問ノードについて訪問スコアを増加させる。その位置のプレーヤーがプレイアウトに勝った場合、それは各ノードの勝利得点も更新します。

MCTSは、一定の反復回数または一定の時間が経過するまで、これら4つのフェーズを繰り返します。

このアプローチでは、ランダムな移動に基づいて各ノードの勝利スコアを推定します。繰り返し回数が多いほど、推定の信頼性は高くなります。アルゴリズムの推定値は、検索の開始時にはそれほど正確ではなくなり、十分な時間が経過すると改善され続けます。

これもまた問題の種類にのみ依存します。


4ドライラン

リンク:/uploads/legend.png[]

ここでは、ノードには総訪問数/勝利スコアとして統計が含まれています。


5実装

それでは、モンテカルロツリー検索アルゴリズムを使用して、Tic-Tac-Toeゲームを実装しましょう。

他の多くのボードゲームにも利用できる、MCTS用の一般化されたソリューションを設計します。記事自体のコードの大部分を見ていきましょう。

説明を簡潔にするために、いくつかの細かい詳細(特にMCTSには関係ありません)をスキップする必要があるかもしれませんが、完全な実装https://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneousをいつでも見つけることができます。 -1[ここ]。

まず、ツリー検索機能を持つためには、

Tree

クラスと

Node

クラスの基本的な実装が必要です。

public class Node {
    State state;
    Node parent;
    List<Node> childArray;
   //setters and getters
}
public class Tree {
    Node root;
}

各ノードには特定の問題があるので、

State

クラスも実装しましょう。

public class State {
    Board board;
    int playerNo;
    int visitCount;
    double winScore;

   //copy constructor, getters, and setters

    public List<State> getAllPossibleStates() {
       //constructs a list of all possible states from current state
    }
    public void randomPlay() {
       /**  get a list of all possible positions on the board and
           play a random move ** /    }
}

それでは、

MonteCarloTreeSearch

クラスを実装しましょう。これは、与えられたゲームポジションから次に良い動きを見つけるための責任があります。

public class MonteCarloTreeSearch {
    static final int WIN__SCORE = 10;
    int level;
    int opponent;

    public Board findNextMove(Board board, int playerNo) {
       //define an end time which will act as a terminating condition

        opponent = 3 - playerNo;
        Tree tree = new Tree();
        Node rootNode = tree.getRoot();
        rootNode.getState().setBoard(board);
        rootNode.getState().setPlayerNo(opponent);

        while (System.currentTimeMillis() < end) {
            Node promisingNode = selectPromisingNode(rootNode);
            if (promisingNode.getState().getBoard().checkStatus()
              == Board.IN__PROGRESS) {
                expandNode(promisingNode);
            }
            Node nodeToExplore = promisingNode;
            if (promisingNode.getChildArray().size() > 0) {
                nodeToExplore = promisingNode.getRandomChildNode();
            }
            int playoutResult = simulateRandomPlayout(nodeToExplore);
            backPropogation(nodeToExplore, playoutResult);
        }

        Node winnerNode = rootNode.getChildWithMaxScore();
        tree.setRoot(winnerNode);
        return winnerNode.getState().getBoard();
    }
}

ここでは、事前定義された時間まで4つのフェーズすべてを繰り返し続け、最後に、信頼できる統計を持つツリーを作成して賢い決定を下します。

それでは、すべてのフェーズに対してメソッドを実装しましょう。

  • 私たちはUCTの実装も必要とする** 選択フェーズから始めます。

private Node selectPromisingNode(Node rootNode) {
    Node node = rootNode;
    while (node.getChildArray().size() != 0) {
        node = UCT.findBestNodeWithUCT(node);
    }
    return node;
}

public class UCT {
    public static double uctValue(
      int totalVisit, double nodeWinScore, int nodeVisit) {
        if (nodeVisit == 0) {
            return Integer.MAX__VALUE;
        }
        return ((double) nodeWinScore/(double) nodeVisit)
          + 1.41 **  Math.sqrt(Math.log(totalVisit)/(double) nodeVisit);
    }

    public static Node findBestNodeWithUCT(Node node) {
        int parentVisit = node.getState().getVisitCount();
        return Collections.max(
          node.getChildArray(),
          Comparator.comparing(c -> uctValue(parentVisit,
            c.getState().getWinScore(), c.getState().getVisitCount())));
    }
}

このフェーズでは、展開フェーズでさらに展開する必要があるリーフノードを推奨します。

private void expandNode(Node node) {
    List<State> possibleStates = node.getState().getAllPossibleStates();
    possibleStates.forEach(state -> {
        Node newNode = new Node(state);
        newNode.setParent(node);
        newNode.getState().setPlayerNo(node.getState().getOpponent());
        node.getChildArray().add(newNode);
    });
}

  • 次に、ランダムなノードを選択し、そこからランダムに再生するようにシミュレートするコードを作成します。

private void backPropogation(Node nodeToExplore, int playerNo) {
    Node tempNode = nodeToExplore;
    while (tempNode != null) {
        tempNode.getState().incrementVisit();
        if (tempNode.getState().getPlayerNo() == playerNo) {
            tempNode.getState().addScore(WIN__SCORE);
        }
        tempNode = tempNode.getParent();
    }
}
private int simulateRandomPlayout(Node node) {
    Node tempNode = new Node(node);
    State tempState = tempNode.getState();
    int boardStatus = tempState.getBoard().checkStatus();
    if (boardStatus == opponent) {
        tempNode.getParent().getState().setWinScore(Integer.MIN__VALUE);
        return boardStatus;
    }
    while (boardStatus == Board.IN__PROGRESS) {
        tempState.togglePlayer();
        tempState.randomPlay();
        boardStatus = tempState.getBoard().checkStatus();
    }
    return boardStatus;
}

これでMCTSの実装は完了です。必要なのはTic-Tac-Toe特有の

Board

クラスの実装だけです。私たちの実装で他のゲームをプレイすることに注意してください。

Board

クラスを変更するだけです。

public class Board {
    int[][]boardValues;
    public static final int DEFAULT__BOARD__SIZE = 3;
    public static final int IN__PROGRESS = -1;
    public static final int DRAW = 0;
    public static final int P1 = 1;
    public static final int P2 = 2;

   //getters and setters
    public void performMove(int player, Position p) {
        this.totalMoves++;
        boardValues[p.getX()][p.getY()]= player;
    }

    public int checkStatus() {
       /**  Evaluate whether the game is won and return winner.
           If it is draw return 0 else return -1 ** /
    }

    public List<Position> getEmptyPositions() {
        int size = this.boardValues.length;
        List<Position> emptyPositions = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (boardValues[i][j]== 0)
                    emptyPositions.add(new Position(i, j));
            }
        }
        return emptyPositions;
    }
}

私達はちょうどTic-Tac-Toeで打ち負かすことができないAIを実装しました。 AIとAIが常に引き分けになることを示すユニットケースを書きましょう。

@Test
public void givenEmptyBoard__whenSimulateInterAIPlay__thenGameDraw() {
    Board board = new Board();
    int player = Board.P1;
    int totalMoves = Board.DEFAULT__BOARD__SIZE **  Board.DEFAULT__BOARD__SIZE;
    for (int i = 0; i < totalMoves; i++) {
        board = mcts.findNextMove(board, player);
        if (board.checkStatus() != -1) {
            break;
        }
        player = 3 - player;
    }
    int winStatus = board.checkStatus();

    assertEquals(winStatus, Board.DRAW);
}


6. メリット

  • それは必ずしもゲームについての戦術的な知識を必要としません

  • 一般的なMCTSの実装は任意の数のゲームに再利用できます。

少し修正して
** ゲームに勝つ可能性が高いノードに焦点を当てます

  • 無駄にならないので高い分岐係数の問題に適して

すべての可能性のある枝での計算
** アルゴリズムは実装がとても簡単です

  • 実行はいつでも停止することができます、そしてそれはまだ提案します

これまでに計算された次善の状態


7. 欠点

MCTSが基本的な形で何も改善されずに使用されている場合、合理的な動きを示唆するのに失敗するかもしれません。ノードが適切に訪問されないと、不正確な見積もりが発生する可能性があります。

  • ただし、MCTSはいくつかの手法を使用して改善できます。これには、ドメイン固有の手法とドメインに依存しない手法が含まれます。

ドメイン固有の手法では、シミュレーション段階では確率的シミュレーションよりもリアルなプレイアウトが行われます。それはゲーム特有のテクニックとルールの知識を必要としますが。


8概要

一見したところでは、ランダムな選択に依存するアルゴリズムがスマートAIにつながる可能性があることを信頼するのは困難です。しかし、MCTSを慎重に実装することで、意思決定の問題と同様に多くのゲームで使用できるソリューションを実際に提供できます。

いつものように、このアルゴリズムの完全なコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[GitHubへの追加]にあります。