在Java中添加Alpha Beta修剪到Negamax
我正在Java中进行国际象棋游戏,并且(我认为)已经成功实现了AI玩家的Negamax。 我在添加alpha beta修剪时遇到了一些麻烦,以改进算法。 我已经尝试了下面的教程和示例代码,但仅仅是无法让我的头脑发现它的工作原理。
以下是我目前必须采取的最佳做法:
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;
}
这里是我尝试在我的(工作)negamax方法中添加aplha-beta修剪:
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;
}
最后是控制台的外观
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)
任何帮助将不胜感激。 先谢谢你。
我想我有它的工作。 如果有人在回答这个问题的时候等待回应,那么代码如下:
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;
}
链接地址: http://www.djcxy.com/p/56355.html
上一篇: Adding Alpha Beta pruning to Negamax in Java
下一篇: How to create an evaluation function for a board game(wizwoz) result