作者cutekid (可愛小孩子)
看板Prob_Solve
標題Re: [問題] n^2-1 -puzzle的問題
時間Mon Apr 28 09:52:11 2014
針對 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的問題上
: 麻煩前輩們指點<(_ _)> 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.233.210
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1398649934.A.9C0.html
1F：推 soheadsome:十分感謝!!!! 我晚點再來仔細看 04/28 12:27
2F：推 soheadsome:那如果n大約4 會衝突嗎？ 04/28 15:25
3F：推 LPH66:你的衝突是指? hash collision? 04/29 07:12
4F：→ LPH66:n 即使到 7 所用到的亂數個數也只有 7^4 = 2401 個 04/29 07:13
5F：→ LPH66:跟 64 bit 的組合比起來依然是不怎麼可能的 04/29 07:14
6F：→ LPH66:再說 Zobrist hash 的目的本來就不是在要求 perfect hash 04/29 07:14
7F：→ LPH66:萬一出事了也只不過是多搜幾種而已 04/29 07:15
※ 編輯: cutekid (61.221.80.36), 04/29/2014 09:49:45