基于wujian100 SoC的智能五子棋设备的设计实现及其与QQ游戏玩家

实验室师兄 陈布曾介绍过有关于wujian100 SoC的相关工作 基于Wujian100的KWS SoC拓展开发笔记

在本文中 我们设计了一个实现五子棋AI核心算法的IP核并将其集成到wujian100 SoC上。将整个设计下载到FPGA开发板后便构成了一个“擅长下五子棋”的智能设备。在与FPGA开发板进行通信的计算机端 利用Python设计了五子棋游戏的控制程序及人机交互界面。同时 也基于Python实现了一个五子棋AI的软件程序 因此可以让硬件端的五子棋AI和软件端的五子棋AI进行对弈。在此基础上 构建了相应脚本让wujian100平台上的硬件五子棋AI与“QQ游戏-五子棋”中的广大线上玩家进行对弈 从而充分验证了五子棋AI的棋艺水平。

视频链接

本文的研究重点不在于五子棋的AI算法 而在于其硬件加速实现方法 除了必要的介绍之外 有关于五子棋AI算法的详细内容不会在此展开 有兴趣的读者可以参考知乎话题 五子棋AI

一、基于博弈树的五子棋AI算法简介

五子棋无禁手的基本游戏规则是 双方棋手分别使用黑白两色的棋子 下在棋盘竖线与横线的交叉点上 先形成“五子连线”者获胜。五子棋AI算法的目的就是根据当前的棋局形势寻找到一个最佳的落子点 使得我方的胜算最大。为了判断到底何处落子才是胜算最大 往往需要多往后推算几步 包括“猜测”对方落子 这种搜索方式的拓扑图就是一颗巨大的博弈树 如下图所示

1.1 极大极小值搜索算法

为了判断落点是不是最佳的 通常都是采用对落点位置进行打分的方法 因而需要建立一套评分机制 对己方越有利 分值越高 对敌方越有利 分值越低 负分 。

在博弈树的搜索过程中

将己方走棋的层称为 MAX 层 为了保证己方的利益最大化 选下一层得分最高的分支 将敌方走棋的层称为 MIN 层 为了保证敌方的利益最大化 选下一层得分最低的分支。

若当前节点是黑方回合 则下一步寻找对黑方而言的最佳落点 再下一步寻找对白方而言最佳的落点 依次遍历下去 即所谓的极大极小值搜索算法。

从上图中来看 每一个节点就是一个棋局。当前处于0号节点 深度是0 黑方回合。搜索树向后推算三步 一共得到8种可能的棋局 7 14号节点 利用估值函数对这8个节点进行估计得分 红色标注 。节点3是黑方回合 黑方会选择对自己最有利的走法 此时黑方会走到节点8 同理 节点4的黑方会走到节点9 节点5的黑方会走到节点11 节点6的黑方会走到节点14。节点1的白方 会选择对自己最有利的走法 该走法使得黑方得分最低 所以节点1的白方会走到节点3 同理 节点2的白方会走到节点5。节点0的黑方会选择对自己最有利的走法 黑方会走到节点1。因此 处于当前棋局的黑方 会落子形成节点1的棋局 该落子点就是当前的最佳落子点。

1.2 Alpha-Beta 剪枝算法

通常来讲 一场对局的步数 对应搜索树的深度 很容易达到50步及以上 对应搜索树的层数 每一步还都有多种可能的落子位置 对应每一层搜索树的节点 如果把每一步都遍历到位 搜索量将是巨大的 其时间代价将难以承受。为此 通常采用Alpha-Beta剪枝算法来去除一些明显不适合的节点 以减少运算量。

分别考虑当前节点是 MAX 节点和 MIN 节点的情况 约定函数 f(node) 表示节点 node 的估值得分 有

