python - Minimax 解释 "for dummies"

Question

我对算法很陌生，我试图理解 minimax，我阅读了很多文章，但我仍然不知道如何将它实现到 python 中的井字游戏中。你能试着用一些伪代码或一些 python 代码尽可能简单地向我解释它吗？

我只需要了解它是如何工作的。我读了很多关于它的资料，我了解基本知识，但我仍然不明白它是如何还手的。

如果可以，请不要给我链接教程和示例，例如 (http://en.literateprograms.org/Tic_Tac_Toe_(Python)) ，我知道它们很好，但我只需要一个白痴解释。

感谢您的宝贵时间:)

Answer 1

“minimax”的想法是，在两人游戏中，一个玩家试图最大化某种形式的分数，而另一个玩家试图最小化它。例如，在 Tic-Tac-Toe 中，X 的获胜可能记为 +1，O 的获胜记为 -1。 X 将是最大玩家，试图最大化最终得分，而 O 将是最小玩家，试图最小化最终得分。

X 被称为最大玩家，因为当它是 X 的着法时，X 需要选择一个使该着法后的结果最大化的着法。当 O 玩家时，O 需要选择一个移动，使该移动后的结果最小化。这些规则递归应用，例如如果只有三个棋盘位置可供下，X 的最佳下法是迫使 O 选择值(value)尽可能高的最小值着法。

换句话说，棋盘位置 B 的博弈论极小极大值 V 定义为

 V(B) = 1   if X has won in this position
 V(B) = -1  if O has won in this position
 V(B) = 0   if neither player has won and no more moves are possible (draw)

否则

 V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for X, and it is X's move
 V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for O, and it is O's move

X 的最优策略总是从 B 移动到 Bi，使得 V(Bi) 最大，即对应于博弈论值 V(B)，对于 O，类似地，选择最小的后继位置。

然而，这在国际象棋等游戏中通常无法计算，因为为了计算博弈论值，需要枚举整个博弈树直到最终位置，而这棵树通常非常大。因此，一种标准方法是创造一个“评估函数”，将棋盘位置映射到希望与博弈论值相关的分数。例如。在国际象棋程序中，评估函数往往会为 Material 优势、开放列等给出正分数。极小极大算法会最小化评估函数分数，而不是棋盘位置的实际(不可计算的)博弈论值。

minimax 的一个重要的标准优化是“alpha-beta 剪枝”。它给出的结果与极小极大搜索相同，但速度更快。 Minimax 也可以根据“negamax”进行转换，其中得分的符号在每个搜索级别都反转。它只是实现 minimax 的另一种方法，但以统一的方式处理玩家。其他博弈树搜索方法包括迭代加深、证明数搜索等。