赫尔辛基大学AI基础教程：搜索和游戏（2.3节）

AiTechYun

编辑：yxy

在本节中，我们将研究一个经典的AI问题：游戏。为了清晰起见，我们将重点关注的最简单的场景是双人游戏，如井字棋和国际象棋等完全信息游戏。

例如：玩井字棋

Maxine和Minnie是真正的游戏爱好者。他们只是喜欢游戏。特别是两人完美的信息游戏，例如井字棋或国际象棋。有一天他们在玩井字棋。Maxine或者简称为MAX使用X.。Minnie或者简称为Min使用O。Min刚打完O，棋盘如下：

Max正在看着棋盘，思考她的下一步行动，因为现在轮到她了，但这时她突然绝望地捂着脸，看起来就像1997年的加里·卡斯帕罗夫(Garry Kasparov)对战深蓝。

是的，Min在第一排即将获得三个O，但Max可以轻松堵住它。那么Max为什么如此悲观呢？

游戏树

为了使用AI来解决游戏，我们将介绍游戏树的概念。游戏的不同状态由游戏树中的节点表示，与规划问题非常相似。不同的是，在游戏树中，节点按照每个玩家在游戏中的回合顺序排列，以便树的“根”节点（通常在图的顶部）是游戏中的开始位置。在井字棋中，是没有X或O的空网格。接着根下的第二级，可能由第一个玩家的落子产生的状态，无论是X还是O.我们称这些节点为根节点的“子”节点。

第二级的每个节点将根据对手下一步的落子后的状态发展下一个子节点。逐级继续，直到达到游戏结束的状态。在井字棋中，这意味着其中一个玩家可以获得三点一线并获胜，或者棋盘已满并且比赛以平局结束。

最小化值和最大化值

为了能够创建想去赢得游戏的AI，我们给每个可能的最终结果添加一个数值。对于棋盘上X有三点一线Max获胜，我们附加值+1，同样，对于Min连上三个O的情况，我们附加值-1。对于棋盘已满并且双方都没有获胜的职位，我们使用中性值0.（无论值是多少，只要按照这个顺序，Max就会尝试最大化该值，而Min会尝试最小化该值。）

游戏树示例

例如，思考下面的游戏树，它不是从根开始，而是在游戏的中盘（否则，树太大了）。请注意，这与本节开头插图中显示的那盘游戏不同。我们用数字1，2，…，14对节点进行了编号。

游戏继续在根节点中显示的棋盘位置，在顶部编号为（1），轮到Min将O放置在三个空白单元中的任何一个上。节点（2） – （4）分别显示三种选择各自产生的结果。在下一步中，每个节点有两个可能的选择让Max画X，于是树再次分支。

当从上面的起始位置开始时，这个游戏三步就结束了：在节点（7）和（9）中，获胜者是使用X的Max，节点（11） – （14）中获胜者是用O的Min。

请注意，由于玩家轮流交替，每一级标记了Max和Min用以表明轮到谁下了。

战略性思维

思考到倒数第二层上的节点（5）到（10）。在节点（7）和（9）中，游戏结束，Max赢得胜利。此时值+1。在剩下的节点（5），（6），（8）和（10）中，游戏也等于结束了，因为Min只需要将她的O放在唯一剩下的单元格中就可以获胜。换句话说，我们知道游戏如何在倒数第二层每个节点处结束。因此，我们可以确定节点（5），（6），（8）和（10）的值是-1。

有趣的部分来了。让我们思考节点（2） – （4）的值。由于我们观察到（2）的两个子节点，即节点（5）和（6）都会导致Min的胜利，我们可以毫不犹豫地将值-1附加到节点（2）。而对于节点（3），左边的子节点（7）会让Max的胜利+1，但是右边的子节点（8）会让Min的胜利-1。节点（3）的价应该是什么？这时我们要思考，谁在节点（3）做出选择。

既然轮到了Max，她当然会选择左边的子节点，节点（7）。因此，每当我们到达节点（3）中的棋盘位置，Max都可以确保胜利，并且我们可以将值+1附加到节点（3）。

节点（4）也与此相同：因为Max可以选择将X放在哪里，她总是可以确保胜利，并且我们将值+1附加到节点（4）。

确定谁赢了

本节中最重要的是如何应用上述的推理，从任何棋盘位置中提前确定游戏结果。

到目前为止，我们已经确定节点（2）的值是-1，这意味着如果我们最终处于这样一个棋盘位置，Min可以确保获胜，而节点（3）和（4）的值是+1，这意味着如果Max做出正确的选择，那么他一定能赢。

最后，我们可以推断出，由于Min是一位老玩家，她可能得出同样的结论，因此她只有一个正确的选择：在中间下O。

在下面的图表中，我们包含了每个节点的值以及从根节点开始时最优的游戏策略。

根节点的值=谁胜出

据说根节点的值是游戏的值，告诉我们谁会赢（如果结果不只是纯赢或输，也会告诉我们胜率）：Max赢得如果游戏+ 1,最小值为1,如果该值为0,那么游戏将以平局结束。在其他游戏中，值也可能为其他（例如扑克中筹码的货币价值）。

