序

上一章，我们介绍了基本极小化极大算法的ALPHA BETA剪枝。以及如何以在线更新和缓存的方式维护每个格子落子的得分。但是即使这样AI也没办法完成全部搜索直到终局。因为这个极小化极大算法的时间复杂度是指数级的。每一个节点继续搜索，都要额外考虑平均8-10步的量。那么第一层是1个节点，第二层是10个节点，第三层就是100个节点。以此类推。
而我们希望我们的AI 在有限时间内，可以提前截断搜索，并对状态应用启发式评价函数，从而有效地将非终止节点变为终止节点。比如当到了一定的深度，或者是终止状态（某个棋子连成5个）。我们都会从递归中退出。只不过前者返回的是当前棋局的启发式得分，而后者会返回必胜的分数（往往是最大的）

评价函数

一个评价函数，首先要满足他返回的分数必然是介于输的分数 和 赢的分数之间。并且计算时间不能不太长。其次，必须可以反映出得分与实际的获胜机会密切相关。

而评价函数则需要计算状态的各种特征，每个特征会反应出一个得分，最后我们运用得分相加的策略。这是最常见的一种评价函数的设计。对五子棋来说，我们则需要考虑不同特征的子力价值（活二，活三，双活三等）根据人类的经验依次对这些特征打分。然后评判棋盘状态下这些特征有多少，代表自己的局面有多好。当然如果是对手的一些特征，那么对我们不利，我们需要去分数减法。

下面是基于这一思想，实现的代码，因为是和分数相关，我们把这个代码写进CachedScoreManager.java 这个文件里

@Override
    public int evaluation(boolean isAI, int humanColor) {
        int blackMaxScore = 0, whiteMaxScore = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (chessBoardAlgo.getValInBoard(j, i) == Player.BLACK.getId()) {
                    blackMaxScore += this.blackScore[i][j];
                } else if (chessBoardAlgo.getValInBoard(j, i) == Player.WHITE.getId()) {
                    whiteMaxScore += this.whiteScore[i][j];
                }
            }
        }
        if (isAI) {
            if (humanColor != Player.BLACK.getId())
                return blackMaxScore - whiteMaxScore;
            else return whiteMaxScore - blackMaxScore;
        } else {
            if (humanColor == Player.BLACK.getId())
                return blackMaxScore - whiteMaxScore;
            else return whiteMaxScore - blackMaxScore;
        }
    }

现在我们的AI程序算是彻底可以工作了，如果我们把评价函数的深度设在5。应该可以在1秒内完成计算。此时的AI已经有不错的棋力。不过普通人类玩家在经过思考后，还是有机会下赢。我们介绍进一步的优化手段，可以让层数增加到9层。

移动顺序

alpha-beta剪枝的有效性很大程度上依赖状态的检查顺序。如果最差的后继最先生成，因为他的得分最小，我们根本没法用他去对后面的搜索做剪枝。如果我们一开始就得到了最优的后继，那么后面我们发现已经有一个分数比之前最优的小了，RUN MIN层的时候，后面就不用算下去了。可以直接剪枝。
如果能够完美实现这1点，那么整个搜索算法只需要检查O(b^（m/2)）个节点就能宣传最佳移动。假设M是6层， B是10. 原来要搜1000000次，现在只要搜1000次。可以让我们的深度扩大一倍。

那么我们就需要对我们的候选方案进行排序。使得能够使局面更加优势的落子排在前面，从而逼近这个完美顺序。

那么思路就是我们在遍历棋盘时，把不同子力的棋子放入不同的桶中，最后按照桶的顺序就JOIN成最后的结果。大概代码思想如下

