蒙特卡洛樹搜索簡介與實現

1.概述

本文將探討蒙特卡洛樹搜索（MCTS）演算法及其應用。

我們將通過在Java中實現井字棋來詳細分析。 我們將設計一個通用解決方案，只需很少的更改可用於許多其他實際應用中。

2. 介紹

簡而言之，蒙特卡洛樹搜索是一種概率搜索演算法。它是作出最優決策的方法，因為它在有著巨大可能性的開放式環境中高效。

是否您已經熟悉像Minimax這樣的遊戲演算法，它需要一個評估當前狀態的函數，並且必須計算遊戲樹中的許多級別才能找到最優解。

不幸的是，在像圍棋這樣的遊戲中這樣做是不可行的，因為在遊戲中存在高分支率（隨著樹的高度增加而導致數百萬的可能性），並且很難編寫好的評估函數來計算 當前狀態。

蒙特卡洛樹搜索將蒙特卡洛方法應用於遊戲樹搜索。 由於它基於對遊戲狀態的隨機抽樣，因此不需要蠻橫地排除每種可能性。 此外，它並不一定要求我們編寫評估或良好的啟發式功能。

3.演算法

最初，我們將用一個根節點構建一個前瞻樹（遊戲樹），然後我們隨機展開它。 在這個過程中，我們將記錄每個節點的訪問次數和獲勝次數。

最後，我們將選擇最有希望的節點。

該演算法由四個階段組成; 讓我們來詳細探索它們。

3.1選擇

在初始階段，演算法從一個根節點開始，並以最高勝率挑選一個子節點。 我們也想確保每個節點都有一個公平的機會。

這個思想是保持選擇最佳的子節點，直到我們到達樹的葉節點。 選擇這樣的子節點的一個好方法是使用UCT公式：

其中：

• wi =第i次移動後的獲勝數
• ni =第i次移動後的模擬次數
• c =探索參數（理論上等於√2）
• t =父節點的模擬總數。

該公式確保沒有哪個狀態會成為飢餓的受害者，並且它比對手更頻繁地發揮有前途的分支。

3.2擴展

當它不能再應用UCT來尋找後繼節點時，它通過從葉節點追加所有可能的狀態來展開遊戲樹。

3.3模擬

在擴展張之後，該演算法任意選取一個子節點，並且模擬從選定節點開始的隨機遊戲，直到它達到遊戲的最終狀態。 如果節點在播放期間被隨機或半隨機選取，則稱為輕播放。 你也可以通過編寫優質啟發式或評估函數來選擇重播放。

3.4反向傳播

這也被稱為更新階段。 一旦演算法達到遊戲結束，它就會評估狀態確定哪個玩家獲勝。 它向上遍歷根，並增加所有訪問節點的訪問分數。 如果該位置的玩家贏得了播放，它還會更新每個節點的勝利分數。

MCTS不斷重複這四個階段，直到一些固定的迭代次數或一些固定的時間量。

在這種方法中，我們根據隨機移動估計每個節點的勝利分數。 迭代次數越多，估計就越可靠。 演算法估計在搜索開始時將不太準確，並在足夠的時間後持續改進。 它僅僅取決於問題的類型。

4.實現

現在，讓我們使用蒙特卡洛樹搜索演算法來實現井字遊戲。

我們將為MCTS設計一個通用解決方案，並可用於其他許多棋盤遊戲。 我們將看看文章中的大部分代碼。

儘管為了使解釋清晰起見，我們可能不得不跳過一些小的細節（與MCTS沒有特別的關係），但總是可以在這裡找到完整的實現。

首先，我們需要樹和節點類的基本實現來實現樹搜索功能：

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(oponent); while (System.currentTimeMillis() < end) { // Phase 1 - Selection Node promisingNode = selectPromisingNode(rootNode); // Phase 2 - Expansion if (promisingNode.getState().getBoard().checkStatus() == Board.IN_PROGRESS) { expandNode(promisingNode); } // Phase 3 - Simulation Node nodeToExplore = promisingNode; if (promisingNode.getChildArray().size() > 0) { nodeToExplore = promisingNode.getRandomChildNode(); } int playoutResult = simulateRandomPlayout(nodeToExplore); // Phase 4 - Update backPropogation(nodeToExplore, playoutResult); } Node winnerNode = rootNode.getChildWithMaxScore(); tree.setRoot(winnerNode); return winnerNode.getState().getBoard(); }}

在這裡，我們不斷迭代這四個階段，直到預定義的時間，最後，我們得到一個具有可靠統計數據的樹來作出明智的決定。

現在，我們來實現所有階段的方法。

我們將從選擇階段開始，這也需要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演算法實現。 我們需要的是一個井字棋實現。 請注意，在我們的實現中玩其他遊戲; 我們只需要更改類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; }}

我們剛剛實施了一個AI，它不能在井字遊戲中被打敗。 我們來寫一個測試用例，它證明人工智慧與人工智慧總是會產生平局：

@Testpublic 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);}

5.優勢

• 不需要有關遊戲的戰術知識。
• 一般的MCTS實現可以在很少修改的情況下重用於任意的遊戲。
• 專註於獲勝的可能性更大的節點。
• 適用於高分支率的問題，因為它不會浪費所有可能分支上的計算。
• 執行可以在任何給定的時間停止，它仍然會建議到目前為止計算的下一個最佳狀態。

6.缺點

如果MCTS的基本形式沒有任何改進，它可能無法給出合理的動作。 如果沒有充分訪問節點會導致估算不準確，則可能會發生這種情況。

但是，使用一些技術可以改進MCTS。 它涉及特定領域以及領域獨立技術。

在特定領域的技術中，模擬階段產生更真實的播出而不是隨機模擬。 雖然它需要遊戲特定技術和規則的知識。

7.總結

乍看之下，很難相信依靠隨機選擇的演算法會帶來AI。 然而，MCTS的深思熟慮的實施確實可以為我們提供一種可用於許多遊戲以及決策問題的解決方案。