关于人机博弈(计算机下棋)的历史.docx

关于人机博弈（计算机下棋）的历史1 .概述博弈（Game Playing）是一种竞争，而竞争现象广泛存在 与社会活动的许多方面，因此博弈论可以很自然地引深并应用到 含有竞争现象的政治、经济、军事、外交等各个领域然而， 从狭义的“博弈”来讲，人机博弈（计算机下棋）是各个领域 博弈理论的起源与基础，在人工智能方面更是一个重要的研究方 向博弈一向被认为是富有只能行为的游戏，因此很早就受到人 工智能界的重视，早在60年代就已经出现了若干博弈程序，并 达到了 一定的水平比较有影响的是1960年NNS国际象棋机 的出现，以及60年代初期IBM完成的具有自学习、自组织、 自适应能力的西洋棋程序等等人机博弈史上最伟大的一次较量是1997年世界首席国际象 棋大师卡斯帕罗夫与IBM公司生产的计算机“更深的蓝”的较 量经过几轮角逐，“深蓝”终以2： 1战胜了卡斯帕罗 夫这是当今世界人工智能飞速发展的一个重要标志博弈问题为搜索策略，机器学习等问题的研究课题提供了很 好的实际背景，而且博弈问题自身也不断提出了 一些新的研究 课题，从而推动了人工智能的研究和发展简单的说，在一盘 棋赛中，对弈各方都要根据当前的局势，分析和预见以后可能 出现的局面，决定自己要采取的各种对策，以争取获得最好的 结果，这便是人机博弈程序所要达到的目的。

从编程人员的角 度讲，程序员必须使计算机做到：通过现有的棋面形势或对手 的合法走步来给出合法的、适当的、最优的走步方式从而， 程序员必须先从博弈的理论上为博弈程序的编写进行研究因 此，我们可以引入“博弈树的搜索”的概念用博弈树作为工 具来对计算机博弈的对策方式进行叙述2 .博弈树首先，从一个十分简单而又十分典型的例子一一“拾火柴棍 游戏”来认识博弈树拾火柴棍游戏的规则是：把规定数目的 一堆火柴棍放入盘中，两博弈者轮流从盘中取走火柴，每次从 盘中取走1, 2或3支火柴均为合法走步否则，为非法走 步；拿走最后一支火柴的博弈者则负了这一局拾火柴棍游戏 中只有一种终局形式，即盘中没有火柴棍了因此，两个博 弈者之间只有一个唯一的胜者，不可能出现和局如果我们令A胜的局面值为WIN, B胜的局面值为LOST, 而和局的值为DRAWo当轮到A走时，A定会选择子结点值为 WIN或DRAW （如果没有值为WIN的子结点的话）如果该结点所 对应的局面轮到A走棋，则该结点的值是其所有子结点中值最 佳（对A而言）的一个的值；如果该结点所对应的局面轮到B 走棋，则该结点的值是其所有子结点中值最差（对A而言）的 一个的值。

这样看来从这棵树的叶子结点倒推向根部，就可以得出所有 结点的值双方就可以从其所面临的棋局中选择一步好棋然 后一步步走向胜利博弈树是从根部向下递归产生的一棵包含所有可能的对弈过 程的搜索树，这里称为完全搜索树从实际来说，除了极少数非常简单的棋类游戏，大多数棋 类游戏，如象棋，围棋，我们都没有建立完全搜索树的可能一方面是因为很多情形根本就到达不了叶子结点，如将一个 棋子反复来回走动就可永远循环下去；另一方面，即使我们将 循环的情形排除，这棵树上的结点数量也已多到了无法处理的程 度以中国象棋为例，其每一局面可有约20-60种走法以平 均40种走法计，建立一棵（双方各走50步）搜索树就需生 成约10的160次方个结点这远远超出了当今计算机的处理 能力也就是说，必须得有其他切合实际的方法搜索策略可 采用宽度、深度或启发式方法，一个阶段搜索结束后，从对策 树中提出优先考虑的“最好的”走步，这就是实用策略的基本 观点3 .极大极小搜索在上面的博弈树中，如果我们令A胜的局面值为1, B胜 的局面值为-1,而和局的值为0当轮到A走时，A定会选择 子结点值最大的走法；而轮到B时，B则会选择子结点值最小 的走法。

