國際象棋程序設(shè)計二數(shù)據(jù)結(jié)構(gòu)-資料下載頁
2025-05-07 20:03本頁面
【正文】 格的白車吃掉了 H4格 的黑兵的例子，要產(chǎn)生這個散列鍵值，先 XOR在H1格的白車 這個隨機(jī)數(shù)把這個圖形擦掉，然后是 在 H4 格的黑兵 把這個圖形也擦掉和 在 H4格的白車 粘貼一個新的圖形，代表新的車的位置【其實順序是無關(guān)緊要的】。 用相同的方法，不同的隨機(jī)數(shù)，可以產(chǎn)生第二個散列鍵值，或稱 散列鎖(Hash Lock)【在英語中 Lock(鎖和 Key(鑰匙是對應(yīng)的】，它是在置換表中存儲的真正有用的信息。這個技術(shù)是用來檢測沖突的，如果恰巧有兩個局面具有相同的散列鍵值，那么他們具有同樣的散列鎖的幾率是微乎其微的。 歷史表 歷史啟發(fā) (History Heuristic)是 殺手著法 (Killer Move)【殺手著法指能產(chǎn)生截斷的著法，以后的連載會提到的】技術(shù)的衍生技術(shù)。一篇研究性的文章是這么解釋的，歷史表用來保存這些著法，在過去的搜中非常有意義因為使用高效搜索技術(shù)的而對它進(jìn)行了很深的搜索，這個著法今后還可能用到。歷史表由一個 64x64 的整數(shù)數(shù)組構(gòu)成【著法的起始格和到達(dá)格，共有 64x64 種組合】，記錄每種著法的數(shù)值，當(dāng)搜索算法認(rèn)為某個著法很有用時，它會讓歷史表增加這步的數(shù)值。表中的數(shù)值是用來對著法排序的， 歷史上占優(yōu)勢 的著法會優(yōu)先考 慮。著法產(chǎn)生的預(yù)處理 著法的產(chǎn)生即決定特定位置下那些著法是合理的和局面的估計一樣，是象棋程序設(shè)計中計算量最大的部分。因此，在這個方面的一點預(yù)處理會對提高速度大有幫助。 我個人喜歡 Jean Goulet 在 1984 年寫的《象棋的數(shù)據(jù)結(jié)構(gòu)》 (Data Structures for Chess， McGill 大學(xué)出版社一書中提到的方案，它概括為： 1.出于著法產(chǎn)生的目的，棋子的顏色是無關(guān)緊要的，除了兵以外，它只朝對面走； ，有 64x5=320 種組合【指除了兵以外的 5種棋子，根據(jù)上一條，這些棋 子是不分黑白的】，黑兵有 48 個格子可以放他們后面一行是走不到的，并且一到第八行就會變成別的棋子，白兵也有 48 個格子； ，可以確定一條著法 射線 ，例如，后從 H3格朝北走，這就是一條 射線 ； ，都有確定的幾條射線可以走，例如位于中央的王可以朝 8 個方向走，而位于盤角的象卻只有一條逃生的路； 前，要計算數(shù)據(jù)庫里在所有格子的所有棋子的所有射線，假設(shè)棋盤是空的即著法只受到棋盤邊緣的限制，不受其他棋子的限制； ，朝每個 方向搜索直到碰到棋子為止。如果是對方的棋子，最后一種著法就是吃子的著法，如果是本方的棋子，最后一種著法就是不合理的。 有了恰當(dāng)?shù)臄?shù)據(jù)庫，著法的產(chǎn)生就變成簡單得接近于線性的尋找了，幾乎用不著什么計算。整個事情就掌握在這么幾千個字節(jié)里，只是置換表的一個零頭。 以上提到的所有技術(shù)位棋盤、置換表、歷史表和預(yù)處理數(shù)據(jù)庫都會反映在我自己的程序中，當(dāng)我寫完這個連載以后就會發(fā)布出來。下個月我會詳細(xì)介紹著法產(chǎn)生的方法。 Fran ois Dominic Laram233。e， 2021 年 6月 類型：全譯加譯注 特別聲明： 1：資料 來源于互聯(lián)網(wǎng)，版權(quán)歸屬原作者 2：資料內(nèi)容屬于網(wǎng)絡(luò)意見，與本賬號立場無關(guān) 3：如有侵權(quán)，請告知，立即刪除。
法律信息相關(guān)推薦
鄂ICP備17016276號-1