人机对弈五子连

人机对弈五子连摘要研究人机博弈的具体实现，选取五子棋实例进行实现分析，用Java语言实现。在五子棋人机对弈中，通过估值模块，深度搜索模块等，来提高电脑棋手的智能。描述估值模块中的影响精准性的几个要素，以及提出若干提高精准性的办法;试分析MaxMin算法，AlphaBeta算法，FailSoft算法，Aspiration算法，Pvs算法等的实现机制，分析它们之间的关系，以及对它们搜索的节点数进行比较，在这些算法的基础上分析一些提高深入搜索效率的辅助型方案，如历史启发，杀手启发，置换表等等。关键词深度搜索；估值；五子棋;AlphaBeta算法FailSoft算法1引言随着近几十年来人工智能的飞速发展，越来越多的具有智能的机器进入了人类的生活，人工智能的重要性如今显而易见。笔者对人工智能比较感兴趣，而五子棋人机对弈程序的开发实现这个课题，正好提供给我这样一个研究的机会，通过对人工智能中博弈方面的研究（人机对弈），让笔者在简单的人机对弈全局设计，以及具体到相关算法上有了深入的了解。人工智能属于计算机科学的领域，它以计算机技术为基础，近几十年来，它的理论和技术已经日益成熟，应用领域也正在不断扩大，显示出强大的生命力。人工智能大致可以分成几个学科，它们每一个都是独特的，但是它们常常又互相结合起来完成设计任务，这时，这些学科之间的差别就变的很模糊。人工智能在专家系统，自然语言理解，自动定理证明，自动程序设计，人工智能在机器人学、模式识别、物景分析、数据库的智能检索、机器下棋（实质上是博弈论问题）和家用电器智能化等领域都有广泛的应用。而这个课题就是和人工智能中的博弈论领域紧密相关的。广义上来讲，博弈是指在一定的环境条件和一定的规则约束下，依靠自己所能够掌握的信息，从各自选择的行为或是策略进行选择并加以实施，并从各自取得相应结果或收益的过程。冯&S226;诺伊曼（JohnvonNeumann,1903-1957）和摩根斯坦恩（OskarMargenstern,1902-1977）在1944年出版了《博弈论与经济行为》（TheoryofGamesandEconomicBehavior）一书中，最早地提出了关于博弈论的概念。但是，对于非合作、纯竞争型博弈，诺伊曼所解决的只有二人零和博弈。在这里所抽象化后的博弈问题是，已知参与者集会（两方），策略集合（所有棋着），和盈利集合（赢子输子），最终是想去找到一个理论上的解或平衡，也就是对参与双方来说都最合理、最优的具体策略。而在这里狭义的讲，博弈论主要是研究棋手们落子中理性化、逻辑化的部分，并将其系统化为一门科学。换言之，博弈就是研究个体如何在错综复杂的相互影响中得出最合理的策略，博弈论正是衍生于古老的游戏或曰博弈如象棋、扑克等。数学家们将具体的问题抽象化，通过建立自完备的逻辑框架、体系研究其规律及变化。应用传统决定论中的“最小最大”准则，即博弈的每一方都假设对方的所有功略的根本目的是使自己最大程度地失利，并据此最优化自己的对策，诺伊曼从数学上证明，通过一定的线性运算，对於每一个二人零和博弈，都是能够找到一个“最小最大解”的，而这个简单的博弈思想，也即是人机博弈中最基础的组成部分，通过假设对手必定选取他所能选择的最优解来实现。可以这么说，从狭义的'博弈”来讲，人机博弈（计算机下棋）是各个领域博弈理论的起源与基础，在人工智能方面更是一个重要的研究方向。因此，在这里，学习掌握博弈论，无疑对实现人机博弈程序是有帮助的。并且人工智能中的博弈部分，由于采用了大量的搜索算法，其中很多被利用到各方面。它的概念、方法和技术，正在各行各业广泛渗透。智能已经成为当今各种新产品、新装备的发展方向。所以，趁着这个机会，对人工智能中比较容易实现的人机博弈进行了解研究学习，也是很实用且很有必要的。而其中的博弈问题为搜索策略，机器学习等问题的研究课题提供了很好的实际背景，而且博弈问题自身也不断提出了一些新的研究课题，从而推动了人工智能的研究和发展。2初步设计方案笔者通过实现一个五子棋对弈程序来完成这个课题。因为在中国象棋，围棋，国际象棋，黑白棋等各种棋类对弈程序中，其中中国象棋规则比较复杂，但是每一层节点数相对较少；围棋需要十分繁深的估值系统的支持；国际象棋同中国象棋比较类似，它们的各种棋子的走法规则各不相同，都比较繁多，但是每一层搜索的节点数相对较少，它们的估值也较多地需要考虑到全局。而五子棋由于每一层搜索节点数量比较庞大，规则简单，估值函数可以做到比较细致，因此我选择实现五子棋来完成人机博弈课题［4］。在程序的实现上，笔者首先完成界面的设计，在界面的设计上，笔者使用了二维数组的棋盘格式，主要是因为笔者考虑到五子棋的落子后，是不会像象棋那样再次移动的，因此笔者没有选择位棋盘的棋盘模式。随后笔者通过在完成的简单的界面上实现输赢的判断从而实现了人人对弈的功能。在这个基础上，笔者随后实现了简单的棋盘上的位置的估值，通过每个合法位置上的估值数值，可以让电脑确定最终的落子位置，而这些实现是在当前棋盘上的搜索决定的，而并没有深入的通过推算对手的落子位置从而决定自己的落子位置这种通过的搜索而实现。在计算了这些之后，笔者为了进一步地提高程序的智能，因此，为程序设计了深入搜索的模块。通过这种深入搜索，让电脑在推测对手的可能落子的位置之后，随后再来决定自己的落子位置，从而提高了电脑棋手的棋力水平。在笔者完成了程序的深入搜索之后，随后添加了不少辅助的算法，来达到完善深入搜索算法的目的。在这些都完成了之后，笔者对界面进行最后的完善，通过添加各种菜单选项来使用户在和电脑对弈的同时，可以不断的改变和比较程序的各个不同算法之间的优劣。因此综上所述，笔者在程序的结构设计上，主要有三个模块，一个是界面模块，一个是估值模块，一个是深入搜索模块。在具体设计中，估值方面笔者通过比较细致的划分类型来完成此模块功能，通过不同情况下的鼓励值的不同，来使其能够评估出一个相对比较合理切合棋局局势的估值。而在深入搜索方面，笔者通过实现一系列的算法，如负极大值算法，AlphaBeta算法，以及在AlphaBeta算法上改进的FailSoft算法，和调用SoftFail算法的Aspirtaion搜索算法，以及运用了历史启发优化的AlphaBeta算法，历史启发的FailSoft算法，和历史启发的Aspirtaion搜索算法等。通过对这些算法的了解和实现，继而进行深入的分析比较，研究它们的优劣。而在界面中，笔者实现了一个人机对弈程序最基础的几个功能，比如开局，悔棋，清盘，退出，介绍等，另外笔者还由于要分析比较各个深入搜索算法的优劣，而在棋盘上添加了显示每一次计算机搜索的节点数目的标签和为了方便使用而设置了各种搜索算发，历史启发优化和搜索深度的菜单选项，另外为了比较分析估值模块的一些关键数值，笔者还设置了调节电脑棋手棋力水平的若干菜单选项等。3估值模块设计首先，笔者选择用定制棋型（如冲四，双活三等）的方法估值，事实上最早笔者选择了一种区域位置的估值算法，但是由于估值效果的不理想，笔者最终选择了明确的特定棋型的算法来完成估值功能。3.1局部估值和全局估值首先，确定将要被评估的棋盘位置，在评估时，对该将要评估的位置进行忽略。这里，笔者选择了对某一个位置进行估值，而不是对整个棋盘进行估值，原因在于，在五子棋对弈中，棋盘上的优势是累积产生的，而不是突发性的，五子棋要取得胜利连成五子的情况，是只有在已经有四个子的情况下才能产生，每个落子造成的影响，只作用在有限的区域内（这也是五子棋类对弈和象棋类对弈的差别，五子棋中一个棋子落下后的不能再移动，使得它的棋局具有稳定性，但是，同属黑白棋类的奥赛罗棋，又有不同）。而在象棋中，棋子的能力（比如说一个车肯定比一个兵要厉害）是主导因素，因为一个兵的领先（特别是在过了河之后）就可能在关键时刻取得胜利，而它们的体现方式就表现在它所处的位置上，也因此，中国象棋以及国际象棋是必须进行全局估值的；而在五子棋中却没什么影响，每个子的作用是属于叠加性质的；在黑白棋里，还可能因为目前状况的分析而产生误导，一方可能一直处于领先状态，但最后几步局面却被对手翻了盘（这种情况出现在奥赛罗棋中）；而在围棋中又势必是必须进行全盘的分析，因为一直吃子而最后却失败的情况在围棋中并不少见，而围棋的估值的困难是大家有目共睹的（由于笔者的围棋水平不高，因此对其无法进行深入的分析）。因此，局面估计方法完全取决于不同棋类的具体规则（包括子的走法，吃子的规则等等），有鉴于此，笔者所设计的五子棋博弈程序中选择对落子的局部估值。3.2特定棋形的判断分析在A和B对弈的棋局中，一个时刻轮到A对弈时棋盘上可能出现的情况。几种可能获胜的情况：（优先级由高到低）表3-1获胜情况分析表棋盘上的情况：优先级在棋盘上，A已有任意组活四，或者A已有任意组死四。一步获胜1TOC\o"1-5"\h\z在棋盘上，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基本的程序代码的优化估值模块在人机博弈中是极其重要的一个模块。笔者以为它应当比深入搜索模块更影响程序的性能（包括智能和速度）。就速度言，因为深入搜索模块中是基于估值模块，且需要不停的调用估值模块中的函数的。一个估值函数优化了之后，哪怕优化了一句代码，在深入搜索模块它被调用成千上万次之后，优化后的效果就会很明显；反之，在估值函数中建立了多余的变量或者有了多余的运算，在深入搜索中这些问题将会被放大，从而造成了速度下降［10］。就智能言，笔者以为因为深入搜索最终是基于估值模块而知晓哪些落子位置好，哪些落子位置不好，它只能依照这些估值函数给出的数据后进行比较排列，而不会自身产生某个位置的估值，它能做的只是在估值函数的基础上更精确细致的呈现问题，因此说，笔者认为最终估值模块比深入搜索模块更要影响最终的结果。（也有资料表示：每加深一层的搜索所提高的棋力往往比调整的估值模块更显效果）。也基于此，在估值函数中，那些变量如果事先能够知得数值的，没有必要为了易读而让其在函数中再计算，可以直接赋其数值。而那些可以不申请的变量，那就尽量不能申请（因为变量申请差不多等于成百上千次的加法运算）。笔者在一份资料上看到有专门为了节省估值中所遇到的判定次数，而设计的一个0X88棋盘（BruceMoreland），这种