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

Question

我无法识别 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;
    }
}

Answer 1

编辑:

问题是你没有捕获移动集，整个 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);

        }
    }
}

这就是我能弄清楚的，它应该递归地遍历每一个可能的 Action 。只要您有足够的内存容量来处理递归调用，这可能适用于任何深度。