当前节点是 MAX 节点 当前节点记为 M 节点 M 有一个 MIN 子节点 记为 m1 且 f(m1) α 则必有 f(M) ≥ α。这是因为节点 M 是 MAX 节点 会选择所有子节点中估值最大的那个节点 所以 MAX 节点不会选择估值比 α 还小的子节点 而只会选择估值比 α 还大的子节点 所以得到 f(M) ≥ α 该值称为 “MAX 节点的 α 值” α 值刻画了 MAX 节点的下界 当前节点是 MIN 节点 当前节点记为 m 节点 m 有一个 MAX 子节点 记为 M1 且 f(M1) β,则必有 f(m) ≤ β 这是因为节点 m 是 MIN 节点 会选择所有子节点中估值最小的那个节点 所以 MIN 节点不会选择估值比 β 还大的子节点 而只会选择估值比 β 还小的子节点 所以得到 f(m) ≤ β 该值称为 “MIN 节点的 β 值” β 值刻画了 MIN 节点的上界。

一般情况的 α-β 剪枝规则 已在上图中标注

α 剪枝 当前节点是 MAX 节点 其 α 值大于等于其父节点的 β 值 则可以将以当前节点为根节点的子树剪枝 该剪枝称为 “α 剪枝”
β 剪枝 当前节点是 MIN 节点 其 β 值小于等于其父节点的 α 值 则可以将以当前节点为根节点的子树剪枝 该剪枝称为 “β 剪枝”。

有关于极大极小值搜索算法和Alpha-Beta剪枝算法的详细内容可以参考以下文章

1) 基于博弈树的五子棋 AI 算法及其 C 实现

2) 五子棋AI算法第二篇-极大极小值搜索算法

3) 五子棋AI算法 三

1.3 估值函数

从上文的叙述中可以看出 估值函数的好坏直接影响了决策树的搜索过程和路径判断 所以估值函数的定义至关重要。关于五子棋的估值函数 不同学者的定义往往大不相同 这也导致决策树的效率和正确率都有较大偏差。

在此 我们参考了以下文章中的估值算法

基于C的α-β剪枝算法实现的AI五子棋游戏

对于一个二维的棋面 五子棋的胜负只取决于一条线上的棋子 根据这一特征 考虑将二维的棋面转换为一维的 按照四个方向来将棋盘转换为 15 × 6 个长度不超过 15 的一维向量 参考下图

评估每个线状态 将每个线状态的评分进行汇总 当做棋面评分

evaluateValue ∑ evaluateLine(lineState[i])

接下来所要做的就是评价每一条线状态 根据五子棋的规则 可以很容易穷举出各种可能出现的基本棋型 首先为这些基本棋型进行识别和评价 得到如下图所示的静态估值表

并且统计每个线状态中出现了多少种下面所述的棋型 并据此得出评价值。考虑到一些实际情况 如果搜索到第四层 总共需要搜索

224 224 × 223 224 × 223 × 222 224 × 223 × 222 × 221 2,461,884,544

个状态节点 搜索如此多的状态节点的开销是十分可观的 因此 提高效率的方式就在于如何减少需要搜索的状态节点。

利用 α - β 剪枝算法对博弈树剪枝 每次搜索仅搜索落子点周围 3 × 3 格范围内存在棋子的位置 这样可以避免搜索一些明显无用的节点 避免对必胜/负局面搜索 当搜索过程中出现了必胜/负局面的时候直接返回不再搜索 规划搜索顺序 很多有价值的落子点更靠近棋盘中央 如果从棋盘中央向外搜索的话 则能够提高 α - β 剪枝的效率。二、五子棋AI核心算法的硬件实现

本次工作中 我们使用XILINX VIVADO HLS编写C 源程序 综合出硬件Verilog代码 封装成IP核 然后将其集成于wujian100 SoC平台之中。

2.1 极大极小值搜索算法的编程实现

代码主体本质上是一个递归函数 但由于递归函数无法被综合 因为可能出现无穷无尽的迭代 硬件上无法实现 在考虑到最大搜索深度不会超过4层 否则 搜索时间太长 的前提下 实例化4个相同的函数 以供层层调用。

编程思路如下

