基于牛角棋的博弈电路系统设计

摘要：机器博弈是人工智能领域的重要应用之一。以牛角棋博弈为载体，介绍了人机博弈系统中机器博弈引擎和人机接口的设计思想，重点论述了招法生成模块、搜索控制模块和局面评估模块在SoPC系统中的实现方案。在基于NiosⅡ设计的SoPC系统中实现了固定深度的深度优先的负极大值算法并且使用α-β剪枝技术对博弈树进行优化。实验结果表明所设计的博弈电路系统实现了牛角棋人机博弈功能，机器给出招法的时间和效果达到高水平博弈棋手的水准。
关键词：牛角棋；机器博弈；片上可编程系统；人工智能

0 引言
    机器博弈是人工智能学科的一个重要研究方向，被称为人工智能领域的“果蝇”，是检验人工智能发展水平的一个重要方面。国内外研究专用博弈集成电路系统的成果还较少，基本上都是采用高性能或多CPU的计算机来实现，使系统像大型服务器那样庞大。因此，本文以牛角棋为载体，进行机器博弈算法硬件实现技术的研究，使用片上可编程系统(System on a Programmable Chip，SoPC)开发了完整的牛角棋的双人博弈系统。进而为开发体积小、实时性能高的机器博弈专用硬件板卡系统进行探索。

1 牛角棋博弈软件设计
1．1 系统总体结构
    根据牛角棋博弈系统的功能需求分析，将系统进行模块划分，系统总体功能结构如图1所示。

1．2 招法生成
    招法生成模块提供了在局面中选出所有可行招法的功能，从而为正确地展开博弈树提供了支持。
1．2．1 牛角棋的数字化描述
    为了让计算机下棋，首先就要将所有的棋局元素，包括棋盘、棋子、棋局、着法、规则、知识等通过数字化(编码)成为数据元素，而各种数据元素再以特定的关系构成相应的数据结构进行存储和处理。
    牛角棋的棋盘和棋子编码如图2所示。12个棋位编码为0～11，红子用0表示，两黑子分别用1和2表示。这样初始棋局便可有两种形式的表示：
    (1)棋位向量(0，-1，-1，-1，-1，-1，-1，-1，-1，-1，1，2)；
    (2)棋子向量(11，10，0)。

[!--empirenews.page--]
1．2．2 招法的形式化描述
    用表示红蓝3枚棋子在第n步时的棋位，第n步时刻的棋位向量的形式化描述为状态Sn：
    
    式中qn+1为第n+1时刻的招法。
    由于红子走子方向不受限制，可上可下，可横走，只能走向空位，不得跳跃。所以红方棋子可以表述为：
    
    蓝方的棋子走棋方向受到限制，只能上不能下，可以横走，只能走向空位，不得跳跃。故蓝方的两枚棋子可以描述为：
    
1．2．3 预置表招法生成
    预置表可看作一个可快速检索到满足某些简单条件的、预先生成的招法列表的知识库。
    对照图2棋盘的编码方式，参照牛角棋的规则，一种预置招法表的设计方案如图3所示。

    preTable是三维的预置表，其中的两个高维度分别代表了2个条件：
    (1)棋子的颜色是什么；
    (2)棋子处在什么位置上。
    在明确上述两个条件的具体值之后，就可以获得全部可行着法的列表。由于预置表是频繁访问的数据，所以，预置表占用的空间不应太大，而且执行时应以能够载入内存为宜，所以针对具体棋类还须因地制宜地采用一些技巧。
1．3 搜索控制
    在解决机器博弈问题中，搜索是机器博弈的核心，他控制着系统各个模块的调用，他效率的高低直接影响搜索的速度，是决定整个博弈系统棋力高低的首要因素。
    首先，他调用招法生成模块，对当前局面产生所有可能的招法并将产生的招法保存到招法列表中。然后，判断当前局面是否有获胜方，如果有获胜方返回当前局面的估值；否则再判断是否是叶子节点，如果是叶子节点，调用估值模块对当前局面进行估值并将其返回；如果不是叶子节点则按照当前招法走一步棋并且调用自身将刚生成的节点展开，此过程一直持续下去直到分出胜负或者搜索到叶子节点。接着，按照走法将当前局面撤销，退到没有走棋时的局面。然后判断是否需要剪枝。以上过程反复执行，将庞大的博弈树一层一层展开以搜索最佳招法，并将其输出。
    在NiosⅡ系统中，使用递归调用的方式来实现搜索算法，使用负极大值算法(Negamax algorithm)，并且采用固定深度的深度优先搜索，同时配合α-β剪枝技术来搜索最佳招法。
