Java Minimax Alpha-Beta修剪递归返回

5 回答

• 0

  我注意到你说你发现了问题，但不应该是minimax alpha beta修剪

  if it is MAX's turn to move
    for child in children
       result = alphaBetaMinimax(child, alpha, beta)
       if result > alpha
          alpha = result
          if node is root
             bestMove = operator of child
       if alpha >= beta
          return alpha
    return alpha
  
  if it is MIN's turn to move
    for child in children
       result = alphaBetaMinimax(child, alpha, beta)
       if result < beta
          beta = result
          if node is root
             bestMove = operator of child
       if beta <= alpha
          return beta
    return beta
  

  你写了：

  if alpha >= beta
      return beta
  return alpha
  

  回复于 2024-04-24T00:40:02+08:00
• 1

  只是回答你的问题

  是否有从for循环中的递归调用中恢复多个整数值的技巧？

  是的，在Java中，您需要将对象传递给递归函数调用，然后修改该对象的内容 . 函数返回后，您将能够访问修改后的值 .

  例如 .

  class ToBeReturned {
      int returnValue1;
      int returnValue2;
      int returnValue3;
  }
  

  回复于 2024-04-24T00:40:02+08:00
• 2

  2013年3月16日，sage88问道：

  是否有从for循环中的递归调用中恢复多个整数值的技巧？它适用于我的minimax和negamax实现，但alpha-beta修剪似乎产生了一些奇怪的结果 .

  在alpha beta修剪中，唯一感兴趣的输出值是节点的得分：min节点中beta的最终值被认为是其父节点的alpha值;同样地，最大节点中的α的最终值被考虑用于其父节点的β值 . 因此：

  The answer to your question is the algorithm itself, as it's the most relevant trick.

  也就是说，你的实现中有两个错误：1）正如Adrian Blackburn最初指出的那样，它错误地从最小节点返回alpha，反之亦然，从而扭曲了它的准确性; 2）通过过早考虑当前节点值中的父alpha或beta，它放弃了修剪机会 . 此版本修复了返回值并最大化了修剪：

  private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) {
      if (depth <= 0 || terminalNode(currentNode.getState())) {
          return getHeuristic(currentNode.getState());
      }
      if (currentNode.getState().getCurrentPlayer().equals(selfColor)) {
          int currentAlpha = -INFINITY;
          for (GameTreeNode child : currentNode.getChildren()) {
              currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta));
              alpha = Math.max(alpha, currentAlpha);
              if (alpha >= beta) {
                  return alpha;
              }
          }
          return currentAlpha;
      }
      int currentBeta = INFINITY;
      for (GameTreeNode child : currentNode.getChildren()) {
          currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta));
          beta = Math.min(beta, currentBeta);
          if (beta <= alpha) {
              return beta;
          }
      }
      return currentBeta;
  }
  

  感谢您提供有趣和有趣的问题:)

  为了更有趣，这里是对 move() 方法的澄清，删除了对 Math.max() 的冗余调用：

  @Override
  public GameState move(GameState state) {
      GameState bestMove = null;
      int bestScore = -INFINITY;
      GameTreeNode gameTreeRoot = new GameTreeNode(state);
      for (GameTreeNode child : gameTreeRoot.getChildren()) {
          int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY);
          if (alpha > bestScore || bestMove == null) {
              bestMove = child.getState();
              bestScore = alpha;
          }
      }
      return bestMove;
  }
  

  最后（更有趣），只是一个建议，一个方法名称更改，以澄清 terminalNode() 的意图，虽然我会将其移动到 GameState 所以它可以不带参数调用：

  private boolean isTerminal(GameState state) {
      //return Is.any(state.getStatus(), win, lose, draw);
      return state.getStatus().equals(win)
          || state.getStatus().equals(lose)
          || state.getStatus().equals(draw);
  }
  

  回复于 2024-04-24T00:40:02+08:00
• 0

  要获得结果，您应该实施某种移动排序 . 在国际象棋中，它通常是捕获或检查 . 这种举动倾向于最大程度地改变评价，因此它们对狡猾的影响很大 . 在跳棋中，它可能会在第8级采用对手的石头或促进自我结石（抱歉不知道使用的术语） .

  回复于 2024-04-24T00:40:02+08:00
• 1

  您已经解决了问题，但遇到的问题很常见 . 因此，无论何时为AI代理构建算法的一部分，都必须正确地进行测试 . 因此，一旦您的minimax算法正确，您可以生成许多随机树并检查结果是否相同 . 例如在python中，你可以这样做：

  class Node():
      def __init__(self, data, children):
          self.data = data
          self.children = children
  
  def generateTree(depth, branching):
      total = branching**depth
      values = [randint(-100, 100) for _ in xrange(total)]
      level = [Node(values[i], []) for i in xrange(total)]
  
      for _ in xrange(depth):
          total /= branching
          level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)]
  
      return level[0], values
  

  现在，您可以生成包含许多随机树的树并比较结果 .

  tree, values = generateTree(depth, branching)
  print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1)
  

  ---

  不要忘记minimax和alpha-beta只返回最佳值，而你是什么对真正的游戏感兴趣是一个举动 . 可以直接修改它们以便它们可以返回移动，但这取决于开发人员决定如何返回移动 . 这是因为可以有许多移动导致最佳解决方案（您可以返回第一个，最后一个或最常见的是找到所有移动并返回随机移动） .

  在您的情况下，问题在于返回值的随机性，因此在测试期间，好的方法是修复随机性 .

  回复于 2024-04-24T00:40:02+08:00