了解最小最大值算法

本文关键字：算法 最大值 了解 | 更新日期: 2024-12-05 19:33:32

我正在尝试为两人 8x8 棋盘游戏创建一个 AI 对手。经过研究，我发现Minimax算法足够方便来完成这项工作。我正在创建的AI对手将与其他AI对手或人类对战。

我对理解最小最大值算法有疑问。

我正在尝试只创建一个 AI 对手，但网络上的解释说我需要为两个玩家（最小玩家和最大玩家）编写代码，正如我从下面的伪代码中理解的那样。

MinMax (GamePosition game) {
  return MaxMove (game);
}
MaxMove (GamePosition game) {
  if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move < - move;
       }
    }
    return best_move;
  }
}
MinMove (GamePosition game) {
  best_move <- {};
  moves <- GenerateMoves(game);
  ForEach moves {
     move <- MaxMove(ApplyMove(game));
     if (Value(move) > Value(best_move)) {
        best_move < - move;
     }
  }
  return best_move;
}

我可以进一步理解，最大玩家将是我将要开发的AI，最小玩家是对手。

我的问题是为什么我必须为最小和最大玩家编写代码才能返回最佳移动？

下面给出的伪代码基于 C#。

提前谢谢。

了解最小最大值算法

您只需要在最坏的情况下为两个玩家搜索最佳解决方案，为什么它被称为 minmax，您不需要更多：

function minimax( node, depth )     
   if node is a terminal node or depth <= 0:        
       return the heuristic value of node  
   α = -∞    
   foreach child in node:          
      α = max( a, -minimax( child, depth-1 ) )  
   return α

节点是一个游戏位置，节点中的子级是下一步移动（从所有可用移动的列表中），深度是两个玩家一起搜索的最大动作。

您可能无法在 8x8 上运行所有可能的移动（取决于您有多少个下一步移动选项）例如，如果每个你都有 8 个不同的可能动作，并且游戏在 40 个动作后结束（应该是最坏的情况），那么你会得到 8^40 个位置。计算机将需要十年甚至更长时间才能解决它，这就是为什么您需要深度参数和使用启发式函数（例如随机森林树）来了解游戏位置有多好，而无需检查所有选项。

minmax更好的算法是Alpha-Beta修剪，一旦找到目标（β参数），就会完成搜索：

function negamax( node, depth, α, β, color )  
   if node is a terminal node or depth = 0     
       return color * the heuristic value of node  
   foreach child of node          
       value = -negamax( child, depth-1, -β, -α, -color )  
   if value ≥ β                
      return value /** Alpha-Beta cut-off */  
  if value ≥ α       
     α = value              
  return α

最好先使用没有很多位置的游戏（例如井字游戏）。

相关文章：