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

摘要

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

目录

声明

摘要

第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 设计的不足及展望

参考文献

攻读硕士学位期间的研究成果

致谢