六角国际象棋中Negamax函数选择劣化走法的原因排查

问题描述 #

基于GDScript实现的六角国际象棋Negamax函数会做出无意义弃子操作（如用骑士吃掉兵），尝试着法排序和静搜索优化后效果有限，还导致性能大幅下降。

相关代码 #

评估函数 #

func GetEvaluation(Turn, NextPositions = Positions):
    var EvaluationTable = {
        White = 0,
        Black = 0
    }
    
    for Piece in NextPositions.Main.values():
        EvaluationTable[Piece.get_parent().get_parent().name] += AIValues[Piece.get_parent().name]
    
    return EvaluationTable[Turn] - EvaluationTable[ColorTable[Turn]]

Negamax函数 #

func Negamax(NextPositions, Depth, Alpha, Beta, Turn, Started = true):
    if Depth == 0 or IsGameOver(NextPositions, Turn):
        return [GetEvaluation(Turn, NextPositions)]
    
    var MaxEvaluation = -INF
    var Data = []
    
    for Key in NextPositions[Turn].keys():
        var PlaceX = get_node("Positions").get_node(Key.left(1))
        var PlaceY = PlaceX.get_node(Key.right(-1))
        var NewPositions = GetPosition(PlaceX, PlaceY, NextPositions)
        
        for Select in NewPositions:
            if Select:
                var CreatePos = CreatePosition(Select, NextPositions[Turn][Key], NextPositions)
                var EvaluationTable = Negamax(CreatePos, Depth - 1, -Alpha, -Beta, ColorTable[Turn], false)
                var Evaluation = -EvaluationTable[0]
                
                if Evaluation >= Beta:
                    return [Evaluation]
                
                if Evaluation > MaxEvaluation:
                    MaxEvaluation = Evaluation
                    Alpha = max(Alpha, Evaluation)
                    
                    if Started:
                        Data = [PlaceX, PlaceY, Select.get_parent(), Select]
    
    return [MaxEvaluation, Data]

代码问题分析 #

1. 评估函数的局限性 #

• 仅计算基础棋子价值，忽略位置与动态收益：当前评估仅累加双方所有棋子的固定价值，没有考虑棋子在六角棋盘上的位置价值（比如中心位置的棋子价值更高），也没有针对吃子等动态操作的即时收益做加权。例如骑士吃兵的走法，评估仅计算“己方骑士价值保留+对方兵价值移除”的静态差，完全没考虑骑士后续被吃的风险，导致AI短视做出弃子决策。
• 局面状态依赖存疑：如果CreatePosition函数未正确深拷贝局面（比如仅浅拷贝字典），会导致评估时引用了被修改的原局面数据，出现错误的价值计算。

2. Negamax搜索逻辑的缺陷 #

• 缺乏静搜索（Quiescence Search）：当搜索深度耗尽（Depth == 0）时直接返回静态评估，无法覆盖“吃子-反吃子”这类短链操作。AI看不到骑士吃兵后被反吃的后续损失，误判为收益走法。
• 无有效着法排序：当前代码未对生成的走法做优先级排序（如先搜索高价值吃子、将军走法），导致alpha-beta剪枝效率极低，性能下降。若之前的着法排序逻辑错误（比如排序规则不符合剪枝需求），反而会加剧性能问题。
• Alpha-Beta剪枝的潜在问题：需确认初始调用时Alpha和Beta是否设为-INF和INF；递归时的参数传递虽符合Negamax规则，但需验证剪枝触发后是否正确终止当前分支的搜索。
• 局面拷贝的正确性：CreatePosition若未实现深拷贝，递归过程中修改的局面会污染上层搜索的原始数据，导致评估结果混乱。

修复建议 #

优化评估函数 #

• 加入位置价值表：为六角棋盘的每个格子定义不同棋子的位置权重，比如中心格子的骑士额外加0.5价值，边缘格子减0.2价值，让AI优先选择更安全的位置。
• 确保吃子后的局面正确统计：验证CreatePosition在吃子时会移除被吃棋子，评估函数能准确计算双方剩余棋子的价值总和。
• 增加动态收益权重：在评估中对吃子走法的即时价值做临时加权（比如吃子的价值差乘以1.2），让AI优先考虑收益明确的走法。

完善Negamax搜索逻辑 #

• 实现静搜索：修改终止条件，当Depth == 0时，不直接返回评估，而是继续搜索所有吃子、将军等“有价值变化”的走法，直到局面平静（无吃子操作）。示例逻辑：

  func QuiescenceSearch(NextPositions, Alpha, Beta, Turn):
      var eval = GetEvaluation(Turn, NextPositions)
      if eval >= Beta:
          return Beta
      Alpha = max(Alpha, eval)
      # 生成所有吃子走法
      var captures = GenerateCaptureMoves(NextPositions, Turn)
      for capture in captures:
          var newPos = CreatePosition(capture...)
          var score = -QuiescenceSearch(newPos, -Beta, -Alpha, ColorTable[Turn])
          if score >= Beta:
              return Beta
          Alpha = max(Alpha, score)
      return Alpha
  

  然后在Negamax的终止条件中替换为：

  if Depth == 0:
      return [QuiescenceSearch(NextPositions, Alpha, Beta, Turn)]
  

• 加入着法排序：生成走法后，按“高价值吃子>将军>威胁走法>普通走法”的优先级排序。比如对每个走法计算得分：吃子走法的得分是被吃棋子价值 - 己方棋子价值（若为兑子则计算净收益），将军走法加固定高分，普通走法按位置价值排序。排序后优先搜索高分走法，触发更多alpha-beta剪枝，提升性能。
• 验证局面深拷贝：在CreatePosition中对NextPositions的所有嵌套字典和对象进行深拷贝，比如GDScript中可手动遍历字典的每个键值对，复制嵌套结构：

  func DeepCopyPosition(pos):
      var newPos = {
          Main = {},
          White = {},
          Black = {}
      }
      # 复制Main字典
      for key in pos.Main:
          newPos.Main[key] = pos.Main[key] # 若Piece是对象，需复制对象属性
      # 复制White和Black字典
      for key in pos.White:
          newPos.White[key] = pos.White[key]
      for key in pos.Black:
          newPos.Black[key] = pos.Black[key]
      return newPos
  

• 调试Alpha-Beta剪枝：打印每个分支的Alpha、Beta和评估值，确认剪枝触发时机是否正确，避免漏剪或误剪。

调试步骤 #

• 打印AI选择的走法及其评估值，对比其他可行走法的评估结果，确认是否因评估值计算错误导致AI选择弃子。
• 逐步增加搜索深度，观察AI行为是否改善，判断是否为深度不足导致的短视问题。
• 检查IsGameOver函数是否正确识别将死、和棋等状态，避免提前终止搜索。

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