6.034 笔记：3.1部分
幻灯片3.4.1
这一部分，我们会看一些编写基本的二人游戏程序的方法，这
些游戏比如井字游戏，跳棋和象棋。
这一领域的大部分工作是由玩象棋引发的，它一直被称作“思
考者的游戏”。回忆一下计算机象棋的历史。信息理论之父
Claude Shannon（克劳德.香农）1949年的一篇论文引发了很多
想法。不久后，Alan Turing（艾伦.图灵）基于其中的想法设
计了一个手模拟的跳棋程序。十年后，第一个玩真正象棋的程
序才出现，而直到Greenblatt（格林布拉特）的MacHack 6，计
算机象棋程序才能打败一个好的棋手。缓慢而稳步的发展最终
导致1997年5月IBM的深蓝战胜卫冕世界冠军Garry Kasparov
（卡斯帕罗夫）。
幻灯片
3.4.2
游戏程序是另一种搜索的应用。状态是棋盘的位置（以及要移
棋的棋手）。操作是合法的移动。目标是赢得棋盘上的位置。打
分函数为状态赋值，也可以作为一种启发式函数。游戏树（以
状态和操作定义）就像是一个典型搜索的搜索树，并且它可以
编码所有可能的游戏。
然而，还是有些小的主要区别的。由于移棋取决于对方玩家的
移动情况，因此我们并不是从游戏树中搜索一条路径。我们所
能做的就是为下一步选择最好的移棋。
幻灯片3.4.3
深度
分支因数
象棋
B=36 d>403640 非常大的数字
我的走棋
结果
对方的走棋
让我们来详细看下游戏树。某些棋盘位置代表初始状态，现在轮到我们走。我们通过所提供的合法的移棋来产生这个位置的子节点。接着，我们考虑对手可能的行动，以产生上述位置的后代。请注意，这些树是巨大的，无法为任何复杂的游戏产生明确的整体形式。
井字游戏的游戏树片断幻灯片3.4.5 分数从此处获胜的可能性打分函数是游戏程序的重要部分。这个函数为棋盘位置赋予一个
数值。我们可以考虑借助这个数值来表示获胜的可能性。既然游
戏一方获胜即为另一方败北，我们为两位对手设置相同的打分函
数，仅仅加负号以区别对方的成绩。
幻灯片3.4.6 对最终输赢的预测太无力了
材料棋的布局机动性
国王的安全性
控制中心一个典型的打分函数是线性函数，其系数集是用来加权棋盘位置所对应的“特征”。每个特征也是用来度量棋盘位置属性的。一个
很容易看到的“材料”，即对棋盘中某一方拥有的棋子的度量值。这里展示了一种对每类棋盘棋子的典型加权方法。其他类型的特征是为了编码棋盘上棋子分布的属性。 从某种意义上讲，如果有一个完美的评价函数，我们评价每一步合法的移棋所产生的位置以及选择具有最高成绩的那一步棋就可以简单地下棋了。从原则上讲，这种功能是存在的，但没有人知
道怎么直接将其写出来或计算出来。
幻灯片3.4.7
静态评价回传分数
MIN －MAX 层游戏程序中采用的主要思路（在Shannon1949年的论文中论述）是有限前瞻联合最小－最大算法。 假设我们以前瞻法考察游戏树，前瞻的深度为2（在有关游戏的文献中指2层）。我们可以利用打分功能，考察树的叶节点的分
数。这称为“静态评价”。我们想做的就是，通过“备份”树的
这些静态评价，为此叶节点之上的每一个节点计算一个数值。
建树的棋手就是在试图将这些数值最大化。然而，我们假设对
手（采用相同的静态评价函数来度量棋盘上的位置）正试图最
小化这些数值。因此，树的每一层可以被分为最大化层或最小
化层。在我们的例子中，叶节点上面的一层是最小化层，因此
我们为这层上的每个节点赋值为其子节点中的最小值。
在下一层，我们要取最大化，因此从提供给我们的选择中取最高的分数，即7。因此，因此，这一分析
提示：无论对手如何做，我们都应该选择能确保最好结果的移棋。这就是最小－最大算法。
幻灯片
3.4.8
尘埃3怎么玩这里是最小－最大算法的代码。正如所见，这是在每层所做最小
和最大的简单递归交替操作。我们对深度的计数是从最大深度向
上进行的，因此当我们达到深度为0时，我们就可以对棋盘进行
静态评价了。
3.4.9 USCF 排名USCF 排名深度主要思想是当我们前瞻的工作越多即前瞻的层数越深，对位置的估计越准，即便我们只有一个简单的评价函数这一情况同样
成立。在某种意义上讲，如果我们能前瞻到游戏树的最低层，
我们所需要做的就是寻评价函数了，要求此评价函数能够在
我们获胜的情况下为1而对方获胜的情况下为－1。
真正值得注意的是看下这一思想能起到多好的效果。如果画一
个搜索象棋盘游戏树的计算机程序达到的搜索层数与他们性能
得分的线，例如所示的图表。最早的严谨的象棋游戏程序
（MacHack6）能得到1200分，它搜索的平均深度为4。最早的硬件辅助的象棋游戏程序之一Belle ，增加一倍搜索深度结果提
高了800分。击败国际冠军的深蓝，搜索平均深度约为13，得
分为2900。
在某种程度上多，这是一个不容乐观的图表，它显示最终效果全是由机械化的搜索来决定的。
幻灯片3.4.10
深蓝实际上是很残忍的。它具有256个专业象棋处理器组成了32个节点的超级计算机。它每秒大约可以进行300亿次走棋。典型
的搜索深度大约为13层，但是在一些动态情况下可能达到30层。
幻灯片3.4.11
想法在发任何情况
α打分的下界β打分的上界
另一个展电脑游戏程度中发挥了至关重要的作用。它其
实只是一个优化的最大最小搜索，但它是如此强大并作为重要的
优化算法，应该被详细地理解。这项技术被称为αβ剪枝，它借
助于从传统的希腊字母来代表评分的上下约束。
这是一个说明该重要想法的例子。假设已经评价过子树的左边（它
的叶节点值为2和7）。既然这是最小化层次，我们选则值为2的。
因此，在树的顶部的最大化玩家知道，此时他选择往左边走保证
能得到至少2分。 现在，我们着手观察子树的右边。一旦看到子树最左边的叶节点值是1，就知道如果最大化的玩家向右走，那么最小化的玩家就会
迫使其向值不超过1的位置走。事实上，也许会更糟糕。可能下一个叶节点会更让我们吃惊，但是它是什么没关系：我们已经知道这一步比往左边走更糟糕，因此为什么还要继续看下去呢？事实上，也许这个未知的位置对于最大化者是很好的，但是最小化者永远都不会选择它。因此，不管那个叶节点发生了什么，最大化者将不受影响。
幻灯片3.4.12
这是这种思想的一些算法代码。可能得分的范围（定义为α和β）
从负无穷到正无穷。α表示下限而β表示上限。我们把目前棋盘
状态作为Max-Value。如果在叶节点，则返回静态值。否则，要
观察这个状态的每一个后继者（通过采用合法移动函数），并称每
一个后继者为极小者（最小值），记录下最大值并返回给α。如果
α（得分的下限）的值大于或等于β，那么就知道我们不需要继续
看了-这被称为中止-然后立刻返回α值。否则在循环结束返回α
值。最小值是完全对称的。
幻灯片3.4.13
让我们看一下在先前例子中运行的这个算法。以α和β的初始
无穷值起调用Max-Value，也就意味着我们对将来的得分情况一
无所知。
幻灯片3.4.14
现在Max-Value是左边有相同α和β值的后继者调用Min-Value。
Min-Value在最左边后继调用Max-Value。
幻灯片3.4.15
Max-Value是对最左边的叶节点，它的静态值为2因此返回这个
值。
幻灯片3.4.16
这第一个值比无穷值要小，就成了Min-Value中β的新值。
幻灯片3.4.17
因此，现在Max-Value是下一个后继者，也就是值为7的叶节
点。
幻灯片3.4.18
7没有2小，因此这个节点β的最后值为2.
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论