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

摘要：机器博弈是人工智能领域的重要应用之一。以牛角棋博弈为载体，介绍了人机博弈系统中机器博弈引擎和人机接口的设计思想，重点论述了招法生成模块、搜索控制模块和局面评估模块在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)。