实现"MiniMax“递归的更好方法

Question

我在游戏中使用了MinMax算法，而且由于MinMax递归的可能性很大，即使使用"alpha-beta剪枝“，也要花很长的时间。

我的代码看起来有点像这样：

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 (或者一般情况下是递归算法)，而且可能有其他方法使用其他技术来找到最优解，但是没有一组精确的规则是不可能知道的。