java - 在Java国际象棋游戏的NegaMax实现中找不到错误

我在确定negamax（alpha-beta）实施中的错误时遇到了麻烦。

我可以使简单的negamax版本正常工作，但是无法将其转换为negaMax的alpha-beta版本。

首先，简单的negaMax版本正在运行....

public class NegaMax {

    static Node bestNode = null;
    public static final Node getMove(Node root, boolean maximizingPlayer) {
        bestNode = null;
        int score = maximizingPlayer
                  ? negaMax(root, 4, maximizingPlayer)
                  : negaMax(root, 4, !maximizingPlayer);

        if(bestNode != null) {
            bestNode.score = score;
        }
        return bestNode;
    }

    private static final int evaluate(Node node, boolean maximizingPlayer) {
        return Integer.parseInt(node.value) * (maximizingPlayer ? 1 : -1);
    }

    private static final int negaMax(Node node, int depthLeft, boolean maximizingPlayer) {
        if(depthLeft == 0) {
            return evaluate(node, maximizingPlayer);
        }

        int max = Integer.MIN_VALUE;
        Node bestChildSoFar = null;
        List<Node> children = node.getChildren();

        for(Node child : children) {
            int score = -negaMax(child, depthLeft - 1, !maximizingPlayer);
            if(score > max) {
                bestChildSoFar = child;
                max = score;
            }
        }
        bestNode = bestChildSoFar;
        return max;
    }

...这里是非...的版本（返回-INFINITY）-（来自Chessprogrammingwiki的源代码思想）...

public class AlphaBetaNegaMax {

    public static final Node getMove(Node root, boolean maximizingPlayer) {
        int score = maximizingPlayer
                  ? alphaBeta(root, Integer.MIN_VALUE, Integer.MAX_VALUE, 4, maximizingPlayer)
                  : alphaBeta(root, Integer.MIN_VALUE, Integer.MAX_VALUE, 4, !maximizingPlayer);

        System.out.println(score);

        return null;  // score is wrong ... fix this first
    }

    private static final int evaluate(Node node, boolean isMaximizingPlayer) {
        return Integer.parseInt(node.value) * (isMaximizingPlayer ? 1 : -1);
    }

    private static final int alphaBeta(Node node, int alpha, int beta, int depthleft, boolean maximizingPlayer) {
        if(depthleft == 0) {
            return evaluate(node, maximizingPlayer);
        }

        List<Node> children = node.getChildren();
        for(Node child : children) {
            int score = -alphaBeta(child, -beta, -alpha, depthleft - 1, !maximizingPlayer);
            if(score >= beta) {
                return beta;
            }
            if(score > alpha) {
                alpha = score;
            }
        }
        return alpha;
    }
}

最佳答案

编辑：

问题是您没有捕获移动组，即整个4个深度的移动组，即，最低移动组对板上的每个零件都移动了4个深，然后决定在最低成本组的第一个移动中使用哪个移动组，您只找到最低的移动，在某些情况下可能是第二，第三或第四移动。如果返回了该移动，则由于您未捕获板子的先前移动，因此无法实际完成该移动。

private static final int INF = Integer.MAX_VALUE;
private static final int DEPTH = 4;
private Move[] best4depthmove = new Move[DEPTH];
private int[] score4deep = new int[DEPTH];

public static final Move getMove(Move previous) {
    for(int x = 0; x < DEPTH; x++)
    {
        best4depthmove[x] = null;
        score4deep[x] = 0;
    }

    negamax(previous, 0);

    return best4depthmove[0];
}

private static final negamax(Move move, int depth)
{
     int newscore = 0;

    if(depth < DEPTH)
    {
        List<Move> moves = Engine.getMoves(move);
        for(Move m : moves)
        {
             newscore = MoveEvaluators.evaluate(m);
             if(newscore > score4deep[depth])
             {
                 score4deep[depth] = newscore;
                 best4depthmove[depth] = m;
             }
             negamax(m, depth+1);

        }
    }
}

这就是我能弄清的，应该递归地进行每一个可能的动作。只要您具有处理递归调用的内存能力，这可能对任何深度都有效。