实验室师兄@陈布曾介绍过有关于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.3 估值函数
从上文的叙述中可以看出,估值函数的好坏直接影响了决策树的搜索过程和路径判断,所以估值函数的定义至关重要。关于五子棋的估值函数,不同学者的定义往往大不相同,这也导致决策树的效率和正确率都有较大偏差。
在此,我们参考了以下文章中的估值算法:
对于一个二维的棋面,五子棋的胜负只取决于一条线上的棋子,根据这一特征,考虑将二维的棋面转换为一维的,按照四个方向来将棋盘转换为 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 × 15 |
x , y
|
当前节点的位置坐标 |
type |
当前节点的类型(MAX_Node / MIN_Node ) |
depth |
搜索深度(从0开始,递归一次,数值加1) |
alpha |
当前节点的父节点下的其它子节点中已搜索出的最小的 α 值,即当前层的下界 |
beta |
当前节点的父节点下的其它子节点中已搜索出的最大的 β 值,即当前层的上界 |
部分源代码如下:
1. for (j = 0; j < BOARD_SIZE; ++j) { 2. for (i = 0; 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); 5. 6. if (weight > max) 7. max = weight; // 更新下层上界 8. if (weight < min) 9. min = weight; // 更新下层下界 10. 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) 2. { 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]); 7. } 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场,并统计了先手胜率和后手胜率,以及对局结束后总步数的分布情况,如下表所示:
先后手 | 场次 | 胜率 |
先手 | 333 | 84.08% |
后手 | 340 | 70.00% |
总共 | 673 | 76.97% |
上图是对局步数分布直方图 & 胜率分布折线图,从上图可以看出80%的对局步数都在50步以内,同时可以发现我们的AI的胜率随着对局步数的增加呈现出先下降后上升的趋势,在对局步数处于80-89步之间的时候胜率降至最低——40.0%,在考虑到玩家水平差异后分析得出以下结论:
- 大部分玩家与我们的AI“过不了几招”;
- 在90回合以后,玩家们与我们的AI“纠缠“越久越难取胜;
- 即使是高水平的玩家想要战胜我们的AI也并不容易,往往需要足够的回合数。
四、总结
我们使用Vivado HLS设计实现了基于Alpha-Beta剪枝算法的五子棋AI,并将其集成于wujian100 SoC之中,然后使用FPGA开发板通过串口与计算机相互通信完成软硬件协同仿真,仿真结果充分体现出了硬件加速的效果。在此基础上,我们还编写脚本实现五子棋AI与广大线上玩家对弈,验证了五子棋AI的智能水平。