用Go写一个中国象棋（十五）| 置换表
在下棋的过程中，我们发现每走一步，AI都需要生成所有走法，导致AI下棋速度很慢，我们可以加入置换表来解决这个问题。
置换表
象棋的搜索树可以用图来表示，而置换结点可以引向以前搜索过的子树上。置换表可以用来检测这种情况，从而避免重复劳动。
例如，一层的搜索显示“1. 51”是最好的落子法，那么在做两层的搜索时你先搜索“1. 51”。如果返回“1. 51 67”，那么你在做三层的搜索时仍旧先搜索这条路线。这样做之所以有好的效果，是因为第一次搜索的线路通常是好的，而Alpha-Beta对落子法的顺序特别敏感。
如果“1.51 2.67”以后的局面已经搜索过了，那就没有必要再搜索“1.51 2.67”以后的局面了。省去重复的工作，这是置换表的一大特色。
但是在一般的中局局面里，置换表的另一个作用更为重要。每个散列项里都有局面中最好的落子法，首先搜索好的落子法可以大幅度提高搜索效率。因此如果在散列项里找到最好的落子法，那么首先搜索这个落子法，就会改进落子法顺序，减少分枝因子，从而在短的时间内搜索得更深。
define.go
//HashSize 置换表大小
const HashSize = 1 << 20
//HashAlpha ALPHA节点的置换表项
const HashAlpha = 1
//HashBeta BETA节点的置换表项
const HashBeta = 2
//HashPV PV节点的置换表项
const HashPV = 3HashItem结构体
打开rule.go，增加HashItem：
//HashItem 置换表项结构
type HashItem struct {
ucDepth int //深度
ucFlag int //标志
svl int //分值
wmv int //最佳走法
dwLock0 uint32 //校验码
dwLock1 uint32 //校验码
wReserved int //保留
}置换表非常简单，以局面的 Zobrist Key % HashSize 作为索引值。每个置换表项存储的内容：ucDepth深度，ucFlag标志，svl分值，wmv最佳走法，dwLock0和dwLock1校验码。
Search结构体
修改Search结构体，增加mvKillers和hashTable：
//Search 与搜索有关的全局变量
type Search struct {
mvResult int // 电脑走的棋
nHistoryTable [65536]int // 历史表
mvKillers [LimitDepth][2]int // 杀手走法表
hashTable [HashSize]*HashItem // 置换表
}mvKillers保存兄弟节点中产生Beta截断的走法。杀手走法产生截断的可能性极大，兄弟节点中的走法未必在当前节点下能走，所以在尝试杀手走法以前先要对它进行走法合理性的判断。
之前我们写过 LegalMove 这个函数，如果杀手走法确实产生截断了，那么后面耗时更多的 generateMove 就可以不用执行了。
我们可以把距离根节点的步数(nDistance)作为索引值，构造一个杀手走法表。每个杀手走法表项存有两个杀手走法，走法一比走法二优先：存一个走法时，走法二被走法一替换，走法一被新走法替换；取走法时，先取走法一，后取走法二。
PositionStruct方法
如何利用置换表信息：
(1) 检查局面所对应的置换表项，如果Zobrist Lock校验码匹配，那么我们就认为命中(Hit)了。
(2) 是否能直接利用置换表中的结果，取决于两个因素：A. 深度是否达到要求，B. 非PV节点还需要考虑边界。
第二种情况是最好的(完全利用)，ProbeHash返回一个非-MATE_VALUE的值，这样就能不对该节点进行展开了。
如果仅仅符合第一种情况，那么该置换表项的信息仍旧是有意义的——它的最佳走法给了我们一定的启发(部分利用)。
//probeHash 提取置换表项
func (p *PositionStruct) probeHash(vlAlpha, vlBeta, nDepth int) (int, int) {
hsh := p.search.hashTable[p.zobr.dwKey&(HashSize-1)]
if hsh.dwLock0 != p.zobr.dwLock0 || hsh.dwLock1 != p.zobr.dwLock1 {
return -MateValue, 0
}
mv := hsh.wmv
bMate := false
if hsh.svl > WinValue {
hsh.svl -= p.nDistance
bMate = true
} else if hsh.svl < -WinValue {
hsh.svl += p.nDistance
bMate = true
}
if hsh.ucDepth >= nDepth || bMate {
if hsh.ucFlag == HashBeta {
if hsh.svl >= vlBeta {
return hsh.svl, mv
}
return -MateValue, mv
} else if hsh.ucFlag == HashAlpha {
if hsh.svl <= vlAlpha {
return hsh.svl, mv
}
return -MateValue, mv
}
return hsh.svl, mv
}
return -MateValue, mv
}RecordHash采用深度优先的替换策略，在判断深度后，将 Hash 表项中的每个值填上：
//RecordHash 保存置换表项
func (p *PositionStruct) RecordHash(nFlag, vl, nDepth, mv int) {
hsh := p.search.hashTable[p.zobr.dwKey&(HashSize-1)]
if hsh.ucDepth > nDepth {
return
}
hsh.ucFlag = nFlag
hsh.ucDepth = nDepth
if vl > WinValue {
hsh.svl = vl + p.nDistance
} else if vl < -WinValue {
hsh.svl = vl - p.nDistance
} else {
hsh.svl = vl
}
hsh.wmv = mv
hsh.dwLock0 = p.zobr.dwLock0
hsh.dwLock1 = p.zobr.dwLock1
p.search.hashTable[p.zobr.dwKey&(HashSize-1)] = hsh
}在下一节中，我们将学习如何使用置换表对走法进行排序？
