Hex游戏AI评估：递归距离函数实现问题排查

问题背景 #

开发基于Alpha-Beta剪枝的Hex游戏AI时，棋盘状态评估模块依赖递归定义的距离函数d(u,v)。该函数的动态邻域N(u)包含己方连通链的空邻接格、虚拟节点等，完全遵循论文给定的递归逻辑实现，但实际计算结果与预期不符：测试场景中d('top',(4,1))的预期值为6，现有代码输出异常，需定位递归逻辑中的问题。

关键排查方向 #

• 终止条件校验：严格核对论文定义的终止规则，确认当u == v时是否直接返回0，虚拟节点（如'top'）的特殊终止逻辑是否正确落地。
• 动态邻域N(u)的准确性：检查邻域生成逻辑，确保仅包含己方连通链的空邻接格，未错误纳入敌方棋子格；同时验证虚拟节点的邻域范围是否符合论文设定。
• 递归去重机制：确认是否通过备忘录（Memoization）记录已计算的d(u,v)值，避免重复访问同一节点导致的无限递归或距离累计错误。
• 距离计算逻辑：验证递归时的距离累加规则是否为1 + min(d(n, v))（其中n ∈ N(u)），是否存在max/min逻辑混淆或累加值错误。
• 测试场景手动推导：针对d('top',(4,1))的测试用例，手动推导每一步递归的邻域节点和距离计算过程，对比代码执行的中间结果，定位差异点。

代码排查重点 #

若提供d(u,v)的核心实现代码，可聚焦以下几点：

• 备忘录字典的键是否统一存储(u,v)对（注意虚拟节点与坐标节点的格式一致性）
• 邻域生成函数中“己方连通链的空邻接格”的判断逻辑，是否正确关联当前棋盘的己方棋子位置
• 递归调用时是否正确传递实时棋盘状态参数（若邻域依赖动态棋盘状态）

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