蒙特卡洛树
1. 概述
在本文中，我们将探讨蒙特卡罗树搜索 （MCTS） 算法及其应用。
我们将通过在Java 中实现井字游戏来详细研究它的阶段。我们将设计一个通用解决方案，该解决方案可用于许多其他实际应用，只需进行最少的更改。
2. 简介
简单地说，蒙特卡罗树搜索是一种概率搜索算法。它是一种独特的决策算法，因为它在具有巨大可能性的开放式环境中的效率。
如果您已经熟悉像 Minimax 这样的博弈论算法，它需要一个函数来评估当前状态，并且它必须在游戏树中计算许多级别才能找到最佳移动。
不幸的是，在像围棋这样分支因子很高的游戏中这样做是不可行的（随着树的高度增加，导致数百万种可能性），并且很难编写一个好的评估函数来计算当前状态有多好。
蒙特卡罗树搜索将蒙特卡罗方法应用于游戏树搜索。由于它基于游戏状态的随机抽样，因此不需要暴力破解每种可能性。此外，它不一定要求我们编写评估或良好的启发式函数。
自 2016 年 3 月以来，随着谷歌的AlphaGo（由 MCTS 和神经网络构建）击败李世石（围棋世界冠军），它已成为一个流行的研究课题。
3. 蒙特卡洛树搜索算法
现在，让我们探讨一下该算法的工作原理。最初，我们将构建一个具有根节点的展望树（游戏树），然后我们将通过随机推出继续扩展它。在此过程中，我们将维护每个节点的访问计数和获胜计数。
最后，我们将选择具有最有希望的统计数据的节点。
该算法由四个阶段组成;让我们详细探讨所有这些。
3.1. 选择
在此初始阶段，算法从根节点开始，然后选择一个子节点，以便选取获胜率最高的节点。我们还希望确保每个节点都有公平的机会。
这个想法是继续选择最佳子节点，直到我们到达树的叶节点。选择此类子节点的一个好方法是使用 UCT（应用于树的置信上限）公式：
其中
Wi =第i步后获胜的次数
Ni =第i步后的模拟次数
C =勘探参数(理论上等于√2)
T =父节点的模拟总数
该公式确保没有状态会成为受害者，并且它也比同类更频繁地发挥有前途的分支。
3.2. 扩展
当它无法再应用 UCT 来查找后续节点时，它会通过附加叶节点中的所有可能状态来扩展游戏树。
3.3. 模拟
扩展后，算法任意选取一个子节点，从所选节点模拟随机博弈，直到达到博弈的结果状态。如果在播放过程中随机或半随机选择节点，则称为轻度播放。您还可以通过编写质量启发式或评估函数来选择繁重的播放。
3.4. 反向传播
这也称为更新阶段。一旦算法到达游戏结束，它就会评估状态以确定哪个玩家赢了。它向上遍历到根，并增加所有访问过的节点的访问分数。如果该位置的玩家赢得了播出，它还会更新每个节点的获胜分数。
MCTS 不断重复这四个阶段，迭代直到固定的次数或固定的时间量。
在这种方法中，我们根据随机移动来估计每个节点的获胜分数。因此，迭代次数越高，估计就越可靠。算法估计在搜索开始时不太准确，并在足够长的时间后继续改进。同样，这完全取决于问题的类型。
4. 演练
在这里，节点包含总访问/获胜分数的统计信息。
5. 实施
现在，让我们实现一个井字游戏 - 使用蒙特卡洛树搜索算法。
我们将为 MCTS 设计一个通用解决方案，该解决方案也可用于许多其他棋盘游戏。下面是大部分核心代码。
首先，我们需要一个基本的实现，让Tree和Node类具有树搜索功能：
代码语言：javascript代码运行次数：0运行复制public class Node {
State state;
Node parent;
List<Node> childArray;
// setters and getters
}
public class Tree {
Node root;
}Copy由于每个节点都有特定的问题状态，让我们也实现一个State类：
代码语言：javascript代码运行次数：0运行复制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 */
}
}Copy现在，让我们实现MonteCarloTreeSearch类，该类将负责从给定的游戏位置查找下一个最佳移动：
代码语言：javascript代码运行次数：0运行复制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();
}
}Copy在这里，我们不断迭代所有四个阶段，直到预定义的时间，最后，我们得到一个具有可靠统计数据的树来做出明智的决策。
现在，让我们实现所有阶段的方法。
我们将从选择阶段开始，这也需要 UCT 实现：
代码语言：javascript代码运行次数：0运行复制private Node selectPromisingNode(Node rootNode) {
Node node = rootNode;
while (node.getChildArray().size() != 0) {
node = UCT.findBestNodeWithUCT(node);
}
return node;
}Copypublic 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(),
Comparatorparing(c -> uctValue(parentVisit,
c.getState().getWinScore(), c.getState().getVisitCount())));
}
}Copy此阶段建议使用应在扩展阶段进一步扩展的叶节点：
代码语言：javascript代码运行次数：0运行复制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);
});
}Copy接下来，我们编写代码来选择一个随机节点并模拟从中随机播放。此外，我们将有一个更新函数来传播从叶到根的分数和访问计数：
代码语言：javascript代码运行次数：0运行复制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;
}Copy现在我们已经完成了 MCTS 的实施。我们所需要的只是一个井字游戏特定的Board类实现。请注意，使用我们的实现玩其他游戏;我们只需要更Board类。
代码语言：javascript代码运行次数：0运行复制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;
}
}Copy我们刚刚实现了一个在井字游戏中无法击败的AI。让我们写一个单位案例来证明 AI vs.AI 总是会导致平局：
代码语言：javascript代码运行次数：0运行复制@Test
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);
}Copy6. 优势
- 它不一定需要任何关于游戏的战术知识
- 通用的 MCTS 实现可以重用于任意数量的游戏，只需进行少量修改
- 专注于赢得游戏机会较高的节点
- 适用于高分支因子的问题，因为它不会浪费所有可能的分支上的计算
- 算法非常容易实现
- 可以在任何给定时间停止执行，它仍然会建议到目前为止计算的下一个最佳状态
7. 缺点
如果 MCTS 以基本形式使用而没有任何改进，则可能无法提出合理的举措。如果没有充分访问节点，导致估计不准确，则可能会发生这种情况。
但是，可以使用一些技术来改善 MCTS。它涉及特定于领域的技术以及独立于领域的技术。
在特定领域的技术中，模拟阶段产生更真实的播放，而不是随机模拟。虽然它需要了解游戏特定的技术和规则。
8. 总结
乍一看，很难相信依赖随机选择的算法可以带来智能人工智能。然而，深思熟虑的MCTS实施确实可以为我们提供一种解决方案，可用于许多游戏以及决策问题。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2023-02-17，如有侵权请联系 cloudcommunity@tencent 删除算法游戏函数解决方案搜索
发布评论