对α-β剪枝算法的性能改进研究

论文摘要

α-β剪枝算法是计算机博弈类游戏算法的基础，是一种优化的博弈树搜索算法，使用α-β剪枝算法搜索博弈树时，可以剪去一些不必要的分枝，从而提高搜索效率；而α-β剪枝算法的剪枝效率又取决于所构建的博弈树的分枝的排列顺序，理想排列顺序下的剪枝效率和最差情况下相比差别极大。本文提出的使用机器学习的算法来改进博弈树分枝的排列顺序，可以极大的提高α-β剪枝算法的剪枝效率。在文中，作者介绍了α-β剪枝算法的剪枝原理及已经存在的各种优化算法，给出了构建用于辅助α-β剪枝算法剪枝的学习系统的通用方法及注意事项。为了验证本文所提出的改进方法，作者首先设计并实现了基于α-β剪枝算法的井字棋游戏，然后通过人机博弈来获取用于训练学习系统的训练样例；其次，作者设计并实现了一个BP神经网络，该网络由14个隐藏节点，9个输出节点构成，能够对博弈树的分枝按其成为最佳路径的概率排序，经过前面提取的训练样例的训练后，BP神经网络对测试样本中的50%可以做出正确预测，即训练后的神经网络能够以当前棋局状态为输入，以50%的正确率预测下一步的最佳走法；最后，作者把训练好的BP神经网络加到了井字棋游戏中，经过验证发现，改进后的井字棋与原有井字棋相比，在博弈结果为平局的情况下，所搜索的节点个数可以减少35%左右。经过一系列的尝试和验证发现，本文所提出方法确实能够很大程度的提高α-β剪枝算法的剪枝效率。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 引言
• 1.1 国内外研究现状
• 1.2 课题的主要工作及章节安排
• 第2章 α-β 剪枝算法及其优化原理
• 2.1 α-β 剪枝算法
• 2.1.1 博弈论
• 2.1.2 极大极小值算法
• 2.1.3 α-β 剪枝算法
• 2.2 已有的α-β剪枝算法优化方式
• 2.2.1 编程方面的优化
• 2.2.2 历史启发
• 2.2.3 杀手启发
• 2.2.4 空着搜索
• 2.2.5 置换表法
• 2.2.6 迭代加深
• 2.2.7 negscout 算法
• 2.2.8 其他优化算法
• 2.3 本文所使用的α-β剪枝算法优化方式
• 2.4 本章小结
• 第3章 如何利用机器学习算法实现对节点排序
• 3.1 训练样例的特征项的选择
• 3.2 训练样例的获取
• 3.3 模型选择
• 3.4 过度拟合与欠拟合
• 3.5 本章小结
• 第4章 用于辅助α-β剪枝算法的学习系统的实现
• 4.1 井字棋的实现
• 4.1.1 状态表示
• 4.1.2 确定目标状态
• 4.1.3 静态评估函数
• 4.1.4 候选走法产生
• 4.2 训练样例的特征项的选择
• 4.3 训练样例的获取
• 4.4 模型选择
• 4.4.1 BP 神经元
• 4.4.2 BP 网络
• 4.4.3 BP 神经网络的设计与实现
• 4.4.4 结果分析
• 4.5 结合神经网络的井字棋游戏设计
• 4.5.1 网络的初始化
• 4.5.2 用于排序的神经网络
• 4.5.3 结果分析
• 4.6 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 附录1 经过改进的泛化函数代码
• 附录2 用于训练的 BP 神经网络代码
• 附录3 用于辅助剪枝的 BP 神经网络的初始化代码
• 附录4 BP 神经网络与主函数结合的代码
• 附录5 训练完成后的 BP 神经网络权矩阵
• 致谢