Hinzufügen von Alpha-Beta-Beschneidung zu Negamax in Java

Question

Ich mache ein Schachspiel in Java und (glaube ich) habe Negamax erfolgreich für den KI-Spieler implementiert. Ich habe einige Probleme, Alpha-Beta-Beschneidung hinzuzufügen, um den Algorithmus zu verbessern. Ich habe folgende Tutorials und Beispielcode ausprobiert, aber ich kann einfach nicht verstehen, wie es funktioniert.

Unten ist der Code, den ich zur Zeit den besten Zug bekommen müssen:

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

Und hier ist mein Versuch aplha-Beta Beschneidung meiner (in Betrieb) negamax Methode bei Zugabe:

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

Und schließlich, wie die Konsole aussieht

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) 

Jede Hilfe würde sehr geschätzt werden. Vielen Dank im Voraus.

Answer 1

Ich denke, ich habe es funktioniert. Wenn jemand nach dieser Frage auf eine Antwort wartet, lautet der Code wie folgt:

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