毕业设计（论文）五子棋博弈毕业设计论文.doc

1 引言 随着近几十年来人工智能的飞速发展，越来越多的具有智能的机器进入了人类的生活，人工智能的重要性如今显而易见。人工智能属于计算机科学的领域，它以计算机技术为基础，近几十年来，它的理论和技术已经日益成熟，应用领域也正在不断扩大，显示出强大的生命力。人工智能大致可以分成几个学科，它们每一个都是独特的，但是它们常常又互相结合起来完成设计任务，这时，这些学科之间的差别就变的很模糊。人工智能在专家系统，自然语言理解，自动定理证明，自动程序设计，人工智能在机器人学、模式识别、物景分析、数据库的智能检索、机器下棋（实质上是博弈论问题）和家用电器智能化等领域都有广泛的应用。而这个课题就是和人工智能中的博弈论领域紧密相关的。 广义上来讲，博弈是指在一定的环境条件和一定的规则约束下，依靠自己所能够掌握的信息，从各自选择的行为或是策略进行选择并加以实施，并从各自取得相应结果或收益的过程。冯.诺伊曼（John von Neumann,1903-1957）和摩根斯坦恩（Oskar Margenstern, 1902-1977）在1944年出版了博弈论与经济行为（Theory of Games and Economic Behavior）一书中，最早地提出了关于博弈论的概念。但是，对于非合作、纯竞争型博弈，诺伊曼所解决的只有二人零和博弈。在这里所抽象化后的博弈问题是，已知参与者集合(两方)，策略集合(所有棋着)，和盈利集合(赢子输子)，最终是想去找到一个理论上的解或平衡，也就是对参与双方来说都最合理、最优的具体策略。而在这里狭义的讲，博弈论主要是研究棋手们落子中理性化、逻辑化的部分，并将其系统化为一门科学。换言之，博弈就是研究个体如何在错综复杂的相互影响中得出最合理的策略，博弈论正是衍生于古老的游戏或曰博弈如象棋、扑克等。数学家们将具体的问题抽象化，通过建立自完备的逻辑框架、体系研究其规律及变化。 应用传统决定论中的“最小最大” 准则，即博弈的每一方都假设对方的所有功略的根本目的是使自己最大程度地失利，并据此最优化自己的对策，冯.诺伊曼从数学上证明，通过一定的线性运算，对於每一个二人零和博弈，都是能够找到一个“最小最大解”的 ，而这个简单的博弈思想，也即是人机博弈中最基础的组成部分，通过假设对手必定选取他所能选择的最优解来实现。可以这么说，从狭义的“博弈”来讲，人机博弈是各个领域博弈理论的起源与基础，在人工智能方面更是一个重要的研究方向。因此，在这里，学习掌握博弈论，无疑对实现人机博弈程序是有帮助的。 并且人工智能中的博弈部分，由于采用了大量的搜索算法，其中很多被利用到各方面。它的概念、方法和技术，正在各行各业广泛渗透。智能已经成为当今各种新产品、新装备的发展方向。所以，趁着这个机会，对人工智能中比较容易实现的人机博弈进行了解研究学习，也是很实用且很有必要的。而其中的博弈问题为搜索策略，机器学习等问题的研究课题提供了很好的实际背景，而且博弈问题自身也不断提出了一些新的研究课题，从而推动了人工智能的研究和发展。2 初步设计方案在中国象棋，围棋，国际象棋，黑白棋等各种棋类对弈程序中，其中中国象棋规则比较复杂，但是每一层节点数相对较少；围棋需要十分繁深的估值系统的支持；国际象棋同中国象棋比较类似，它们的各种棋子的走法规则各不相同，都比较繁多，但是每一层搜索的节点数相对较少，它们的估值也较多地需要考虑到全局。而五子棋由于每一层搜索节点数量比较庞大，规则简单，估值函数可以做到比较细致，因此通过实现一个五子棋对弈程序来完成这个课题 在程序的实现上，首先完成界面的设计，在界面的设计上，使用了二维数组的棋盘格式，主要是因为考虑到五子棋的落子后，是不会像象棋那样再次移动的，因此没有选择位棋盘的棋盘模式。 随后通过在完成的简单的界面上实现输赢的判断从而实现了人人对弈的功能。在这个基础上，随后实现了简单的棋盘上的位置的估值，通过每个合法位置上的估值数值，可以让电脑确定最终的落子位置，而这些实现是在当前棋盘上的搜索决定的，而并没有深入的通过推算对手的落子位置从而决定自己的落子位置这种通过的搜索而实现。 在计算了这些之后，为了进一步地提高程序的智能，因此，为程序设计了深入搜索的模块。通过这种深入搜索，让电脑在推测对手的可能落子的位置之后，随后再来决定自己的落子位置，从而提高了电脑棋手的棋力水平。在完成了程序的深入搜索之后，随后添加了不少辅助的算法，来达到完善深入搜索算法的目的。 在程序的结构设计上，主要有三个模块，一个是界面模块，一个是估值模块，一个是深入搜索模块。在具体设计中，估值方面通过比较细致的划分类型来完成此模块功能，通过不同情况下的鼓励值的不同，来使其能够评估出一个相对比较合理切合棋局局势的估值。而在深入搜索方面，通过实现一系列的算法，如负极大值算法，AlphaBeta算法，以及在AlphaBeta算法上改进的FailSoft算法，和调用SoftFail算法的Aspirtaion搜索算法，以及运用了历史启发优化的AlphaBeta算法，历史启发的FailSoft算法，和历史启发的Aspirtaion搜索算法等。通过对这些算法的了解和实现，继而进行深入的分析比较，研究它们的优劣。 而在界面中，实现了一个人机对弈程序最基础的几个功能，比如开局，悔棋，清盘，退出，介绍等，另外还由于要分析比较各个深入搜索算法的优劣，而在棋盘上添加了显示每一次计算机搜索的节点数目的标签和为了方便使用而设置了各种搜索算发，历史启发优化和搜索深度的菜单选项，另外为了比较分析估值模块的一些关键数值，还设置了调节电脑棋手棋力水平的若干菜单选项等。3 估值模块设计现有的计算机的运算能力仍然十分有限，不可能一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们用一些静态的方法，来估计局面的优劣。这些方法在很大程度上依赖于具体的游戏规则和我们对于该游戏的经验知识，其中相当一部分不完全可靠。例如，中国象棋的程序通常将一个炮赋予远高于一个兵的价值，但一个兵在高手的运用之下往往可以产生不次于炮的作用。写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好是一个经验丰富的高手。然后还要进行无数次的试验，经历几番失败后才可能得到一个令人满意的估值函数。3.1 估值函数与博弈性能在博弈程序的几大主要部分里，估值函数是与具体的棋类知识紧密结合的一部分。可以说估值函数在很大程度上决定了博弈程序的棋力高低。显然，开发人员可以向估值函数加入大量的棋类知识，使之对于局面的评估更为精确。但也可以写出简单的估值函数，以期能够使估值的过程简单而节省运算时间，期望通过更深层的搜索可以使棋力提高。 Performance（性能）=Speed（速度）× Knowledge（知识）这一公式具有理论上的意义，它指出过于简单的估值函数和过于复杂的估值函数同样性能不佳。在同等的知识含量下，速度越快，性能越高。在同等速度之下，知识量越大性能越高。在速度和知识量二者的相互作用下，开发者要寻找的是一种平衡，是能够使性能最大化的速度和知识量。没有人能指出具体的估值函数应具备多大的知识量才是合适的，开发者们通常要通过大量的实验，来确定要将哪些知识放进估值函数。StefanMeyer-Kahlen&曾指出，当搜索层数达到一定的深度之后（例如8层），估值函数的知识量显得更重要一些。通常在这时增加一两层搜索深度不能看到明显的性能提高。而估值函数的知识量的增加则较明显的提高了博弈性能。而在层次较浅的搜索当中，不同深度的搜索之间的性能差异则十分明显。3.2 特定棋形的判断分析在A和B对弈的棋局中，一个时刻轮到A对弈时棋盘上可能出现的情况。几种可能获胜的情况：(优先级由高到低)表3-1 获胜情况分析表棋盘上的情况：优先级在棋盘上，A已有任意组活四，或者A已有任意组死四。一步获胜 1在棋盘上，B已有任意组活四，或者B已有任意组死四。2在棋盘上，A已有任意组活三，或者A已有多于一组的死三。两步获胜 3在棋盘上，A已有一组死三 和 任意组的活二。三步获胜 4在棋盘上，B已有任意组活三，或者B已有多于一组的死三。5在棋盘上，B已有一组死三 和 任意组的活二。6 关于棋子死活的规定：轮到一方落子，当它落子后，它的落子连成的一条线有两条不损伤的出路或者它已经连成五子取得胜利，并且，随后不论对手如何落子，仍然至少有一个机会可以进一层。比如说，关于活三的定义：所谓的活三指有两种选择可以冲四，不论对手如何落子，在对手落子之后，仍然至少有一种方法可以冲四。因此，比如B?AAA?B中的A的三个子，不能算是活三；比如B?AAA?B中的A的三个子，也不能算是或三，尽管它有可能成为活四。 考虑到以上的情况，因此在设计估值模块的时候，对那些优先级高的情况给予比较高的鼓励分值Value，通过鼓励分值的不同来划分每一种可能情况，进而以提升电脑棋手的棋力。 在设计的时候，尽可能把所有情况全面考虑，并且，由于先前关于活子的定义，设置为搜索一个预估值位置的时候，需要保证左右展开后碰壁，之间的空间距离至少要有六格(而不是五子)，否则就是死子。 在实现的这个程序中，在估值模块里，主要是通过增加细致的特定棋形的判断来提高电脑棋手的棋力水平。3.3 特定棋型的估值 对于特定的棋型，都有一个不同的估值，以此来区别不同棋型的优劣，也以此来决定最终的落子位置。毫无疑问，像已有四子连成一线且还可以继续落子的情况，明显要比只有三个子连成一线的情况要好，或者说优先级要更高，对弈双方对此种棋局，肯定都是把第一种情况放为首要分析的位置上。因此，要使棋手做出这种判断，就要把第一种情况的估值设置得高。 在上文中的分析中，已经举了一个分析特定棋形的例子，因此能够基本给出正确的判断。 但是对于一系列的落子情况，比如，活四，活三，活二，死四，死三，死二等等，要有不同的并且合理的一个价值数值(即鼓励值)，而这个给定的价值数值同样极其重要。关于这个价值数值可以是预先定好的静态的常量，也可以是通过程序的不断对弈学习，而不断修正这些价值数值。(当然要让电脑通过对弈来学习改变这些特定棋形的鼓励值是极其困难的) 另外，极其细致的特定棋型的划分也是极其关键的。事实上，在一个死三的棋型下，有许多种情况把它们当作同一种棋型其实会产生偏差。比如，“ABBB-”，和“-B-BB-”的情况就很不相同了（-表示空格）。因此，对一些特定的棋型进行细致的划分，是一种可以提高人工智能的方法。 在程序的具体实现过程中，预设置了如下棋形：表3-2 特定棋形的估值棋形名称棋形模式估值(鼓励值)活四?AAAA?300000死四AAAA?2500死四BAAA?A3000死四CAA?AA2600活三?AAA?3000死三AAAA?500死三B?A?AA?800死三CA?AA600死三D1(两侧)A?A?A550死三D2(中间)A?A?A700活二?AA?650死二AAA?150死二B?A?A?250死二C?A?A?200 在设计的时候尽力做到细致划分；而在给于它们的估值上，也尽量拉开差距。通过这些来达到最终估值的准确性。但是比较遗憾的是，笔者在最后测试电脑棋手棋力的过程中发现，在笔者实现的五子棋对弈程序中，深入搜索层数并没有对电脑棋手的棋力有太大提高，笔者在思考后认为，关键原因在于笔者所设计的这些特定棋形的鼓励值仍然有问题，比如说其中特定棋形的活三比死四A所给出的鼓励值要高是没有疑问的，但是高多少，是一个什么样的比值，以及它们和其他特定棋形所给出的鼓励值之间的关系等等，却不是能够轻易能够解决的，也因此，在一层的搜索中，这些问题并没有很明显凸现，但是当层数变深在深入搜索之后，这些问题就出现了。并且在和其他的一些因素相影响之后，如局部估值中的电脑棋手的对弈方针(影响估值的两个分别乘以己方估值和对手估值的系数)，就会使问题变得显而易见。3.4 已落子位置对估值的影响 在估值的时候，必须要考虑棋子的合法落子情况。不同的棋类博弈，其估值必定有极大的差别，各种因为规则而造成的不同因素影响估值的设计。不同的棋类游戏各有所谓的规则，规则中就有博弈双方都可以走哪些着法。某些博弈游戏很容易就找到合理着法，所实现的五子棋，它就具有很简单的落子规则，即棋盘上所有的空位都可以落子，它们都是合理的着法。 具体地说，所设计的五子棋估值需要考虑的因素是预估位置周围有没有被堵，以及棋子具体的位置形式(比如活三，活四)，除此之外还必须考虑大局，即棋子的所处的位置所产生的影响等等。又因为估值是在合法落子位置上的估值，因此可以说它是基于对于合法落子位置判断上的。 而合法落子位置的判断，又由于各种棋类的不同规则而迥然各异。也因此而形成了不同的棋盘表示方法以最有效率的满足估值等的需要。对那些中国象棋和国际象棋等棋子有明显差异“非黑白棋”而言，它们的表示方法可以以棋子为中心，而无需以棋盘为中心，这样可以使电脑在估值以及深度搜索时更加有效率。可以通过只考虑部分棋子而不是整个棋盘来进行操作。 在60年代后期，位棋盘在苏联诞生。通常来说，一个位棋盘是由一个64位的字来表示局面中的某个棋子的状态，一位代表一个格子。由于位棋盘是通过一个字来表现某种棋盘上的状态，因此它在估值分析的时候，可以极快运算出结果。当然，这个对于无差别且落子后即静态的五子棋而言，意义不是很大。(笔者由于在程序中没有用到位棋盘，对位棋盘的具体情况并没有深入了解)3.5 同一位置对敌我双方的影响 在所实现的五子棋程序中，如果当电脑选择落子后，它造成的影响除了对电脑方的棋子产生作用，比如可以冲四，活三等等；另外同时，它也会对对手的棋子产生作用，比如说，能堵住对方棋子的出路。而这个就是同一落子位置对敌我双方造成了的影响。 对一个落子估值的时候，首先在己方的视角上对其进行评估，获得一个返回的估值Value_Me；随后在对方的视角上，假设这次落子的是对方，再进行一次局部的评估，获得一个返回的估值Value_Enemy；通过Value = K1 * Value_Me + K2 * Value_Enemy而获得最终的结果。式子中的K1和K2就是一对关键系数，当K1 / K2 越大的时候，就表示电脑落子的时候，攻击性更强，反之则表示电脑落子的时候更多的考虑是阻断对方的落子，防守性更强些。 没有找到如何公平确定一个落子位置的关于己方和对手的影响的一个公认的确定比值的资料（可能有些由于采用了全局估值，因此这种问题不显得重要）。 这一个比值的数值可以通过每次对弈后的分析，来不断修正。但是在实现的时候，使用的是一个静态的预定值。或者可以通过在每次棋局终局后，通过返回上层的观察，来确定这个比值是否可靠。在实现的程序中，在菜单里提供了可以任用户更改此相关数值的菜单选项，通过调节这两个系数可以设置电脑棋手的对弈方针，是以防守为主，又或者是以进攻为主。3.6 改进和思考3.6.1 基本的程序代码的优化 估值模块在人机博弈中是极其重要的一个模块,它应当比深入搜索模块更影响程序的性能(包括智能和速度)。 就速度言，因为深入搜索模块中是基于估值模块，且需要不停的调用估值模块中的函数的。一个估值函数优化了之后，哪怕优化了一句代码，在深入搜索模块它被调用成千上万次之后，优化后的效果就会很明显；反之，在估值函数中建立了多余的变量或者有了多余的运算，在深入搜索中这些问题将会被放大，从而造成了速度下降。 就智能言，因为深入搜索最终是基于估值模块而知晓哪些落子位置好，哪些落子位置不好，它只能依照这些估值函数给出的数据后进行比较排列，而不会自身产生某个位置的估值，它能做的只是在估值函数的基础上更精确细致的呈现问题，因此说，最终估值模块比深入搜索模块更要影响最终的结果。 也基于此，在估值函数中，那些变量如果事先能够知得数值的，没有必要为了易读而让其在函数中再计算，可以直接赋其数值。而那些可以不申请的变量，那就尽量不能申请(因为变量申请差不多等于成百上千次的加法运算)。在一份资料上看到有专门为了节省估值中所遇到的判定次数，而设计的一个0X88棋盘(Bruce Moreland),这种就是很好的方法。3.6.2 关于估值的设置以及棋力的提高 估值(鼓励值)应该如何设置是一个很关键的问题。因为这个设置是很主观的设置，很难进行客观并且贴切的设置。 事实上关键在于无法确知调整之后的电脑智能是否有提高，或者说由于调整，在设计者以为电脑智能得到提高的时候，其实电脑智能下降了。因为测试电脑博弈智能的方法似乎很烦琐。一个方案也许一个晚上能够设计好，但是调整可能需要一周一月或更长。 总而言之，评估函数可以说是一个博弈程序的关键，直接决定电脑棋手的棋力，但是由于优化估值函数又很难达到一个让人满意的效果。或者可以通过更细致的划分具体的情况，以及一些经验的遗传等等进行设计，或者电脑会简单的自由的思考棋局时，那时或者会有一些好的办法产生。 4 深入搜索模块设计 为了对算法分析的方便，进行统一描述：设置每一个落子位上，落子后对棋局的影响所反映出的一个估值数为Value。另外设定对于人类棋手和电脑棋手而言，都是取尽量取同父同层中合法落子位置中的估值数偏向大的，以下各算法分析都遵照这个假设约定。4.1基本搜索技术 4.1.1博弈树博弈树是从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树，这里称为完全搜索树。 如图1所示 图1 博弈搜索树 此过程类似于在一个状态图中寻求从初始状态通向终了状态的过程。只是状态图搜索仅有一个主体参加，仅是单方面做出的路径选择。而博弈树的搜索则有对立的双方参加，一方只能做出一半选择，而这一半选择的目的是使对方远离其竭力靠近的目标。也就是说状态图搜索是纯粹的或树（OR tree），而博弈树搜索是与或树（AND/OR tree）。 让我们面对一下不幸的实际。那就是，除了极少数非常简单的棋类游戏，大多数棋类游戏，如象棋，我们都没有建立完全搜索树的可能。一方面是因为很多情形根本就到达不了叶子节点，如将一个棋子反复来回走动就可永远循环下去。另一方面，即使我们将循环的情形排除，这棵树上的节点数量也已多到了无法处理的程度。以中国象棋为例，其每一局面可有约20-60种走法。以平均40种走法计，建立一棵（双方各走50步）搜索树就需生成约10160个节点，这远远超出了当今计算机的处理能力。即使生成一个节点仅需10-8秒，生成这棵树也要10140年以上。显然这是不切实际的；也就是说，必须得有其他切合实际的方法。4.1.2 极大极小值算法（MinimaxAlgorithm） 在通常的棋局当中，一个局面的评估往往并不像输、赢、平3种状态这么简单，在分不出输赢的局面中棋局也有优劣之分。也就是说，要用更细致的方法来刻画局面的优劣，而不是仅仅使用1、-1、0三个数字刻画3种终了局面。假定我们有一个函数可以为每一局面的优劣评分。例如甲胜为+ ；乙胜为- ；和局为0；其他的情形依据双方剩余棋子的数量及位置评定- ! + 之间的具体分数。这样我们可以建立一棵固定深度的搜索树，其叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子节点的最小值。这个评分的函数称作静态估值函数（StaticEvaluationFunction）。用以取代超出固定深度的搜索。显然，我们无法拥有绝对精确的静态估值函数。否则，只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分，在此基础上进行的少量搜索的可靠性，理论上是不如前述的WIN，LOST，DRAW 三种状态的博弈树的，但这个方法却是可实现的。利用具体的知识构成评估函数的搜索叫做启发式搜索（HeuristicSearch）。估值函数在有些文献中也称为启发函数（HeuristicFunction）。4.1.3深度优先搜索（DepthFirstSearch） 在生成极大极小树并对其进行搜索的方法上，我们面临着多种选择。几乎所有的人在使用基本的极大极小算法时都选择了深度优先搜索方法。这样可以在搜索过程中的任何时候仅仅生成整棵树的一小部分，搜索过的部分被立即删去。显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现。并且同其他的选择相比，速度上也并不逊色。深度优先搜索极大极小树的过程中，任何时候只要保存与其层数相同个数的节点。仅生成将要搜索的节点，搜索完成的节点可以立即删去以节省空间。用伪代码将深度优先搜索集大极小树算法描述如下：（伪代码仅仅是为说明算法，其内容是简略的。代码假定是用于中国象棋）/类C伪代码，极大极小算法 Int MiniMax（position p，int d） Int bestvalue，value； if（Game Over）/检查棋局是否结束 Return evaluation（p）；/棋局结束，返回估值 if（depth <= 0）/是否叶子节点 Return evaluation（p）；/叶子节点，返回估值 if（p.color= RED）/是否轮到红方走棋 bestvalue = -INFINITY；/是，令初始最大值为极小 Else bestvalue = INFINITY；/否，令初始最小值为极大 for（eachpossiblymovem）/对每一可能的走法m MakeMove（m）；/产生第i个局面（子节点） value = MiniMax（p，d-1）；/递归调用MiniMax向下搜索子节点 UnMakeMove（m）；/恢复当前局面 if（p.color= RED） bestvalue = max（value，bestvalue）；/取最大值 Else bestvalue = min（value，bestvalue）；/取最小值 Return bestvalue；/返回最大/最小值/endofminimaxalgorithm4.1.4负极大值算法（Negamax Algorithm） 普通的极大极小值算法看起来有一点笨，既然一方试图取极大值而另一方试图取极小值也就是说我们总要检查哪一方要取极大值而哪一方又要取极小值，以执行不同的动作。Knuth和 Moore在1975年提出了负极大值（Negamax）方法，消除了两方的差别，而且简洁优雅。使用负极大值方法，博弈双方都取极大值。算法如下面的伪代码所示：/类C伪代码，负极大值算法 Int NegaMax（positionp，intdepth） Int n，value，bestvalue= -INFINITY；/最大值初始为负无穷 if（GameOver（p） Return evaluation（p）；/胜负已分，返回估值。 if（depth=0）/叶子节点 Return evaluation（p）；/调用估值函数，返回估值。 for（eachpossiblymovem）/对每一可能的走法 MakeMove（m）；/产生新节点 value = -NegaMax（p，d-1）；/递归搜索子节点 unMakemove（m）；/撤销新节点 if（value >= bestvalue） bestvalue = value；/取最大值 Return bestvalue；/返回最大值/endofNegamax 可以看出，负极大值算法比极大极小值算法短小并且简单。关键的不同在于：value = -NegaMax（p，d-1） 注意其中的负号。负极大值算法的核心在于：父节点的值是各子节点的值的负数的极大值。如要这个算法正确运作，还要注意一点额外的东西。初看上去，负极大值算法比极大极小值算法稍难理解，但事实上负极大值算法更容易被使用。在算法的原理上，这两种算法完全等效。负极大值算法仅仅是一种更好的表达形式。今天的博弈程序大多采用的也都是基于负极大值形式的搜索算法。4.2搜索算法的改进4.2.1 Alpha-Beta搜索 Alpha剪枝示意图 Beta剪枝示意图将Alpha剪枝和Beta剪枝加入minimax搜索，就得到Alpha-Beta搜索算法。将这个算法用类C的伪代码描述如下：/伪代码，alpha-beta算法Int AlphaBeta（nPly，nAlpha，nBeta）if（game over）return Eveluation； /胜负已分，返回估值if（nPly = 0）return Eveluation； /叶子节点返回估值if（Is Min Node）/此句用于判断当前节点是何种节点/是取极小值的节点for（each possible move m）/对每一可能的走法mMake move m；/生成新节点score = alphabeta（nPly-1，nAlpha，nBeta）/递归搜索子节点unmake move m；/撤销搜索过的节点if（score < nBeta）nBeta = score；/取极小值if（nAlpha >= nBeta）return Alpha；/alpha剪枝，抛弃后继节点return nBeta；/返回最小值Else/取极大值的节点for（each possible move m）/对每一可能的走法mmake move m；/生成新节点score = alphabeta（nPly-1，nAlpha，nBeta）/递归搜索子节点unmake move m；/撤销搜索过的节点if（score > nAlpha） /取极大值nAlpha = score；if（nAlpha >= nBeta）return nBeta；/beta剪枝，抛弃后继节点return nAlpha；/返回极大值/endofalphabeta pseudocodeAlpha-Beta搜索能够让我们忽略许多节点的搜索。对于每一个被忽略的非叶子节点来说，这都意味着不仅节点本身，而且节点下面的子树也被忽略掉了。这就导致了Alpha-Beta搜索需要遍历的节点远远少于极大极小算法所遍历的节点。这也同时意味着对搜索同一棵树来说，Alpha-Beta搜索所花费的时间远远少于极大极小算法所花费的时间。同极大极小搜索算法一样，Alpha-Beta搜索算法也有点繁琐，我们不仅要在奇数层进行al-pha剪枝，而且还要在偶数层进行beta剪枝。不过只要将负极大值的形式套用上去，这样在任何一层都只进行beta剪枝，它就会同负极大值算法一样简洁。使用伪代码描述如下/alpha-beta search with Negamax frameInt alphabeta（int nPly，int alpha，int beta）if（Game over）return eval（）；/胜负已分，返回估值if（nPly<= 0）return eval（）；/叶子节点返回估值for（each possible move m）/对每一可能的走法Make move m；/产生子节点/递归搜索子节点score = -alphabeta（nPly-1，-beta，-alpha）unmake move m；/撤销搜索过的子节点if（score >= alpha）alpha = score；/保存最大值if（alpha >= beta）break；/beta剪枝returnalpha；/返回极大值自1928年极大极小方法诞生以来，其间出现了多种改进搜索效率的方法，但Alpha-Beta搜索算法到目前为止仍是使用最为广泛的搜索算法。也可以说，Alpha-Beta搜索是博弈树搜索的基础技术。4.2.2 Fail-soft alpha-beta在上面的Alpha-Beta的过程中，在搜索开始的时候，我们调用了alphabeta（depth，alpha，beta）；在这里，我们将初始的alpha和beta分别赋予了- 和+ ，在递归调用的过程中，alpha和beta不断改变着。越往后，其范围越小，也就是说，落在其范围之外的内容越来越多。剪枝的效率越来越高。如果我们在一开始就将alpha、beta限定得较小，那么整个的搜索过程是必将减去更多的枝条。但是，我们将可能得到3种结果：一种是要找的目标就落在alpha、beta的范围之内，这样花费了很少的时间就得到了结果；还有两种情况就不那么幸运了，要找的值或者比alpha小，或者比beta大。在这两种情形下，只有重新搜索。但是，在上面的Alpha-Beta过程中，一但搜索失败，我们无法知道任何与结果有关的信息。在这个Alpha-Beta的过程中返回值是alpha。所以它无法返回任何比alpha还小的值。我们对基本的Alpha-Beta做一点形式上的小改进，让它返回当前的score。这样的Alpha-Beta搜索叫做Fail-soft alpha-beta/类C伪代码，Fail-soft alpha-beta searchInt FAlphaBeta（int depth，int alpha，int beta）Int current= -INFINITY；/current= 负无穷if（game over or depth <= 0）/游戏是否结束return eval（）；/返回估值if（depth <= 0）/是否是叶子节点return eval（）；/返回估值for（each possible move m）/对所有可能的走法Make move m；/产生子节点score = -FAlphaBeta（depth-1，-beta，-alpha）/递归搜索新节点unmake move m；/恢复当前局面if（score > current）current= score；/保留极大值if（score >= alpha）alpha = score；/修改alpha边界if（score >= beta）break；/beta剪枝returncurrent；/返回最佳值或是边界/endofFail-softalpha-beta有了这一点改变，就可以从alpha、beta的返回值得到关于结果的一点信息：如果Falphabeta返回值小于初始的窗口，我们知道要找的结果小于alpha；如果Falphabeta返回值大于初始的窗口，我们知道要找的结果大于beta。这一改进并不能使剪枝更有效率，但却是其他一些改进算法的基础。在相当一部分文献当中，Alpha-Beta算法，指的就是Fail-soft alpha-beta这种形式的Alpha-Beta算法。4.2.3渴望搜索（AspirationSearch）这个名字听上去与Alpha-Beta搜索毫无关系的算法是基于 Fail-softalpha-beta的搜索算法。只是在最外部调用时与基本的Alpha-Beta不同。我们在使用Alpha-Beta搜索开始时调用如下语句：alphabeta（depth，-INFINITY，INFINITY）；INFINITY是一个非常大的数，也就是伪代码中的无穷大。这样，一切可能的值都在-INFINITYINFINITY这个范围之中。在向下搜索的过程中，alpha和beta的范围不断缩小，并因而引发更多的剪枝，从而使搜索效率提高。如果我们在一开始就将-INFINITY和INFINITY换成一对小值，会如何呢？这样做实际上在根节点处就给出了小范围的alpha和beta，让剪枝在靠近根节点处就开始了。但是我们无法断定，搜索的结果将在怎样的一对alpha和beta之间。除非alpha和beta是负无穷和正无穷。但是可以猜。假定我们猜测搜索的结果在x附近，那我们可以令alpha=x-window（win-dow是要搜索范围的大小的一半），beta = x +window，调用 Value=FAlphabeta（depth，x-window，x+window）来搜索结果。特别是当window很小的时候，搜索的效率会比较高，因为有了更多的剪枝。可能得到的结果有3种：返回的值Value落在（x-window，x+window）区间内。在这种情况下，我们知道要找的值就在猜测的范围之内，可以直接使用导致此值的BestMove。返回的值Value&x+window。在这种情况下，我们也知道要找的值大于等于 x+win-dow，但是不知道它的精确值是多少。所以这种情形被称为failhigh，此时无疑需要重新给定范围，再次搜索才能找到所要的走法。由于已知要找的值位于value到正无穷之间，通常在重新搜索时会令根节点处的alpha = value，beta = INFINITY，也就是调用FAlphabeta（depth，value，INFINITY）；返回的值vx-window。在这种情况下，我们也知道实际的值小于等于x-window，但是不知道它的精确值是多少。所以这种情形被称为faillow。此时也需要重新给定范围，再次搜索才能找到所要的走法。由于已知要找的值位于负无穷到 value之间，通常在重新搜索时会令根节点处的alpha = -INFINITY，beta = INFINITY，也就是调用FAlphabeta（depth，-IN-FINITY，value）。上面这个方法就叫做渴望搜索。将这个过程用伪代码描述如下：/类C伪代码，渴望搜索Int alpha = X-WINDOW；Int beta = X+WINDOW；for（；）score = FAlphabeta（depth，alpha，beta）if（score <= alpha）alpha = -WIN；