Javaでの三目並べゲームのモンテカルロ木探索

投稿日: 2019-10-18 2022-10-28
タグ: Algorithms, Data Structures

1. 概要

この記事では、モンテカルロ木探索（MCTS）アルゴリズムとそのアプリケーションについて説明します。

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

2. 序章

簡単に言えば、モンテカルロ木探索は確率的探索アルゴリズムです。これは、非常に多くの可能性を秘めたオープンエンド環境での効率性のため、独自の意思決定アルゴリズムです。

Minimax のようなゲーム理論アルゴリズムに既に精通している場合は、現在の状態を評価する関数が必要であり、最適な動きを見つけるためにゲームツリーの多くのレベルを計算する必要があります。

残念ながら、 Go のように分岐係数が高く（木の高さが高くなると何百万もの可能性があります）、良い評価を書くのが難しいゲームではそうすることができません。現在の状態がどれだけ良いかを計算する関数。

モンテカルロ木探索は、ゲーム木探索にモンテカルロ法を適用します。ゲームの状態のランダムなサンプリングに基づいているため、それぞれの可能性からブルートフォース攻撃を行う必要はありません。また、必ずしも評価や優れたヒューリスティック関数を作成する必要はありません。

そして、簡単な補足–それはコンピュータGoの世界に革命をもたらしました。 2016年3月以降、Googleの AlphaGo （MCTSとニューラルネットワークで構築）が Lee Sedol （Goの世界チャンピオン）を打ち負かすにつれて、これは一般的な研究トピックになりました。

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

それでは、アルゴリズムがどのように機能するかを見てみましょう。最初に、ルートノードを使用して先読みツリー（ゲームツリー）を構築し、次にランダムなロールアウトで拡張し続けます。その過程で、各ノードの訪問数と勝者数を維持します。

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

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

3.1. 選択

この初期フェーズでは、アルゴリズムはルートノードから開始し、最大の勝率を持つノードを選択するように子ノードを選択します。また、各ノードに公平なチャンスが与えられるようにしたいのです。

ツリーのリーフノードに到達するまで、最適な子ノードを選択し続けるという考え方です。このような子ノードを選択する良い方法は、UCT（ツリーに適用されるUpper Confidence Bound）式を使用することです。その中で

w _i = i番目の移動後の勝利数
n _i = i番目の移動後のシミュレーションの数
c =探索パラメーター（理論的には√2に等しい）
t=親ノードのシミュレーションの総数

この公式は、どの州も飢餓の犠牲になることはなく、また、対応する州よりも頻繁に有望な支部を演じることを保証します。

3.2. 拡張

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

3.3. シミュレーション

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

3.4. 誤差逆伝播法

これは、更新フェーズとも呼ばれます。アルゴリズムがゲームの終わりに達すると、状態を評価して、どのプレーヤーが勝ったかを判断します。ルートまで上向きにトラバースし、訪問したすべてのノードの訪問スコアを増分します。また、そのポジションのプレーヤーがプレイアウトに勝った場合、各ノードの勝ちスコアを更新します。

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

このアプローチでは、ランダムな動きに基づいて各ノードの勝ちスコアを推定します。したがって、反復回数が多いほど、推定の信頼性が高くなります。アルゴリズムの推定値は、検索の開始時の精度が低くなり、十分な時間が経過しても改善され続けます。繰り返しますが、それは問題のタイプにのみ依存します。

4. ドライラン

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

5. 実装

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

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

説明をわかりやすくするために、いくつかの小さな詳細（特にMCTSに関連しない）をスキップする必要があるかもしれませんが、完全な実装ここをいつでも見つけることができます。

まず、ツリー検索機能を使用するには、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);
    });
}

次に、ランダムノードを選択してランダムな再生をシミュレートするコードを記述します。また、 update 関数を使用して、リーフからルートまでスコアと訪問数を伝播します。：

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クラスの実装だけです。私たちの実装で他のゲームをプレイすることに注意してください。 ボードクラスを変更するだけです。

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を慎重に実装することで、多くのゲームや意思決定の問題で使用できるソリューションを実際に提供できます。

いつものように、アルゴリズムの完全なコードはGitHubのにあります。

getdocs

13036