第一步 假设我方 或者对方 落子 更新棋盘状态 判断棋面输赢 如果已经输了或者赢了就没必要继续搜索下去了 否则 遍历棋盘上可落子的位置 假设对方 或者我方 落子 进入下一层搜索 得到上一步搜索返回的权值weight 更新下层上界max 或者下层下界min 当前节点为MAX_Node时 如果max ≥ alpha 此处的max是在当前节点的子节点中已搜索出的最大值 在全部搜索完成前等价于当前节点的 α 值 此处的alpha是当前节点的父节点下的其它子节点中已搜索出的最小的 α 值 在全部搜索完成前等价为上层父节点的 β 值。即满足当前节点的α ≥ 父节点的β的条件 则可以直接返回至上一层 将当前节点及其子节点全部剪枝 即 α 剪枝 当前节点为MIN_Node时 如果min ≤ beta 此处的min是在当前节点的子节点中已搜索出的最小值 在全部搜索完成前等价于当前节点的 β 值 此处的beta是当前节点的父节点下的其它子节点中已搜索出的最大的 β 值 在全部搜索完成前等价为上层父节点的 α 值。即满足当前节点的β ≤ 父节点的α的条件 则可以直接返回至上一层 将当前节点及其子节点全部剪枝 即 β 剪枝 否则 返回已搜索出的下层节点中的最大值max 或者是最小值min 搜索到限定层数之后 评估棋面 返回权值。

相关参数定义如下

参数定义ChessBoard用于存放棋盘状态的二维数组BOARD_SIZE棋盘规格 默认为15 × 15x, y当前节点的位置坐标type当前节点的类型 MAX_Node / MIN_Node depth搜索深度 从0开始 递归一次 数值加1 alpha当前节点的父节点下的其它子节点中已搜索出的最小的 α 值 即当前层的下界beta当前节点的父节点下的其它子节点中已搜索出的最大的 β 值 即当前层的上界

部分源代码如下

1. for (j j BOARD_SIZE; j) {
2. for (i i BOARD_SIZE; i) {
3. if (ChessBoard[j][i] EMPTY canSearch(ChessBoard, i, j)) {
4. weight minMax3(ChessBoard, i, j, nextType(type), depth 1, min, max);
6. if (weight max)
7. max weight; // 更新下层上界
8. if (weight min)
9. min weight; // 更新下层下界
11. // alpha-beta
12. if (type MAX_NODE) {
13. if (max alpha) {
14. ChessBoard[y][x] EMPTY;
15. return max;
16. }
17. }
18. else {
19. if (min beta) {
20. ChessBoard[y][x] EMPTY;
21. return min;
22. }
23. }
24. }
25. else
26. continue;
27. }
28. }
c 

2.2 五子棋IP核集成方法

设计完成五子棋IP核之后 将其集成到wujian100 SoC平台之中 用Vivado综合出网表 并生成bit流 下载到平头哥的XC7A-FPGA开发板中。然后使用配套的CDK开发软件编写C程序 通过uart串口与计算机通信 与计算机端Python程序进行联合仿真。在此之前 有必要先简单介绍一下wujian100 SoC平台。

2.2.1 wujian100 SoC平台简介

wujian100_open是一个基于MCU的SoC平台 支持通过EDA工具进行前端仿真和制作FPGA进行测试 其硬件组成结构如下图所示

我们的IP核就是挂载于图中低速总线上的Dummy 0/1/2/3预留接口处。

2.2.2 平头哥 XC7A-FPGA开发板简介

平头哥开发的基于Xilinx Artix-7系列FPGA的开发板主要用于平头哥中低端CPU核的验证和评估 板上集成了Xilinx Artix-7 XC7A200T FPGA芯片。

2.2.3 五子棋AI IP核设计

整个IP核的顶层采用了AXI-Stream协议进行数据传输 共存在三个接口

参数定义control_in控制端口data_in数据输入端口data_out数据输出端口

对control_in写“0”会将棋盘复位 写“1”之后即开始通过数据加载模块data_in接收输入落子坐标 经过核心计算模块计算之后 通过数据输出模块data_out输出五子棋AI的落子坐标。

我们这个IP是用Vivado HLS进行设计的 在整个程序中 对棋盘进行遍历和判断时用到了大量的for循环 Vivado HLS提供了一个流水线优化 我们对所有的循环进行了优化 综合之后得到以下Timing报告

预估最大时钟频率可达106.22 MHz 各类资源消耗如下图所示

