Transposition table导致算法运行变慢，是否为实现方式有误？

你当前采用std::vector存储Zobrist键对应置换条目的方案，本质是用线性结构做键值查询，两种现有实现的时间复杂度都无法满足深搜场景下的性能需求：

• 全遍历查询的时间复杂度为O(n)，存储条目数随搜索深度上升后，查询耗时会线性增长，自然会出现重算比查询更快的情况
• 有序vector+二分查找的方案虽然将查询复杂度降到了O(log n)，但插入有序vector需要移动大量元素，插入复杂度为O(n)，高频插入场景下开销依然很高

1 更换为哈希结构存储置换表 #

Zobrist键本身就是设计用于哈希索引的特征值，直接用哈希结构存储可以把查询、插入的平均时间复杂度降到O(1)，有两种实现可选：

• 直接调用标准库实现：使用std::unordered_map<uint64_t, TranspositionEntry>，Zobrist键作为哈希表的key，直接调用原生的find、insert接口即可，无需自己实现排序、查找逻辑
• 自定义开地址哈希表（性能更高）：
  • 预设固定大小的数组作为哈希槽，建议大小取2的幂次，例如2^20（约100万条，匹配你之前预留的空间大小）
  • 取Zobrist键的低N位（N为数组大小的对数，2^20对应N=20）直接作为槽位索引
  • 哈希冲突时采用线性探测/二次探测查找空闲槽位
  • 无需无限扩容，固定大小的表即可满足绝大多数棋类搜索的需求

2 配置合理的置换淘汰策略 #

深搜场景下不需要存储所有历史局面，大部分浅搜生成的旧条目对后续深搜没有参考价值，建议给每个置换条目增加如下元信息，配合淘汰策略降低冲突率：

• 该条目对应的搜索深度
• 该条目的值类型（精确值/alpha边界值/beta边界值）
  槽位冲突时，优先保留深度更高、值类型优先级更高的条目，直接淘汰低优先级条目即可，不需要全量保留所有数据

额外优化点 #

你已经实现了Zobrist键的增量更新，可以在存储时仅保存Zobrist键的高位（比如低20位作为槽位索引的场景下，仅存高44位），查询时仅对比高位即可确认条目是否匹配，进一步降低查询时的比对开销。

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