11

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

我只需要了解它是如何工作的。我读了很多关于那的东西，我理解了基本的，但我仍然不知道它是如何返回的。

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

感谢您的时间 ：）

4

2 回答 2

9

“极小极大”的概念是在两人游戏中，一个玩家试图最大化某种形式的分数，而另一个玩家试图最小化它。例如，在井字游戏中，X 的胜利可能计为 +1，O 的胜利可能计为 -1。X 将是最大玩家，试图最大化最终得分，而 O 将是最小玩家，试图最小化最终得分。

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

换句话说，棋盘位置 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，选择最小的后继位置。

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

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

于 2012-05-17T15:29:14.783 回答
3

Minimax 是一种在交替回合的两人游戏中探索潜在移动空间的方法。你想赢，而你的对手想阻止你赢。

一个关键的直觉是，如果现在轮到你了，保证你获胜的两步顺序是没有用的，因为你的对手不会与你合作。你试图做出让你获胜机会最大化的动作，而你的对手做出让你获胜机会最小化的动作。

出于这个原因，从你做出的对你不利的动作或对手做出的对你有益的动作中探索分支并不是很有用。

于 2012-05-16T22:22:25.490 回答