所以，对于中间结点的值可以有如下计算方法：如果 该结点所对应的局面轮到A走棋，则该结点的值是其所有子结 点中值最大的一个的值而如果该结点所对应的局面轮到B走 棋，则该结点的值是其所有子结点中值最小的一个的值极大极小搜索策略就是考虑双方对弈若干步之后，从可能的 走步中选一步相对好棋的走法，即在有限的搜索深度范围内进行 求解为此要定义一个静态估计函数f,以便对棋局的事态(接 点)作出优劣估植，这个函数可根据事态优劣特征来定义(主 要用于对端结点的“价值”进行度量)一般规定有利于MAX 的事态，f(p)取正值，有利于MIN的事态，f(p)取负值， 势均力敌，f(p)取0值若f(p) =+8,则表示MAX赢， 若f(p) =- 8,则表示min赢显然，我们无法拥有绝对精 确的静态估值函数否则，只要这个静态估值函数就可以解决 所有的棋局了估值函数给出的只是一个较粗略的评分，在此基础上进行的 少量搜索的可靠性，理论上是不如前述的WIN, LOST, DRAW 三种状态的博弈树的，但这个方法却是可实现的利用具体的 知识构成评估函数的搜索叫做启发式搜索4 . a -0剪枝法的应用极大极小搜索过程是把搜索树的生成和格局估值这两个过程 分开来进行，即先生成全部搜索树，然后再进行端结点静态估 值和倒推值计算，这显然会导致低效率。

20世纪60年代至 今，博弈树搜索算法的大多数重要改进包括基本的粤造责澡 葬邺月藻贼葬a -0搜索、迭代深化、空窗搜索、历史辕杀 手启发等一系列方法把这些方法单独或者结合使用，将在很 大程度上提高博弈树的搜索效率在极大极小搜索的过程中，存在着一定程度的数据冗余 举一个最简单的例子：在象棋博弈的过程中，如果某一个结点 轮到甲走棋，而甲向下搜索结点时发现第一个子结点就可以将死 乙（结点值为最大值），则剩下的结点就无需再搜索了，甲的 值就是第一个子结点的值这个过程，就可以将大量冗余的 （不影响结果的）结点抛弃«剪枝示例B剪枝示例将上述这个情形推广一下设想左半部所示的一棵极大极小树的片断，结点下面数字为 该结点的值，结点B的值为18,结点D的值为16,由此我 们可以判断结点C的值将小于等于16 （取极小值）；而结点 A的值为结点Max （B, C）,为18,也就是说不再需要估结 点C的其他子结点如E、 F的值就可以得出父结点A的值 了 o这样将结点D的后继兄弟结点减去称为a剪枝设想有右半部所示的一棵极大极小树的片断，结点B的估 值为8,结点D的估值为18,由此我们可以判断结点C的值 将大于等于18 （取极大值）；而结点A的值为结点Min （B,C),为8。

也就是说不再需要求结点C的其他子结点如E、 F的值就可以得出父结点A的值了这样将结点D的后继兄弟 结点减去称为B剪枝因此，Q剪枝法的规则是：对于任一结点X,设B是该结点父亲的B值且D=-B,那末，如果X的值判断为大于 或等于D,则可以停止生成X的其它儿子a -0剪枝法能够让我们忽略许多节点的搜索对于每一 个被忽略的非叶子节点来说，这都意味着不仅节点本身，而且节 点下面的子树也被忽略掉了这就导致了 a -6剪枝需要遍历 的节点远远少于极大极小算法所遍历的节点这也同时意味着对 搜索同一棵树来说，a -3剪枝法所花费的时间远远少于极大 极小算法所花费的时间同极大极小搜索算法一样，a -P剪枝算法也有点繁琐， 我们不仅要在奇数层进行a剪枝，而且还要在偶数层进行B 剪枝不过只要将负极大值的形式套用上去，这样在任何一层 都只进行B剪枝，它就会同负极大值算法一样简洁自1928年极大极小方法诞生以来，其间出现了多种改进搜 索效率的方法，但a -6剪枝搜索算法到目前为止仍是使用最 为广泛的搜索算法也可以说，a -P剪枝搜索是博弈树搜索 的基础技术5 .综述通过上述分析研究，我们可以得出人机博弈程序的基本组 成：1 .某种在机器中表示棋局的方法，能够让程序知道博弈的 状态。

2 .产生合法走法的规则，以使博弈公正地进行，并可判 断人类对手是否乱走3 .从所有合法的走法中选择最佳的走法的技术4 . 一种评估局面优劣的方法，用以同上面的技术配合做出 智能的选择同时也阐明了：产生（博弈树）、估价（极大极小搜 索）、搜索剪枝）三个环节在人机博弈中的重要性 与运用过程人机博弈在各种文献中被描述为人工智能的果蝇就是说人 类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛 的领域产生了重要影响，与果蝇在遗传学中的研究所起的作用相 似所以，IBM的“更深的蓝”能成功的挑战人类也不能算是一 件令人难受的事情毕竟，由博弈技术衍生而来的多种应用， 如航空调度、天气预报、资源勘探、军事博弈、金融、经济 调控等领域，也取得了大量引人瞩目的成果。