用Go写一个中国象棋（十三）| 象棋AI进阶
假设目前棋局搜索深度为N，那么AI只会考虑N以内的利益，而对N+1及以后的局势没有任何考虑。那么造成的结果就是AI就是一个视力为N的近视眼，很容易因为N以内的短期利益而造成大局上的劣势，这就是水平线效应。
水平线效应
到目前为止，搜索算法都会把局面推演到固定的深度，但是这未必是件好事。例如，假设程序最多可以用迭代加深的Alpha-Beta算法搜索到5层，那么来看下这几个例子：
1. 沿着某条路线，你发现在第3层有将死或逼和的局面。显然你不想再搜索下去了，因为游戏的最终目的达到了。搜索5层不仅是浪费时间，而且可能会让电脑自己把自己引入不合理的状态。
2. 现在假设在5层你吃到了兵。程序可能会认为这个局面稍稍有利，并且会这么走下去。然而，如果你看得更深远些，可能会发现吃了兵以后你的帅就处于被将的状态！
3. 最后，假设你的帅被将了，不管你怎么走，都会在第4层被对手吃掉，但是有一条路线可以坚持到第6层。如果你的搜索深度是5，那么在第4层被吃掉的路线会被检测出来，这些情况会评估成灾难局面，但是唯一能使帅在第6层(超出了搜索树)将死的那条路线，对于AI来说不能被发现的。
那么如果你要通过牺牲一个车来延缓帅的被吃呢？对AI来说，在第4层丢车要比丢帅损失小，所以在这个搜索水平上，它情愿丢一个那么大的子，来推迟那个可怜的帅的被吃。
如何解决水平线效应
解决水平线效应的方法有以下几种：
(1) 静态(Quiescence)搜索
进入静态搜索时，要考虑两种情况，一是不被将军的情况，首先尝试不走是否能够截断，然后搜索所有吃子的走法(可以按照MVV/LVA排序)。二是被将军的情况，这时就必须生成所有的走法了(可以按照历史表排序)。
打开define.go，增加cucMvvLva：
//cucMvvLva MVV/LVA每种子力的价值
var cucMvvLva = [24]int{
0, 0, 0, 0, 0, 0, 0, 0,
5, 1, 1, 3, 4, 3, 2, 0,
5, 1, 1, 3, 4, 3, 2, 0}打开rule.go，增加：
//mvvLva 求MVV/LVA值
func (p *PositionStruct) mvvLva(mv int) int {
return (cucMvvLva[p.ucpcSquares[dst(mv)]] << 3) - cucMvvLva[p.ucpcSquares[src(mv)]]
}//searchQuiesc 静态(Quiescence)搜索过程
func (p *PositionStruct) searchQuiesc(vlAlpha, vlBeta int) int {
nGenMoves := 0
mvs := make([]int, MaxGenMoves)
//检查重复局面
vl := p.repStatus(1)
if vl != 0 {
return p.repValue(vl)
}
//到达极限深度就返回局面评价
if p.nDistance == LimitDepth {
return p.evaluate()
}
vlBest := -MateValue
//这样可以知道，是否一个走法都没走过(杀棋)
if p.inCheck() {
//如果被将军，则生成全部走法
nGenMoves = p.generateMoves(mvs, false)
mvs = mvs[:nGenMoves]
sort.Slice(mvs, func(a, b int) bool {
return p.search.nHistoryTable[a] > p.search.nHistoryTable[b]
})
} else {
//如果不被将军，先做局面评价
vl = p.evaluate()
if vl > vlBest {
vlBest = vl
if vl >= vlBeta {
return vl
}
if vl > vlAlpha {
vlAlpha = vl
}
}
//如果局面评价没有截断，再生成吃子走法
nGenMoves = p.generateMoves(mvs, true)
mvs = mvs[:nGenMoves]
sort.Slice(mvs, func(a, b int) bool {
return p.mvvLva(mvs[a]) > p.mvvLva(mvs[b])
})
}
//逐一走这些走法，并进行递归
for i := 0; i < nGenMoves; i++ {
if p.makeMove(mvs[i]) {
vl = -p.searchQuiesc(-vlBeta, -vlAlpha)
p.undoMakeMove()
//进行Alpha-Beta大小判断和截断
if vl > vlBest {
//找到最佳值(但不能确定是Alpha、PV还是Beta走法)
//"vlBest"就是目前要返回的最佳值，可能超出Alpha-Beta边界
vlBest = vl
//找到一个Beta走法
if vl >= vlBeta {
//Beta截断
return vl
}
//找到一个PV走法
if vl > vlAlpha {
//缩小Alpha-Beta边界
vlAlpha = vl
}
}
}
}
//所有走法都搜索完了，返回最佳值
if vlBest == -MateValue {
return p.nDistance - MateValue
}
return vlBest
}(2) 空步(Null-Move)裁剪
空步裁剪的代码非常简单，但某些条件下并不适用，一是被将军的情况下，二是进入残局时(自己一方的子力总价值小于某个阈值)，三是不要连续做两次空步裁剪，否则会导致搜索的退化。
//nullMove 走一步空步
func (p *PositionStruct) nullMove() {
dwKey := p.zobr.dwKey
p.changeSide()
p.mvsList[p.nMoveNum].set(0, 0, false, dwKey)
p.nMoveNum++
p.nDistance++
}
//undoNullMove 撤消走一步空步
func (p *PositionStruct) undoNullMove() {
p.nDistance--
p.nMoveNum--
p.changeSide()
}
//nullOkay 判断是否允许空步裁剪
func (p *PositionStruct) nullOkay() bool {
if p.sdPlayer == 0 {
return p.vlRed > NullMargin
}
return p.vlBlack > NullMargin
}(3) 将军延伸
修改searchFull，增加bNoNull判断：
//searchFull 超出边界(Fail-Soft)的Alpha-Beta搜索过程
func (p *PositionStruct) searchFull(vlAlpha, vlBeta, nDepth int, bNoNull bool) int {
vl:= 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
}
}
//初始化最佳值和最佳走法
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() {
nNewDepth = nDepth
} else {
nNewDepth = nDepth - 1
}
// PVS
if vlBest == -MateValue {
vl = -p.searchFull(-vlBeta, -vlAlpha, nNewDepth, false)
} else {
vl = -p.searchFull(-vlAlpha-1, -vlAlpha, nNewDepth, false)
if vl > vlAlpha && vl < vlBeta {
vl = -p.searchFull(-vlBeta, -vlAlpha, nNewDepth, 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 {
//如果不是Alpha走法，就将最佳走法保存到历史表
p.setBestMove(mvBest, nDepth)
}
return vlBest
}水平线效应总结
这里需要注意的是静态搜索和将军延伸会带来一个问题——遇到“解将还将”的局面，搜索就会无止境地进行下去，直到程序崩溃；所以要用到前一节进到的内容，进行重复局面的检查。
最后要说一句：象棋中的很多局面(其他游戏也一样)太不可预测了，实在很难恰当地评估。评价函数只能在“静态”的局面下起作用，即这些局面在不久的将来不可能发生很大的变化。
在下一节中，我们将学习界面上对应的修改？
0
好复杂的算法，我真的看不懂，但是我想看懂。。。