作者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/cn.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