電腦暗棋殘局資料庫壓縮之研究

A Study for Compressing Endgame Databases of Computer Dark Chess

范綱宇(Gang-Yu Fan)

指導教授 ： 陳志昌 ； 徐讚昇

中原大學/理學院/應用數學研究所/碩士(2015年)

https://doi.org/10.6840/cycu201500280

摘要

殘局庫的輔助能提高電腦棋類遊戲的棋力，建置殘局庫需要花費大量的時間與儲存空間，所以建完殘局庫後再以壓縮工具壓縮，而目前暗棋殘局研究至5 ~ 6子殘局庫。
本篇論文的目的著重於降低暗棋殘局庫的儲存空間，以Chen, et al.所使用的建置殘局庫方法作為比較對象(Baseline)，先改變殘局資料庫的編碼後，再透過gzip壓縮工具壓縮，找出最合適的暗棋殘局編碼。
實驗結果顯示6 明子資料庫能壓縮至Baseline的55.68 %，在不影響查詢庫的查詢下，大幅降低殘局庫的儲存空間，期望能對各棋類殘局庫之擴展與延伸有更進一步的發展

關鍵字：電腦暗棋、殘局資料庫

關鍵字

殘局資料庫 ； 電腦暗棋

並列摘要

Building endgame databases improves the strength of computer game programs. Currently, the number of pieces in Chinese dark chess endgames reaches six pieces. It takes a mount of time and space for construction and storage. Thus, the built databases need to be compressed by applying state-of-the-art compression programs, such as gzip, before being stored in the disk.

The aim of the thesis is to reduce the space needed to store endgame databases of Chinese dark chess in the disk. The baseline for comparison is the method proposed by Chen, et al. We change the index scheme used in building endgames. The endgames were then compressed by applying gzip. The appropriate index for Chinese dark chess is thus found.

The experiment results shows that endgames comprising of six revealed pieces are compressed upto 55.68% compared to the baseline. The storage space for endgame databases is significantly reduced while maintaining the same efficiency of querying databases. We expect that our method could facilitate the endgame development for other board games.

Keywords：Computer chinese dark chess、Endgame databases

並列關鍵字

Endgame databases ； Computer chinese dark chess

參考文獻

[2] 林庭羽（2013）。電腦暗棋殘局庫之研究，中原大學應用數學研究所，碩士論文

[6] 陳柏年（2011）。電腦對局知識取得與應用。國立臺灣大學資訊工程研究所，博士論文

[3] 李明臻 （2011）。台灣直棋的勝負問題之研究。國立臺灣大學資訊工程研究所，碩士論文

[5] 陳志昌（2005）。電腦象棋知識庫系統之研製。國立臺灣大學資訊工程研究所，博士論文。

[11] 謝曜安（2008）。電腦暗棋之設計與實作。國立臺灣師範大學資訊工程研究所，碩士論文