Ajout de l'élagage Alpha Beta à Negamax en Java

Question

Je fais un jeu d'échecs en Java et (je pense) ai implémenté avec succès Negamax pour le joueur AI. J'ai de la difficulté à ajouter de l'alpha bêta pour améliorer l'algorithme. J'ai essayé les tutoriels suivants et l'exemple de code mais je n'arrive pas à comprendre comment cela fonctionne.

est Ci-dessous le code que j'ai actuellement pour obtenir le meilleur mouvement:

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

Et voici ma tentative d'ajouter la taille APLHA-bêta à mon (travail) Méthode negamax:

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

Et enfin à quoi ressemble la console

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) 

Toute aide serait grandement appréciée. Merci d'avance.

Answer 1

Je pense que je l'ai fonctionné. Si quelqu'un suivant cette question attendait une réponse le code est comme suit:

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