PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] n^2-1 -puzzle的問題

看板Prob_Solve (計算數學 Problem Solving)作者cutekid (可愛小孩子)時間10年前 (2014/04/28 09:52)推噓3(3推 0噓 4→)

留言7則, 2人參與討論串2/2 (看更多)

針對 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://www.ptt.cc/bbs/Prob_Solve/M.1398649934.A.9C0.html