java - Alpha Beta 修剪似乎并没有提高我的国际象棋 minimax 性能

Question

import java.util.ArrayList;
import java.util.HashMap;

public class MiniMax {
    public static final int SUGGESTIVE_MAX_DEPTH = 10;
    public static int counter;
    //AI (white), depth>0
    public static int[]  getComputerMove(Board b, int depth) {
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(true);
        int[] currentMove = new int[4];
        int max = Integer.MIN_VALUE;
        int[] bestMove = new int[4];
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 2; i < a.size() - 1; i += 2) {
                currentMove[0] = a.get(0);
                currentMove[1] = a.get(1);
                currentMove[2] = a.get(i);
                currentMove[3] = a.get(i + 1);
                int moveSetValue = min(b.simulateMove(currentMove), depth - 1, max, Integer.MAX_VALUE);
                if (moveSetValue > max) {
                    max = moveSetValue;
                    bestMove = currentMove.clone();
                }
            }

        }
        System.out.println(counter);return bestMove; 
    }
    //maximizer (white)
    private static int max(Board b, int depth, int alpha, int beta) {
        if (depth == 0 || Math.abs(b.getSum()) > 999990) { counter++; 
            return b.getSum(); 
        }
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(true);
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 2; i < a.size() - 1; i += 2) {
                int[] moveSet = new int[4];
                moveSet[0] = a.get(0);
                moveSet[1] = a.get(1);
                moveSet[2] = a.get(i);
                moveSet[3] = a.get(i + 1);
                int moveValue = min(b.simulateMove(moveSet), depth - 1, alpha, beta);
                alpha = (int) Math.max(alpha, moveValue);
                if (alpha >= beta) {
                    return alpha;
                }

            }
        }
        return alpha;
    }
    //minimizer (black)
    private static int min(Board b, int depth, int alpha, int beta) {
        if (depth == 0 || Math.abs(b.getSum()) > 999990) {
            counter++; return b.getSum();
        }
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(false);
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 0; i < a.size() - 1; i += 2) {
                int[] moveSet = new int[4];
                moveSet[0] = a.get(0);
                moveSet[1] = a.get(1);
                moveSet[2] = a.get(i);
                moveSet[3] = a.get(i + 1);
                int moveValue = max(b.simulateMove(moveSet), depth - 1, alpha, beta);
                beta = (int) Math.min(beta, moveValue);
                if (alpha >= beta) {
                    return beta;
                }
            }
        }
        return beta;
    }
}

我导入了 HashMap 但从未真正使用过它，所以我这里没有换位表。我的 minimax 实现似乎真的很慢。我确实有一个评估函数，可以根据每 block 棋子的位置增加或减少值(value)，所以不应该有很多具有相同值(value)的棋盘状态。话虽这么说，我的计数器变量在深度 6 应该停止在 ~27000 时上升到数百万。我认为我正确地实现了 alpha beta 剪枝，但失败了。然而，我认为在我这样做之后性能没有明显提高。

一些解释:

coloredMoves 获取所有可能的棋步。移动被定义为移动 block 的坐标位置和位置的坐标。

编辑:这里的深度意味着每一个单独的 Action 。我可能高估了使用极小极大值进行 alpha beta 剪枝的性能吗？在线显示它至少应该是 6。我的算法只在现实时间运行在 4 的深度，这是相当可悲的。

Answer 1

我在您的源代码中找不到任何错误。 alpha beta 的速度增益在很大程度上取决于尝试移动的顺序。如果您的移动生成器例如添加典当首先从左到右移动然后截止将很晚。如果你实现了一个好的移动排序函数，那么移动计数应该至少落到最小最大数的根。

有多种方法可以对国际象棋走法进行排序。要对根部的移动进行排序，您可以使用“迭代加深”。之后 history heuristic and killer heuristic帮助对游戏树中的移动进行排序。

您的问题的另外一个改进可以是转移

moveSet[0] = a.get(0);
moveSet[1] = a.get(1);

如果在 simulateMove 函数中没有更改数组，则到它的 for 循环的前面。