五子棋 minimax 的置换表命中率仅 1%～4%，该如何排查？

结论：先检查缓存是否正确，再判断命中率是否偏低

仅凭 1%～4% 的命中率，无法认定置换表实现有错。命中率取决于搜索深度、候选落子的生成方式、剪枝方式、表的保留时间，以及你如何统计“命中”。目前没有完整的搜索函数和统计代码，无法确定这个比例的具体原因。

给出的代码中有两个需要处理的问题：

• get_initial_hash() 调用 update_hash() 时漏传了 current_hash，也没有将累积值 h 传入计算。
• 置换表只保存 (depth, value)，却把所有缓存分数都当作精确值直接返回。对于发生 alpha-beta 截断的搜索，这可能导致返回错误结果。

还需要确认缓存键是否完整描述局面，以及落子、撤销和搜索深度的含义是否一致。

1. 修正初始 Zobrist 哈希计算

原代码中的调用是：

h = update_hash(piece, r, c)

但函数需要四个参数：

def update_hash(player, row, col, current_hash):

按照所贴代码，只要初始棋盘上有棋子，就会因缺少参数而触发 TypeError。如果一直从空棋盘开始，这条分支不会执行，错误可能暂时不会出现。

初始哈希需要从 0 开始，依次异或所有已落棋子对应的随机数：

def update_hash(player, row, col, current_hash):
    p_idx = 1 if player == 'X' else 2
    return current_hash ^ zobrist_table[row][col][p_idx]


def get_initial_hash(grid):
    h = 0
    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = grid[r][c]
            if piece != ' ':
                h = update_hash(piece, r, c, h)
    return h

这里沿用原程序的约定：棋子只有 'X'、'O'，空格表示空位，棋盘大小与 BOARD_SIZE 一致。

落子和撤销时对同一个随机数各异或一次，是正确的增量更新方式，因为：

(h ^ x) ^ x = h

不为空位分配哈希贡献也没有问题。当前随机数表的索引 0 没有使用，只是多生成了一组随机数，不会因此降低命中率。

2. 验证哈希是否真正对应棋盘

先检查两个性质：增量哈希应等于完整重算的哈希；撤销落子后，哈希应恢复原值。

可以用下面的方式检查，假定 move 是合法的空位落子：

before_hash = board.current_hash
assert before_hash == get_initial_hash(board.grid)

assert board.set_move(move, 'X')
assert board.current_hash == get_initial_hash(board.grid)

board.undo_move(move)
assert board.current_hash == before_hash
assert board.current_hash == get_initial_hash(board.grid)

还应使用两组不同的合法落子顺序构造完全相同的棋盘，确认最终哈希一致。Zobrist hashing 使用异或，最终结果应只取决于棋子的位置和颜色。

这些断言只能检查哈希更新是否自洽，不能证明整个搜索算法正确。调试时还需要确认每条递归返回路径都执行了对应的 undo_move()，包括发生剪枝的路径。

zobrist_table 应在置换表使用期间保持不变。如果重新生成随机数表，就不能继续沿用已有的棋盘哈希和缓存条目。

3. 缓存键应包含影响搜索结果的状态

当前键只有：

state_key = board.current_hash

通常建议把下一步行棋方也放入键中：

state_key = (board.current_hash, player_to_move)

如果搜索始终从固定先手、严格交替的合法局面出发，行棋方可能已经由棋子数量确定。但显式记录行棋方，可以避免在自定义局面或不同搜索入口之间错误复用缓存。

分数的含义也要统一。例如，可以始终让正分表示对 'X' 有利；如果使用 negamax，则可以约定分数始终相对于当前行棋方。保存和读取时必须遵循同一种约定。

如果候选落子生成依赖“最后一步落在哪里”等历史信息，同一棋盘也可能得到不同的搜索分支。此时需要检查这些历史信息是否确实属于搜索状态，或者候选落子能否改为由当前局面确定。

4. alpha-beta 的缓存需要区分精确值和边界

这是当前置换表中更重要的正确性问题。alpha-beta 截断时，搜索可能还没有遍历完所有候选落子。返回的分数有时只能说明真实搜索值不小于某个值，或者不大于某个值，不能统一作为精确值使用。

常见条目包含：

(depth, score, flag)

其中 flag 分为：

• EXACT：精确值，可以直接复用。
• LOWERBOUND：下界；当 score >= beta 时，可以直接截断。
• UPPERBOUND：上界；当 score <= alpha 时，可以直接截断。

以下示例采用较容易核对的方式：缓存边界满足截断条件时直接返回，否则继续搜索，不用缓存收窄窗口。

搜索入口查询缓存

EXACT = 'EXACT'
LOWERBOUND = 'LOWERBOUND'
UPPERBOUND = 'UPPERBOUND'

# depth 表示当前节点还需要搜索的剩余深度。
state_key = (board.current_hash, player_to_move)
alpha_orig = alpha
beta_orig = beta

entry = transposition_table.get(state_key)
if entry is not None:
    cached_depth, cached_score, flag = entry

    if cached_depth >= depth:
        if flag == EXACT:
            return cached_score
        if flag == LOWERBOUND and cached_score >= beta:
            return cached_score
        if flag == UPPERBOUND and cached_score <= alpha:
            return cached_score

搜索结束后保存条目

下面的代码应放在当前节点的候选落子搜索结束后，包括通过 break 结束的剪枝分支。value 是该节点得到的分数，alpha_orig、beta_orig 是入口保存的窗口：

if value <= alpha_orig:
    flag = UPPERBOUND
elif value >= beta_orig:
    flag = LOWERBOUND
else:
    flag = EXACT

old_entry = transposition_table.get(state_key)
if old_entry is None or depth >= old_entry[0]:
    transposition_table[state_key] = (depth, value, flag)

return value

这段保存逻辑可以避免较浅的结果直接覆盖较深的结果。如果搜索在截断处直接 return，就需要在返回前保存条目，或统一处理出口。

以上片段假定使用普通 alpha-beta 搜索，且当前节点确实完成了计划中的搜索。因超时或取消而中断的结果，不能直接按相同规则标记为有效条目。

5. 确认 depth 的含义

条件：

cached_depth >= depth

通常要求 depth 表示剩余搜索深度，而不是从根节点走了多少层。如果两者混用，就会错误判断缓存是否足够深入。

复用更深条目是博弈搜索中的常见做法，但不同深度的截断评估不保证得到相同分数。如果你正在严格比较“固定深度下，有缓存和无缓存的结果是否一致”，可以先只复用 cached_depth == depth 的条目，排除深度差异的影响。

6. 把命中率拆开统计

建议至少记录以下计数：

对应比例分别是：

键命中率 = key_hits / probes
深度可用率 = depth_hits / probes
直接复用率 = returns / probes

如果你统计的 1%～4% 实际是 returns / probes，并不表示其余查询都没有找到相同棋盘。条目可能存在，只是深度不足，或者其边界不能用于当前窗口。

命中率较低还可能与以下条件有关：

• 搜索较浅，尚未出现足够多的不同落子顺序汇合到同一局面。
• 剪枝和候选落子限制改变了实际访问的节点集合。
• 置换表在递归调用中反复清空，或生命周期过短。
• 大量叶节点被查询，却没有保存结果。
• 期待旋转、镜像棋盘也能命中，但尚未实现对称局面归一化。普通 Zobrist hashing 不会自动合并这些局面。

完成正确性检查后，再用相同局面和搜索设置，比较启用和禁用置换表时的节点数与耗时。判断置换表是否有效，应结合这些结果，不能只看一个命中百分比。

备注：内容仅供参考。