评估函数

与人类的思维相同，程序在决策每一步棋时应该评估所有落点的优劣，选择最优的一步棋，因此我们需要为程序制定一套评价标准（评估函数）。每当程序执子时，它将依据这个评估函数做出决策。设计评估函数并没有固定的方法，这里采用一种比较简单的方法：五元组评价。

对于每一个落点，它只会影响包含它的五个连续的位置，因此我们将棋盘行、列、斜线方向分成若干个五元组。五元组的个数等于所有五子连珠情况的个数。五元组被表示为一个长度为5的坐标数组，其中坐标为row * BOARD_SIZE + col。

在一个五元组中，当己方棋子越多且连续，胜率越大，我们为五元组的多种情况做以下规定：

  • 五元组中有任意个对方棋子，得分为 0
  • 五元组中没有己方棋子，得分为 0
  • 五元组中有 1 个己方棋子，得分为 1
  • 五元组中有 2 个连续己方棋子，得分为 20
  • 五元组中有 3 个连续己方棋子，得分 600
  • 五元组中有 4 个连续己方棋子，得分 4000
  • 五元组中有 5 个连续己方棋子，得分 1000000

计算单个五元组中棋子chessType的评分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::array<int, 6> shape_score{0, 1, 20, 600, 4000, 1000000};

int Gobang::tuple_evaluate(ChessType chessType, const FiveTuple & fiveTuple){
    int n = 0;
    for(int i = 0; i < 5; ++i){
        if(IS_SAME_TYPE(board[XPOS(fiveTuple[i])][YPOS(fiveTuple[i])], chessType)){
            ++n;
        }else if(IS_SAME_TYPE(board[XPOS(fiveTuple[i])][YPOS(fiveTuple[i])], OPP(chessType))){
            n = 0;
            break;
        }
    }
    return shape_score[n];
}

对每一个落子进行评价时，有两种思路：

  • 对落子后的单个落点进行评分。即在该落点落子后，计算包含该落点的所有五元组的评分。
  • 对落子后的整个棋局进行评分。即在该落点落子后，计算整个棋局所有五元组的评分。

显然第二种方式更合理，因为它更具有全局意识。另外，在评估棋局时我们要攻防兼顾，因此将全局的评估函数设为己方评分与对方评分之差。 $H$ 表示全局评分值，$S(x, y)$ 表示 $(x, y)$ 处棋盘的评分，即五元组评分之和。

在计算所有五元组的评分时，我们不应该遍历每一个位置的五元组，因为一个五元组包含五个位置，这样会导致4倍多余的计算。本程序实现的思路是将所有五元组放在一个容器中，而每一个位置仅保存所有包含该位置的五元组的索引（哈希）。在计算评估函数值时，遍历容器中的五元组；检查落子是否形成连珠时，也能方便的搜索落点的五元组，并有利于后续优化。

标识单个五元组的索引类似于向量表示，将五元组两端的坐标移位拼接成一个数。

1
2
3
int Gobang::fiveTuple_index(const FiveTuple& fiveTuple){
    return (fiveTuple[0] << 8) + fiveTuple[4];
}

贪心搜索

设计完评估函数，我们可以实现一个基于贪心搜索的初级版本。其思想是搜索所有空余落点，找到评价函数值最大的落点，在该处落子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Gobang::greedy_select(){
    int x = 0, y = 0;
    int max = INT_MIN;
    for(int i = 0; j < BOARD_SIZE; ++i){
        for(int j = 0; j <BOARD_SIZE; ++j){
            if(board[i][j] != 0){
                continue;
            }
            board[i][j] = order * computer;
            int h = total_evaluate(computer) - total_evaluate(player);
            if(h > max){
                max = h;
                x = i;
                y = j;
            }
            board[i][j] = 0;
        }
    }
    return POSITION(x, y);
}

该算法可以计算出下一步所有落点的评估函数值，但在现实对弈中，仅考虑当前一步时远远不够的，有下棋经验的人都会或多或少向后推演几步，因此，我们需要增加它的搜索层数。

局部搜索

考虑新算法前，先进行一次必要的剪枝操作。在选择最佳落点时，玩家往往只用考虑已下棋子周围的落点，而非遍历整个棋盘。我们维护一个openlist，用于存储已下棋子周围的位置，下完一步棋，就将其继续扩展。

openlist被定义为std::set<int>，该函数扩展openlist，并返回扩展前的openlist，用于后续的回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
std::set<int> Gobang::extend_openlist(int xpos, int ypos){
    assert(IN_BOARD(xpos, ypos));
    assert(0 != board[xpos][ypos]);
    std::set<int> oldlist = openlist;
    std::vector<int> neighbors = neighbor(xpos, ypos, 1);  // (xpos, ypos)周围的空余位置，步长为1
    for(auto pos : neighbors){
        if(0 == board[XPOS(pos)][YPOS(pos)]){
            openlist.insert(pos);
        }
    }
    openlist.erase(POSITION(xpos, ypos));
    return oldlist;
}

MinMax算法

