python - 实现“MiniMax”递归的更好方法

Question

我在游戏中使用了 MinMax 算法，因为有很多可能性 MinMax 递归需要太长时间，即使是“alpha-beta pruning”

我的代码看起来像这样：

min(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        beta = min(beta, max(state,depth,alpha,beta) )
        if alpha >= beta: return beta
    return beta

max(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        alpha = max(beta, min(state,depth,alpha,beta) )
        if alpha >= beta: return alpha
    return beta

我知道有时您可以使用for循环而不是递归，但我找不到转换它的方法。

如果有人有一个好主意，我会很高兴听到它！

谢谢，

Answer 1

通常，minmax 中的递归不能用等效的迭代算法代替，这就是为什么有优化方法（如 beta 剪枝）试图通过尽快停止递归树的某些分支来提高性能。

对于您的游戏，可能完全不需要 minmax（或者通常是递归算法），并且可能有其他方法可以使用其他技术找到最佳解决方案，但如果没有一组精确的规则是不可能的。