Cannot find bug in NegaMax implementation for java chess game

Question

I am having trouble identifying the error in my negamax (alpha - beta) implementation.

I can make the simple negamax version work fine, however I am unable to convert it to its alpha-beta version of negaMax.

First the simple negaMax version that is working ....

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;
    }    

... and here the version that is not ... (returns -INFINITY) --(sourcecode ideas from 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

I found the bug and this one was quite subtle ... The issue was I was assuming the absolute values of both Math.MIN_VALUE and Math.MAX_VALUE were the same, forgetting about how java represents integers with 2's compliment

I just defined INFINITY as 9999999 and referred to this symmetrical value for both positive and negative infinity and it worked (the swapping of alpha and beta is where these values must be symmetrical or we see this bug)

I think this applet on the web has a similar issue: http://ksquared.de/gamevisual/launch.php (I notified the author and he replied. He indeed he had the exact same bug!)