数据结构——人机对弈（minimax、negamax、alpaha-beta剪枝算法）

研究契机

本学期学校开设数据结构课程，研究了一下minimax、negamax、alpha-beta剪枝算法，以供自己以后复习参考。

minimax算法

也就是极大化极小算法，对于零和博弈，一方所赢就是另一方所输，对于一棵博弈树，可以被分成max层和min层，所谓max层，在实际应用中就代表博弈时自己的回合，在自己的回合想要将自己的利益最大化，所以会遍历博弈树种孩子孩子结点的权值，并回传权值种最大的值，而对于min层，可以理解为对手回合，对手在自己的回合想要将我们的利益最小化，所以会遍历所有的孩子结点并回传最小值，在算法实现中可以用递归来实现。在这样的原理中，就可以通过遍历博弈树，比较每一种情况的权值，找到当前回合的全局最优解或局部最优解。

negamax算法

negamax算法和minimax在本质思想上是一致的，可以看作对minimax使用了一些数学技巧，首先将所有叶子结点上的值取负，然后在每一次回传时都会再次取负，这样每一次比较都只需取最大值即可，但是本质上都是采用了通过遍历博弈树最大化自身利益最小化对手利益的思想。

alpfa-beta剪枝

在程序实际运行过程中，计算机对于博弈树的遍历时自顶向下的，对于博弈过程中不会采取的路径可以进行剪枝。具体实现方法是将设定alpha代表自身最大利益，beta代表本回合对手能够将为我们的利益降到的权值，将alpha初始化为-∞，beta初始化为∞，在遍历博弈树时，在max层可以更新alpha的值，在min层可以更新beta的值，具体可以通过for循环来实现，当出现alpha>beta的情况时，就会进行剪枝，因为这条路径会导致对手降低我们取得的权重，也就是损害了我们的利益，我们在决策时不会选择这条路径，因此可以进行剪枝。

人机对战应用

在棋类游戏和一些信息对称的零和博弈游戏中，够可以采用minmax算法或者nagamax算法来预测最优解或者局部最优解，这样就可以实现人机对战，而采用alpha-beta剪枝算法，可以避免对不必要路径遍历所带来的时间和空间损耗。

代码实现

贴出了我所设计程序过程中所使实现的算法，针对不同需求可以进行优化

int minimax(int(*board)[3], int depth, int alpha, int beta) {
    int result = score(board, 3).result;
    if (depth == 0 || result != -1) {//如果可以分出输赢，直接返回结果
        if (result != -1)//首先判断是否结束
            return score(board, 3).score;
        else//如果未平局，找到最优解，否则返回既定估值
        {
            if (judge(board, 3) == -2)
            {
                return -1000;
            }
            points p;
            p = seekpoints3(board);//生成最佳位置
            return p.score[0];//返回最佳位置对应的最高分
        }
    }
    else if (depth % 2 == 0)
    {//max层,我方决策
        int sameboard[3][3];
        copyboard(board, sameboard);
        points p = seekpoints3(sameboard);//找寻最优点

        for (int i = 0; i < 9; ++i) {
            if (p.score[i] > -INT_MAX)
            {
                sameboard[p.pos[i].x][p.pos[i].y] = 2;
                int a = makedec1(sameboard, depth - 1, alpha, beta);
                sameboard[p.pos[i].x][p.pos[i].y] = 0;//还原
                if (a > alpha) {
                    alpha = a;
                    if (depth == 2) {
                        Decision.pos.setx(p.pos[i].x);
                        Decision.pos.sety(p.pos[i].y);
                        Decision.eval = a;
                    }
                }
                if (beta <= alpha)break;//剪枝
            }
        }
        return alpha;//返回最大值
    }
    else
    {//min层,敌方决策
        int rboard[3][3];
        reverseboard(board, rboard);
        points p = seekpoints3(rboard);

        int sameboard[3][3];
        copyboard(board, sameboard);

        for (int i = 0; i < 9; ++i) {
            if (p.score[i] > -INT_MAX) {
                sameboard[p.pos[i].x][p.pos[i].y] = 1;
                int a = makedec1(sameboard, depth - 1, alpha, beta);
                sameboard[p.pos[i].x][p.pos[i].y] = 0;//还原
                if (a < beta)beta = a;
                if (beta <= alpha)break;//剪枝
            }
        }
        return beta;//返回最小值，即对我方最不利
    }
}
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
60
61
62

调试过程

在研究minimax、negamax、aplha-beta剪枝算法时，资料中的描述都比较抽象，有些晦涩，但通过手工模拟，同时进行分析后，最终较为深入的理解了算法的思想。在使用剪枝算法完成自己的程序时，由于计算机的处理方式和实际生活中人的处理方式是有一定差异的，因此在程序中要进行相应的修改，才能运行得到想要的决策。