在这个IP核设计中并没有用到DMA 因为这里主要涉及到的位置为坐标 不涉及到大量的数据传输 所以 我们直接将其挂载到E902上 通过AHB转AXI的IP核相连接。E902则是在接收到PC端落子坐标的信息后 把数据传输到IP核 IP核进行落子判断后 把数据返回给E902 E902再返回给PC。

三、软硬件协同仿真

我们在使用Vivado HLS工具设计完成了五子棋AI的C 源程序之后 同时编写了C 测试程序 初步仿真算法程序的功能正确性。测试程序tb.cpp主模拟了四步落子输入

1. int posx[4] {7,7,8,8};
2. int posy[4] {7,8,6,7};
c 

仿真结果如下

1. 6 6 7 6 6 8 6 7

下图直观地反映了仿真时的博弈过程

从五子棋的常用战术来看 我们的五子棋AI算法的每一步“出招”都合乎预期 但是 这仅仅只能当做初步的仿真判断。为了更准确地评估算法的智能水平 我们将IP核挂载在了wujian100 SoC平台上 并下载到FPGA开发板中 与计算机之间通过uart串口进行通信 分别使用CDK开发工具和Python完成联合仿真。

3.1 CDK C源程序

wujian100 开源项目中包含了一个uart的example程序 我们在此基础上编写完成CDK C源程序 程序的主要功能描述如下

通过串口接收计算机端Python程序发送过来的落子坐标或者是重开棋局信号reset
在接收到计算机端reset信号之后 通过往GB_CONTROL_IN_BADDR端口写“0”来重开棋局
在接收到计算机端落子坐标之后 将其发送给五子棋AI IP核
接收五子棋AI IP核返回的落子坐标 并将其发送给计算机。

1 接收计算机端落子坐标的方法

uart串口发送过来的数据是32位int型 但是uart在发送数据时是按一个byte接一个byte来的 先发送的是低8位数据 因此在接收的时候要将4个byte的数据拼接成一个32位数据

1. static uint8_t posPlayer[8] {0}; // 数组存放的是连续接收到的8个字节的坐标数据
2. ...
3. x_tmp posPlayer[3] 24 | posPlayer[2] 16 | posPlayer[1] 8 | posPlayer[0];
4. y_tmp posPlayer[7] 24 | posPlayer[6] 16 | posPlayer[5] 8 | posPlayer[4];
5. x_pos *(uint32_t *) x_tmp; // 计算机落子横坐标
6. y_pos *(uint32_t *) y_tmp; // 计算机落子纵坐标
c

2 复位棋局的方法

将计算机端发送过来的坐标x, y都等于99作为复位本局游戏的reset信号 补充 如果x, y 15, 15 表示硬件端AI先手落子 由IP核内部相应的函数控制)

1. if(x_pos 99 y_pos 99) *(volatile uint32_t *) GB_CONTROL_IN_BADDR 0x0;
c

3 向IP核发送坐标点的方法

先向GB_CONTROL_IN_BADDR写“1” 然后向GB_DATA_IN_BADDR写横坐标x 再向GB_DATA_IN_BADDR写纵坐标y。

1. *(volatile uint32_t *) GB_CONTROL_IN_BADDR 0x1;
2. *(volatile uint32_t *) GB_DATA_IN_BADDR x_pos;
3. *(volatile uint32_t *) GB_DATA_IN_BADDR y_pos;
c

4 接收AI落子坐标的方法

在向IP核和发送完坐标之后 C程序会等待IP核计算完成并返回落子坐标。之前说过 IP核的数据传输方式是AXI Stream协议 我们将其valid信号接到了wujian100 SoC的中断引脚上。当IP核计算完成发回数据时 会触发MCU的中断 然后 在其中断服务程序go_bang_intr()中接收AI落子坐标 并通过串口发送到计算机端

1. void go_bang_intr(void)
3. xy_result[0] *(volatile uint32_t *) GB_DATA_OUT_BADDR;
4. xy_result[1] *(volatile uint32_t *) GB_DATA_OUT_BADDR;
5. printf( %d\n , xy_result[1]);
6. printf( %d\n , xy_result[0]);
c

3.2 计算机端Python源程序

