论文部分内容阅读
摘要：本文基于实际作品，采用SOPC技术和Nios II处理器，描述了具有人工智能的人机博弈系统的设计原理和实现方法。该系统的硬件以DE0-CV开发板为核心，使用 LTM触摸屏作为人机交互设备，实现了三子棋和五子棋游戏，使用Verilog语言实现了包括触摸屏的显示驱动在内的所有硬件的驱动功能在集成开发环境中用C++语言实现了人机博弈的软件算法。核心算法在实现棋局识别和策略优化的基础上加入了深度搜索算法，提高了系统的全局思考能力。
关键词：SOPC；人机搏弈；五子棋；深度搜索
1、引言
机器博弈是人工智能领域中一个重要且具有挑战性的研究方向之一。它是人工智能的一块试金石，而棋类游戏又是博弈的一个标准型问题，其研究成果中的各种搜索算法、模式识别为人工智能带来了很多重要的方法理论。嵌入式系统已经广泛应用到国民经济的各个方面。基于NiosII软核处理器的SOPC技术凭借其设计方式灵活、开发周期短、可反复重构等特点，日益广泛应用到嵌入式系统开发中。
基于以上的背景，采用SOPC技术来实现人机博弈在嵌入式领域的应用这种设计思想应运而生。本系统选择以五子棋的人机博弈作为设计重点，来阐明基于SOPC的人机博弈系统的设计与开发过程。本设计采用SOPC技术和Nios II处理器实现了机器博弈在嵌入式系统中的应用，这套硬件系统满足游戏的音效和视觉效果，并具备博弈智能。
2、整体设计
2.1本系统实现了以下功能：
1. LCD屏图像显示；
2. 触摸控制功能；
3. Tictactoe和五子棋两种棋的人机博弈；
4. 对弈有双人和人机两种模式可选；
5 对弈难度有初级难度和高级难度两种模式可选；
6. 红外控制提示音输出；
2.2系统总体结构
如图2.1所示，系统总体分为三大模块：FPGA开发板（DE0-CV）、红外语音模块、LTM触摸屏模块，其中：
1.DE0-CV开发板以Altera CycloneV 5CEBA4F23C7N FPGA为核心，使用Verilog语言设计CPU，触摸屏、GPIO及语音红外接口的驱动以及触摸屏的显示内容，CPU上运行软件算法程序并实现对于LTM触摸屏和音频模块的控制
2. LTM触摸屏模块：用来提供人机交互界面，控制整个系统的操作，协调各部分的功能，是人工博弈系统的核心控制单元。 。
3.语音播放模块：实现系统语音提示功能。
3、硬件设计
3.1 DE0-CV 开发板
DE0 FPGA开发板是台湾友晶公司开发的一套轻薄型的SOPC开发平台， DE0搭载了Altera CycloneV 5CEBA4F23C7N FPGA，可提供15，408 LEs（逻辑单元）以及346 I/O，并搭配了丰富的外部接口。
3.2 主控模块
本设计使用Altera Cyclone III EP3C16F484C6N FPGA芯片作为硬件系统的功能平台，在该FPGA上面实现Nios II 软核CPU配置、触摸屏的驱动模块、触摸屏显示设计、红外发射模块和计时器模块的设计等功能。在SOPC Builder中构建的Nios II软核CPU是整个硬件系统的控制核心，它实现了控制系统运转， 计时器开闭，红外发射器控制，触摸屏 显示和外部输入信息获取等功能。
3.3软件部分
由人机博弈算法流程图 4.1可以看出，五子棋机器博弈的核心就是机器走棋的算法，本节将对本系统实现的五子棋机器走棋算法分层介绍，本系统实现的五子棋机器走棋的算法主要包括棋盘表示、局面估值、搜索算法、生成走法、界面控制这几个部分。
1.棋盘显示和界面控制
其中棋盘表示和界面控制即交互界面，在LTM触摸屏上实现，介于五子棋盘的特点，程序中的棋盘表示是采用15*15二维数组来表示的。白子，黑子，空位分别用不同的编码来记录，并加以区分。
2.局面估值、搜索算法、走法生成
由于五子棋机器博弈每一步下棋的过程中，局面估分、搜索算法、走法生成这些过程都是柔和在一起，而不是独立分开的过程，所以本程序也将走法生成、局面估值、搜索算法嵌在一起，构成了机器走棋函数。本系统的对弈设计了两种难度的选择，由两种走棋函数来实现机器不同等级的智能。
初级难度的机器走棋函数只是让机器对目前盘面进行分析，选择最优的位置落子。经过对五子棋知识深入的研究，以及不断的下棋来积累经验，使本设计能够将五子棋机器博弈程序对各种棋型的估分做得很完善，使它能够从盘面“看”出哪一点有利，哪一点不利，并权衡利、弊的大小，从而选择出最优的落子点 。本文实现的估值函数比较完善，所以本系统初级难度的机器走棋函数的效果比较理想。这让初级难度的机器博弈算法对棋型的判断和比较比一般的博弈程序更为出色。本算法实现的高级难度的机器走棋函数让博弈程序在具有正确评估局面能力的基础上，还能够像人一样进行深层次的思考，推导目前盘面N回合博弈之后的局面，从而及早做出合理的进攻和防守策略。
极大-负极大值算法是通过极大-极小值算法[6]变换过来，二者是等价的。极大-极小值算法是考虑双方对弈若干步之后， 从可能的走法中选一步相对好的来走。若最大（Max）节点为甲方下的棋，此时选择估值最大的点走。 最小（ Min ）节点为乙方下的棋， 此时选择估值最小的点行走。因此 Min节点的父节点（ Max节点）所赋的倒推值等于端節点估值中的最大值。另一方面， Max节点的父节点（ Min节点） 所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替使用极小极大的选值方法。这种算法在搜索时将任何机器的弈棋水平都假设为最高，这样的搜索质量很高，得到的走法也比较合理。极大-负极大值算法则是将原本取Min节点对应的负值取反，就变成了正值，所以原本Min节点是取负的最小值，现在则取正的最大值，这就叫极大-负极大值算法。 本算法的估值函数在对黑子和红子估值时，对黑子得到的是正值，对白子为负值。
本算法中实现极大-负极大算法过程如下：
1.先对黑子（机器）估值，對初一组N个极大的值，存为根节点
2.将这层以上的所有走法的棋子依次下入虚拟棋盘后对白子（玩家）估值，每次取出N个节点
3.不断重复1和2 ，直到达到预定搜索深度。
以上过程如下图所示：
图4.2中搜索广度N=3，搜索的深度为3。其中第一层为黑子落子的最好的两个点，即取其估分值最大的两个点。第二层为在第一层的基础上，第一层每个点落子之后，白子最佳的两个落子点。第三层为在前两层的基础上，第二层中每个白子落子之后对应黑子的两个最佳的走法。
搜索广度和深度越大，计算越耗时，但经实验表明机器的博弈智能越高。本系统选取搜索深度为5，广度为3，经大量的实验表明，在不耗费很长的计算时间开销的情况下，博弈算法达到了比较好的智能，较成功的平衡了搜索算法与智能水平之间的矛盾，本文实现的估值函数比较完善，使得该博弈程序能在没有深度搜索的情况下识别出更多的棋型，这种算法显著增强了对搜索的质量，在实现同种智能的情况下大大降低了硬件要求，跟有利于机器博弈算发在嵌入式系统中的应用。这也使得本机在没有深度搜索的情况下，相对于其他的五子棋博弈程序，本系统实现的算法表现更为出色。
参考文献：
[1]Tictactoe[OL].http：//en.wikipedia.org/wiki/Tic-tac-toe
[2]五子棋[OL]. http：//baike.baidu.com/view/2697.htm
[3]张志刚.FPGA与SOPC设计教程—DE2实践.西安电子科技大学出版社[M].2007.4
[4]触摸屏[OL].http：//baike.baidu.com/view/10658.htm
[5]TRDB_LTM_UserGuide_v1.23[OL].http：//www.terasic.com
[6]张明亮.一种新的博弈树搜索算法及其研究应用[D].学位论文.2007.10
[7]史上最聪明的五子棋[OL].http：//www.4399.com/flash/ 30402.htm
[8]皇冠五子棋[OL].http：//www.xiaoyouxi.cn/down/soft/ 730/ 22701.htm
[9]蒋鹏，雷贻祥，陈圆圆.C/C++ 中国象棋程序入门与提高[M].电子工业出版社.2009.5
关键词：SOPC；人机搏弈；五子棋；深度搜索
1、引言
机器博弈是人工智能领域中一个重要且具有挑战性的研究方向之一。它是人工智能的一块试金石，而棋类游戏又是博弈的一个标准型问题，其研究成果中的各种搜索算法、模式识别为人工智能带来了很多重要的方法理论。嵌入式系统已经广泛应用到国民经济的各个方面。基于NiosII软核处理器的SOPC技术凭借其设计方式灵活、开发周期短、可反复重构等特点，日益广泛应用到嵌入式系统开发中。
基于以上的背景，采用SOPC技术来实现人机博弈在嵌入式领域的应用这种设计思想应运而生。本系统选择以五子棋的人机博弈作为设计重点，来阐明基于SOPC的人机博弈系统的设计与开发过程。本设计采用SOPC技术和Nios II处理器实现了机器博弈在嵌入式系统中的应用，这套硬件系统满足游戏的音效和视觉效果，并具备博弈智能。
2、整体设计
2.1本系统实现了以下功能：
1. LCD屏图像显示；
2. 触摸控制功能；
3. Tictactoe和五子棋两种棋的人机博弈；
4. 对弈有双人和人机两种模式可选；
5 对弈难度有初级难度和高级难度两种模式可选；
6. 红外控制提示音输出；
2.2系统总体结构
如图2.1所示，系统总体分为三大模块：FPGA开发板（DE0-CV）、红外语音模块、LTM触摸屏模块，其中：
1.DE0-CV开发板以Altera CycloneV 5CEBA4F23C7N FPGA为核心，使用Verilog语言设计CPU，触摸屏、GPIO及语音红外接口的驱动以及触摸屏的显示内容，CPU上运行软件算法程序并实现对于LTM触摸屏和音频模块的控制
2. LTM触摸屏模块：用来提供人机交互界面，控制整个系统的操作，协调各部分的功能，是人工博弈系统的核心控制单元。 。
3.语音播放模块：实现系统语音提示功能。
3、硬件设计
3.1 DE0-CV 开发板
DE0 FPGA开发板是台湾友晶公司开发的一套轻薄型的SOPC开发平台， DE0搭载了Altera CycloneV 5CEBA4F23C7N FPGA，可提供15，408 LEs（逻辑单元）以及346 I/O，并搭配了丰富的外部接口。
3.2 主控模块
本设计使用Altera Cyclone III EP3C16F484C6N FPGA芯片作为硬件系统的功能平台，在该FPGA上面实现Nios II 软核CPU配置、触摸屏的驱动模块、触摸屏显示设计、红外发射模块和计时器模块的设计等功能。在SOPC Builder中构建的Nios II软核CPU是整个硬件系统的控制核心，它实现了控制系统运转， 计时器开闭，红外发射器控制，触摸屏 显示和外部输入信息获取等功能。
3.3软件部分
由人机博弈算法流程图 4.1可以看出，五子棋机器博弈的核心就是机器走棋的算法，本节将对本系统实现的五子棋机器走棋算法分层介绍，本系统实现的五子棋机器走棋的算法主要包括棋盘表示、局面估值、搜索算法、生成走法、界面控制这几个部分。
1.棋盘显示和界面控制
其中棋盘表示和界面控制即交互界面，在LTM触摸屏上实现，介于五子棋盘的特点，程序中的棋盘表示是采用15*15二维数组来表示的。白子，黑子，空位分别用不同的编码来记录，并加以区分。
2.局面估值、搜索算法、走法生成
由于五子棋机器博弈每一步下棋的过程中，局面估分、搜索算法、走法生成这些过程都是柔和在一起，而不是独立分开的过程，所以本程序也将走法生成、局面估值、搜索算法嵌在一起，构成了机器走棋函数。本系统的对弈设计了两种难度的选择，由两种走棋函数来实现机器不同等级的智能。
初级难度的机器走棋函数只是让机器对目前盘面进行分析，选择最优的位置落子。经过对五子棋知识深入的研究，以及不断的下棋来积累经验，使本设计能够将五子棋机器博弈程序对各种棋型的估分做得很完善，使它能够从盘面“看”出哪一点有利，哪一点不利，并权衡利、弊的大小，从而选择出最优的落子点 。本文实现的估值函数比较完善，所以本系统初级难度的机器走棋函数的效果比较理想。这让初级难度的机器博弈算法对棋型的判断和比较比一般的博弈程序更为出色。本算法实现的高级难度的机器走棋函数让博弈程序在具有正确评估局面能力的基础上，还能够像人一样进行深层次的思考，推导目前盘面N回合博弈之后的局面，从而及早做出合理的进攻和防守策略。
极大-负极大值算法是通过极大-极小值算法[6]变换过来，二者是等价的。极大-极小值算法是考虑双方对弈若干步之后， 从可能的走法中选一步相对好的来走。若最大（Max）节点为甲方下的棋，此时选择估值最大的点走。 最小（ Min ）节点为乙方下的棋， 此时选择估值最小的点行走。因此 Min节点的父节点（ Max节点）所赋的倒推值等于端節点估值中的最大值。另一方面， Max节点的父节点（ Min节点） 所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替使用极小极大的选值方法。这种算法在搜索时将任何机器的弈棋水平都假设为最高，这样的搜索质量很高，得到的走法也比较合理。极大-负极大值算法则是将原本取Min节点对应的负值取反，就变成了正值，所以原本Min节点是取负的最小值，现在则取正的最大值，这就叫极大-负极大值算法。 本算法的估值函数在对黑子和红子估值时，对黑子得到的是正值，对白子为负值。
本算法中实现极大-负极大算法过程如下：
1.先对黑子（机器）估值，對初一组N个极大的值，存为根节点
2.将这层以上的所有走法的棋子依次下入虚拟棋盘后对白子（玩家）估值，每次取出N个节点
3.不断重复1和2 ，直到达到预定搜索深度。
以上过程如下图所示：
图4.2中搜索广度N=3，搜索的深度为3。其中第一层为黑子落子的最好的两个点，即取其估分值最大的两个点。第二层为在第一层的基础上，第一层每个点落子之后，白子最佳的两个落子点。第三层为在前两层的基础上，第二层中每个白子落子之后对应黑子的两个最佳的走法。
搜索广度和深度越大，计算越耗时，但经实验表明机器的博弈智能越高。本系统选取搜索深度为5，广度为3，经大量的实验表明，在不耗费很长的计算时间开销的情况下，博弈算法达到了比较好的智能，较成功的平衡了搜索算法与智能水平之间的矛盾，本文实现的估值函数比较完善，使得该博弈程序能在没有深度搜索的情况下识别出更多的棋型，这种算法显著增强了对搜索的质量，在实现同种智能的情况下大大降低了硬件要求，跟有利于机器博弈算发在嵌入式系统中的应用。这也使得本机在没有深度搜索的情况下，相对于其他的五子棋博弈程序，本系统实现的算法表现更为出色。
参考文献：
[1]Tictactoe[OL].http：//en.wikipedia.org/wiki/Tic-tac-toe
[2]五子棋[OL]. http：//baike.baidu.com/view/2697.htm
[3]张志刚.FPGA与SOPC设计教程—DE2实践.西安电子科技大学出版社[M].2007.4
[4]触摸屏[OL].http：//baike.baidu.com/view/10658.htm
[5]TRDB_LTM_UserGuide_v1.23[OL].http：//www.terasic.com
[6]张明亮.一种新的博弈树搜索算法及其研究应用[D].学位论文.2007.10
[7]史上最聪明的五子棋[OL].http：//www.4399.com/flash/ 30402.htm
[8]皇冠五子棋[OL].http：//www.xiaoyouxi.cn/down/soft/ 730/ 22701.htm
[9]蒋鹏，雷贻祥，陈圆圆.C/C++ 中国象棋程序入门与提高[M].电子工业出版社.2009.5