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 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 getAllPossibleStates() {
// constructs a list of all possible states from current state }
public void randomPlay() {
/* get a list of all possible positions on the board andplay 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 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 getEmptyPositions() {
int size = this.boardValues.length;
List 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，它不能在井字游戏中被打败。 我们来写一个测试用例，它证明人工智能与人工智能总是会产生平局：
@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);
}
5.优势不需要有关游戏的战术知识。
一般的MCTS实现可以在很少修改的情况下重用于任意的游戏。
专注于获胜的可能性更大的节点。
适用于高分支率的问题，因为它不会浪费所有可能分支上的计算。
执行可以在任何给定的时间停止，它仍然会建议到目前为止计算的下一个最佳状态。
6.缺点
如果MCTS的基本形式没有任何改进，它可能无法给出合理的动作。 如果没有充分访问节点会导致估算不准确，则可能会发生这种情况。
但是，使用一些技术可以改进MCTS。 它涉及特定领域以及领域独立技术。
在特定领域的技术中，模拟阶段产生更真实的播出而不是随机模拟。 虽然它需要游戏特定技术和规则的知识。
7.总结
乍看之下，很难相信依靠随机选择的算法会带来AI。 然而，MCTS的深思熟虑的实施确实可以为我们提供一种可用于许多游戏以及决策问题的解决方案。