带Alpha-Beta剪枝的Minimax跳棋AI决策劣于无剪枝版本的问题排查

我独立开发了一款基于Minimax算法和Alpha-Beta剪枝的跳棋AI，但发现启用Alpha-Beta剪枝的AI决策表现反而不如未启用剪枝的版本。推测是剪枝操作误删了当前看似劣势但后续会产生有利局面的分支。

实现代码 #

def terminal(state,turn):
    count_x = 0
    count_o = 0
    if turn == 'x' or turn == 'kx':
        if not actions(state,'x'):
            return True
    if turn == 'o' or turn == 'ko':
        if not actions(state,'o'):
            return True 
    for r in state:
        for c in r:
            if c == 'x' or c == 'kx':
                count_x += 1
            elif c == 'o' or c =='ko':
                count_o += 1
            if count_x != 0 and count_o != 0:
                return False
    return True

def utility2(state): #win or lose
    count_x = 0
    count_o = 0
    for r in state:
        for c in r:
            if c == 'x' or c == 'kx':
                count_x += 1
            if c == 'o' or c == 'ko':
                count_o += 1
    if count_x > 0 and count_o == 0: #X wins
        return 50
    elif count_x == 0 and count_o > 0:#O wins
        return -50
    else:
        if not actions(state,'o'):
            return 50
        elif not actions(state, 'x'):
            return -50

def count(state,turn):
    count_x = 0
    count_o = 0
    for r in state:
        for c in r:
            if c == 'x' or c == 'kx':
                count_x += 1
            elif c=='o'or c =='ko':
                count_o += 1
    if turn == 'x' or turn == 'kx':
        return count_x
    else:
        return count_o
        
def utility(state): #calculate win chance mid game
    #MAX is 'x'
    count = 0
    for r in state:
        for c in r:
            if c == 'x':
                count += 1
            elif c == 'o':
                count -= 1
            elif c == 'kx':
                count += 5
            elif c == 'ko':
                count -= 5
            else:
                count += 0
    return count

def maxvalue(state,depth,max_depth,alpha,beta):
    # print("max = "+ str(depth))
    if terminal(state,'x'):
        return utility2(state)
    if depth >= max_depth:
        return utility(state)
    v = -999
    for action in actions(state,'x'):
        results = result(state,action)
        for r in results:
            v = max(v,minvalue(r,depth+1,max_depth,alpha,beta))
            alpha = max(alpha,v)
            # if alpha >= beta:
            #     return v
    return v

def minvalue(state,depth,max_depth,alpha,beta): #this combines in to a depth first search
    # print("min = " + str(depth))
    if terminal(state,'o'):
        return utility2(state)
    if depth >= max_depth:
        return utility(state)
    v = 999
    for action in actions(state,'o'):
        results = result(state,action)
        for r in results:
            v = min(v,maxvalue(r,depth+1,max_depth,alpha,beta))
            beta = min(beta,v) #BETAAA
            # if alpha >= beta:
            #    return v
    return v

def minimax(state,turn,max_depth):
    """
    Returns the optimal action for the current player on the state.
    """
    if terminal(state,turn):
        return None
    else:
        if turn == 'x':
            moves = []
            alpha = -999
            beta = 999
            for action in actions(state,'x'):
                results = result(state,action)
                for r in results:
                    new_v = minvalue(r,1,max_depth,alpha,beta) 
                    moves.append((r,new_v))
                    alpha = max(alpha,new_v)
                    if alpha >= beta:
                        return getbestmoves(moves,'x')
            
            return getbestmoves(moves,'x')
        if turn == 'o':
            moves = []
            alpha = -999
            beta = 999
            for action in actions(state,'o'):
                results = result(state,action)
                for r in results:
                    new_v = maxvalue(r,1,max_depth,alpha,beta)
                    moves.append((r,new_v))
                    beta = min(beta,new_v)
                    if alpha >= beta:
                        return getbestmoves(moves,'o')
            return getbestmoves(moves,'o')

def getbestmoves(moves,turn):
    if turn == 'x':
        for move in moves:
            print(move[1])
        max_value = max(moves, key=lambda x: x[1])[1]
        result = []
        for move in moves:
            if move[1] == max_value:
                result.append(move[0])
        print("max = " + str(max_value))
        return random.choice(result)
    elif turn == 'o':
        min_value = min(moves, key=lambda x: x[1])[1]
        result = []
        for move in moves:
            if move[1] == min_value:
                result.append(move[0])
        print("min = " + str(min_value))
        return random.choice(result)

测试场景 #

state =     [['x', '-', 'x', '-', '-', '-', 'x', '-'],
            ['-', '-', '-', 'x', '-', '-', '-', '-'],
            ['x', '-', '-', '-', '-', '-', 'x', '-'],
            ['-', '-', '-', '-', '-', 'x', '-', '-'],
            ['o', '-', '-', '-', 'x', '-', '-', '-'],
            ['-', 'o', '-', '-', '-', 'o', '-', '-'],
            ['o', '-', 'o', '-', 'o', '-', 'o', '-'],
            ['-', '-', '-', '-', '-', '-', '-', 'o']]

