Negamax与深度的alpha-beta修剪bug 0

我正在编程alpha-beta修剪的negamax。但是，它只有在“坏”行被移除时才有效，但我不知道为什么。我的代码是基于这个pseudo-code。这是对的吗？大多数实现在循环内调用negamax（在根节点的单独函数上），我应该这样做吗？为什么？Negamax与深度的alpha-beta修剪bug 0

private static double AlphaBetaWithMemory(Board board, int player, 
     int depth, 
     int max_depth, double alpha, double beta) { 


    double eval = Double.NEGATIVE_INFINITY; 
    List<Integer> moves; 
    if (depth == max_depth 
      || board.gameOver()) { 
     double h = board.heuristic(player); 
     return h; 
    } else { 
     movs=board.getMoves(); 
     for (Integer m : moves) { 
      if (depth == 1) { 
       double val = -AlphaBetaWithMemory(
         board.move(m), (player + 1) % 2, 
         depth + 1, 
         max_depth, -beta, -alpha); 
       if (val > eval) { 
        best_mov = m; 
        eval = val; 
       } else if (val == eval) { 
        if (Math.random() > 0.5) { 
         best_mov = m; 
        } 
       } 
       alpha = Math.max(alpha, val); //"BAD" LINE 
      } else { 
       double val = -AlphaBetaWithMemory(
         board.mover(m), (player + 1) % 2, 
         depth + 1, 
         max_depth, -beta, -alpha); 
       eval = Math.max(eval, val); 
       alpha = Math.max(alpha, val); 
       if (alpha >= beta) { 
        return beta; 
       } 
      } 
     } 
    } 
    return eval;

来源

2014-12-02 dv1729

保持“坏行”会发生什么？在第一次调用'AlphaBetaWithMemory'时，其中一个参数是'board.move（m）'，在第二次调用时它是'board.mover（m）'。这只是一个错字吗？ – manlio 2014-12-04 14:28:42

的问题是：

else if (val == eval) { 
     if (Math.random() > 0.5) { 
      best_mov = m; 
     } 
}

为了解决这个问题（并保持随机性）我只是需要洗牌 “MOVS”。我知道排序“movs”会更有效率。

来源

2014-12-04 20:52:38 dv1729

Negamax与深度的alpha-beta修剪bug 0

回答

相关问题