其任意子点的值不能大于,而取极小值的节点，其任意子节点的值不能小于,事实上，算法建立了个范围为,的窗口，对于搜索到的有意义的子节点，其值必在落在,这范围内。故对于最取节点，而算法在搜索取极大值节点的子节点时，值不怕增大，在搜索取最小值节点的子节点时，值不断减小，随着这个窗口不断减小，剪枝效率也就越来越高。因而，改进效率的关键就在于怎么尽可能地缩小,这个窗口的大小而又不失其正确性。这可以从两个方面加以考虑，第种就是人为地减小这个窗口的大小，比较经典的算法有算法渴望搜索极小窗口搜索又称算法，算法是种很优秀的算法，在实际应用中相当普遍，故本文采用搜索来优化。第二种对优化的思路是如果在开始就能够毕业设计论文博弈算法的设计及其实现搜索到比较好的节点，那么很快就能得到比较大的值，很快就能得到比较小的值，从而缩小了窗口的大小，但怎么开始就得到比较好的搜索节点这可能与具体的游戏相关，也可以采用历史启发算法。后面我们分别实现。极小窗口搜索算法算法分析顾名思义，极小窗口搜索中的窗口是最小的容量，该算法先计算第个子节点的值作为当前最佳节点值，如果是取极大值的节点，对以后的子节点搜索中，用,窗口大小搜索，对于取极小值的节点，则用,对后继子节点进行搜索，得到值，由于不能取边界，这实际上是零大小的窗口搜索，所以很快能得到结果，比如取极大值的节点，要么比大，要么比小，比小的节点直接可以忽略过了，但如果比大，也并不准确，但可以确定，最大的值肯定比还要大，故必须重新搜索，采用新的窗口大小，取极大值的节点采用取极小值的节点采用,进行搜索。综上所述，给出算法与般的算法仅在外层调用搜索函数时所给出的,的参数的不同，其余样。所以，仅需要对函数中调用处稍稍进行修改将黑方处的代码改为将白方处的代码改为毕业设计论文博弈算法的设计及其实现预估排序和历史启发下面再来讨论第二种优化思路，开始就搜索较好的节点，从而引发更高效的剪枝。这可以采用子节点预估值排序和历史启发两种方式实现预估排序对于五子棋，最粗略的好判断标准就是看棋盘上同方的棋子连续相连的个数，在大多数情况也确实是这样，我们的估值函数就是这样编写的，所以，对于要搜索的子节点，可以对这些子节点先进行粗略的估值，将这些子节点按他们的估值进行排序，然后，按排序后的节点顺序进行搜索。程序中用类实现了排序的算法，定义了结构该结构保存子节点走法记录在中的粗略估值，用保存所有子节点及其估值，用模板库中的函数进行排序，该排序算法需要向量中的元素有重载的操作函数，用来比较排序。所以在结构中重载了操作符函数。预估值排序的算法实现在类中。也可以将预估值排序与算法相结合，与预估排序的算法大致相同。预估值排序的实现在类中。二历史启发历史启发简单地说就是根据部分已经搜索的结果来调整将要搜索的节点顺序。所要解决的问题又有两个，是如何保存已经搜索过的历史记录，二是如果快速取得这些保存的记录。表由于五子棋的子节点很多每层最多个，不可能保存所有的搜索节点，故只能保存部分节点，当节点很多时，当前搜索的节点是否被搜索过，如何快速地取得该节点，这个时间最好是常量。显而易见，哈稀表很适毕业设计论文博弈算法的设计及其实现合完成这项工作。在实现中，用结构来保存棋局信息，定义如下位校验值棋局的历史搜索得分而在编写使用的程序时，则需要先的头文件。在所有的类的派生类中的函数中遍历每种走法的语句中使用了偿试每个位置毕业设计论文博弈算法的设计及其实现这循环试着在棋盘上的每个位置上下子，表示后面的语句可以并行执行。但这些并行执行必须在循环结束时同步。三需要注意的问题所有并行执行需要注意的问题便是共享变量的读写，在并行的循环中的共享变量在循环外定义的变量有和，并且对它们进行了写操作，所以必须定义临界区临界区名。另外，在并行运行中所调用的函数也应该注意共享变量的问题，上面的循环中调用了，中除估值引擎的指针外都使用的是局部变量，而中所用的估值函数也全都未涉及共享变量写的问题，所以就不需要临界区操作了。毕业设计论文博弈算法的设计及其实现第章总结结论各算法效率对比下表给出了各种算法的效率占有用时间。计算机为白方，黑方先下。计算机为单核的。表各搜索算法在深度时耗时表各搜索算法在深度时耗时因为极大极小值算法不截枝，由极大极小值算法可以知道，当深度为时，白方的第步需要计算个叶子节点，故计算机每秒能计算大约，即每秒大约计算万步，可见，估算法平均每步耗时极大极小值估值排序估值排序估值排序有限范围限定估值排序算法平均每步耗时估值排序估值排序估值排序有限范围限定估值排序毕业设计论文博弈算法的设计及其实现值函数的效率并不太高。从表可以看出，极小窗口算法效率是比效率要高的，因为它开始就用很小的窗口搜索，但加入预估值排序后算法比算法效率要低些了，大概是因为预估值的关系，开始搜索到了比较好的节点，减小了的窗口，剪枝效率已经很高，而算法毕竟要多搜索次，故反而不如预估值排序的算法。当引入预估值排序后，由于开始就搜索了比较好的走法，所以的截枝效率大大地提高，加入表后效率基本差不多，但第步却花了较长时间，再看后面的几步的时间差，基本上是差不多的。速度最快的是有限范围限定估值排序，因为有效范围限定大大减少了搜索范围。综上所述，计算机博弈中的搜索算法是以截枝为基础的，其截枝效率的高低取决于表示的窗口大小，窗口越小，截枝效率越高，其后的各种算法都是围绕减小的这个窗口来进行改进的。成果与不足通过本次毕业设计，基本上掌握了博弈算法的构成，包括走法产生，估值，和搜索三个部分，并对这几部分进行了实现，特别对搜索算法进行实现，掌握了基本的算法原理，能够初步地根据实际情况运用算法并作定程度的改进。现在计算机向着并行处理方向发展，在本次设计中也考虑了并行处理，通过学习的使用，初步了解和掌握了并行处理的些基本原理，如同步互斥共享变量等使用方法。同时，在实现过程中对软件工程的些原理也进行了学习，初步掌握了软件开发的分析设计实现的过程，为将来的进步学习实践打下了定的基础。通过本次实践，也发现了自己很多的不足，自己的实践能力还需要进步提高，在设计过程中经验不中，以后需要多多学习，特别是编写的代码效率不高。如估值部分的效率还不高，需要进步优化。采用表的算法效率还不太高，需要进步优化。对于并行的搜索算法没有进行深入的探索，这也是今后努力改进的个方向。人机界面还需要改进，不太美观计算机在思考时程序会出现假死状态。上述这些方面都当前应该改进的方面，当然，不足之处还有很多，计算机科学知识浩如大海，在今后我将继续努力在计算机科学领域学习探究。毕业设计论文博弈算法的设计及其实现参考文献程序设计清华大学出版社著年月数据结构严蔚敏吴伟民著著年月游戏编程人机博弈重庆大学出版社王小春著年月深入浅出第版华中科技大学出版社侯俊杰著年月面向对象程序设计清华大学出版社谭浩强年月用户指南百度文库年月软件工程机械工业出版社陆丽娜著年月连珠五子棋入门金盾出版社彭建国，那威著年月人工智能及其应用清华大学出版社蔡