1．4 局面评估
    对叶子结点所对应的局面打分是估值函数的职责，通过对局面的量化值来表示局面的好坏，而博弈树的其他节点的值则通过算法从叶子节点返回得到。函数的输入是待评估的函数，输出是一个数值。
    博弈树的叶子结点是需要调用估值函数加以估值的结点。而博弈树的中间结点和根节点的分值，均可利用极大极小原理从叶子节点的取值倒推出来。除了残局阶段，搜索树中的大部分叶子结点，都是未分胜负的结点，需要估值函数对该局面做出评价，并以数值的形式反映优劣程度。一般地，将所有特征的取值的加权和作为估值函数值。局面p的估值函数V(p)，一般形式如下：
    
    式中：fi表示特征；wi表示权值。
    需要注意到是，对于负极大值算法中叶子节点的估值必须对那一方走棋敏感，评估模块设置使能信号，在搜索状态机发出评估使能信号后，评估模块立即对当前局面进行评估并在一定的延时后返回局面的评估值。如果评估使能信号无效，评估模块的输出保持在高阻态，不对局面进行评估。
[!--empirenews.page--]
2 牛角棋博弈系统硬件设计
    本系统的处理器为NiosⅡ嵌入式软核处理器。NiosⅡ是Altera公司提出的数字系统SoPC解决方案，使得处理器可配置到可编程逻辑器件之中，因此被称为软核处理器。NiosⅡ软核处理器与常见的微控制器相似，它们都是在一个芯片上包含了处理器、存储器、以及输入／输出电路等功能模块。相对于微控制器，NiosⅡ软核处理器最大的特点为它是一种软核、可配置的系统。软核表示处理器的目标器件只有在下载设计文件后才具备处理器的功能；可配置意味着处理器系统的组成和性能可以根据需要进行调整。另外，系统还包含计时模块和PLL分频模块，硬件系统主要包括NiosⅡ快速型内核、SDRAM、三态桥(tristate bridge)cfi控制器、sysid和并行输入输出(pio)。对系统的各个模块添加和配置完成之后，可以使用SoPC Builder自动配置各个模块的的地址和系统的中断。

3 测试结果
    该设计采用的开发板为A1tera公司的DE2 FPGA开发板，板上的FPGA为CycloneⅡ系列，芯片的型号为EP2C35F672C2。
    SoPC系统配置完成以后，在原理图中将系统各个模块的硬件系统进行连接，生成硬件系统原理图。之后，对系统进行综合、时序分析等操作，完成硬件系统的调试。接着对FPGA的引脚进行锁定，然后将硬件系统全编译生成FPGA配置文件用于配置FPGA。在使用QuartusⅡ将SoPC系统硬件配置到FPGA之后即可在NiosⅡIDE中对系统的软件进行在线调试。
    博弈树的搜索最大层数设置为15层，对系统重新进行编译成功以后将FPGA配置文件和软件一起下载到FPGA上进行验证，图4为验证过程中的一些局面。其中(a)为游戏开始时的局面，蓝方2枚棋子和红方棋子的棋位分别为11，10，0，图中显示的是十六进制，此时机器等待用户选择走棋方；(b)为游戏过程中的一个局面，此时蓝方2枚棋子和红方棋子的棋位分别为9，6，4；(c)是游戏结束时的局面，此时红子被蓝子憋在牛角尖处无法移动，蓝方获胜，LEDG7闪亮。

    在SoPC系统中，设置的最大搜索层数为15层。从上面的结果可以看出，每个局面搜索时间最大为2 s，满足系统设计是的性能要求：最大搜索深度大于10层；每个局面最大搜索时间最大不超过3 s。针对系统的智能性和速度方面的测试结果如表1所示。选10个人每人做10次实验，共计100次实验，对实验结果进行综合分析得到数据如表1所示。
    从上面结果可以看出：系统的智能性还有待提高，这主要是为了使系统搜索更快而降低搜索层数导致的结果。

4 结语
    本文以牛角棋的博弈过程为研究载体，论述了机器博弈系统的设计和实现过程。实验结果表明本文方法具有较好的智能性和实时性。随着现代集成技术的发展，FPGA的规模和速度不断提高。更加丰富的逻辑资源和嵌入了RAM块，使得利用FPGA技术设计复杂度很高的棋类博弈系统(如中国象棋)成为可能。