針對 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的問題上
: 麻煩前輩們指點<(_ _)> 謝謝