测试发现无剪枝版本生成的v值更优，且仅2层深度的无剪枝Minimax bot能击败带剪枝的AI。

问题排查关键点 #

1. 核心剪枝逻辑未生效：maxvalue和minvalue函数中的Alpha-Beta剪枝判断代码被注释，导致剪枝逻辑完全缺失，而minimax函数中的剪枝属于错误的上层提前终止，并非真正的Alpha-Beta剪枝。
2. 剪枝时机错误：在minimax函数中，每计算一个子节点就触发剪枝并返回，此时未遍历完当前层所有可能的动作，会直接丢弃后续可能存在的更优解。
3. Alpha-Beta参数传递错误：maxvalue和minvalue递归调用时，未传递更新后的alpha/beta值，导致剪枝信息无法在搜索树中正确传递，即使恢复剪枝逻辑也无法正常工作。
4. 终端状态判断逻辑错误：terminal函数中，遍历棋子时只要同时检测到双方棋子就直接返回False，会忽略“某方有棋子但无合法动作”的终端场景，导致游戏结束判断不准确。
5. 效用函数逻辑漏洞：utility2函数未处理“双方都无合法动作”的平局场景，可能返回未定义的结果，影响搜索的准确性。

修复建议 #

1. 恢复并修正剪枝逻辑 #

取消maxvalue和minvalue中剪枝代码的注释，确保递归传递更新后的alpha/beta值：

def maxvalue(state,depth,max_depth,alpha,beta):
    if terminal(state,'x'):
        return utility2(state)
    if depth >= max_depth:
        return utility(state)
    v = -999
    for action in actions(state,'x'):
        results = result(state,action)
        for r in results:
            current_v = minvalue(r,depth+1,max_depth,alpha,beta)
            v = max(v, current_v)
            alpha = max(alpha, v)
            if alpha >= beta:
                return v
    return v

def minvalue(state,depth,max_depth,alpha,beta):
    if terminal(state,'o'):
        return utility2(state)
    if depth >= max_depth:
        return utility(state)
    v = 999
    for action in actions(state,'o'):
        results = result(state,action)
        for r in results:
            current_v = maxvalue(r,depth+1,max_depth,alpha,beta)
            v = min(v, current_v)
            beta = min(beta, v)
            if alpha >= beta:
                return v
    return v

2. 修正minimax函数的剪枝时机 #

移除minimax函数中的提前返回逻辑，让下层的maxvalue/minvalue处理剪枝，上层仅负责收集所有可能动作的评估结果：

def minimax(state,turn,max_depth):
    """
    Returns the optimal action for the current player on the state.
    """
    if terminal(state,turn):
        return None
    else:
        if turn == 'x':
            moves = []
            alpha = -999
            beta = 999
            for action in actions(state,'x'):
                results = result(state,action)
                for r in results:
                    new_v = minvalue(r,1,max_depth,alpha,beta) 
                    moves.append((r,new_v))
                    alpha = max(alpha,new_v)
            return getbestmoves(moves,'x')
        if turn == 'o':
            moves = []
            alpha = -999
            beta = 999
            for action in actions(state,'o'):
                results = result(state,action)
                for r in results:
                    new_v = maxvalue(r,1,max_depth,alpha,beta)
                    moves.append((r,new_v))
                    beta = min(beta,new_v)
            return getbestmoves(moves,'o')

3. 修复终端状态判断逻辑 #

调整terminal函数，先判断当前玩家的合法动作，再统计棋子数量，确保所有终端场景都被正确识别：

def terminal(state,turn):
    # 判断当前玩家是否有合法动作
    if turn in ['x', 'kx']:
        if not actions(state,'x'):
            return True
    if turn in ['o', 'ko']:
        if not actions(state,'o'):
            return True 
    # 统计双方棋子数量
    count_x = 0
    count_o = 0
    for r in state:
        for c in r:
            if c in ['x', 'kx']:
                count_x += 1
            elif c in ['o', 'ko']:
                count_o += 1
    # 只有一方有棋子时游戏结束
    return count_x == 0 or count_o == 0

4. 完善效用函数 #

补充平局场景的处理，避免返回未定义值：

def utility2(state):
    count_x = 0
    count_o = 0
    for r in state:
        for c in r:
            if c in ['x', 'kx']:
                count_x += 1
            if c in ['o', 'ko']:
                count_o += 1
    if count_x > 0 and count_o == 0:
        return 50
    elif count_x == 0 and count_o > 0:
        return -50
    # 检查双方是否都无动作
    x_has_actions = bool(actions(state,'x'))
    o_has_actions = bool(actions(state,'o'))
    if not x_has_actions and not o_has_actions:
        return 0  # 平局
    elif not o_has_actions:
        return 50
    elif not x_has_actions:
        return -50

内容的提问来源于stack exchange，提问作者user24528023