Scratch编程教程-游戏树

游戏树

游戏树是一种递归搜索函数，它检查策略游戏的所有可能移动及其结果，以确定最佳移动。它们在不需要实时决策并且每次游戏的可能选择相对较少的情况下对人工智能非常有用。最常见的例子是国际象棋，但它们适用于许多情况。

局限性

游戏树有几个主要的局限性。

时间

如上所述，游戏树很少用于实时场景（计算机没有很多时间来思考的情况下）。原因很快就会变得明显，简而言之：这种方法需要计算机进行大量的处理，这需要时间。

出于上述原因（以及其他原因），它们在回合制游戏中表现最佳。

它们需要完全了解如何移动。

具有不确定性的游戏通常与游戏树不兼容。它们可以在此类游戏中实现，但这将非常困难，结果可能不尽如人意。

在具有许多可能选择的情况下，它们无法准确确定最佳选择。

一般概念

游戏树通常用于棋盘游戏中以确定最佳移动。为了说明问题，将以井字游戏作为例子。

其基本思想是从当前的棋盘位置开始，检查计算机可以进行的所有可能移动。然后，查看对手可能进行的移动。然后再回到计算机的回合。理想情况下，计算机将来回翻转，为自己和对手进行移动，直到游戏结束。它将对每种可能的结果执行此操作（参见下图），有效地玩数千次（通常更多）游戏。从这些游戏的胜者和失败者中，它试图确定给它最佳胜利机会的结果。

这可以类比人们在棋盘游戏中的思考方式-例如：“如果我走这步，他们可能会走这一步，我可以用这个来应对”等等。游戏树就是这样做的。它们检查每个可能的移动和对手的移动，然后尝试查看它们在能够考虑的尽可能多的移动后是否处于获胜状态。

可以想象，可能的游戏数量非常大。在井字游戏中，有9种可能的第一步移动（忽略旋转优化）。在第二轮有8种可能，然后是7种、6种等等。总共有255,168种可能的游戏。游戏树的目标是在第一步中检查它

计算机的行动概述

计算机开始评估一个移动，通过计算所有可能的移动。在井字游戏中，它会填充网格上的任意空方块，因此可能的移动数量将等于空方块的数量。
一旦找到这些移动，计算机循环遍历每个可能的移动，并尝试确定该移动是否会使计算机获胜。它通过对位置（通过执行计算机的原始可能移动之一获得）运行相同的算法（递归），但试图计算对手的最佳移动来实现这一点。
为了确定一个移动是“好”还是“坏”，游戏树会继续扩展并延伸，直到游戏结束（达到“终端节点”）。然后，根据游戏的结果为终端节点分配值；值越高，对计算机而言结果越好。因为只有两种可能的结果（胜利或失败），可以使用“-1”和“1”来表示谁赢了（下面的示例提供了比“-1”和“1”更多种类的值）。现在终端节点的值已确定，再往上的节点（如下图中的节点D、E、F和G）。如果节点代表计算机的移动选择，它是一个“max节点”，如果节点代表玩家的移动选择，它是一个“min节点”。max节点的值变为其下方节点中的最高值。min节点的值变为其下方节点中的最低值。在下面的示例中，D的值为4，E的值为1。B的值变为1（4和1中的最小值）。通过继续向上移动，给每个节点赋予一个值。然后，顶部节点（A）获得下方节点中的最高值；具有最高值的节点是计算机应该选择的移动。

组件

所有游戏树都需要相同的脚本概念。本文中给出的脚本名称不是官方的，而是表示脚本功能的名称。

移动脚本：返回由给定玩家移动可能获得的位置的数组。
进行移动脚本：根据上述部分中描述的逻辑，从上述脚本返回的移动中选择最佳移动。
获胜者脚本：接受一个位置，并输出是否是已完成的游戏，如果是，则输出谁赢了。

伪代码

function get-best-move-for:(aPlayer) in-game:(aPosition)

if (has-won:(aPlayer) in-game:(aPosition)) {// 如果玩家赢了，返回位置本身，标记为对我们有利
    报告(aPosition.labelAsGood)
}
if (has-lost:(aPlayer) in-game:(aPosition)) {// 如果玩家输了，返回位置本身，标记为对我们不利
    报告(aPosition.labelAsBad)
}
if (has-tied-in-game:(aPosition)) {// 如果比赛平局，则返回位置本身，标记为对我们来说可以
    报告 (aPosition.labelAsOk)
}
moves = get-all-moves-for:(aPlayer) in-game:(aPosition) // 获取所有可能的动作以供选择
检查 = 0
while: (checking < length-of:(moves)) do: { // 遍历每个可能的移动
    currentMove = item:(checking) of:(moves) //获取要测试的移动
    opponentMove = get-best-move-for:(opponent-to:aPlayer) in-game:(currentMove) // 看看对手会做什么
    if (opponentMove.labeledAsGood) {// 如果对手赢了，这对我们来说是个坏棋
        标签：（项目：（检查）的：（移动））为：“坏”
    }
    if (opponentMove.labeledAsTie) {//如果对手会赢，对我们来说没问题
        label:(item:(checking) of:(moves)) as:"ok"
    }
    if (opponentMove.labeledAsBad) {// 如果对手输了，这对我们来说是好棋
        label:(item:(checking) of:(moves)) as:"good"
    }
    change:(checking) by:(1) // 测试下一个可能的走法
}
report (best-labeled-move-among:(moves)) // 移动可能的最佳着法 (where "good" beats "ok" and "ok" beats "bad")

