3D井字棋Minimax（含Alpha-Beta剪枝）运行过慢问题求助

问题描述 #

开发3D井字棋不败AI时，实现了带Alpha-Beta剪枝的Minimax函数，但测试时函数无限运行。尝试引入深度变量限制搜索深度，却返回错误走法。玩家1用1表示，玩家2用-1表示，代码及测试用例如下：

def generate_winning_lines(board):
    n = len(board)
    winning_lines = set()
        
    # Add lines in xy plane
    winning_lines |= {tuple([(x, y, z) for y in range(n)]) for x in range(n) for z in range(n)}
    
    # Add lines in yz plane
    winning_lines |= {tuple([(x, y, z) for y in range(n)]) for z in range(n) for x in range(n)}
    
    # Add lines in zx plane
    winning_lines |= {tuple([(x, y, z) for x in range(n)]) for z in range(n) for y in range(n)}
    
    # Add lines in x direction
    winning_lines |= {tuple([(x, y, z) for x in range(n)]) for y in range(n) for z in range(n)}
    
    # Add lines in y direction
    winning_lines |= {tuple([(x, y, z) for y in range(n)]) for x in range(n) for z in range(n)}
    
    # Add lines in z direction
    winning_lines |= {tuple([(x, y, z) for z in range(n)]) for x in range(n) for y in range(n)}
    
    # Add diagonal lines
    winning_lines |= {tuple([(x, x, x) for x in range(n)])}
    winning_lines |= {tuple([(x, x, n-1-x) for x in range(n)])}
    winning_lines |= {tuple([(x, n-1-x, x) for x in range(n)])}
    winning_lines |= {tuple([(x, n-1-x, n-1-x) for x in range(n)])}
    winning_lines |= {tuple([(x, x, y) for x in range(n)]) for y in range(n)}
    winning_lines |= {tuple([(y, x, x) for x in range(n)]) for y in range(n)}
    winning_lines |= {tuple([(x, y, x) for x in range(n)]) for y in range(n)}
    winning_lines |= {tuple([(x, n -1 -x, y) for x in range(n)]) for y in range(n)}
    winning_lines |= {tuple([(y, x, n -1 -x) for x in range(n)]) for y in range(n)}
    winning_lines |= {tuple([(x, y, n -1 -x) for x in range(n)]) for y in range(n)}

    return winning_lines
def victory_check(board, winning_lines):
    p1, p2 = None, None
    for line in winning_lines:
        values = [board[x][y][z] for x, y, z in line]
        if all(v == 1 for v in values):
            p1 = True, 1
        elif all(v == -1 for v in values):
            p2 = True, -1
        if p1 and p2:
            return True, 0
        elif p1:
            return p1
        elif p2:
            return p2
    return False, 0

def get_possible_moves(board):
    n = len(board)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if board[i][j][k] == 0:
                    yield i,j,k

def best_move(board, winning_lines):
    n = len(board)
    best_score = float('-inf')
    move = (-1, -1, -1)
    for i,j,k in get_possible_moves(board):
        board[i][j][k] = -1
        curr_score = minimax(board, float('-inf'), float('inf'), False, winning_lines, 0)
        board[i][j][k] = 0
        if curr_score > best_score:
            move = (i,j,k)
            best_score = curr_score
    return move

def minimax(board, alpha, beta, to_max, winning_lines, depth):
    terminal = victory_check(board, winning_lines)
    if terminal[0]:
        return terminal[1]
    if to_max:
        best = float('-inf')
        for i,j,k in get_possible_moves(board):
            board[i][j][k] = -1
            score = minimax(board, alpha, beta, False, winning_lines, depth + 1)
            board[i][j][k] = 0
            best = max(score, best)
            alpha = max(alpha, best)
            if beta <= alpha:
                break
        return best
    else:
        best = float('inf')
        for i,j,k in get_possible_moves(board):
            board[i][j][k] = 1
            score = minimax(board, alpha, beta, True, winning_lines, depth + 1)
            board[i][j][k] = 0
            best = min(score, best)
            beta = min(beta, best)
            if beta <= alpha:
                break
        return best

# Testcase
board = [ # We want the function to return (0, 1, 1)
        [
            [1,-1,0],
            [0,0,0],
            [0,0,1],
        ],
        [
            [0,0,0],
            [0,0,0],
            [0,0,0],
        ],
        [
            [0,0,0],
            [0,0,0],
            [0,0,0],
        ],
    ]

问题排查 #

• 胜负判断缺失平局处理：victory_check仅判断胜负，未检查棋盘是否填满的平局情况。Minimax函数没有终止平局局面的搜索，导致递归持续到棋盘完全填满，引发无限运行。
• Minimax玩家角色混淆：to_max=True分支落子-1（AI棋子），但该分支本应对应最大化AI得分的回合；to_max=False分支落子1（人类棋子），角色与落子操作的逻辑匹配错误，导致搜索逻辑混乱。
• 深度限制无评估支撑：仅用深度截断搜索但未实现局面评估函数，直接返回默认值，AI无法判断当前局面优劣，导致走法错误。
• 获胜线重复生成：generate_winning_lines中存在大量重复的获胜线，增加了胜负判断的计算量，拖慢搜索速度。

