WindowsProject/AI-arith.cpp // 核心算法源文件
WindowsProject/AI-arith.h // 核心算法头文件
WindowsProject/main.cpp // UI界面及主函数源文件
five-in-a-row.exe // 可执行文件：五子棋小游戏
Windows Desktop Application
C++
目标是实现一个五子棋人机博弈小游戏，游戏应满足以下条件：
- 人执黑棋，计算机执白棋；
- 左键落子，右键悔棋。
求解五子棋这类博弈问题的方法即对抗搜索。这里通过设计评价函数，基于极大极小算法和α-β剪枝，达到人机博弈的目的。
从空棋盘开始，每步行棋之后，将当前棋盘及其相关信息记录到一个状态state中，并以一个state为一个结点建立搜索树，以完成对下一步行棋位置的搜索和悔棋等操作。
在人工智能领域中，一般用Agent表示可以感知环境并在环境中行动的事物，它通过传感器感知环境并对所处环境产生影响。
数学中的__博弈论__（Game Theory）是经济学的一个分支。当一个问题中存在多个Agent，且每个Agent都会受到其它Agent的显著影响时，不论这些Agent之间是合作的还是竞争的，我们都可以将该问题看作__博弈__（Game）。人工智能中的博弈通常指的是有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。五子棋就是博弈的一个很好的例子，如果一方获胜，那么另一方一定落败。
在解决这类问题的过程中，我们不但需要考虑自身行动，还需要考察对手的行动。解决这类问题的方法可以称为__对抗搜索__（Adversarial Search）。
极小极大算法（minimax algorithm）是对抗搜索的一类经典算法。以两个Agent（人和AI）参加的博弈为例，下面将用尽可能简单的语言对算法加以阐述。
假设某时刻棋盘上各棋子的位置已知，此时轮到计算机行棋，以搜索两层为例，算法的具体实现过程如下：
- 考虑计算机能够落子的位置：依据五子棋的规则，计算机容易找到所有合理的落子位置；
- 考察对手可能的行动：对于计算机的每种落子方案，考察对手在下一步可能的落子位置。 这里计算机应当假设其对手是“聪明”的，也就是说，他总是能找出对他自身最有利的落子位置。通过上述过程便能够建立极小极大算法的搜索树，如下图中的黑色部分所示。
根据上面的分析，这里需要定义一个函数h(x)，用于评价棋盘上各棋子呈现出的某一形态对计算机而言的优劣程度，称之为评价函数。h(x)越大，则说明此时的形势对计算机越有利，反之则不利。此时对于参加博弈的两个Agent，试图使h(x)尽可能大的一方通常称为MAX，另一方称为MIN。关于评价函数如何定义和优化，在后文的“评价函数的设计”中会进行详细分析。
有了评价函数h(x)之后，便能够实现上述算法。在轮到计算机落子时，计算机枚举每种落子方案，并“预想”下一步对手可能的行动。由于对手的行动会使h(x)尽可能小，因此应当选取计算机的每种落子情况下，对手不同行动产生的h(x)中最小的一个，用MIN表示这种落子方案后的结果，并从所有MIN中选取最大值，按照最大值所属的方案落子，如上图中的红色部分所示。极小极大算法也由此得名。
上述只是极小极大算法中搜索两层的情况。在实际应用中可能需要考虑搜索多层，此时对手也可能会通过极小极大算法搜索得到落子方案，因此算法的计算量将随着层数的增加呈指数级增长。
α-β剪枝（alpha-beta pruning）是一种应用于极小极大搜索树上的剪枝方法，能够在很大程度上降低搜索的时间代价。
依据极小极大算法的特性，搜索树上MAX层和MIN层总是交替出现。在搜索过程中，可以时刻为每一结点维护一数对(α,β)，分别记录该结点当前可取评价函数的最小和最大值。对于MAX层而言，若其下一层出现评价函数小于α的结点，由于其下一层为MIN层，当前搜索子树的取值必然小于α，则该子树的搜索结果在MAX层中必然被舍弃。因此，在这种情况下可以对相应子树进行“α剪枝”，“β剪枝”同理。
上文已经提及，将一个时刻的棋盘及其相关信息记录为一个状态。这里定义一个类state，state的一个对象表示一个状态。其中二维数组CB[][]（ChessBoard）用于记录棋盘，黑棋（人，α-β剪枝算法中的MIN方）先手，用-1表示；白方（AI，α-β剪枝算法中的MAX方）后手，用1表示，空格用0表示。
state类中还封闭了其它一些信息和部分与状态相关的函数。
state的定义如下：
typedef class state { // 定义一个状态
public:
/* 该状态的基本信息 */
int CB[15][15] = { 0 }; // ChessBoard：AI（MAX）1，对手（MIN）-1，空0
int Last_i = -1; // 上一步横坐标
int Last_j = -1; // 上一步纵坐标
int eva = INT_MIN; // 用于存储其评价函数的值
/* 搜索树的建立 */
state* father; // 父结点
vector<state*> child;// 子结点（用容器存储）
/* α-β剪枝相关 */
int alpha = INT_MIN;
int beta = INT_MAX;
/* state类的成员函数 */
int F(); // 评价函数
int GoalTest(); // 目标测试函数：AI（MAX）胜返回1，对手（MIN）胜返回-1，其余返回0
state* minimax(int depth); // 极小极大值搜索：返回下一步行棋后的状态
void clear(); // 重新初始化其上一次搜索的临时数据
}state;
state中含有父结点指针father、子结点指针容器child，用于一个状态的父结点和子结点，用于搜索算法和悔棋操作。
由于对抗搜索和α-β剪枝算法本身已经相当明确，对于其具体流程这里就不再过多赘述。下面将重点分析α-β剪枝算法在五子棋博弈问题中的关键：评价函数的确定。
下面将对棋型进行分析与评分，以保证评价函数的合理性。最常见的基本棋型大体有以下七种：连五，活四，冲四，活三，眠三，活二，眠二。
每种棋型中“X”表示黑棋，“O”表示白棋。示意是从黑子的角度考虑的，在实际情况中若黑、白棋子出现下列棋型，则评分分别按正、负计算即可。
- 连五：五颗棋子形成的棋型，五颗棋子连接。
连五的形成意味着胜负已分，因此评分应远高于其它棋型，设定为10000。- XXXXX
- 活四：四颗棋子形成的棋型，有两个连五点（即在两个位置落子均可以形成连五，用“+”表示，下同）。
活四的威胁性较大，一旦形成无法防守，因此评分设定为1000。- +XXXX+
- 冲四: 四颗棋子形成的棋型，有一个连五点。
冲四与活四相较而言威胁性较小，在唯一的连五点上落子即可防守，因此评分设定为100。- +XXXXO
- X+XXX
- XX+XX
- 活三: 三颗棋子形成的棋型，有至少一个活四点，可以分为两种。
活三是五子棋进攻中最常见的一种棋型，从活三可以轻易转化为活四。对弈双方在面对活三时需要谨慎对待，若没有更好的进攻手段，需要进行防守，以防止活四的形成。将活三的评分设定为100。- +XXX+
- X+XX
- 眠三: 三颗棋子形成的棋型，仅存在冲四点，不存在活四点，可以分为六种。
眠三与活三相较而言威胁性较小，即使不防守也只能形成冲四，左右胜负的概率较小，因此评分设定为10。- ++XXXO
- +X+XXO
- +XX+XO
- X++XX
- X+X+X
- O+XXX+O
- 活二: 两颗棋子形成的棋型，有至少一个活三点，可以分为三种。
活二的下一手能够形成活三，在某些时刻，特别是开局阶段，具有一定的威胁性，其评分设定为10。- ++XX++
- +X+X+
- X++X
- 眠二: 两颗棋子形成的棋型，有至少一个眠三点，可以分为四种。
眠二的威胁性较小，且一般在棋盘上大量存在，其对局势不易造成很大的影响，因此将其评分设定为1。- +++XXO
- ++X+XO
- +X++XO
- X+++X
依据以上分析，设定每种棋型的评分如下表所示：
| 棋型 | 评分 |
|---|---|
| 连五 | 10000 |
| 活四 | 1000 |
| 眠四 | 100 |
| 活三 | 100 |
| 眠三 | 10 |
| 活二 | 10 |
| 眠二 | 1 |
对于任意一个状态，将其拆分为“−” “|” “/” “\”四个方向，搜索每种颜色的棋子在每个方向上上述棋型出现的次数（对于“/” “\”这两个方向，由于长度小于5的斜线上无法形成连五，不具有威胁，因此仅考虑长度大于等于5的斜线），用黑棋评分减去白棋评分即可得到当前状态评价函数的值。
搜索层数与解的最优性、算法效率都是密切关联的。
根据极大极小值算法的基本思想，假设每次递归都应至少搜索两层（如对于AI而言，枚举AI的所有可能的行动文案，对于每种方案模拟对手的最优行棋，以选择对自己最优的结果）。当仅搜索两层时，AI和对手的决策都是基于两步之后的棋盘状态（该状态下评价函数的值）得出的。若搜索两层以上，可以简单理解为，区别在于两步以后棋盘状态的评判方法发生了变化，并非由评价函数计算得出，而是再次递归，由两步之后的棋盘状态得出。由此可见，搜索层数增大能够使AI“预见”更多步行棋之后的状态，从而采取更最优的行动。
然而，在实际情况中盲目增加搜索层数并不可取。
一方面，由于人的水平有限，未必能想象到数步行棋之后的情况，因此AI搜索层数的增加可能反而“画蛇添足”（因为AI总是认为与之对战的人能够在每一步都做出最优解，但实际情况未必如此）。
另一方面，搜索层数的增加意味的搜索时间的指数级增长。搜索层数逐渐增加时，在游戏过程中已经能感受到明显的卡顿，这从实用性的角度无法接受。
[1] Stuart J. Russell, Peter Norvig. 人工智能：一种现代的方法（第3版）[Ｍ]. 北京: 清华大学出版社, 2013: 64-95．
[2] marble_xu. Python五子棋AI实现(2):棋型评估函数实现[OL]. https://blog.csdn.net/marble_xu, 2019-05-23.