python 中的 alpha beta 修剪算法错误

Question

在接下来的修剪中，返回的alpha是正确的，而beta保持不变，我做错了什么？这是一棵在底部节点具有以下值的树

tree = [[[5, 1, 2], [8, -8, -9]], [[9, 4, 5], [-3, 4, 3]]]
root = 0
pruned = 0

def children(branch, depth, alpha, beta):
    global tree
    global root
    global pruned
    i = 0
    for child in branch:
        if type(child) is list:
            (nalpha, nbeta) = children(child, depth + 1, alpha, beta)
            if depth % 2 == 1:
                beta = nalpha if nalpha < beta else beta
            else:
                alpha = nbeta if nbeta > alpha else alpha
            branch[i] = alpha if depth % 2 == 0 else beta
            i += 1
        else:
            if depth % 2 == 0 and alpha < child:
                alpha = child
            if depth % 2 == 1 and beta > child:
                beta = child
            if alpha >= beta:
                pruned += 1
                break
    if depth == root:
        tree = alpha if root == 0 else beta
    return (alpha, beta)

def alphabeta(in_tree=tree, start=root, lower=-15, upper=15):
    global tree
    global pruned
    global root

    (alpha, beta) = children(tree, start, lower, upper)

    if __name__ == "__main__":
        print ("(alpha, beta): ", alpha, beta)
        print ("Result: ", tree)
        print ("Times pruned: ", pruned)

    return (alpha, beta, tree, pruned)


if __name__ == "__main__":
    alphabeta()

这些代码是否正确，或者我应该采用不同的方法吗？编辑问题很可能源于测试版部分的模数(%)

EDIT2 更新代码

tree = [[[1, 8], [5], [6, 4, 7], [9], [3, 2], [6, 10, 2]]]
side = 1
alpha = -1000
beta = 1000
depth = 3
p = []
betacuts=[]
alphacuts=[]
counta=-1
countb=-1

def getLengthLoL(position):
    if len(position)==0:
        if isinstance(tree,int):
            return tree
        return len(tree)
    if len(position)==1:
        if isinstance(tree[p[0]],int):
            return tree[p[0]]
        return len(tree[p[0]])
    if len(position)==2:
        if isinstance(tree[p[0]][p[1]],int):
            return tree[p[0]][p[1]]
        return len(tree[p[0]][p[1]])
    if len(position)==3:
        if isinstance(tree[p[0]][p[1]][p[2]],int):
            return tree[p[0]][p[1]][p[2]]
        return len(tree[p[0]][p[1]][p[2]])
    if len(position)==4:
        if isinstance(tree[p[0]][p[1]][p[2][p[3]]],int):
            return tree[p[0]][p[1]][p[2][p[3]]]
        return len(tree[p[0]][p[1]][p[2][p[3]]])
def makeMove(move):
    global side
    if side:
        side = 0
    else:
        side = 1
    p.append(move)

def backMove(move):
    global side
    if side:
        side = 0
    else:
        side = 1
    p.pop()

def evaluation(score):
    if side==0:
        return -1*score
    else:
        return score

def minmax( alpha, beta, depth ):
    global counta
    global countb
    if depth==0:
        return evaluation(getLengthLoL(p))
    moves = getLengthLoL(p)
    for move in range(int(moves)):
        makeMove(move)
        val = -1*minmax(-beta,-alpha,depth-1)
        backMove(move)
        if val >= beta:
            betacuts.append(val)
            countb += 1
            beta=val;
            return beta;
        if val > alpha:
            alphacuts.append(val)
            counta += 1
            alpha = val;

    return alpha


myScore = minmax(alpha,beta,depth)
print (betacuts,alphacuts)
print (myScore)

此代码从一开始就打印了错误的 alpha 和 beta

Answer 1

所以这是一种更传统的方法。我没有仔细检查过，但我知道这是正确的方法。变量 p 正在编码 "position"。只有树的所有分支的深度都相同时，代码才会准确。在这种情况下，这就是深度变量设置为 3 的原因。需要做更多的工作才能使其在任何树上运行。

tree = [[[0,1,2],[-1,2,5],[-2,2,0]],[[-2,-1,-3],[-4,-3,-1],[1,2,8]],[[4,6,1],[1,7,-1],[-2,-4,1]]]

side = 1
alpha = -1000
beta = 1000
depth = 3

p = []
def getLengthLoL(l, address):
    item = l
    for index in address:
        item = item[index]
    return len(item) if isinstance(item, list) else item

def makeMove(move):
    global side
    if side:
        side = 0
    else:
        side = 1
    p.append(move)

def backMove(move):
    global side
    if side:
        side = 0
    else:
        side = 1
    p.pop()

def evaluation(score):
    if side==0:
        return -1*score
    else:
        return score 

def minmax( alpha, beta, depth ):
    if depth==0:
        return evaluation(getLengthLoL(tree,p))
    moves = getLengthLoL(tree,p)
    for move in range(int(moves)):
        makeMove(move)
        val = -1*minmax(-beta,-alpha,depth-1)
        backMove(move)
        if val >= beta:
            return beta;        
        if val > alpha:
            alpha = val;
    return alpha        

myScore = minmax(alpha,beta,depth)
print myScore

python 中的 alpha beta 修剪算法错误

Error in alpha beta prunning algorithm in python

python

algorithm

artificial-intelligence

pruning