電腦象棋知識庫的切捨技術

Abstract

對儲存設備來說，資料的切捨非常重要，因為比起沒切捨而言，它能讓系統儲存更多的資料，如此一來，所用的磁帶量就比較少，在傳送及備份時也會比較快速。切捨也減少了網際網路上檔案的傳送時間和通訊頻寬。 本文介紹電腦象棋知識庫的切捨方法及實作經驗，以使龐大且完整的知識庫得以被切捨、精簡化卻不更改其走步的手順。如此一來，原本龐大、繁瑣、動輒上百萬譜的知識庫，可被切捨為便於攜帶，或網路上方便且快速傳輸的檔案，供棋友互相交流或研究使用。我們並且跟據原本的後代節點數及勝負和等資訊，提出一套精確的棋步與走子價值，作為探討開局走法的研究基礎及使用策略，以避免因審局的不準而造成MiniMax的分數差異，使得電腦在開局的階段下出緩著或劣著，導致輸棋的關鍵。 本論文之部份研究成果已實作在「師大深象」電腦象棋軟體中，在2006年5月底參加在義大利舉行之第11屆國際電腦象棋奧林匹亞競賽中，榮獲銅牌。未來希望能有更好的成績表現。

Data compression is very important to storage equipments, because it enables the system to store more data than uncompressed situations. As a result, the consumption of hard disk is lesser and the speed of transmission and backup is quicker. Data compression reduces the file transfer time and communication bandwidth of internets. This thesis introduces the cutoff methods and implementation experiences of Computer chess knowledge base. By using our method, the large and complete knowledge base could be cutoff and simplified, but the decision of moves is unchanged, hence it is an undistorted cutoff. Now an initially large and complicated knowledge base with millions of chess records could be cutoff to an easy-carry and fast-transfer file for communication or backup. To avoid the inaccurate estimates of the MiniMax sores due to the evaluation function, we propose a more accurate estimation strategies according to the information such as the number of children nodes and win-lose ratio. Partial research results of this thesis was implemented in the Chinese Chess software “Deep Elephant” which won a bronze medal of the 11th International Computer Chess Olympic in Italy. We wish we can make it better in the future.