用蒙特卡罗树搜索算法在人工智能中击败2048(及其他游戏)

我最近参与了一个名为Jupiter的开源项目，这是一个在线人工智能，旨在击败流行的在线游戏2048。

在编写这款人工智能时，我决定使用一种称为蒙特卡洛树搜索(MCTS)算法的机器学习方法。蒙特卡洛算法(Monte Carlo Algorithm)与木星(Jupiter)中使用的算法一样，已经在几个著名的人工智能领域得到了应用，包括DeepMind&39；的AlphaGo，它在2017年5月击败了围棋世界冠军阿尔法围棋(AlphaGo)。

注意：我从这个StackOverflow答案中得到了使用蒙特卡罗方法击败2048的想法。

蒙特卡罗方法是使用大量的随机模拟实验来洞察实验的最终结果的想法。实验的随机模拟通常被称为蒙特卡罗模拟。

例如，假设您正在抛硬币，并试图计算硬币落地的概率。用蒙特卡罗方法，我们可以模拟10,000次投掷硬币，并计算出硬币头部落地的百分比。

可以看出，结果收敛到预期值50%。蒙特卡罗模拟的一个显著特点是，模拟次数越多，精度越高。例如，如果我们只执行两个模拟，则两个模拟中头部落地的概率都很高(25%)，结果为100%。与50%的预期结果相比，这是非常不准确的。

如果多次模拟同一实验，则结果的平均值应该会收敛到模拟的期望值。

换句话说，蒙特卡罗模拟是一种估计给定实验中会发生什么的方法，而不必实现任何特定的算法或启发式算法。

蒙特卡罗方法被用于各种领域，包括游戏人工智能开发、金融和经济以及进化生物学等。

蒙特卡罗方法在任何带有随机因素的实验中都是有用的，在这些实验中，最终结果不能通过算法来预测。例如，在2048年，每次移动后都会在随机位置添加一个新的瓷砖，这使得无法计算即将到来的瓷砖的确切位置以及随后的游戏最终结果。

在这些类型的实验中，运行大量的蒙特卡罗模拟可以帮助获得平均最终结果的感觉，各种事件发生的概率，以及实验中变量之间的关系。

例如，使用蒙特卡罗方法来研究木星，可以让我更好地理解诸如开始走法、游戏中的走法次数和棋盘中最好的棋子等变量是如何影响游戏的最终结果的。

游戏状态：棋盘上的一组方块，代表特定时间的棋盘。

真正的游戏：在浏览器上玩和显示的游戏，而不是模拟。

在任何给定的游戏状态下，让我们假设可以进行四种可能的移动：左、右、上或下。

确实存在某些情况，在给定的游戏状态下某一步是不可能的。删除不可能的移动稍后可以很容易地添加到算法中。

使用蒙特卡罗方法，我们可以对每一步都运行一组游戏模拟。

对于每个可能的移动，程序都会模拟一组模拟，这些模拟首先播放该集的移动。在此之后，游戏的其余部分可以完全随机进行，直到游戏结束。

//假设游戏对象存在//假设currentGame变量作为真实的gameconst totalSimulations=200；//为每一步可能的移动播放50个模拟Const Moves=["；Left"；，"；Right"；，"；Down"；，"；Up"；]；possibleMoves.forEach(Move)=>；{//模拟所有四个可能的开始移动(设i=。//创建模拟模拟.board=currentGame.board；//将当前游戏状态复制到模拟模拟.makeMove(Move)；//(！Simulation ation.GameOver()){simulation.makeMove(possibleMoves[Math.floor(Math.random()*4)])；}//随机移动，直至模拟游戏结束}})；

在所有模拟完成后，程序可以收集所有模拟的最终游戏总分，并对每一步进行平均。然后，我们可以通过优化以获得最高的最终游戏分数来找到最优的走法。

例如，如果从左侧开始的模拟的最终平均得分为250，而通过玩其他动作开始的模拟的最终平均得分为225，则左侧是最优的移动。

在本程序中，最优的走法是具有最高平均最终游戏分数的模拟的走法。

注意：我可以选择针对不同的值进行优化，例如游戏中的移动次数。

然而，这实际上不会对算法的功能产生影响，因为游戏中的移动次数几乎准确地预测了游戏分数。在2048年，每次游戏移动后添加的新瓷砖通常是2个瓷砖，但有10%的机会变成4个瓷砖。这意味着新平铺的期望值为2.2(2×90%+4×10%)。每次拼贴组合后，拼贴的总值也会保留(例如：2拼贴与另外2拼贴组合为4拼贴)。因此，可以通过将新瓦片的期望值乘以游戏中的移动次数来计算游戏分数，或者使用以下公式来计算游戏分数：2.2×(实际游戏移动计数+平均移动计数)。

要将优化最高分数的功能添加到我们当前的代码中：为每个可能的移动添加模拟的最终总分数组，并选择该数组中值最高的移动，如下所示：

Const PossibleMoves=["；Left"；，"；Right"；，"；Down"；，"；Up"；]；Const totalSimulations=200；let moveSimulationTotalScores=[0，0，0，0]；PossibleMoves.forEach((Move，moveIndex)=>；{//模拟所有四个可能的开始移动(设i=0；//将当前游戏状态复制到模拟模拟.makeMove(Move)；//在(！Simulation ation.Gameover()){simulation.makeMove(possibleMoves[Math.floor(Math.random()*4)])时进行初始移动；}//进行随机移动，直到模拟游戏结束SimulationTotalScores[moveIndex]+=Simulation ation.getScore()；}})；//进行模拟总得分最高的最佳移动topScore=Math.max(...moveSimulationTotalScores)；让topScores。

最后，给出了一个写得很好的2048游戏类，该算法很容易实现。在JavaScript中，可以进行许多性能升级，首先是添加Web Worker的并发性，然后删除最终游戏分数非常低的移动。

我希望您喜欢这篇文章，并发现它有助于您在自己的项目中理解和实现蒙特卡罗方法。