优化

上述方法仅展示了游戏树的基本应用。实际上，在不进行一些修改的情况下，上述方法不适用于许多游戏。上述脚本应该为任何游戏树打下基础，但绝不是最佳选择。以下是改进游戏树速度或性能的一些方法。

不完全搜索

尽管搜索每个移动是可能的，但通常更快的方法是仅向前思考游戏的3-6个移动。6个移动通常足以确定一个移动的好坏，并且不会太大程度上牺牲速度。人类以类似的方式玩游戏。他们不会为每个移动计算整个游戏；他们总是思考给定移动未来3-6个移动的后果，并根据这些后果进行决策。以此为例，如果平均国际象棋局面有20种走法（低估），并且游戏需要完全搜索，假设每局平均40个走法（另一种低估），则需要搜索20^40个局面（约为10^52个）。即使是拥有强大处理器的现代计算机也无法搜索到这个数量级。但计算机可以轻松搜索4或5个步骤深度，并查看位置来确定谁在获胜，这就是它们的做法。它们不是搜索深达40多个步骤，而是搜索2-8个步骤，并评估最终位置。

当然，如果计算机不完全搜索游戏，它的决策将不会是完美的。因此，深度通常是控制难度级别的参数。更难的计算机玩家将搜索更深的深度，但缺点是速度较慢。

更复杂的评估脚本

在国际象棋中，更适合确定谁在“获胜”的方法是计算每个棋子的价值。例如，可以通过将所有“好棋子的点数”相加并减去所有“坏棋子的点数”来计算棋盘的“价值”（通常为每个国际象棋棋子分配一个值，其中兵的价值为1分，皇后为9分）。评估脚本越准确，移动越好，但运行时间（通常）越长。在准确性和速度之间找到平衡很重要。更高的速度允许更深入的搜索，而更高的准确性使搜索的深度更有效。

其他改进脚本的方法

剪枝（尝试跳过似乎不重要的位置以加快搜索速度）
- Alpha-Beta剪枝是最有效的消除搜索的方法之一，不会牺牲准确性（也就是说，无论是否实现Alpha-Beta剪枝，计算机在相同深度使用相同评估函数进行搜索时将得出相同的决策）。在下面的图片中，想象计算机从左到右进行搜索。它搜索一直到D，并给它一个值为2。然后给E一个值为1。结果是将C（一个最大节点）的值设为2。然后计算机查看G，并且看到它比2（值为6）更高，因此停止查看H（或者F可能导致的任何其他移动）。这背后的推理是这样的：

F至少为6（它是一个最大节点）。因此，F必须大于或等于C（其值为2）。由于F必须大于或等于C，对手（最小节点）将永远不会选择F而不选择C；相反，最小节点将不得不选择较低的C值。

虽然消除一个移动似乎无关紧要，在更大的分支因素中，可以消除更多的移动。继续向分支P前进，可以看到反向情况发生。已确定Q的值为4，小于I（值为5）。由于最大节点只会选择最佳移动（而P不能大于4），继续搜索分支P（到终端节点U和V）是不必要的。
如果能够预测哪些移动可能是最佳的，Alpha-Beta剪枝会变得更加有效。例如，如果在井字棋格的中心放置“X”通常比在两侧放置更好，那么先检查“将X放在中心”的移动可能导致需要搜索更少的移动。

搜索到“稳定位置”可以帮助减少视野效应。基本上，如果一个节点看起来不稳定（例如，计算机刚刚走了一步），仅在该分支中更深地搜索通常可以揭示一个决定性的移动，有助于计算机做出更好的移动。虽然为每个脚本搜索一个更深的层与仅仅将整个搜索扩展到更深的层没有区别，但是尝试找到可能导致大的损失或收益的位置并仅搜索这些位置比搜索所有可能的移动更高效，特别是在最后一层。
许多计算机首先按给定深度搜索所有移动，然后仅对最佳移动搜索到额外的深度。如果最佳移动被证明是糟糕的（通过额外深度的添加输入），计算机将对第二个移动进行额外深度的搜索，继续进行一定数量的移动，直到某个移动在进一步搜索时不被证明是“有缺陷”的为止。
许多实现游戏树的程序使用其他优化技术，例如在存在许多常见对称位置的游戏中（例如井字棋），通过过滤旋转/镜像来减少搜索量，将位置的计算结果存储在内存中以供后续访问等。

这些优化方法存在的问题

地平线效应：地平线效应指的是计算机因为无法搜索到足够深度的移动而导致做出糟糕的决策。如果计算机的搜索深度有限，而某个不利后果发生在几个回合之后，计算机可能无法意识到这个后果。这在国际象棋中经常会出现，例如计算机吃掉对方的棋子后却没有看到对方的回击，或者当计算机受到威胁时，它会一直试图拖延不可避免的结果，从而导致糟糕的决策。
对于每回合移动数较多的游戏（也称为游戏树的“分支因子”），计算机会遇到严重问题。前面提到的图片中的分支因子是2。国际象棋的分支因子约为30（平均每回合30个移动）。其他游戏（例如围棋）可能有非常大量的可能移动，结果是计算机无法搜索到足够深度来做出合理的移动。新手经常能击败计算机在围棋中，因为计算机无法应对大量的移动，计算机需要搜索的位置数量可以用以下表达式表示：(分支因子)^搜索深度。在国际象棋中，大约是30^深度，在围棋中更大。