人工智能第2版学习——博弈中的搜索1

书：人工智能第2版
有需要电子版的可以私信我。

这次学习第4章的博弈树和极小化极大评估。

引言

前面的搜索，都是研究如何从初始态到达最终态，而现实中，存在很多事情，是有人阻碍你到达目标的。比如下棋、井字游戏、Nim游戏。
本章书中用井字游戏来辅助介绍二人博弈。

井字游戏

这个游戏大多数人都玩过吧。两个玩家，交替走子，如果在同一行、同一列或同一对角线有三个一样的符号，就算那个玩家赢。

博弈树

在我们走子前，一般都会在脑子里或者用纸进行尝试走子，以选择更有利的走子方式。比如可以设想，“如果我这么走，会使自己获胜更有利吗？”我们也可以用博弈树来评估。下图就是一个井字游戏的博弈树。

这个博弈树不完整，只显示了前两步，而井字游戏，最长可以走到9步，有39种可能的博弈。如果是个复杂的游戏，面临组合爆炸的情况，此时评估走子只能尽可能向前看，然后用博弈棋局的启发式评估来评估好坏。

启发式评估

对于相对复杂的博弈，应使用启发式评估。
还是用井字游戏来说明。用N(X)表示X可能完成的行、列和对角线的书目，N(O)同理，如下图(我感觉图示不太对，N(X)不应该是4，N(O)不应该是2吗，不过不影响分析)：

此时定义博弈棋局E(X)的启发式评估：E(X)=N(X)-N(O)。这个数据具体多少不重要，重要的是是否相对有利，下图给出上面提到的博弈树的启发式评估：

博弈树的极小化极大评估

上面图4.6中，只有第三层的评估值，我们需要应用某种技术，把这些评估值渗透到上面两层去，以帮助玩家做出决策，这就需要用到极小化极大评估。

我们需要明确一点，玩家的目标是：在受到对手阻碍的情况下，找到通往胜利的路径，而不是最快的取的胜利。

如果用MAX和MIN来表示两个玩家，MAX试图最大化启发式评估，MIN则试图最小化启发式评估，MAX先走子，并假设每次走子只有可能的走子方式，如下图：

MAX的评估值是起后继节点的最大值，MIN则相反。(很好理解，这个评估值是评估MAX获胜的，所以MAX取最大，MIN去最小。)
示例：

回到井字游戏，根据博弈树的极小化极大评估，MAX第一步走正中间最有可能获胜。

具有α-β剪枝的极小化极大算法

在规模较小的游戏中，可以不用启发式评估，但是大多数博弈树很大，评估时也很难完整评估，此时只能搜索到某一层。α-β剪枝可以与极小化极大算法组合，无需检查树种的每个节点，得到与单独使用极小化极大算法相同的度量，按书中意思，可以少检查一半的节点。
基本原则：如果发现一个走子方式很差，就彻底放弃它。直接看例子：

图中，小框中的数字是时间戳，即顺序。
书中解释很清楚，我就截图不自己解释了。


书后面还给了几个例子，我就不多说了，感兴趣的可以去看书。

点个赞呗。