针对 Zobrist Hashing 回您:
/////////////////////
// define puzzle size
#define N 3
//////////////////////
// Zobrist Hash Table:
//
//
// 维度一: 数字(ex: N = 3,数字为 1 ~ 9
// N = 4,数字为 1 ~ 16)
//
// 维度二: 座标(由左至右;由上至下)
(ex: N = 3,座标为 0 1 2
3 4 5
6 7 8)
UINT64 ZobristTable[N * N + 1][N * N];
////////////////////////////////
// 产生 unsigned int 64 随机乱数
UINT64 rand64(void){
return rand() ^
((UINT64)rand() << 15) ^
((UINT64)rand() << 30) ^
((UINT64)rand() << 45) ^
((UINT64)rand() << 60) ;
}
////////////////////
// 初始化 Hash Table
void InitializeZobristTable(){
int i;
int j;
for(i = 1; i <= N * N; ++i){
for(j = 0; j < N * N; ++j){
ZobristTable[i][j] = rand64();
}
}
}
做好上面的准备功夫以后
以 N = 3初始盘面假设为
3 1 2
5 4 6
7 8
则 Hash Key 取得方法为
UINT64 ZobristKey;
ZobristKey ^= ZobristTable[3][0];
ZobristKey ^= ZobristTable[1][1];
ZobristKey ^= ZobristTable[2][2];
ZobristKey ^= ZobristTable[5][3];
ZobristKey ^= ZobristTable[4][4];
ZobristKey ^= ZobristTable[6][5];
ZobristKey ^= ZobristTable[7][6];
ZobristKey ^= ZobristTable[8][7];
如果今天 6 往下移动
3 1 2
5 4
7 8 6
新 Hash Key 则为
ZobristKey ^= ZobristKeyTable[6][5];
ZobristKey ^= ZobristKeyTable[6][8];
解说完毕 :)
※ 引述《soheadsome (师大狗鼻哥)》之铭言：
: 这次也是半作业文
: 人工智能的作业
: 这次是要用local beam search来解puzzle的问题
: 3<= n <= 7
: 但我现在卡在我不知道puzzle盘面的hash要怎么做
: 讲义也没写
: 我有找到一个棋盘的hash algorithm
: http://goo.gl/1fwGcG
: 我不知道要怎么使用到puzzle的问题上
: 麻烦前辈们指点<(_ _)> 谢谢