目前，我正在用Java编写一个简单的游戏（夺旗游戏）。为了创建我的AI机器人，我决定使用带有alpha-beta剪枝的minmax算法。运行我的函数后，如何最好地访问导致最佳评估分支的位置？那个位置将代表AI机器人选择的移动（在树形结构中可视化时，这是导致我的函数返回的分支）。基于这种结构，我尝试实现如下：
public int minmax(String[][] position,int depth, int alpha, int beta, boolean maximizingPlayer){ //TODO recursion ends with game over if(depth == 0){ return AssessGame.assess(position, maximizingPlayer); } if(maximizingPlayer){ int maxEval = Integer.MIN_VALUE; for(String[][] child: generateChildren(position)){ int eval = minmax(child, depth -1, alpha,beta,false); maxEval = Integer.max(maxEval,eval); alpha = Integer.max(alpha,eval); if( beta <= alpha){ break; } } return maxEval; } else{ int minEval = Integer.MAX_VALUE; for(String[][] child: generateChildren(position)){ int eval = minmax(child, depth -1, alpha,beta,true); minEval = Integer.min(minEval,eval); beta = Integer.min(beta,eval); if( beta <= alpha){ break; } } return minEval; } }我尝试创建了一个评估类，该类还保存了子节点的位置，但似乎无法弄清楚在哪里返回什么以获得正确的位置。
public class BestMove { public int value; public String[][] position; public BestMove(int value, String[][] position) { this.value = value; this.position = position; }}public BestMove minmax(String[][] position, int depth, int alpha, int beta, boolean maximizingPlayer) { // TODO recursion ends with game over if (depth == 0) { return new BestMove(AssessGame.assess(position, maximizingPlayer), position); } if (maximizingPlayer) { int maxEval = Integer.MIN_VALUE; String[][] bestPosition = null; for (String[][] child : generateChildren(position)) { BestMove move = minmax(child, depth - 1, alpha, beta, false); int eval = move.value; if (eval > maxEval) { maxEval = eval; bestPosition = child; } alpha = Integer.max(alpha, eval); if (beta <= alpha) { break; } } return new BestMove(maxEval, bestPosition); } else { int minEval = Integer.MAX_VALUE; String[][] bestPosition = null; for (String[][] child : generateChildren(position)) { BestMove move = minmax(child, depth - 1, alpha, beta, true); int eval = move.value; if (eval < minEval) { minEval = eval; bestPosition = child; } beta = Integer.min(beta, eval); if (beta <= alpha) { break; } } return new BestMove(minEval, bestPosition); }}回答：
经过一些试验，这是对我有效的方法：
public BestMove minmax(String[][] position, int depth, int alpha, int beta, boolean maximizingPlayer) { if (depth == 0 || noPiecesLeft(position)) { return new BestMove(AssessGame.assess(position, teamID, depth), position); } if (maximizingPlayer) { int maxEval = Integer.MIN_VALUE; String[][] bestPosition = null; for (String[][] child : generateChildren(position, true)) { BestMove move = minmax(child, depth - 1, alpha, beta, false); int eval = move.value; if (eval > maxEval) { maxEval = eval; bestPosition = child; } alpha = Integer.max(alpha, eval); if (beta <= alpha) { break; } } return new BestMove(maxEval, bestPosition); } else { int minEval = Integer.MAX_VALUE; String[][] bestPosition = null; for (String[][] child : generateChildren(position, false)) { BestMove move = minmax(child, depth - 1, alpha, beta, true); int eval = move.value; if (eval < minEval) { minEval = eval; bestPosition = child; } beta = Integer.min(beta, eval); if (beta <= alpha) { break; } } return new BestMove(minEval, bestPosition); }}