public List<Integer> generateCandidatePiece(int role, boolean importOnly, int neiDist, int limit) {
        List<Integer> fives = new ArrayList<>();
        List<Integer> myFours = new ArrayList<>();
        List<Integer> enemyFours = new ArrayList<>();
        List<Integer> myBlockedFours = new ArrayList<>();
        List<Integer> enemyBlockedFours = new ArrayList<>();
        List<Integer> myTwoThrees = new ArrayList<>();
        List<Integer> enemyTwoThrees = new ArrayList<>();
        List<Integer> myThrees = new ArrayList<>();
        List<Integer> enemyThrees = new ArrayList<>();
        List<int[]> myTwos = new ArrayList<>();
        List<int[]> enemyTwos = new ArrayList<>();
        List<Integer> ones = new ArrayList<>();
        int white = Player.WHITE.getId();
        int[][] myScore = role == white ? whiteScore : blackScore;
        int[][] enemyScore = role == white ? blackScore : whiteScore;
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (chessBoardAlgo.getValInBoard(x, y) != 0) continue;

                int scoreMe = myScore[y][x];
                int scoreEnemy = enemyScore[y][x];
                int idx = convertToIdx(y, x, size);
                if (scoreMe >= Score.FIVE.value || scoreEnemy >= Score.FIVE.value) {
                    fives.add(idx);
                } else if (scoreMe >= Score.FOUR.value) {
                    myFours.add(idx);
                } else if (scoreEnemy >= Score.FOUR.value) {
                    enemyFours.add(idx);
           ....
        }
        if (!fives.isEmpty()) return fives;

        // 自己能活四，则直接活四，不考虑冲四
        if (!myFours.isEmpty()) return myFours;

        // 对面有活四，自己冲四都没，
        if (!enemyFours.isEmpty() && myBlockedFours.isEmpty()) {
            // 遇到 XX 0 X 的情况，除了防中间的活四位，也可以防左右的冲四位
            enemyFours.addAll(enemyBlockedFours);
            return enemyFours;
        }

        // 自己没活四，对面有活四且自己有冲四

        if (!enemyFours.isEmpty()) {
            enemyFours.addAll(myBlockedFours);
            enemyFours.addAll(enemyBlockedFours);
            return enemyFours;
        }

        List<Integer> results = new ArrayList<>();
        results.addAll(myTwoThrees);
        results.addAll(enemyTwoThrees);
        results.addAll(myBlockedFours);
        results.addAll(myThrees);
        results.addAll(enemyBlockedFours);
        results.addAll(enemyThrees);
...
       return results;

地平线效应

地平线效应，也称为地平线问题，是一个人工智能问题，其中许多博弈中可能的状态或位置的数量是巨大的，而计算机只能搜索其中的一小部分，通常是几个较低的层。游戏树。因此，如果计算机只搜索 5 层，它可能会做出一些有害的动作，但效果是看不见的，因为计算机不会搜索到错误的深度（即超出“地平线”）。比如我们的搜索深度时，下完某一步棋局面大好，但是如果多看几步就会发现，其实那个局面是对手给的一个陷阱，最终是对手必胜的局面。那么我们在有限的搜索深度下无法获得这个信息，而错误的给了一个高分在这个走法上。这就是目前AI最大的问题。这经常发生在一些冲四应手上。对面对面不停冲四，可以很快消耗掉我们的搜索深度，让我们的棋力明显退步。我们在后面几章中，来解决这个问题。其中一个经典的做法是单步延伸，也就是如果对手冲四，我们只有唯一的应手时，不计入搜索深度中。不过这样也会造成时间上的爆炸。因为对手的冲四策略是可以排列组合的，比如先冲四A再冲四B，和先冲四B再冲四A，带来的局面是一样的，我们则需要为一样的局面计算2次完整深度的搜索。因为之前的冲四我们没计算深度。这个问题我们需要用更好的方式去解决它。

前向剪枝

alpha-beta剪枝剪掉的是对最终评估没有影响的树的分支。但前向剪枝是去剪掉那些看上很草稿但也可能实际很好的移动。因此，这一策略以出错风险增大的代价去节省了计算时间。这也是大多数人类棋手的做法，仅考虑每个局面的几步移动（至少潜意识的）
这个技术其实很好运用。因为要求我们被迫放弃一些不好的移动，而减少每一层搜索的量。假设我们考虑每一层所有落子的可能。那么在棋局一开始我们会有15 * 15 个可能。那么每层的平均深度可以上百。
而很多其实是人类棋手根本不会考虑的落子。所以这个时候，我们应该去丢掉一些明显不是好棋的落子。
这里我们假设，凡是相邻有棋的地方，我们是需要考虑做进攻和防守的。同时我们也要考虑相邻的范围。比如我们封堵单边活三可能的冲四，可以紧挨着封堵，也可以跳开一格封堵（对手依然无法冲四）。同时进攻时也是如此，但是如果我们要考虑跳开一格的落子可能，也会造成候选集大一倍。所以根据人类经验，跳开一步的下法更适合进攻。防守还是紧贴着效果会不太差。
基于上述思考，我们做的第一个优化，是引入一个NEIBOR函数。

这个方法维护在ChessboardByteArrayAlgo里

public boolean hasNeighbor(int x, int y, int distance, int count) {
        if (x < 0 || x >= size || y < 0 || y >= size) throw new IllegalArgumentException();
        int sx = x - distance, ex = x + distance;
        int sy = y - distance, ey = y + distance;
        for (int i = sy; i <= ey; i++) {
            if (i < 0 || i >= size) continue;
            for (int j = sx; j <= ex; j++) {
                if (j < 0 || j >= size) continue;
                if (i == y && j == x) continue;
                if (location[getIdx(i,j)] != 0) count--;
                if (count <= 0) return true;
            }
        }
        return false;
    }

下面在生成候选落子时, 加入一个邻居是否有子的判断，我们默认neiDist是1，那么考虑进攻时不能丢弃一些明显的进攻手段，所以在neiDist 为2时，我们看看符不符合进攻的局面。

 int farAttackPotential = chessBoardAlgo.steps() <= 7 ? 2 * Score.TWO.value : Score.TWO.value;
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (chessBoardAlgo.getValInBoard(x, y) != 0) continue;
                if (!chessBoardAlgo.hasNeighbor(x, y, neiDist, 1)) {
                    if (chessBoardAlgo.hasNeighbor(x, y, 2, 1) && myScore[y][x] >= farAttackPotential) {
                        // exception 1 -> (1) 0 1 1 0

                        // exception 2 -> (1) 0 1 1 2
                        //             ->  0  0 0 0 0
                        //             ->  0  0 1 0 0
                        //             ->  0  0 0 0 0
                    } else {
                        continue;
                    }

                }

最后我们之前已经把移动顺序调整好了，因此在可能的移动列表中，后期才出现的移动不太可能是好的移动。这里有2种做法，一种是直接丢弃，另一种是减少搜索这些移动的深度。这里我们选择前种做法。我们引入一个动态的LIMIT限制，来表示这种丢弃的激进程度。此外如果我们已经发现局面上有双活三的情况，可以不考虑活二的侯选步来加速。这个只是一个基于人类经验的规则，没有普适性。

 if (!results.isEmpty() && (!enemyTwoThrees.isEmpty() || !myTwoThrees.isEmpty()))
            return results;

        List<int[]> twos = new ArrayList<>();
        twos.addAll(myTwos);
        twos.addAll(enemyTwos);
        twos.sort((a,b)-> Integer.compare(b[1],a[1]));
        if (!twos.isEmpty()) {
            for (int[] i : twos) {
                results.add(i[0]);
            }
        } else {
            results.addAll(ones);
        }
        if (results.size() > limit) return results.subList(0, limit);
        return (results.isEmpty() && chessBoardAlgo.getValInBoard(size / 2, size / 2) == 0)
                ?
                List.of(convertToIdx(size / 2, size / 2, size))
                :
                results;
    }

下面我们可以完整的试一下7层深度的算法，他应该除了在初期会略慢一些，下到后面应该都可以在1秒速度内响应。并且已经具备人类普通棋手的智能水平了。

总结

这一章我们完整的把alpha beta 的极小化极大搜索算法的优化给讲完了。我们已经获得了一个还不错的五子棋AI。
希望你们可以在实现别的棋类AI时借鉴这种设计思路。
比如如果获取棋局的特征从而设计出评价函数。如何对每个候选落子评分做排序，以及如何通过前向剪枝，来提升计算时间，而最低概率不影响找到最优落子。