问Minimax解释"for dummies“

EN

“极小极大”的概念是，在两人博弈中，一个玩家试图最大化某种形式的分数，而另一个玩家试图最小化它。例如，在Tic-Tac-Toe中，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剪枝“。它给出与极小极大搜索相同的结果，但速度更快。Minimax也可以用"negamax“来表示，其中分数的符号在每个搜索级别都是颠倒的。这只是一种实现极小极大的替代方法，但以统一的方式处理玩家。其他博弈树搜索方法包括迭代加深、证明号搜索等。

Minimax是一种在交替轮换的两人游戏中探索潜在移动空间的方法。你正试图取胜，而你的对手试图阻止你取胜。

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

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