在极大极小算法上增加剪枝功能解决方法

在极大极小算法上增加剪枝功能
朋友初入游戏开发，给了我一段代码，要求增加剪枝功能，我做普通应用开发，这种算法接触的不多，最近也挺忙的，看的心慌头大。。希望朋友们帮下忙，谢谢
代码是java的，不过影响不大呢。
部分源码：

Java code


// 极小值极大值搜索函数
    static int MinMaxSearch(int depth) {
        if (currentPlayer == BLACK)
            return Min(depth);
        else
            return Max(depth);
    }

    public static int Max(int depth) {
        int[] allMoves = new int[MAX_GEN_MOVES];
        int eatCount, value, bestValue = 0;
        int[] eatTable = new int[2];
        bestValue = -INFINITY_VALUE;
        if (depth <= 0) {
            return evaluatePosition();
        }
        int genCount = generateAllMoves(allMoves);
        for (int i = 0; i < genCount; i++) {
            eatCount = makeOneMove(allMoves[i], eatTable); // 走棋并吃子
            if (eatCount != 0) { // 如果吃子成功
                theDepth++;
                value = Min(depth - 1); // 递归
                undoOneMove(allMoves[i], eatCount - 1, eatTable); // 还原
                theDepth--;
                // 如果当前走棋方是白方，找一个评分最大的局面(对白方最有利)
                if (value > bestValue) {
                    bestValue = value;
                    if (depth == search_deepth) { // 如果是根节点 保存最佳走法
                        bestMove = allMoves[i];
                    }
                }
            }
        }
        
        // 如果是杀棋，就根据距杀棋的步数给出评价
        if (bestValue == -INFINITY_VALUE) {
            return theDepth - INFINITY_VALUE;
        }
        return bestValue;
    }

    public static int Min(int depth) {
        int[] allMoves = new int[MAX_GEN_MOVES];
        int eatCount, value, bestValue = 0;
        int[] eatTable = new int[2];
        bestValue = INFINITY_VALUE;
        if (depth <= 0) {
            return evaluatePosition();
        }
        int genCount = generateAllMoves(allMoves);
        for (int i = 0; i < genCount; i++) {
            eatCount = makeOneMove(allMoves[i], eatTable); // 走棋并吃子
            if (eatCount != 0) { // 如果吃子成功
                theDepth++;
                value = Max(depth - 1); // 递归
                undoOneMove(allMoves[i], eatCount - 1, eatTable); // 还原
                theDepth--;
                // 如果当前走棋方是黑，找一个评分最小的局面(对黑方最有利)
                if (value < bestValue) {
                    bestValue = value;
                    if (depth == search_deepth) { // 如果是根节点 保存最佳走法
                        bestMove = allMoves[i];
                    }
                }
            }
        }
        
        // 如果是杀棋，就根据距杀棋的步数给出评价
        if (bestValue == INFINITY_VALUE) {
            return INFINITY_VALUE - theDepth;
        }
        return bestValue;
    }

------解决方案--------------------
剪枝即是在极大极小搜索中的一个提高效率的方法。即在生成博弈树的过程中生成一个节点后，计算倒退值，根据倒退值就可以判断是否需要对这个分支继续进行搜索。

主要考虑的是不要进行无谓的搜索。还是蛮简单的，楼主静下心来好好写写，很快就写出来了

在极大极小算法上增加剪枝功能解决方法

相关推荐