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 但还有其他吗?)
最佳答案
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),具有一些变体/启发式算法。
关于algorithm - Minimax 算法的优点/缺点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36892813/