基于FPGA的牛角棋博弈算法研究与实现

论文摘要

机器博弈是人工智能学科的一个重要研究方向,被称为人工智能领域的“果蝇”,是检验人工智能发展水平的一个重要方面。如今,机器博弈已经成为一个独立而重要,颇有发展前途的学术研究领域,但是它在中国起步较晚。国内外研究专用博弈集成电路系统的成果还较少,基本上都是采用高性能或多CPU的计算机来实现,使系统像大型服务器那样庞大。因此,本文以牛角棋为载体,进行机器博弈算法硬件实现技术的研究,进而为开发体积小、实时性能高的机器博弈专用硬件板卡系统进行探索。本文对牛角棋机器博弈技术进行了研究,并分别使用SOPC和有限状态机开发了完整的牛角棋的双人博弈系统。本文的工作主要在以下几个方面：首先对机器博弈基本搜索算法进行了研究,详细介绍了系统中使用到的极大极小、α-β剪枝、负极大值搜索等算法,并且分析了牛角棋博弈系统的招法生成、评估模块的解决方案。其次分别使用SOPC和有限状态机设计实现了牛角棋的二人对弈系统。基于SOPC的博弈系统使用了固定深度的深度优先的负极大值算法并且使用α-β剪枝技术对博弈树进行优化；而基于有限状态机的博弈系统则使用了基本极大极小算法,并且采用固定深度的深度优先搜索,配合α-β剪枝技术对博弈树进行优化。两种设计方法的共同点是包含的模块相同,都包含招法生成、搜索控制、评估和交互模块,但是使用的设计方法不同。最后对系统进行测试和分析测试结果,并且将两种设计结果进行比较。本设计采用的设计和仿真软件有Altera公司的FPGA开发平台Quartus Ⅱ、仿真软件Modelsim和SOPC开发软件Nios Ⅱ IED,硬件部分采用Altera公司的DE2开发板进行实现。开发板上的FPGA芯片型号为EP2C35F672C6。采用了JTAG下载方式,在开发板上进行调试和验证。在DE2开发板上实现了牛角棋的人机博弈。实验结果表明,本文实现的博弈算法工作稳定、实时性较好,可以为下一步开发专用的博弈硬件板卡系统提供技术基础。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 机器博弈的研究意义
• 1.2 机器博弈的发展与现状
• 1.2.1 机器博弈的发展
• 1.2.2 FPGA在机器博弈中的应用
• 1.3 博弈论
• 1.3.1 博弈的分类
• 1.3.2 博弈论的基本概念
• 1.4 本文的主要工作和结构安排
• 第2章 相关理论简介
• 2.1 牛角棋游戏介绍
• 2.1.1 棋盘
• 2.1.2 棋子
• 2.1.3 棋规
• 2.2 牛角棋博弈系统基础
• 2.2.1 机器博弈系统要素
• 2.2.2 博弈树的展开
• 2.3 招法生成算法
• 2.3.1 棋盘扫描法
• 2.3.2 预置表
• 2.4 机器博弈搜索算法
• 2.4.1 搜索算法的分类
• 2.4.2 极大极小算法
• 2.4.3 α-β剪枝算法
• 2.4.4 负极大值算法
• 2.4.5 置换表
• 2.5 评估函数
• 2.6 本章小结
• 第3章 系统总体设计
• 3.1 系统功能分析
• 3.2 系统需求分析
• 3.3 系统的数学化描述
• 3.3.1 牛角棋的数字化描述
• 3.3.2 招法的形式化描述
• 3.4 系统总体结构
• 3.4.1 初始化模块
• 3.4.2 招法生成模块
• 3.4.3 局面评估模块
• 3.4.4 搜索控制模块
• 3.4.5 人机交互模块
• 3.5 两种实现方法的设计
• 3.5.1 基于NiosⅡ的设计
• 3.5.2 基于优先状态机的设计
• 3.6 本章小结
• 第4章 基于NiosⅡ的牛角棋博弈系统实现
• 4.1 SOPC系统结构
• 4.2 牛角棋博弈系统硬件设计
• 4.2.1 硬件系统总体结构
• 4.2.2 NiosⅡ软核处理器的配置
• 4.2.3 存储器配置
• 4.2.4 并行输入/输出
• 4.2.5 其他
• 4.3 牛角棋博弈软件设计
• 4.3.1 人机对弈信息流程
• 4.3.2 招法生成
• 4.3.3 搜索控制
• 4.3.4 局面评估
• 4.3.5 交互设计
• 4.4 本章小结
• 第5章 基于有限状态机的牛角棋博弈系统实现
• 5.1 开发流程
• 5.2 有限状态机
• 5.2.1 有限状态机简介
• 5.2.2 状态机的HDL设计
• 5.3 牛角棋博弈系统的实现
• 5.3.1 数据表示
• 5.3.2 招法生成
• 5.3.3 搜索控制
• 5.3.4 局面评估
• 5.4 系统仿真
• 5.5 本章小结
• 第6章 测试与结果分析
• 6.1 测试方案设计
• 6.2 测试结果
• 6.2.1 SOPC系统测试
• 6.2.2 状态机系统测试
• 6.3 测试结果分析
• 6.4 NiosⅡ和有限状态机实现结果的比较
• 6.4.1 搜索时间的比较
• 6.4.2 棋力高低的比较
• 6.5 本章小结
• 第7章 总结与展望
• 7.1 工作总结
• 7.2 设计的不足及展望
• 参考文献
• 攻读硕士学位期间的研究成果
• 致谢