带记忆化的 Minimax:缓存键、深度与评估函数
项目代码: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 来说,着法越少越接近“无子可动即胜”,取负号恰好也合理。这是这个启发式比较巧的地方。
但它有两个明显问题:
- 不识别终局。Gopher 无子可下是输,Dodo 无子可动是赢,代码都没有显式判断,只是让
legals返回空列表、评估得到 0。0 在 Gopher 里可能被当成“比负数更好”,在 Dodo 里又刚好是最高分——同一个 0,含义完全不同。 - 视角固定为根玩家。
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补单元测试,用固定局面做回归。
相关技能
- C++
- Git