优化建议 #

1. 修复胜负判断与平局处理 #

修改victory_check，补充平局判断，确保所有终止条件都能被捕获：

def victory_check(board, winning_lines):
    p1_win = False
    p2_win = False
    n = len(board)
    for line in winning_lines:
        values = [board[x][y][z] for x, y, z in line]
        if all(v == 1 for v in values):
            p1_win = True
        elif all(v == -1 for v in values):
            p2_win = True
    if p1_win and p2_win:
        return True, 0  # 实际游戏中不会出现
    elif p1_win:
        return True, 1
    elif p2_win:
        return True, -1
    # 检查是否平局：无空位置
    if all(board[i][j][k] != 0 for i in range(n) for j in range(n) for k in range(n)):
        return True, 0
    return False, 0

2. 修正Minimax角色逻辑 #

明确to_max对应的玩家行为，确保落子与角色匹配，并添加最大深度参数：

def minimax(board, alpha, beta, to_max, winning_lines, depth, max_depth):
    terminal = victory_check(board, winning_lines)
    if terminal[0]:
        return terminal[1]
    # 达到最大深度时返回局面评估分
    if depth >= max_depth:
        return evaluate_board(board, winning_lines)
    if to_max:
        best = float('-inf')
        # to_max=True：AI回合，落子-1，最大化得分
        for i,j,k in get_possible_moves(board):
            board[i][j][k] = -1
            score = minimax(board, alpha, beta, False, winning_lines, depth + 1, max_depth)
            board[i][j][k] = 0
            best = max(score, best)
            alpha = max(alpha, best)
            if beta <= alpha:
                break
        return best
    else:
        best = float('inf')
        # to_max=False：人类回合，落子1，最小化得分
        for i,j,k in get_possible_moves(board):
            board[i][j][k] = 1
            score = minimax(board, alpha, beta, True, winning_lines, depth + 1, max_depth)
            board[i][j][k] = 0
            best = min(score, best)
            beta = min(beta, best)
            if beta <= alpha:
                break
        return best

3. 实现局面评估函数 #

当搜索达到最大深度时，通过评估潜在获胜线数量判断局面优劣：

def evaluate_board(board, winning_lines):
    ai_score = 0
    human_score = 0
    for line in winning_lines:
        values = [board[x][y][z] for x, y, z in line]
        ai_count = values.count(-1)
        human_count = values.count(1)
        empty_count = values.count(0)
        # 仅计算无对方棋子的潜在获胜线，避免无效评估
        if ai_count > 0 and human_count == 0:
            ai_score += ai_count ** 2  # 棋子越多，权重越高
        if human_count > 0 and ai_count == 0:
            human_score += human_count ** 2
    return ai_score - human_score

4. 调整最佳走法函数调用 #

传入合理的最大深度（3x3x3棋盘建议4-6，可根据性能调整）：

def best_move(board, winning_lines):
    n = len(board)
    best_score = float('-inf')
    move = (-1, -1, -1)
    max_depth = 4  # 可根据实际性能调整
    for i,j,k in get_possible_moves(board):
        board[i][j][k] = -1
        curr_score = minimax(board, float('-inf'), float('inf'), False, winning_lines, 0, max_depth)
        board[i][j][k] = 0
        if curr_score > best_score:
            move = (i,j,k)
            best_score = curr_score
    return move

5. 优化获胜线生成 #

避免重复生成获胜线，减少冗余计算：

def generate_winning_lines(n):
    winning_lines = set()
    # 三维基础线：行、列、竖线
    winning_lines.update(tuple((x, y, z) for z in range(n)) for x in range(n) for y in range(n))
    winning_lines.update(tuple((x, y, z) for y in range(n)) for x in range(n) for z in range(n))
    winning_lines.update(tuple((x, y, z) for x in range(n)) for y in range(n) for z in range(n))
    # 面对角线（三个平面）
    winning_lines.update(tuple((x, y, z) for y in range(n)) for x in range(n) if x == y for z in range(n))
    winning_lines.update(tuple((x, y, z) for y in range(n)) for x in range(n) if x + y == n-1 for z in range(n))
    winning_lines.update(tuple((x, y, z) for x in range(n)) for z in range(n) if x == z for y in range(n))
    winning_lines.update(tuple((x, y, z) for x in range(n)) for z in range(n) if x + z == n-1 for y in range(n))
    winning_lines.update(tuple((x, y, z) for y in range(n)) for z in range(n) if y == z for x in range(n))
    winning_lines.update(tuple((x, y, z) for y in range(n)) for z in range(n) if y + z == n-1 for x in range(n))
    # 空间对角线
    winning_lines.add(tuple((x, x, x) for x in range(n)))
    winning_lines.add(tuple((x, x, n-1-x) for x in range(n)))
    winning_lines.add(tuple((x, n-1-x, x) for x in range(n)))
    winning_lines.add(tuple((x, n-1-x, n-1-x) for x in range(n)))
    return winning_lines

使用时直接传入棋盘大小：

winning_lines = generate_winning_lines(3)

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