我正在尝试为一个两人8×8棋盘游戏创建一个AI对手。经过研究，我发现Minimax算法足够有效来完成这项任务。我正在创建的AI对手将与另一个AI对手或人类玩家对战。

我在理解Minimax算法方面有些疑问。

我只是想创建一个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 α

node是一个游戏位置，child在node中是下一步移动（来自所有可用移动的列表），depth是两个玩家一起搜索的最大移动数。

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

对于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 α

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