项目代码:https://github.com/yicongl1/Gopher-and-Dodo

棋盘和合法着法定义好之后,剩下的就是“选哪一步”。IA02 项目里我用的是 Minimax + 记忆化,没有 alpha-beta。这篇记录搜索的结构、缓存键的设计,以及评估函数留下的问题。

搜索骨架

Minimax 本身很标准:最大化层取己方着法的最大值,最小化层取对手着法的最小值,深度到 0 时调用评估函数。

def minmax(state, depth, maximizing_player, player, hex_size, game):
    if depth == 0:
        return evaluation(state, player, game, hex_size)

    opponent = player_opponent(player)

    if maximizing_player:
        return max(
            minmax(apply_action(state, a, player, game),
                   depth - 1, False, player, hex_size, game)
            for a in legals(state, player, hex_size, game)
        )
    else:
        return min(
            minmax(apply_action(state, a, opponent, game),
                   depth - 1, True, player, hex_size, game)
            for a in legals(state, opponent, hex_size, game)
        )

根节点不在 minmax 里,而是单独一层:

for action in legals(state, player, hex_size, game):
    new_state = apply_action(state, action, player, game)
    eval = minmax(new_state, 4, False, player, hex_size, game)
    if eval >= max_eval:
        max_eval = eval
        best_action = action

所以实际搜索是“根着法 + 4 层”,共 5 个半回合。time_left 参数目前没有参与任何决策——这是一个明确的待改进点。

缓存键里为什么要放深度

记忆化用装饰器实现:

def memoize(f):
    cache = {}

    def memoized_minmax(state, depth, maximizing_player, player, hex_size, game):
        state_key = tuple((cell, p) for cell, p in state)
        key = (state_key, depth, maximizing_player, player, hex_size, game)

        if key in cache:
            return cache[key]

        val = f(state, depth, maximizing_player, player, hex_size, game)
        cache[key] = val
        return val

    return memoized_minmax

键里不能只有棋盘。同一个局面在不同深度下的值不同(深度 1 是“再看一步”,深度 4 是“再看四步”),所以 depth 必须进键;maximizing_player 决定当前层取 max 还是 min,也必须进;player 是根玩家,决定了评估函数的视角。

还有一个容易忽略的点:state_key 保留了 state 列表的顺序。同一组棋子如果服务器给出的顺序不同,键就不同,缓存会 miss。更稳的做法是先排序:

state_key = tuple(sorted(state))

代价是每次都要排序,但缓存命中率会更高。

评估函数:机动性,以及它的两个问题

当前评估只看“自己还有多少合法着法”:

return -len(legals(state, player, hex_size, game))

对 Gopher 来说,着法越少越接近输,所以取负号合理。对 Dodo 来说,着法越少越接近“无子可动即胜”,取负号恰好也合理。这是这个启发式比较巧的地方。

但它有两个明显问题:

  1. 不识别终局。Gopher 无子可下是输,Dodo 无子可动是赢,代码都没有显式判断,只是让 legals 返回空列表、评估得到 0。0 在 Gopher 里可能被当成“比负数更好”,在 Dodo 里又刚好是最高分——同一个 0,含义完全不同。
  2. 视角固定为根玩家。evaluation(state, player, ...) 里的 player 始终是根玩家,即使当前节点轮到对手走,数的也是根玩家的着法。严格来说,评估应该在每个节点从“当前轮到谁”的角度出发,再在递归里翻转符号。

这两点我在 README 的“已知限制”里都写明了。它们不影响“能下完一局”,但会影响棋力上限。

为什么最后没用 alpha-beta

仓库早期版本实现过 alpha-beta 剪枝。README 里留了一句历史说明:作者对比后发现,带记忆化的普通 Minimax 胜率更好,所以比赛版本用了现在这套。

这个结论要谨慎看待。一般来说,alpha-beta + 好的着法排序 + 置换表会比纯 Minimax 强;如果当时的 alpha-beta 实现有 bug、或者着法顺序很差,确实可能打不过记忆化版本。更稳妥的做法是:

  • 用同一组固定局面做基准测试,而不是只看几局比赛的胜负;
  • 记录每个版本的搜索节点数、耗时和胜率;
  • 再决定保留哪个。

这也是我后来做 MPPT 项目时得到的同一个教训:先固定评价指标,再比较算法。

性能量级

在本机(Windows 11 / Python 3.14)上的粗略测量:

  • Dodo 4×4 初始局面走一步(depth 4)约 4.5 秒;
  • Gopher 4×4 对随机对手完整一局约 1.7 秒;
  • 6×6 的分支因子更大,固定 depth 4 有明显超时风险。

慢的根源不只是搜索,而是 legals:它对每个棋子、每个方向都用 (cell, player) in state 线性扫描,整体接近 O(n⁴)。把状态换成 dict[(x, y)] = player 之后,同样的深度会快一个量级。

如果重做

  • 状态改字典 + 棋子集合,先把 legals 降下来;
  • 评估加入终局判断、连通性和推进距离;
  • 按剩余时间动态调整深度;
  • 缓存加上限,或改成按对局清空;
  • 给 legals / apply_action 补单元测试,用固定局面做回归。

仓库:https://github.com/yicongl1/Gopher-and-Dodo