编辑语：
技术解码栏目：是面向开发者详细解读芯片开放社区（OCC）上关于处理器、芯片、基础软件平台、集成开发环境及应用开发平台的相关技术，方便开发者学习及快速上手，提升开发效率。
近日，来自复旦大学的王松、陈布同学，基于wujian100 SoC开发了五子棋AI设备，并通过人机对战，充分验证了五子棋AI的智能性。
（五子棋AI设备人机对战过程演示）
本周【技术解码】要为大家介绍的是，王松、陈布同学设计开发五子棋AI设备的实战过程。本文将概述该案例的开发过程，讲解基于博弈树的五子棋AI算法原理。有关五子棋AI算法的硬件实现、软硬件协同仿真等具体的开发内容，将在后续的《揭秘五子棋AI设备的炼成：wujian100 SoC助力人机对弈（下）》中更新。
作者介绍
王松：复旦大学微电子学院2020级直博生
陈布：复旦大学微电子学院2019级硕士研究生
一、前言
wujian100 SoC是平头哥基于RISC-V架构打造的开源的芯片设计平台，该平台是一款超低功耗的MCU平台，也是一款基于安全可信系统框架与CSI标准软件接口，支持从硬件到软件到系统的全栈敏捷开发。在此平台基础上，可以快速地进行IP核拓展并进行系统前端仿真，并对拓展的硬件设计部分进行功能验证。
二、开发过程概述
① 设计一个实现五子棋AI核心算法的IP核并将其集成到wujian100 SoC上。
② 将整个设计下载到FPGA开发板后便构成了一个“擅长下五子棋”的智能设备。
③ 在与FPGA开发板进行通信的计算机端，利用Python设计五子棋游戏的控制程序及人机交互界面。同时，再基于Python实现一个五子棋AI的软件程序，因此可以让硬件端的五子棋AI和软件端的五子棋AI进行对弈。
④ 在此基础上，构建相应脚本让wujian100平台上的硬件五子棋AI与“QQ游戏-五子棋”中的广大线上玩家进行对弈，从而充分验证五子棋AI的棋艺水平。
三、基于博弈树的五子棋AI算法简介
五子棋无禁手的基本游戏规则是，双方棋手分别使用黑白两色的棋子，下在棋盘竖线与横线的交叉点上，先形成“五子连线”者获胜。五子棋AI算法的目的就是根据当前的棋局形势寻找到一个最佳的落子点，使得我方的胜算最大。
为了判断到底何处落子才是胜算最大，往往需要多往后推算几步，包括“猜测”对方落子，这种搜索方式的拓扑图就是一颗巨大的博弈树，如下图所示：
3.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的棋局，该落子点就是当前的最佳落子点。
3.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算法（三）
3.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 格范围内存在棋子的位置，这样可以避免搜索一些明显无用的节点；
- 避免对必胜/负局面搜索，当搜索过程中出现了必胜/负局面的时候直接返回不再搜索；
- 规划搜索顺序 ，很多有价值的落子点更靠近棋盘中央，如果从棋盘中央向外搜索的话，则能够提高 α - β 剪枝的效率。
