长治学院学士学位论文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所给出的鼓励值要