浅谈博弈电路系统设计

机器博弈是人工智能学科的一个重要研究方向，被称为人工智能领域的“果蝇”，是检验人工智能发展水平的一个重要方面。国内外研究专用博弈集成电路系统的成果还较少，基本上都是采用高性能或多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)。

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表示权值。

需要注意到是，对于负极大值算法中叶子节点的估值必须对那一方走棋敏感，评估模块设置使能信号，在搜索状态机发出评估使能信号后，评估模块立即对当前局面进行评估并在一定的延时后返回局面的评估值。如果评估使能信号无效，评估模块的输出保持在高阻态，不对局面进行评估。

2 牛角棋博弈系统硬件设计

本系统的处理器为NiosⅡ嵌入式软核处理器。NiosⅡ是Altera公司提出的数字系统SoPC解决方案，使得处理器