2

I am making a chess game in Java and (I think) have successfully implemented Negamax for the AI player. I am having some trouble adding alpha beta pruning to this to improve the algorithm. I have tried following tutorials and example code but just can't get my head around how it works.

Below is the code I currently have to get the best move:

private Move getBestMove() {
    System.out.println("Getting best move");
    System.out.println("Thinking...");

    List<Move> validMoves = generateMoves(true);
    int bestResult = Integer.MIN_VALUE;
    Move bestMove = null;

    for (Move move : validMoves) {

        executeMove(move);
        System.out.println("Evaluating: " + move);

        int evaluationResult = -evaluateNegaMax(this.lookForward, "", Integer.MIN_VALUE, Integer.MAX_VALUE);
        undoMove(move);

        if (evaluationResult > bestResult) {
            bestResult = evaluationResult;
            bestMove = move;
        }
    }
    System.out.println("Done thinking! The best move is: " + bestMove);
    return bestMove;
}

And here is my attempt at adding aplha-beta pruning to my (working) negamax method:

public int evaluateNegaMax(int lookForward, String indent, int alpha, int beta) {

    if (lookForward <= 0
            || this.chessGame.getGameState() == ChessGame.GAME_STATE_WHITE_WON
            || this.chessGame.getGameState() == ChessGame.GAME_STATE_BLACK_WON) {

        return evaluateState();
    }

    List<Move> moves = generateMoves(false);

    for (Move currentMove : moves) {

        System.out.println(indent + "Handling move: " + currentMove + " : " + alpha);
        if (currentMove == null) {
            continue;
        }

        executeMove(currentMove);

        alpha = Math.max(alpha, -evaluateNegaMax(lookForward-1, "    ", -beta, -alpha));

        if (alpha > beta) {
            break;
        }

        undoMove(currentMove);
    }
    return alpha;
}

And finally what the console looks like

Starting game flow
Looking 2 moves aheadExecuted: E/2 -> E/4
Tested 0 moves
Getting best move
Thinking...
Evaluating: B/8 -> A/6
Handling move: B/1 -> A/3 : -2147483648
    Handling move: A/8 -> B/8 : -2147483647
Handling move: B/1 -> C/3 : 2
    Handling move: B/8 -> A/8 : -2147483647
    Handling move: A/6 -> B/4 : -3
    Handling move: A/6 -> C/5 : -3
    Handling move: G/8 -> F/6 : -2
Handling move: D/1 -> E/2 : 2
    Handling move: B/8 -> A/8 : -2147483647
Handling move: D/1 -> F/3 : 2
    Handling move: A/8 -> B/8 : -2147483647
    Handling move: A/8 -> B/8 : -2147483647
    Handling move: F/6 -> E/4 : -32
    Handling move: F/6 -> G/4 : -17
    Handling move: F/6 -> D/5 : -17
Handling move: G/1 -> E/2 : 2
    Handling move: B/1 -> A/3 : -2147483647
    Handling move: B/1 -> C/3 : -29
    Handling move: E/1 -> F/1 : -28
    Handling move: E/2 -> G/1 : -19
    Handling move: E/2 -> C/3 : -19
    Handling move: E/2 -> G/3 : -19
    Handling move: E/2 -> D/4 : -19
Handling move: G/1 -> F/3 : 19
    Handling move: A/8 -> B/8 : -2147483647
Handling move: G/1 -> H/3 : 19
    Handling move: B/8 -> B/2 : -2147483647
Exception in thread "Thread-2" java.lang.NullPointerException
    at Chess.logic.ChessGame.movePiece(ChessGame.java:166)
    at Chess.ai.AiPlayerHandler.executeMove(AiPlayerHandler.java:158)
    at Chess.ai.AiPlayerHandler.evaluateNegaMax(AiPlayerHandler.java:84)
    at Chess.ai.AiPlayerHandler.getBestMove(AiPlayerHandler.java:47)
    at Chess.ai.AiPlayerHandler.getMove(AiPlayerHandler.java:31)
    at Chess.logic.ChessGame.waitForMove(ChessGame.java:125)
    at Chess.logic.ChessGame.startGame(ChessGame.java:95)
    at Chess.logic.ChessGame.run(ChessGame.java:338)
    at java.lang.Thread.run(Thread.java:745)

Any help would be greatly appreciated. Thank you in advance.

P. Brew
  • 734
  • 4
  • 12
  • Could you please clarify your question? Is it how to implement alpha-beta search with negamax? At the moment it looks like you are asking for someone to implement it for you in your code, which is too broad. – Giewev Apr 11 '16 at 16:35
  • Essentially that is what I am asking. I did have a go at implementing it myself but it was just returning the completely wrong results. From my research it should only be a few lines of code to add to what I currently have. Maybe I should have posted my attempt rather than the working code without any attempt. I'll change that over now. Thanks for your comment. – P. Brew Apr 11 '16 at 17:29
  • It seems the bug is not in the code you show. Why do you get the null pointer exception? This is what you have to investigate. We can't solve this problem for you without the code. – Rémi Apr 12 '16 at 13:45
  • @Rémi had the evaluateNegaMax() method working before I added the alpha-beta part to it. It printed the full tree fine. The the error occurs from what I have added. I can add the original method if it helps. Just don't like posting a wall of code and expect someone to know what I'm talking about. – P. Brew Apr 12 '16 at 14:39

1 Answers1

4

I think I have it working. If anyone following this question was waiting for a response the code is as follows:

    public int evaluateNegaMax(int depth, String indent, int alpha, int beta) {
    if (depth <= 0
            || this.chessGame.getGameState() == ChessGame.GAME_STATE_WHITE_WON
            || this.chessGame.getGameState() == ChessGame.GAME_STATE_BLACK_WON) {

        return evaluateState();
    }

    List<Move> moves = generateMoves(false);
    int bestValue = Integer.MIN_VALUE;

    for (Move currentMove : moves) {

        executeMove(currentMove);
        int value = -evaluateNegaMax(depth - 1, indent + "    ", -beta, -alpha);
        System.out.println(indent + "Handling move: " + currentMove + " : " + value);
        undoMove(currentMove);
        counter++;

        if (value > bestValue) {
            bestValue = value;
        }

        if (bestValue > alpha) {
            alpha = bestValue;
        }

        if (bestValue >= beta) {
            break;
        }
    }
    System.out.println(indent + "max: " + alpha);
    return alpha;
}
P. Brew
  • 734
  • 4
  • 12