用Go写一个中国象棋（十）| 象棋AI
Alpha -Beta搜索算法是机器博弈领域中最为重要的算法之一，这里我们不展开讨论，只做简单的介绍，有兴趣的小伙伴请自行研究。
Alpha -Beta
在象棋里，双方棋手都知道每个棋子在哪里，他们轮流走并且可以走任何合理的落子法。下棋的目的就是将死对方，或者避免被将死，或者有时争取和棋是最好的选择。
把象棋定义为一棵有根的树(即“博弈树”)，一个结点就代表棋类的一个局面，子结点就是这个局面走一步可以到达的一个局面。
Alpha-Beta算法的基本思想——只要有一步好的落子法，就能淘汰其他可能导致灾难的结点，而这样的结点是很多的。当不同路线的局面发生重复时可以节省下分析局面的时间。
历史表
历史表是很好的走法排序依据，用来保存杀棋落子法，因为这个落子法今后还可能用到。
记录每种落子法的数值，当搜索算法认为某个落子法很有用时，它会让历史表增加这步的数值：
//Search 与搜索有关的全局变量
type Search struct {
mvResult int // 电脑走的棋
nHistoryTable [65536]int // 历史表
}修改PositionStruct：
//PositionStruct 局面结构
type PositionStruct struct {
sdPlayer int // 轮到谁走，0=红方，1=黑方
vlRed int //红方的子力价值
vlBlack int //黑方的子力价值
nDistance int // 距离根节点的步数
ucpcSquares [256]int // 棋盘上的棋子
search *Search
}修改NewPositionStruct，初始化search：
//NewPositionStruct 初始化棋局
func NewPositionStruct() *PositionStruct {
p := &PositionStruct{
search: &Search{},
}
if p == nil {
return nil
}
return p
}searchFull
增加searchFull函数：
//searchFull 超出边界(Fail-Soft)的Alpha-Beta搜索过程
func (p *PositionStruct) searchFull(vlAlpha, vlBeta, nDepth int) int {
vl:= 0
//到达水平线，则返回局面评价值
if nDepth <= 0 {
return p.evaluate()
}
vlBest := -MateValue //是否一个走法都没走过(杀棋)
mvBest := 0 //是否搜索到了Beta走法或PV走法，以便保存到历史表
mvs := make([]int, MaxGenMoves)
nGenMoves := p.generateMoves(mvs)
mvs = mvs[:nGenMoves]
sort.Slice(mvs, func(a, b int) bool {
return p.search.nHistoryTable[a] > p.search.nHistoryTable[b]
})
//逐一走这些走法，并进行递归
for i := 0; i < nGenMoves; i++ {
if ok, pcCaptured := p.makeMove(mvs[i]); ok {
vl = -p.searchFull(-vlBeta, -vlAlpha, nDepth-1)
p.undoMakeMove(mvs[i], pcCaptured)
//进行Alpha-Beta大小判断和截断
if vl > vlBest {
//找到最佳值(但不能确定是Alpha、PV还是Beta走法)
vlBest = vl
//vlBest就是目前要返回的最佳值，可能超出Alpha-Beta边界
if vl >= vlBeta {
//找到一个Beta走法, Beta走法要保存到历史表, 然后截断
mvBest = mvs[i]
break
}
if vl > vlAlpha {
//找到一个PV走法，PV走法要保存到历史表，缩小Alpha-Beta边界
mvBest = mvs[i]
vlAlpha = vl
}
}
}
}
//所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到历史表，返回最佳值
if vlBest == -MateValue {
//如果是杀棋，就根据杀棋步数给出评价
return p.nDistance - MateValue
}
if mvBest != 0 {
//如果不是Alpha走法，就将最佳走法保存到历史表
p.search.nHistoryTable[mvBest] += nDepth * nDepth
if p.nDistance == 0 {
// 搜索根节点时，总是有一个最佳走法(因为全窗口搜索不会超出边界)，将这个走法保存下来
p.search.mvResult = mvBest
}
}
return vlBest
}searchMain
迭代加深目前最明显的效果是充分发挥历史表的作用——浅层搜索结束后，历史表中积累了大量非常宝贵的数据，这将大幅度减少深层搜索的时间。
在迭代加深的基础上实现时间控制，这将是非常简单的：
//searchMain 迭代加深搜索过程
func (p *PositionStruct) searchMain() {
// 清空历史表
for i := 0; i < 65536; i++ {
p.search.nHistoryTable[i] = 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)
// 搜索到杀棋，就终止搜索
if vl > WinValue || vl < -WinValue {
break
}
// 超过一秒，就终止搜索
if time.Now().Sub(start).Milliseconds() > 1000 {
break
}
}
}aiMove
打开game.go，增加aiMove函数：
//aiMove AI移动
func (g *Game) aiMove(screen *ebiten.Image) {
//AI走一步棋
g.singlePosition.searchMain()
_, pcCaptured := g.singlePosition.makeMove(g.singlePosition.search.mvResult)
//把AI走的棋标记出来
g.mvLast = g.singlePosition.search.mvResult
if g.singlePosition.isMate() {
//如果分出胜负，那么播放胜负的声音
g.playAudio(MusicGameWin)
g.showValue = "Your Lose!"
g.bGameOver = true
} else {
//如果没有分出胜负，那么播放将军、吃子或一般走子的声音
if g.singlePosition.checked() {
g.playAudio(MusicJiang)
} else {
if pcCaptured != 0 {
g.playAudio(MusicEat)
} else {
g.playAudio(MusicPut)
}
}
}
}clickSquare
修改clickSquare，增加电脑走棋：
//clickSquare 点击格子处理
func (g *Game) clickSquare(screen *ebiten.Image, sq int) {
pc := 0
if g.bFlipped {
pc = g.singlePosition.ucpcSquares[squareFlip(sq)]
} else {
pc = g.singlePosition.ucpcSquares[sq]
}
if (pc & sideTag(g.singlePosition.sdPlayer)) != 0 {
//如果点击自己的棋子，那么直接选中
g.sqSelected = sq
g.playAudio(MusicSelect)
} else if g.sqSelected != 0 && !g.bGameOver {
//如果点击的不是自己的棋子，但有棋子选中了(一定是自己的棋子)，那么走这个棋子
mv := move(g.sqSelected, sq)
if g.singlePosition.legalMove(mv) {
if ok, pc := g.singlePosition.makeMove(mv); ok {
g.mvLast = mv
g.sqSelected = 0
if g.singlePosition.isMate() {
// 如果分出胜负，那么播放胜负的声音，并且弹出不带声音的提示框
g.playAudio(MusicGameWin)
g.showValue = "Your Win!"
g.bGameOver = true
} else {
// 如果没有分出胜负，那么播放将军、吃子或一般走子的声音
if g.singlePosition.checked() {
g.playAudio(MusicJiang)
} else {
if pc != 0 {
g.playAudio(MusicEat)
} else {
g.playAudio(MusicPut)
}
}
g.aiMove(screen)
}
} else {
g.playAudio(MusicJiang) // 播放被将军的声音
}
}
//如果根本就不符合走法(例如马不走日字)，那么不做任何处理
}
}运行程序，可以看到电脑已经会自己走棋了！现在我们可以和电脑进行简单的对弈了！
如果小伙伴们想学习更多这方面的知识，可以访问：
http://www.xqbase.com/computer/stepbystep3.htm
在下一节中，我们将学习如何使AI变得更聪明？
0