前面提到过 我们的五子棋AI算法只是五子棋游戏的核心算法 相应的控制程序是通过Python来编写的 为此 我们参考了以下项目中完整的Python五子棋游戏

参考项目中同样使用Alpha-Beta剪枝算法实现了一个五子棋的AI 只不过其估值函数与我们的硬件AI有所不同。同时项目中还包含完整的人机交互界面 我们在其基础上修改源程序 实现Python端AI与硬件端AI的即时对战。

Python端AI的落子坐标将通过串口发送到FPGA开发板

1. posPlayer []
2. x, y self.AI.findBestChess(self.map.map, self.player)
3. ...
4. posPlayer.append(struct.pack( i , int(x)).hex())
5. posPlayer.append(struct.pack( i , int(y)).hex())
6. tmp .join(posPlayer)
7. data_in binascii.unhexlify(tmp)
8. ser.write(data_in) # 通过串口发送Python端落子坐标
python

然后 Python端将通过另一个线程来接收FPGA端通过串口发送回来的硬件端AI落子坐标

1. posAI []
2. ...
3. def Receiving(): # 接收函数
4. global posAI
5. while True: # 循环接收数据
6. if ser.in_waiting: # 当接收缓冲区中的数据不为零时 执行下面的代码
7. strr ser.read(ser.in_waiting).decode( gbk )
8. posAI.append(strr)
9. else:
10. if threading_end_flag:
11. break
python

游戏的画面显示以及游戏胜负的最终判断都是在计算机端通过Python程序来完成。

除此之外 我们也可以让硬件端AI与人类玩家对战 实现人机对战 只需将Python AI的落子坐标替换成人类玩家的落子坐标即可 具体方法不再赘述。

3.3 硬件端AI vs 软件端AI

至此 整个软硬件协同仿真的过程可以总结如下

CDK C程序初始化五子棋AI IP核 等待接收计算机端Python AI落子坐标 Python源程序初始化 通过串口向FPGA发送Python AI落子坐标 FPGA端接收Python AI落子坐标 将其发送给硬件五子棋AI IP核 FPGA端通过中断来接收五子棋AI IP核返回的落子坐标 将其通过串口发送给计算机 再次等待接收计算机端Python AI落子坐标。

硬件端AI vs 软件端AI的记录如下图所示

其中白方属于硬件端AI 黑方属于软件端AI 白方先手。利用timer不完全精确地记录双方运行时间后 得到以下加速比 双方AI算法不完全相同 仅作参考

3.4 人机对战实验

由于五子棋AI使用的算法是相对固定的 两个AI的对战并不会产生多样性 因此 有必要考虑让我们的AI去与真正的人类对弈。为此 我们特地用Python编写了一个Script 让我们的五子棋AI能够与QQ游戏大厅中广大的五子棋玩家对弈 同时记录数据 视频演示见本篇开头链接 。

在花费了两个星期的时间记录了700场对局之后 我们剔除了少部分步数不超过10步的对局 有效的对局数一共有673场 并统计了先手胜率和后手胜率 以及对局结束后总步数的分布情况 如下表所示

先后手场次胜率先手33384.08%后手34070.00%总共67376.97%

上图是对局步数分布直方图 胜率分布折线图 从上图可以看出80%的对局步数都在50步以内 同时可以发现我们的AI的胜率随着对局步数的增加呈现出先下降后上升的趋势 在对局步数处于80-89步之间的时候胜率降至最低——40.0% 在考虑到玩家水平差异后分析得出以下结论

大部分玩家与我们的AI“过不了几招” 在90回合以后 玩家们与我们的AI“纠缠“越久越难取胜 即使是高水平的玩家想要战胜我们的AI也并不容易 往往需要足够的回合数。四、总结

我们使用Vivado HLS设计实现了基于Alpha-Beta剪枝算法的五子棋AI 并将其集成于wujian100 SoC之中 然后使用FPGA开发板通过串口与计算机相互通信完成软硬件协同仿真 仿真结果充分体现出了硬件加速的效果。在此基础上 我们还编写脚本实现五子棋AI与广大线上玩家对弈 验证了五子棋AI的智能水平。

本文转自网络，原文链接：https://developer.aliyun.com/article/783923
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！