这是《算法的乐趣》读书笔记。 在JavaScript(es6 )中重新实现算法。
华容道游戏看似简单，但求解需要设计的数据结构却很复杂，还涉及棋类游戏的棋局判断，整个过程很辛苦。 我尽量用面向对象的思想封装。 整个过程分几个部分记录。 今天是第二部分，局面处理Zobrist算法的原理和实现。
Zobrist算法原理
gydxtd算法以适合象棋游戏的棋局编码方式，通过编制特殊的变换表，给出棋盘上各位置所有可能状态不重复的随机码，对不同位置的随机码计算异或，在极低冲突率的前提下将复杂的棋局转换为整数型rxxd
gydxtd算法步骤：
识别棋局的最小单位(格子或交叉点)，决定每个最小单位可能的所有状态数。 以华容道局面为例，最小单位为20个小格子，每个格子有空状态、横长矩形占据状态、硬矩形占据状态、小眼占据状态、大眼占据状态5种。
为每个单元的所有状态分配随机编码值。 国际象棋游戏一般需要“行数列数状态数”的状态，以华容道为例，需要为545=100的状态分配代码值。
对于指定的棋局，用与每个单位的状态对应的代码值(随机数)进行异或运算，最终得到rxdpy值。
gydxtd算法的优点：
碰撞概率小，如果随机码值范围足够大，局面rxdpy碰撞的概率非常小，实际应用中几乎没有考虑碰撞。
局面发生变化时，不需要对局面整体重新计算rxdpy的值，只要计算变化的最小单位的状态变化即可。
Zobrist算法的实现
编码表的定义
编码表被定义为三维数组。
class Zobrist{
constructor ()//三维表属性
this.zobHash=[]
for(letI=0； i HRD_GAME_ROW； I//初始化
{
this.zobhash.push([] ) )。
for(letj=0； j HRD_GAME_COL； j )
{
this.zobHash[i].push([] )
for(letk=0； k MAX_WARRIOR_TYPE； k )
{
do{
var tmp=Math.random (
tmp=math.floor(tmp*math.pow ) 2，15 ) ) /对16位随机整数值
}while (！ 跳过tmp//零值
this.zobHash[i][j].push(tmp
}
}
}
}
get(I，j，k ) ) { //get接口
return this.zobHash[i][j][k]
}
}
计算局面gydxtd的值
通过逐个处理棋盘方格，从棋盘方格的清晰鼠标信息中获取清晰的鼠标类型，获取与该类型对应的码值，并利用该码值进行rxdpy值的异或运算。
函数zobhash (zobhash，state ) )。
{
let hash=0；
let heroes=state.heroes；
for(letI=1； i=HRD_GAME_ROW； I )
{
for(letj=1； j=HRD_GAME_COL； j )
{
let index=state.board[i][j] - 1； //获取网格上的干净鼠标号
lettype=(index=0index heroes.length )？ heroes[index].type : 0； //数组索引值超出范围，为零
hash^=zobhash.get(I-1，j - 1，type )； //异或计算
//console.log (index '-- ' type '-- ' zobhash [ I-1 ] [ j-1 ] [ type ] '=' hash ]
}
}
返回散列；
}
取镜像gydxtd的值
棋盘状态左右镜像问题：两个局面的鼠标位置不同，但如果忽略鼠标的名称信息，就单纯从形状上看是左右对称的镜像结构。 对于华容道游戏来说，这种左右镜像的情况对滑驹求结果的影响是一样的。
镜像左右对称，进行坐标转换后即可获得。
functiongetmirrorzobristhash (zobhash，state )。
{
let hash=0；
p>let heroes = state.heroes;
for(let i = 1; i <= HRD_GAME_ROW; i++)
{
for(let j = 1; j <= HRD_GAME_COL; j++)
{
let index = state.board[i][j] - 1;
let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;
//(HRD_GAME_COL - 1) - (j - 1)) 坐标变换
hash ^= zobHash.get(i - 1,HRD_GAME_COL - j,type);
}
}
return hash;
}
程序测试
设计了三个棋局，测试目标：同一个棋局的gydxtd与镜像rxdpy相等，镜像棋局的gydxtd与其镜像rxdpy相等。
var zobHash = new Zobrist()
var gameState = new HrdGameState()
var gameStateL = new HrdGameState()
var gameStateR = new HrdGameState()
var hs = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]
var hsl = [ new Warrior(WARRIOR_TYPE.HT_BOX,0,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,2,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
new Warrior(WARRIOR_TYPE.HT_HBAR,0,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,4),
new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]
var hsr = [ new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,1,0),
new Warrior(WARRIOR_TYPE.HT_BOX,2,0),
new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,1,2),
new Warrior(WARRIOR_TYPE.HT_HBAR,2,2),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
new Warrior(WARRIOR_TYPE.HT_VBAR,3,3),
new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
new Warrior(WARRIOR_TYPE.HT_BLOCK,2,4)
]
gameState.initState(hs)
gameStateL.initState(hsl)
gameStateR.initState(hsr)
console.dir(getZobristHash(zobHash,gameStateL) + '--' + getMirrorZobristHash(zobHash,gameStateR)) //两值相等
完整代码
代码托管在开源中国，其中的hyd.js即华容道解法。
https://gitee.com/zhoutk/test
小结
尽量使用面向对象的思想来解决问题，让数据和操作绑定在一起，努力使代码容易看懂。