電腦棋類一直是人工智慧發展的重要領域之一，而電腦暗棋至今仍較少人對其做較深入的研究。暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、象棋是屬於完全資訊的棋類遊戲，所以如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情況下，會因分枝度過大而無法做深入的搜尋，因此難以做出較佳的決策。

本論文希望改良先前謝曜安研究生的暗棋程式，首先改進他的走步生成方式，與審局函數的計算。由於他的審局函數是採用靜態子力去計算分數，不論盤面資訊如何，其各個子力價值恆為固定，在許多情況下會產生誤判，我們希望可以藉由盤面改變而動態的改變子力價值，更客觀小心的審視盤面，並以這審局函數來實作在暗棋中關於其棋種間特殊的食物鏈關係，以期加強暗棋程式的棋力程度，並使棋力超越人類玩家水平。

Computer chess is always an important research area in artificial intelligence. At present, there is less paper dealing with the playing strategies of Dark chess. Dark chess is an incomplete information game with probabilities, which is not the same as complete information games, such as chess or Chinese chess. If we use conventional game-tree searching techniques to tackle Dark chess, then the number of branches will be very large because there are lots of moves for both “dark pieces” and “bright pieces”. Hence, it is not easy to improve the strength of the Dark chess program by using the conventional game-tree searching techniques.

This thesis is written to improve the Dark Chess program which was developed by the postgraduate Hsieh,Yao-An. We improve his move generator first, and then the evaluation function. As his evaluation function used static scores to calculate the materials’ values, regardless of how the chess game plays out, in many cases it will lead to wrong judgments. We want to dynamically change the chess materials scores when the chess board is changed to a more objective measurement. We carefully consider the unique food chain relations of the chess species and design a Dark Chess program to enhance the evaluation function. Finally,　we combine several techniques to improve the strength of the program.

摘要 i
ABSTRACT ii
致謝 iii
目 錄 iv
圖目錄 v
表目錄 vii
第一章 緒論 1
第一節 暗棋規則及玩法介紹 1
第二節 論文概要 4
第二章 資料結構 5
第一節 棋盤-棋子映射結構 5
第二節 著法預處理 11
第三節 著法產生流程 13
第三章 搜尋演算法 14
第一節 簡介 14
第二節 Min-Max搜尋演算法 15
第三節 Nega-Max搜尋演算法 18
第四節 Alpha-Beta搜尋演算法 19
第五節 Transposition Table 23
第六節 允許空步 31
第七節 Iterative Deepening 32
第八節 利用食物鏈的關係與威脅度設計審局函數 33
第九節 翻棋策略 39
第四章 結論與未來方向 41
第一節 結論 41
第二節 未來研究方向 42
參考著作 43

[1] “Wikipedia”，網址：http://zh.wikipedia.org/wiki/。
[2] “象棋百科全書”，網址：http://www.elephantbase.net/index.htm。
[3] “Chess Programming wiki”，網址：http://chessprogramming.wikispaces.com/。
[4] 謝曜安，“電腦暗棋之設計及實作”，國立臺灣師範大學資訊工程研究所碩士論文，2008。
[5] 賴學誠，“電腦暗棋程式與經驗法則之配合與實作”，國立東華大學資訊工程研究所碩士論文，2008。
[6] 黃文樟，“電腦象棋深象中局程式的設計與實作”，國立臺灣師範大學資訊工程研究所碩士論文，2006。
[7] 王小春，“人機博奕”，重慶大學出版社，2002年6月。
[8] 吳身潤，“人工智慧程式設計”，維科圖書，2002年3月。
[9] Stuart Russell , Peter Norvig，Artificial Intelligence：A Modern Approach 2/E，PEARSON，2003年12月。
[10] 何宏發、謝秋桂，“電腦象棋-原理、設計、實作及工具箱”，第三波出版社，1988年12月。
[11] 方裕欽，“UCT算法的適用性及改進策略研究－以黑白棋為例”，國立臺灣師範大學資訊工程研究所碩士論文，2008。
[12] 林子哲，“「深象」象棋軟體平行化之研究”，國立臺灣師範大學資訊工程研究所碩士論文，2007。
[13] 涂志堅，“電腦象棋的設計與實現”，中山大學碩士論文，2004。
[14] 郭哲宇，“電腦象棋擴大空步剪裁演算法的設計及實作”，國立臺灣師範大學資訊工程研究所碩士論文，2007。