【文件属性】：
文件名称：置换表替换策略-it安全隐患排查系统
文件大小：3.75MB
文件格式：PDF
更新时间：2021-06-18 06:54:19
博弈 搜索算法 博弈树
同，而这个 64 位的校验值就可作为标签来区分每个局
面。虽然 64 位的校验值理论上仍然可能存在冲突，但
实战中这种情况非常罕见，因此可以忽略[7]。
4.2 置换表替换策略
我们利用Zobrist 哈希方法让每一个局面在置换表中
对应唯一的位置，但并不保证置换表中每一个位置对应唯
一的局面，这样虽然将每一个局面都对应到置换表中，但
却经常发生两个不同局面映射到同一位置而发生冲突的问
题。如果向置换表中存储节点时发生了冲突，是否应该覆
盖原来的项？对于这个问题有以下解决方案：(1)始终替换
的方式[9]，即简单地覆盖已经存在的值。(2)同样深度或更
深时替换的方式[9]，除非新局面的深度大于或等于哈希表
中已有的值，否则保留已经存在的节点。(3)双层存储方式
[10]，如果待置入节点的深度大于等于置换表第1 层节点存
储的深度，将当前第1 层存储内容移至第2 层，第1 层存
储写入待置入节点信息，否则，将待置入节点信息写入第
2 层中存储。(4)多层存储方式，一个 m 层的置换表有 n
个哈希位置，每个哈希位置记录m个局面，那么整个置换
表可记录m×n个局面信息。记录一个局面时，找到它对
应的哈希位置中的m个局面，不考虑该局面本身的搜索深
度，而直接覆盖深度最小的那个局面。
4.3 置换表与α-β剪枝的结合
如前所述，在α-β剪枝中，一个节点会出现 fail
high、fail low 和 exact 三种情况之一。一般只有
exact 型才可作为当前节点的准确值存入置换表中，
但 fail high、fail low 所对应的边界值仍可帮助我们
/ 2
( 1) / 2 ( 1) / 2
2 1 (
1 (
d
d
d d
d
b d
b d
N
N b
为偶数)
为奇数)