Hex棋Alpha-Beta搜索代理Queenbee评估函数：性能优化与调试求助

我为Hex棋实现了一个基于Queenbee评估函数的Alpha-Beta截断搜索代理，但函数运行存在问题。该评估函数逻辑在某论文的3.2节有描述，逻辑简单易懂。

我提供了仅计算棋盘左侧Queenbee距离的实现代码，现在有两个技术问题：

1. 函数在小棋盘尺寸下运行正常，但大棋盘计算耗时过长，如何优化计算速度？
2. 函数包含大量递归调用，调试测试难度高，在VSCode中能否跳过所有递归调用，直接返回至原调用者？

实现代码 #

def qb_distance_left(pos, d, v, qb_list):
        r, c = pos[0], pos[1]
        if c == 0: # 当前位置在棋盘左边缘，返回距离d
            return d
        if len(qb_list) >= 2:
            qb_list.pop(qb_list.index(min(qb_list)))
            m2 = qb_list.pop(qb_list.index(min(qb_list)))
            if d > m2: # 当前距离已超过找到的第二小距离，停止搜索并返回
                return d
        adjList = [(r,c-1), (r+1, c-1), (r-1, c), (r+1, c), (r-1, c+1), (r, c+1)]
        adjList = [pos for pos in adjList if pos[0] >= 0 and pos[0] < state.size and pos[1] >= 0 and pos[1] < state.size and pos not in v]
        result = []
        visited = [x for x in v]
        visited.append((r,c))
        for pos in adjList:
            if  pos not in state.board:
                result.append(qb_distance_left(pos,d+1,[x for x in visited], [x for x in result]))
            elif state.board.get(pos) == state.player:
                result.append(qb_distance_left(pos,d, [x for x in visited], [x for x in result]))
        result = [x for x in result if x != float("inf")]
        if len(result) < 2:  # 无有效Queenbee距离
            return float("inf")
        result.pop(result.index(min(result)))
        return result[result.index(min(result))]

1. 大棋盘计算速度优化方案 #

• 用集合替代列表存储访问节点：当前用列表v做已访问判断，pos not in v是O(n)复杂度，换成集合后判断速度变为O(1)。同时改用回溯法管理访问状态：递归前将当前节点加入集合，递归结束后移除，避免每次复制整个列表的开销。
• 修复剪枝逻辑：当前qb_list的传递方式错误（每次传入[x for x in result]），导致剪枝条件失效。应维护一个跟踪当前最小两个距离的变量，递归时传递该变量，当当前深度d大于第二小距离时，直接返回终止搜索。
• 添加记忆化缓存：用字典缓存已计算过的(pos, player)对应的Queenbee距离，避免重复计算相同位置的结果。
• 迭代替代递归：将递归实现改为迭代式BFS/DFS，减少递归栈的开销，同时避免大棋盘下的栈溢出风险。
• 优化邻接节点生成：根据当前位置的坐标直接生成不越界的邻接节点，减少事后过滤的步骤，提升生成效率。

2. VSCode中跳过递归调用的调试方法 #

• 条件断点+跳转返回：在递归函数第一行设置条件断点（比如初始调用时d=0，条件设为d == 0），触发断点后，右键点击调试工具栏的「返回」下拉箭头，选择「跳出所有递归」；或直接在调试控制台执行return命令强制返回。
• 设置下一语句：进入递归调用后，找到原调用者的下一行代码，右键选择「设置下一语句」，直接跳转到该位置跳过所有递归步骤。
• 临时代码修改：调试时在递归函数开头添加临时判断，非初始调用直接返回临时值，比如：

  def qb_distance_left(pos, d, v, qb_list):
      # 调试用：非初始调用直接返回
      if d != 0:
          return float("inf")
      # 原代码逻辑...
  

  调试完成后删除该临时代码即可。

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