Skip to content

Latest commit

 

History

History
152 lines (119 loc) · 10.7 KB

README.md

File metadata and controls

152 lines (119 loc) · 10.7 KB
Raw

five-in-a-row

文件说明

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）参加的博弈为例，下面将用尽可能简单的语言对算法加以阐述。

假设某时刻棋盘上各棋子的位置已知，此时轮到计算机行棋，以搜索两层为例，算法的具体实现过程如下：

  • 考虑计算机能够落子的位置：依据五子棋的规则，计算机容易找到所有合理的落子位置；
  • 考察对手可能的行动：对于计算机的每种落子方案，考察对手在下一步可能的落子位置。 这里计算机应当假设其对手是“聪明”的，也就是说，他总是能找出对他自身最有利的落子位置。通过上述过程便能够建立极小极大算法的搜索树，如下图中的黑色部分所示。

image

根据上面的分析，这里需要定义一个函数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，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”表示白棋。示意是从黑子的角度考虑的，在实际情况中若黑、白棋子出现下列棋型，则评分分别按正、负计算即可。

  1. 连五：五颗棋子形成的棋型，五颗棋子连接。
    连五的形成意味着胜负已分，因此评分应远高于其它棋型，设定为10000。
    • XXXXX
  2. 活四：四颗棋子形成的棋型，有两个连五点（即在两个位置落子均可以形成连五，用“+”表示，下同）。
    活四的威胁性较大，一旦形成无法防守，因此评分设定为1000。
    • +XXXX+
  3. 冲四: 四颗棋子形成的棋型，有一个连五点。
    冲四与活四相较而言威胁性较小，在唯一的连五点上落子即可防守，因此评分设定为100。
    • +XXXXO
    • X+XXX
    • XX+XX
  4. 活三: 三颗棋子形成的棋型，有至少一个活四点，可以分为两种。
    活三是五子棋进攻中最常见的一种棋型，从活三可以轻易转化为活四。对弈双方在面对活三时需要谨慎对待，若没有更好的进攻手段，需要进行防守，以防止活四的形成。将活三的评分设定为100。
    • +XXX+
    • X+XX
  5. 眠三: 三颗棋子形成的棋型，仅存在冲四点，不存在活四点，可以分为六种。
    眠三与活三相较而言威胁性较小，即使不防守也只能形成冲四，左右胜负的概率较小，因此评分设定为10。
    • ++XXXO
    • +X+XXO
    • +XX+XO
    • X++XX
    • X+X+X
    • O+XXX+O
  6. 活二: 两颗棋子形成的棋型，有至少一个活三点，可以分为三种。
    活二的下一手能够形成活三，在某些时刻，特别是开局阶段，具有一定的威胁性，其评分设定为10。
    • ++XX++
    • +X+X+
    • X++X
  7. 眠二: 两颗棋子形成的棋型，有至少一个眠三点，可以分为四种。
    眠二的威胁性较小，且一般在棋盘上大量存在，其对局势不易造成很大的影响，因此将其评分设定为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.