这一切都是基于这样一种假设，即双方的选择对自己最好，但对另一方最差(这就是所谓的“零和博弈”)。

注：

找到最佳的办法

在确定了游戏树中所有节点的值之后，可以推导出最优移动：在任何Min节点处（轮到Min下的地方），最优选择由其值最小的子节点给出，相反，在任何最大节点（轮到Max的地方），最优选择由其值最大的子节点给出。有时候，也会有不管选择哪一个结果都一样的选择。

Minimax算法

我们可以利用上述游戏价值的概念来理解Minimax算法。它在理论上保证了任何确定性的、双人的、完全信息的零和博弈的最佳游戏玩法。在给定游戏状态的情况下，该算法简单地计算给定状态的子节点的值，并且如果轮到Max则选择具有最大值的那个值，并且如果轮到Min则选择具有最小值的那个值。

该算法使用很少的代码就可以实现。但在这里，掌握主要思路就可以了。如果有兴趣查看实际算法（警告：需要编程），请查看（https://en.wikipedia.org/wiki/Minimax）。

听起来不错，但这就结束了吗？

如上所述，Minimax算法可用于在任何确定性的、双人的、完全信息的零和博弈中实现最佳游戏玩法。这类游戏包括井字棋，四子连珠，国际象棋，围棋等等（猜拳不属于这类游戏，因为它涉及隐藏于其他玩家的信息; 大富翁或西洋双陆棋也不是确定性的）那么，但这个主题已经结束了吗？答案是，在理论上，是的，但在实际中，没有。

注：

较大游戏树的问题

在许多游戏中，游戏树太大而无法完全遍历。例如，在国际象棋中，平均分支因子（即每个节点的平均子节点数量，不计不可移动的）大约为35.这意味着只要探索前进两步的所有可能场景，我们就需要访问大约35 x 35 = 1225个节点 ……三步则需要访问42875个节点; 四步1500625; 10步骤需要2758547353515625（即大约2700万亿）节点。在围棋中，平均分支因子估计大约为250，Minimax不可用。

更多技巧：管理大的游戏树

管理大量游戏树需要很多的技巧。其中许多是IBM深蓝计算机在1997年击败国际象棋世界冠军卡斯帕罗夫的关键因素。

如果我们只能探索游戏树的一小部分，我们需要一种方法来在到达终端节点（比如，游戏结束并且胜利者已知的节点）之前停止minimax递归。这是通过使用一个所谓的启发式评估函数来实现的，该函数以一个棋盘位置作为输入（同时包含下一个该轮到谁的信息），并返回一个分数，该分数应该是从给定棋盘位置继续进行的游戏的可能结果的估计。

注：

好的启发式评估

例如，良好的国际象棋启发式算法通常会计算按其类型加权的材料（棋子）总数：女王通常被认为价值是车的两倍，马或象的三倍，兵的九倍。国王当然比其他所有东西的价值都要高，因为输掉它就等于输了比赛。此外，占据战略要地被认为是一种优势，启发式为这些位置赋予更高的价。

上面提出的minimax算法需要最小的变化来获得深度受限的版本，在给定深度受限法的所有节点上返回启发式搜索：深度时指的是在应用启发式评估函数之前游戏树被展开的步数。

练习7：Max为何悲观？

让我们回到本节开头描述的井字棋。为了缩小可能的最终游戏空间，我们可以观察到，Max必须明确地将X放在第一排以避免即将到来的失败：

现在轮到Min画O。使用Minimax算法以此为根，评估在这种游戏状态下的值以及游戏树中的其他状态。

你的任务： 看看从下面棋盘位置开始的游戏树。用笔和纸填写游戏结束时底层节点的值。请注意，这次有些游戏以平局结束，这意味着节点的值是0。

接下来继续填充倒数第二级节点的值。由于这级没有分支，与底层的值相同。

在倒数第三级，通过为每个节点选择子节点的最大值来填充值 – 如你所见，这是一个MAX级。最后，通过选择根节点的子节点值的最小值来填充根节点的值。这就是游戏的值。

输入游戏的值作为答案。

注：

简单搜索的局限性

可能看起来像我们有一种方法可以通过指定它们之间的状态和转换，并找到从当前状态到目标的路径来解决任何问题。可惜，当我们想在实际问题中应用AI时，情况会变得更加复杂。基本上，即使是一个中等复杂的现实世界情景中的状态数量无法控制，我们无法通过穷举搜索（“蛮力”）甚至巧妙的启发式方法找到解决方案。

而且，当我们选择一个行动时，将我们从一个状态转换到另一个状态的转换不具有确定性。这意味着，无论我们选择做什么都不会总是完全确定结果，因为有些因素是我们无法控制的，而这些因素往往不为我们所知。

我们上面讨论的算法可以适用于处理一些随机性，例如在从洗牌平台选择牌时的随机性或掷骰子。这意味着我们需要引入不确定性和概率的概念。只有这样我们才能开始接近现实世界的AI而不是简单的谜题和游戏。这是会是我们第3章的主题。

完成第2章后，你应该能够：

规划一个真实世界的问题为一个搜索问题

为简单的游戏（如井字棋）做游戏树

使用minimax原则在小的游戏树中找到最佳移动