algorithm - Minimax 算法的优点/缺点

Question

A disadvantage of the minimax algorithm is that each board state has to be visited twice: one time to find its children and a second time to evaluate the heuristic value.

极小极大算法还有其他缺点或优点吗？比如说像国际象棋这样的游戏，会有更好的选择吗？ (当然是带有 alpha-beta 剪枝的 minimax 但还有其他吗？)

Answer 1

Minimax 对于国际象棋等游戏来说往往太慢了。对于每一轮，玩家都有很多选择要决定，一盘棋的分支因素是巨大的，因此我们走得越深，速度就越慢。平均而言，国际象棋的分支因子趋向于 30。即每回合创建 30 个子树。

在给出具体算法之前，他们都使用了我们所说的alpha beta pruning。 Alpha beta 减少了要扩展的节点数，因此我们减少了分支因子。

请记住，minimax 和 alpha beta 有许多不同的变体，但最重要的算法是:

• Negamax:这里的想法是，一个玩家的移动分数始终是另一个玩家的 -ve 但相同的幅度允许您计算 max(a,b) = -min (-a,-b)。

简单解释:

score = -negamax(depth-1,-player)
best = max(score,best)

窗口搜索算法

以下算法使用窗口以减少搜索空间。该窗口最初将假定 alpha 和 beta 的值。

• Principal Variation Method:该方法通过“猜测”初始 alpha 和 beta 来减少访问的节点数。为此，它仅探索一个分支并选择候选 值。使用这个值我们修剪。如果我们发现矛盾，这个值会比我们再次开始改变候选的候选值产生更高的分数。

• MTD(f) minimax 的另一种变体。使用零窗口搜索。这意味着，在我们找到候选者(比如“v”)之后，我们假设 alpha beta 值将是 (v-1,v) 因此只有 v 是可能的解决方案。如果我们发现矛盾，则更改候选人并重复。

当今国际象棋计算机程序最好和最常用的算法是 MTD(f)，具有一些变体/启发式算法。

来源:Converting Minimax to Negamax (python)