博弈树模型

2.1　博弈树模型

计算机博弈理论的主要研究对象是双人博弈中的数学模型和相关算法，在双人博弈中，有给定的初始盘面，双方按规则轮流落子而更改盘面直至终盘，以获取最大回报为目标。在双人零和博弈中，战胜对手而获胜即为最大回报，因此也是双人零和博弈的目标。

计算机博弈理论的目标是对于给定的初始盘面，发现对弈双方的最佳落子序列以至终盘，并以此为基础，发现任给初始盘面的最佳落子点。

计算机博弈理论的数学基础是博弈树模型。博弈树是一种数据结构，用于描述博弈中不同博弈盘面之间的关系。具体地讲，博弈树的节点表示不同的博弈盘面，博弈树的边表示从一个博弈盘面转换到另一个博弈盘面的落子行为。

假设双人博弈过程中的双方分别是A和B。对于一个给定的初始盘面S，如果轮到A落子，我们就可以通过建立一棵博弈树描述双方可能的落子过程。其中，S就是这棵博弈树中的根节点，A在S状态下所有可能的落子点对应于从S所引出的边，每条边导致一个新盘面，这些新盘面是S的第一层子节点。对于每一个S的第一层子节点，B所有可能的落子会导致新的盘面，从而成为S第一层子节点的子节点，即S的第二层子节点。整棵搜索树就按照这样的过程不断构建，直到每一分支都最终到达表示终盘的节点。终盘节点表示博弈过程的终结，终盘节点没有子节点，因此是博弈树的叶子节点。所有的叶子节点无须处在同一层，但每个叶子节点都表示终盘状态，因此可以在叶子节点上评估胜负。这样的一棵博弈树就是一棵完整博弈树。

下面，我们以实例的形式为井字游戏（tic-tac-toe）构建博弈树。井字游戏是一个简单的双人零和博弈，对弈双方轮流把X和O画在一个3×3的网格内，在横向、纵向或对角线方向先连成三子一线的一方为胜。图2.1表示的是井字游戏的三层博弈树，博弈树的根节点是井字游戏的初始盘面状态，其第一层子节点和第二层子节点都根据对称关系进行了简化，即对称的盘面状态都使用同一节点来表示。

图2.1　井字游戏的三层博弈树

如果一个双人博弈总能在有限落子过程中结束，我们就可以根据以上方法为其构建一棵完整的博弈树，也可以在理论上“解决”该博弈，即通过一个博弈树的遍历算法而发现双方最佳的落子序列，从而保证最终导致最佳对弈结果。

解决博弈问题的博弈树遍历算法如算法2.1所示，其基本思想如下：评估博弈树中各个叶子节点的胜负结果，并逐层返回；对于任何一个博弈树中间节点，如果其所有的子节点都已经有胜负结果，则可通过其所有子节点的胜负结果来评估该节点，具体规则是如果某个子节点能导致胜利，即选择该子节点而胜利，如果所有子节点都导致失败，该节点也为失败，否则该节点的结果是平局。博弈树根节点的胜负结果即是博弈问题的答案。很明显，该算法的时间复杂度和空间复杂度都是O（N），其中N是博弈树上节点的个数。

算法2.1 博弈树遍历算法伪代码

对于一个并非过于简单的博弈问题，其博弈树的节点数都非常大，我们无法承受使用博弈树遍历算法来解决博弈问题所花费的时间。由于计算机时间资源与空间资源的限制，计算机博弈程序只能访问局部的博弈树来寻找博弈问题的近似最优解。在实际计算中，程序能访问到的博弈树节点只是完整博弈树中根节点附近极小的一部分。因此，在构建计算机博弈程序时，我们必须回答以下3个问题：①博弈的盘面状态是什么？②访问博弈树中的哪些节点？③当访问到的节点不是叶子节点时，如何衡量其优劣？

博弈的每个盘面对应于博弈树上的一个节点，程序需要在博弈树的节点上把盘面状态标识清楚和完整，盘面状态的具体内容取决于博弈本身。以围棋为例，围棋的盘面状态包含棋盘上每个点的棋子情况、上一步是否产生劫及其位置、上一步是否是虚手，等等。

博弈树中节点的访问取决于博弈树搜索算法。不同的搜索算法对于博弈树节点的访问有不同的顺序，这在很大程度上也决定在有限的时间内某些节点是否被访问到，因此也直接影响博弈水平的高低。搜索算法是计算机博弈的一个核心，我们将在本章中讨论多种传统计算机博弈的搜索算法，其中包括第2.4节的极小极大搜索算法、第2.5节的负极大搜索算法、第2.6节的α-β搜索算法、第2.7节的负侦查搜索算法、第2.8节的静止搜索算法和第2.9节的搜索算法中所使用的置换表技术。

无论使用哪一种搜索算法，其访问的博弈树节点的数目是十分有限的，通常只包含非终盘状态下内部节点。如果某个节点的子节点都被访问到了，该节点的优劣当然可以通过其子节点的优劣进行评估；否则就必须根据盘面状态进行评估，由于没有涉及搜索该节点的子节点，这种评估也称为静态盘面评估。静态盘面评估是计算机博弈的另一个核心，我们将在本章第2.3节中进行讨论。