用Go写一个中国象棋（十一）| 象棋AI进阶
到上一章结束，我们的AI已经会基本的走棋了，但是很多时候却很低能，我们需要做一些改进，让AI变得更聪明。
Zobrist校验码
在象棋博弈的研究中，经常需要使用到哈希表的技术。对于Alpha-Beta来说，提高效率不可避免的需要用到置换表技术(后面章节会介绍)，也就是一种特殊的哈希表。
Zobrist就是一种非常有效的将局面映射为一个独特的哈希值的方法，对于任何一个不同的局面，其使用Zobrist所算出来的哈希值是完全不同的。
Zobrist校验码技术有以下几个作用：
(1) 用Zobrist键值来实现置换表。置换表会以前搜索过的局面，让你节省很多搜索的时间。置换表还有一个并不起眼的作用是，它可以帮助你改善着法的顺序。
(2) 用Zobrist键值来实现兵型的散列表。你可以用一个键值只记录棋盘上的兵，对兵型做了很复杂的分析后，在散列表中记录分析的结果，它可以为你评估兵型节省很多时间。
(3) 可以用Zobrist键值制造一个很小的散列表，来检测当前着法路线中有没有重复局面，以便发现长将或其他导致和局的着法。
(4) 可以用Zobrist键值创建支持置换的开局库。
RC4Struct
打开define.go，增加如下代码：
const (
//MaxMoves 最大的历史走法数
MaxMoves = 256
//LimitDepth 最大的搜索深度
LimitDepth = 64
//DrawValue 和棋时返回的分数(取负值)
DrawValue = 20
//NullMargin 空步裁剪的子力边界
NullMargin = 400
//NullDepth 空步裁剪的裁剪深度
NullDepth = 2
)打开rule.go，增加如下代码：
//RC4Struct RC4密码流生成器
type RC4Struct struct {
s [256]int
x, y int
}
//initZero 用空密钥初始化密码流生成器
func (r *RC4Struct) initZero() {
j := 0
for i := 0; i < 256; i++ {
r.s[i] = i
}
for i := 0; i < 256; i++ {
j = (j + r.s[i]) & 255
r.s[i], r.s[j] = r.s[j], r.s[i]
}
}
//nextByte 生成密码流的下一个字节
func (r *RC4Struct) nextByte() uint32 {
r.x = (r.x + 1) & 255
r.y = (r.y + r.s[r.x]) & 255
r.s[r.x], r.s[r.y] = r.s[r.y], r.s[r.x]
return uint32(r.s[(r.s[r.x]+r.s[r.y])&255])
}
//nextLong 生成密码流的下四个字节
func (r *RC4Struct) nextLong() uint32 {
uc0 := r.nextByte()
uc1 := r.nextByte()
uc2 := r.nextByte()
uc3 := r.nextByte()
return uc0 + (uc1 << 8) + (uc2 << 16) + (uc3 << 24)
}
//ZobristStruct Zobrist结构
type ZobristStruct struct {
dwKey uint32
dwLock0 uint32
dwLock1 uint32
}
//initZero 用零填充Zobrist
func (z *ZobristStruct) initZero() {
z.dwKey, z.dwLock0, z.dwLock1 = 0, 0, 0
}
//initRC4 用密码流填充Zobrist
func (z *ZobristStruct) initRC4(rc4 *RC4Struct) {
z.dwKey = rc4.nextLong()
z.dwLock0 = rc4.nextLong()
z.dwLock1 = rc4.nextLong()
}
//xor1 执行XOR操作
func (z *ZobristStruct) xor1(zobr *ZobristStruct) {
z.dwKey ^= zobr.dwKey
z.dwLock0 ^= zobr.dwLock0
z.dwLock1 ^= zobr.dwLock1
}
//xor2 执行XOR操作
func (z *ZobristStruct) xor2(zobr1, zobr2 *ZobristStruct) {
z.dwKey ^= zobr1.dwKey ^ zobr2.dwKey
z.dwLock0 ^= zobr1.dwLock0 ^ zobr2.dwLock0
z.dwLock1 ^= zobr1.dwLock1 ^ zobr2.dwLock1
}
//Zobrist Zobrist表
type Zobrist struct {
Player *ZobristStruct //走子方
Table [14][256]*ZobristStruct //所有棋子
}
//initZobrist 初始化Zobrist表
func (z *Zobrist) initZobrist() {
rc4 := &RC4Struct{}
rc4.initZero()
z.Player.initRC4(rc4)
for i := 0; i < 14; i++ {
for j := 0; j < 256; j++ {
z.Table[i][j] = &ZobristStruct{}
z.Table[i][j].initRC4(rc4)
}
}
}dwKey在检查重复局面时用，也作为置换表的键值。
dwLock0和dwLock1用作置换表的校验值，另外，dwLock1还是查找开局库的依据(后面章节会介绍)。
initZobrist生成Zobrist校验码
MoveStruct
保存玩家走法信息：
//MoveStruct 历史走法信息
type MoveStruct struct {
ucpcCaptured int //是否吃子
ucbCheck bool //是否将军
wmv int //走法
dwKey uint32
}
//set 设置
func (m *MoveStruct) set(mv, pcCaptured int, bCheck bool, dwKey uint32) {
m.wmv = mv
m.ucpcCaptured = pcCaptured
m.ucbCheck = bCheck
m.dwKey = dwKey
}PositionStruct结构体
修改PositionStruct结构体：
//PositionStruct 局面结构
type PositionStruct struct {
sdPlayer int //轮到谁走，0=红方，1=黑方
vlRed int //红方的子力价值
vlBlack int //黑方的子力价值
nDistance int //距离根节点的步数
nMoveNum int //历史走法数
ucpcSquares [256]int //棋盘上的棋子
mvsList [MaxMoves]*MoveStruct //历史走法信息列表
zobr *ZobristStruct //走子方zobrist校验码
zobrist *Zobrist //所有棋子zobrist校验码
search *Search
}zobr走子方zobrist校验码，表示当前走子的一方。
zobrist所有棋子zobrist校验码，包含了红黑双方棋子。
PositionStruct方法
修改NewPositionStruct，增加校验码的初始化：
//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
}
p.zobrist.initZobrist()
return p
}// setIrrev 清空(初始化)历史走法信息
func (p *PositionStruct) setIrrev() {
p.mvsList[0].set(0, 0, p.checked(), p.zobr.dwKey)
p.nMoveNum = 1
}如果要改变走子方，只要异或一个“走子方”的键值就可以了：
//changeSide 交换走子方
func (p *PositionStruct) changeSide() {
p.sdPlayer = 1 - p.sdPlayer
p.zobr.xor1(p.zobrist.Player)
}如果一个棋子动过了，Zobrist会得到完全不同的键值，所以这两个键值不会挤在一块儿或者冲突，把它们用作散列表键值的时候会非常有效。
另一个优点在于，键值的产生是可以逐步进行的。例如，最左边的黑车起始位置是51，那么键值里一定异或过一个“zobrist[20][51]”。如果你再次异或这个值，那么根据异或的工作原理，这个黑车就从键值里删除了。
这就是说，如果你有当前局面的键值，并且需要把最左边的黑车在起始位置前进一格，你只要异或一个“黑车在51”的键值，把黑车从51移走，并且异或一个“黑车在67”的键值，把黑车放在67上。比起从头开始一个个棋子去异或，这样做可以得到同样的键值。
//addPiece 在棋盘上放一枚棋子
func (p *PositionStruct) addPiece(sq, pc int) {
p.ucpcSquares[sq] = pc
// 红方加分，黑方(注意"cucvlPiecePos"取值要颠倒)减分
if pc < 16 {
p.vlRed += cucvlPiecePos[pc-8][sq]
p.zobr.xor1(p.zobrist.Table[pc-8][sq])
} else {
p.vlBlack += cucvlPiecePos[pc-16][squareFlip(sq)]
p.zobr.xor1(p.zobrist.Table[pc-9][sq])
}
}//delPiece 从棋盘上拿走一枚棋子
func (p *PositionStruct) delPiece(sq, pc int) {
p.ucpcSquares[sq] = 0
// 红方减分，黑方(注意"cucvlPiecePos"取值要颠倒)加分
if pc < 16 {
p.vlRed -= cucvlPiecePos[pc-8][sq]
p.zobr.xor1(p.zobrist.Table[pc-8][sq])
} else {
p.vlBlack -= cucvlPiecePos[pc-16][squareFlip(sq)]
p.zobr.xor1(p.zobrist.Table[pc-9][sq])
}
}修改startup，增加校验码初始化：
//startup 初始化棋盘
func (p *PositionStruct) startup() {
pc := 0
p.sdPlayer, p.vlRed, p.vlBlack, p.nDistance = 0, 0, 0, 0
p.zobr.initZero()
for i := 0; i < 256; i++ {
p.ucpcSquares[i] = 0
}
for sq := 0; sq < 256; sq++ {
pc = cucpcStartup[sq]
if pc != 0 {
p.addPiece(sq, pc)
}
}
p.setIrrev()
}在下一节中，我们将学习如何检查重复局面？