贪心搜索具有一层的搜索深度，如果要搜索多层，需要考虑和模拟对方的落子，即搜索对方可能落点，并依据评估函数进行决策，但在考虑己方和对方的落子时存在区别：

  • 当己方落子时，总是考虑局面对自己最有利的情况，即选择评估函数值最大的落点
  • 当对方落子时，总是考虑局面对自己最不利的情况，即选择评估函数值最小的落点

如果把每一个可能的落子情况视为一个树节点，树的根节点为开局（或搜索开始时）棋局，那么当游戏参与者交替行棋，树的每一层节点选择子节点的行为不同：当前层为我方落子时，选择子节点中评估函数值最大的；当前层为对方落子时，选择子节点中评估函数值最小的。这种树称为博弈树，也称为Min-Max树。

以井字棋（“三子棋”）为例，假如评估函数被设置为“X”（我方）胜利为1，“O”（对方）胜利为-1，下面详细展示了一棵三层的博弈树状态。

Max层节点的值取子节点的最大值，Min层节点的值取子节点最小值，叶子节点的值为评估函数值。树搜索过程为DFS，一旦到达搜索深度或者已经出现胜利（或失败）棋局则返回上层，停止搜索。另一个详细的MinMax搜索过程如下图：

实现MinMax算法后，程序能够做到向下搜索3层，但随着搜索层数的增加以及棋局向后发展，棋局状态数即节点数是呈指数增长的，程序运行时间也会越来越久。

alpha-beta剪枝

为了提高搜索效率，MinMax算法总是离不开一种剪枝策略，即 $\alpha-\beta$ 剪枝。仔细观察博弈树，可以发现在搜索过程中我们不需要遍历所有节点，当无法从某条分支上获取更优的值时进行剪枝。

如图，根节点为Max节点，它会选择子节点中的最大值，因此当搜索完左分支后可以确定根节点的值至少为 -13，即下限 $\alpha$ 为 -13。当右子节点搜索完它的左分支后已经获取了一个值-75，由于右子节点为Min节点，它会选择子节点中的最小值，那么右子节点的值小于 -75，即上限 $\beta$ 为 -75。此时右子树已经确定不会被选择，所以不会再去搜索它的右分支。

$\alpha-\beta$ 剪枝算法有多种形式化表述，这是我认为最详细的一种：

  • 初始根节点 $\alpha = -\infty$ ，$\beta = +\infty$
  • Max层节点 $\alpha = max(\alpha, \text{所有子节点评价值})$ , $\beta$ 等于父节点 $\beta$
  • Min层节点 $\alpha = min(\beta, \text{所有子节点评价值})$ , $\alpha$ 等于父节点 $\alpha$
  • 当某个节点 $\alpha > \beta$ ，停止搜索该节点的其它子节点

实现 $\alpha-\beta$ 剪枝算法后的MinMax搜索如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

struct MinmaxNode{
    ChessType type;
    int pos;
    int value;
    int next_best;
    MinmaxNode(ChessType type, int pos): type(type), pos(pos){}
};
// 参数node为父节点 
void Gobang::minmax_v1(int depth, MinmaxNode & node, int alpha, int beta){
    if(depth == 0 || check_win(node.type, XPOS(node.pos), YPOS(node.pos))){
        node.value = total_evaluate(computer) - total_evaluate(player);
        return;
    }
    std::vector<int> list(openlist.begin(), openlist.end());
    if(node.type == computer){  // MIN
        node.value = INT_MAX;
        for(int pos : list){
            fill_board(OPP(node.type), XPOS(pos), YPOS(pos));
            std::set<int> oldlist = extend_openlist(XPOS(pos), YPOS(pos));
            MinmaxNode snode(OPP(node.type), pos);
            // the next node is MAX
            // for MAX, beta equals parent's beta
            minmax_v1(depth - 1, snode, INT_MIN, beta);
            // traceback
            unfill_board_back(XPOS(pos), YPOS(pos));
            openlist = oldlist;
            if((node.value > snode.value)){
                node.value = snode.value;
                node.next_best = snode.pos;
            }
            beta = std::min(beta, node.value);
            if(beta < alpha){
                break;
            }
        }
    } else if(node.type == player){  // MAX
        node.value = INT_MIN;
        for(int pos : list){
            fill_board(OPP(node.type), XPOS(pos), YPOS(pos));
            std::set<int> oldlist = extend_openlist(XPOS(pos), YPOS(pos));
            MinmaxNode snode(OPP(node.type), pos);
            // the next node is MIN
            // for MAX, alpha equals parent's alpha
            minmax_v1(depth - 1, snode, alpha, INT_MAX);
            // traceback
            unfill_board_back(XPOS(pos), YPOS(pos));
            openlist = oldlist;
            if((node.value < snode.value)){
                node.value = snode.value;
                node.next_best = snode.pos;
            }
            alpha = std::max(alpha, node.value);
            if(alpha > beta){
                break;
            }
        }
    }
}

剪枝后，搜索时间已经大大减少，VS优化代码后，搜索3层所用时间基本在200ms以内。至此，我们已经实现了一个具有一定棋力的五子棋AI，但是和有一定水平的玩家相比，仅搜索3层是远远不够的。后续的内容将继续围绕如何优化搜索以减少搜索时间、提高搜索层数展开。

参考