用Go写一个中国象棋（十六）| 置换表
当我们有了置换表之后，就可以用多种方式来优化走法顺序。
优化走法顺序
在之前我们只用历史表作优化，从现在开始采用多种优化方式：
(1) 如果置换表中有过该局面的数据，但无法完全利用，那么多数情况下它是浅一层搜索中产生截断的走法，我们可以首先尝试它。
(2) 然后是两个杀手走法(如果其中某个杀手走法与置换表走法一样，那么可以跳过)。
(3) 然后生成全部走法，按历史表排序，再依次搜索(可以排除置换表走法和两个杀手走法)。
define.go
//走法排序阶段
const (
PhaseHash = 0
PhaseKiller1 = 1
PhaseKiller2 = 2
PhaseGenMoves = 3
PhaseRest = 4
)SortStruct结构体
打开rule.go，增加：
//SortStruct 走法排序结构
type SortStruct struct {
mvHash int //置换表走法
mvKiller1 int //杀手走法
mvKiller2 int //杀手走法
nPhase int //当前阶段
nIndex int // 当前采用第几个走法
nGenMoves int // 总共有几个走法
mvs []int // 所有的走法
}PositionStruct方法
增加initSort和nextSort方法：
//initSort 初始化，设定置换表走法和两个杀手走法
func (p *PositionStruct) initSort(mvHash int, s *SortStruct) {
if s == nil {
return
}
s.mvHash = mvHash
s.mvKiller1 = p.search.mvKillers[p.nDistance][0]
s.mvKiller2 = p.search.mvKillers[p.nDistance][1]
s.nPhase = PhaseHash
}
//nextSort 得到下一个走法
func (p *PositionStruct) nextSort(s *SortStruct) int {
if s == nil {
return 0
}
switch s.nPhase {
case PhaseHash:
//置换表着法启发，完成后立即进入下一阶段；
s.nPhase = PhaseKiller1
if s.mvHash != 0 {
return s.mvHash
}
fallthrough
case PhaseKiller1:
//杀手着法启发(第一个杀手着法)，完成后立即进入下一阶段；
s.nPhase = PhaseKiller2
if s.mvKiller1 != s.mvHash && s.mvKiller1 != 0 && p.legalMove(s.mvKiller1) {
return s.mvKiller1
}
fallthrough
case PhaseKiller2:
//杀手着法启发(第二个杀手着法)，完成后立即进入下一阶段；
s.nPhase = PhaseGenMoves
if s.mvKiller2 != s.mvHash && s.mvKiller2 != 0 && p.legalMove(s.mvKiller2) {
return s.mvKiller2
}
fallthrough
case PhaseGenMoves:
//生成所有着法，完成后立即进入下一阶段；
s.nPhase = PhaseRest
s.nGenMoves = p.generateMoves(s.mvs, false)
s.mvs = s.mvs[:s.nGenMoves]
sort.Slice(s.mvs, func(a, b int) bool {
return p.search.nHistoryTable[a] > p.search.nHistoryTable[b]
})
s.nIndex = 0
fallthrough
case PhaseRest:
//对剩余着法做历史表启发；
for s.nIndex < s.nGenMoves {
mv := s.mvs[s.nIndex]
s.nIndex++
if mv != s.mvHash && mv != s.mvKiller1 && mv != s.mvKiller2 {
return mv
}
}
default:
// 5. 没有着法了，返回零。
}
return 0
}
//setBestMove 对最佳走法的处理
func (p *PositionStruct) setBestMove(mv, nDepth int) {
p.search.nHistoryTable[mv] += nDepth * nDepth
if p.search.mvKillers[p.nDistance][0] != mv {
p.search.mvKillers[p.nDistance][1] = p.search.mvKillers[p.nDistance][0]
p.search.mvKillers[p.nDistance][0] = mv
}
}修改NewPositionStruct，增加hashTable初始化：
//NewPositionStruct 初始化棋局
func NewPositionStruct() *PositionStruct {
p := &PositionStruct{
zobr: &ZobristStruct{
dwKey: 0,
dwLock0: 0,
dwLock1: 0,
},
zobrist: &Zobrist{
Player: &ZobristStruct{
dwKey: 0,
dwLock0: 0,
dwLock1: 0,
},
},
search: &Search{},
}
if p == nil {
return nil
}
for i := 0; i < MaxMoves; i++ {
tmpMoveStruct := &MoveStruct{}
p.mvsList[i] = tmpMoveStruct
}
for i := 0; i < HashSize; i++ {
p.search.hashTable[i] = &HashItem{}
}
p.zobrist.initZobrist()
return p
}searchFull
修改searchFull，使用nextSort来返回走法列表：
//searchFull 超出边界(Fail-Soft)的Alpha-Beta搜索过程
func (p *PositionStruct) searchFull(vlAlpha, vlBeta, nDepth int, bNoNull bool) int {
vl, mvHash := 0, 0
if p.nDistance > 0 {
//到达水平线，则调用静态搜索(注意：由于空步裁剪，深度可能小于零)
if nDepth <= 0 {
return p.searchQuiesc(vlAlpha, vlBeta)
}
//检查重复局面(注意：不要在根节点检查，否则就没有走法了)
vl = p.repStatus(1)
if vl != 0 {
return p.repValue(vl)
}
//到达极限深度就返回局面评价
if p.nDistance == LimitDepth {
return p.evaluate()
}
//尝试置换表裁剪，并得到置换表走法
vl, mvHash = p.probeHash(vlAlpha, vlBeta, nDepth)
if vl > -MateValue {
return vl
}
//尝试空步裁剪(根节点的Beta值是"MateValue"，所以不可能发生空步裁剪)
if !bNoNull && !p.inCheck() && p.nullOkay() {
p.nullMove()
vl = -p.searchFull(-vlBeta, 1-vlBeta, nDepth-NullDepth-1, true)
p.undoNullMove()
if vl >= vlBeta {
return vl
}
}
} else {
mvHash = 0
}
//初始化最佳值和最佳走法
nHashFlag := HashAlpha
//是否一个走法都没走过(杀棋)
vlBest := -MateValue
//是否搜索到了Beta走法或PV走法，以便保存到历史表
mvBest := 0
//初始化走法排序结构
tmpSort := &SortStruct{
mvs: make([]int, MaxGenMoves),
}
p.initSort(mvHash, tmpSort)
//逐一走这些走法，并进行递归
for mv := p.nextSort(tmpSort); mv != 0; mv = p.nextSort(tmpSort) {
if p.makeMove(mv) {
// 将军延伸
if p.inCheck() {
vl = -p.searchFull(-vlBeta, -vlAlpha, nDepth, false)
} else {
vl = -p.searchFull(-vlBeta, -vlAlpha, nDepth-1, false)
}
p.undoMakeMove()
//进行Alpha-Beta大小判断和截断
if vl > vlBest {
//找到最佳值(但不能确定是Alpha、PV还是Beta走法)
vlBest = vl
//vlBest就是目前要返回的最佳值，可能超出Alpha-Beta边界
if vl >= vlBeta {
//找到一个Beta走法, Beta走法要保存到历史表, 然后截断
nHashFlag = HashBeta
mvBest = mv
break
}
if vl > vlAlpha {
//找到一个PV走法，PV走法要保存到历史表，缩小Alpha-Beta边界
nHashFlag = HashPV
mvBest = mv
vlAlpha = vl
}
}
}
}
//所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到历史表，返回最佳值
if vlBest == -MateValue {
//如果是杀棋，就根据杀棋步数给出评价
return p.nDistance - MateValue
}
//记录到置换表
p.RecordHash(nHashFlag, vlBest, nDepth, mvBest)
if mvBest != 0 {
p.setBestMove(mvBest, nDepth)
if p.nDistance == 0 {
//如果不是Alpha走法，就将最佳走法保存到历史表
p.search.mvResult = mvBest
}
}
return vlBest
}searchMain
修改searchMain，增加对置换表和杀手走法表的清空处理：
//searchMain 迭代加深搜索过程
func (p *PositionStruct) searchMain() {
// 清空历史表
for i := 0; i < 65536; i++ {
p.search.nHistoryTable[i] = 0
}
// 清空杀手走法表
for i := 0; i < LimitDepth; i++ {
for j := 0; j < 2; j++ {
p.search.mvKillers[i][j] = 0
}
}
// 清空置换表
for i := 0; i < HashSize; i++ {
p.search.hashTable[i].ucDepth = 0
p.search.hashTable[i].ucFlag = 0
p.search.hashTable[i].svl = 0
p.search.hashTable[i].wmv = 0
p.search.hashTable[i].wReserved = 0
p.search.hashTable[i].dwLock0 = 0
p.search.hashTable[i].dwLock1 = 0
}
// 初始化定时器
start := time.Now()
// 初始步数
p.nDistance = 0
// 迭代加深过程
vl := 0
rand.Seed(time.Now().UnixNano())
for i := 1; i <= LimitDepth; i++ {
vl = p.searchFull(-MateValue, MateValue, i, false)
// 搜索到杀棋，就终止搜索
if vl > WinValue || vl < -WinValue {
break
}
// 超过一秒，就终止搜索
if time.Now().Sub(start).Milliseconds() > 1000 {
break
}
}
}运行程序，会发现AI的下棋速度提升了很多，因为AI不需要每次都生成全部的走法。
如果小伙伴们想学习更多这方面知识，可以访问http://www.xqbase.com/computer/stepbystep5.htm
在下一节中，我们将学习如何使用开局库？
0
